/*******************************************************************************
 *	BList_func.h	BEAM List implementation based upong stdc++ lists
 *			T.Barnaby,	BEAM Ltd,	4/8/00
 *	Copyright (c) 2012 All Right Reserved, Beam Ltd, http://www.beam.ltd.uk
 *******************************************************************************
 */
#include <stdlib.h>
#include <stdio.h>
#include <memory.h>

template <class T> BList<T>::BList() {
	onodes = nodeCreate();
	onodes->next = onodes;
	onodes->prev = onodes;
	olength = 0;
}

template <class T> BList<T>::BList(const BList<T>& l) {
	onodes = nodeCreate();
	onodes->next = onodes;
	onodes->prev = onodes;
	olength = 0;
	append((BList<T>&)l);
}

template <class T> BList<T>::~BList() {
	clear();
	delete [] (char*)onodes;
}

template <class T> void BList<T>::start(BIter& i) const {
	i = onodes->next;
}

template <class T> BIter BList<T>::begin() const {
	return onodes->next;
}

template <class T> BIter BList<T>::end() const {
	return onodes->prev;
}

template <class T> BIter BList<T>::end(BIter& i) const {
	i = onodes->prev;
	return onodes->prev;
}

template <class T> void BList<T>::next(BIter& i) const {
	BNode*	n = i;
	
	if(n != onodes)
		n = n->next;
	i = n;
}

template <class T> void BList<T>::prev(BIter& i) {
	BNode*	n = i;
	
	if(n != onodes)
		n = n->prev;
	i = n;
}

template <class T> BIter BList<T>::goTo(int pos) const {
	BIter	i;
	int	c;

	for(i = begin(), c = 0; (c < pos) && !isEnd(i); next(i), c++);
	return i;
}
	
template <class T> int BList<T>::position(BIter i) {
	BIter	ii;
	int	c;

	for(ii = begin(), c = 0; !isEnd(ii); next(ii), c++){
		if(ii == i)
			return c;
	}
	return -1;
}

template <class T> unsigned int BList<T>::number() const {
	return olength;
}

template <class T> unsigned int BList<T>::size() const {
	return number();
}

template <class T> int BList<T>::isEnd(BIter& i) const {
	Node*	n = (Node*)(BNode*)i;

	return (n == onodes);
}

template <class T> void BList<T>::clear(){
	BIter	i;
	
	for(start(i); !isEnd(i); )
		del(i);
}

template <class T> T& BList<T>::front(){
	return get(begin());
}

template <class T> T& BList<T>::rear(){
	return get(end());
}

template <class T> T& BList<T>::get(BIter i){
	return nodeGet(i)->item;
}
	
template <class T> const T& BList<T>::get(BIter i) const {
	return nodeGet(i)->item;
}
	
template <class T> void BList<T>::append(const T& item){
	BIter	i = end();
	
	insertAfter(i, item);
}

template <class T> void BList<T>::insert(BIter& i, const T& item){
	Node*	c = (Node*)(BNode*)i;
	Node*	n = nodeCreate(item);
	
	n->next = c;
	n->prev = c->prev;
	c->prev->next = n;
	c->prev = n;
	olength++;
	i = n;
}

template <class T> void BList<T>::insertAfter(BIter& i, const T& item){
	next(i);
	insert(i, item);
}

template <class T> void BList<T>::del(BIter& i){
	Node*	n = (Node*)(BNode*)i;
	
	if(olength){
		i = n->next;
		n->prev->next = n->next;
		n->next->prev = n->prev;
		delete n;
		olength--;
	}
}

template <class T> void BList<T>::deleteLast(){
	BIter	i = end();
	
	del(i);
}

template <class T> void BList<T>::deleteFirst(){
	BIter	i = begin();
	del(i);
}

template <class T> void BList<T>::push(const T& item){
	append(item);
}

template <class T> T BList<T>::pop(){
	T	t = rear();

	deleteLast();
	return t;
}

template <class T> void BList<T>::queueAdd(const T& i){
	append(i);
}

template <class T> T BList<T>::queueGet(){
	T	t = front();
	
	deleteFirst();
	return t;
}

template <class T> void BList<T>::append(const BList<T>& l){
	BIter	i;
					
	for(l.start(i); !l.isEnd(i); l.next(i)){
		append(l.get(i));
	}
}

template <class T> int BList<T>::has(const T& v) const {
	BIter		i;

	for(start(i); !isEnd(i); next(i)){
		if(get(i) == v)
			return 1;
	}
	return 0;
}

template <class T> void BList<T>::swap(BIter i1, BIter i2){
	BNode*	n1 = (BNode*)i1;
	BNode*	n2 = (BNode*)i2;
	BNode*	n1p = n1->prev;
	BNode*	n1n = n1->next;
	BNode*	n2p = n2->prev;
	BNode*	n2n = n2->next;

	if(n1->next == n2){
		n1p->next = n2;
		n2n->prev = n1;

		n1->prev = n2;
		n2->prev = n1p;
		n1->next = n2n;
		n2->next = n1;
	}
	else if(n1->prev == n2){
		n2p->next = n1;
		n1n->prev = n2;

		n1->prev = n2p;
		n2->prev = n1;
		n1->next = n2;
		n2->next = n1n;
	}
	else {
		n1p->next = n2;
		n1n->prev = n2;
		n2p->next = n1;
		n2n->prev = n1;

		n1->prev = n2p;
		n2->prev = n1p;
		n1->next = n2n;
		n2->next = n1n;
	}
}

template <class T> void BList<T>::sort(){
	BIter		i;
	BIter		s;
	int		n = number();
	int		c;
	
	while(n){
		for(c = n - 1, i = begin(); c > 0; c--, next(i)){
			s = i;
			next(s);
			if(get(i) > get(s)){
				swap(i, s);
				i = s;
			}
		}
		n--;
	}
}

template <class T> void BList<T>::sort(SortFunc func){
	BIter		i;
	BIter		s;
	int		n = number();
	int		c;

	while(n){
		for(c = n - 1, i = begin(); c > 0; c--, next(i)){
			s = i;
			next(s);
			if(func(get(i), get(s)) > 0){
				swap(i, s);
				i = s;
			}
		}
		n--;
	}
}

template <class T> T& BList<T>::operator[](BIter i){
	return get(i);
}

template <class T> const T& BList<T>::operator[](const BIter& i) const {
	return get(i);
}

template <class T> T& BList<T>::operator[](int i){
	BIter	ii;
	
	if((ii = goTo(i))){
		return get(ii);
	}
	else {
		fprintf(stderr, "BList over range\n");
		exit(1);
	}
}

template <class T> const T& BList<T>::operator[](int i) const {
	BIter	ii;
	
	if((ii = goTo(i))){
		return get(ii);
	}
	else {
		fprintf(stderr, "BList over range\n");
		exit(1);
	}
}

template <class T> BList<T>& BList<T>::operator=(const BList<T>& l){
	BIter	i;
	
	if(this != &l){
		clear();
		for(l.start(i); !l.isEnd(i); l.next(i)){
			append(l[i]);
		}
	}
	
	return *this;
}

template <class T> BList<T> BList<T>::operator+(const BList<T>& l) const {
	BList<T>	rl = *this;
	BIter		i;
	
	for(l.start(i); !l.isEnd(i); l.next(i)){
		rl.append(l[i]);
	}
	return rl;
}

template <class T> typename BList<T>::Node* BList<T>::nodeGet(BIter i){
	return (Node*)(BNode*)i;
}

template <class T> const typename BList<T>::Node* BList<T>::nodeGet(BIter i) const{
	return (Node*)(BNode*)i;
}

template <class T> typename BList<T>::Node* BList<T>::nodeCreate(const T& item){
	return new Node(item);
}
template <class T> typename BList<T>::Node* BList<T>::nodeCreate(){
	Node*	n;
	
	n = (Node*)new char [ sizeof(Node) ];
	memset(n, 0, sizeof(Node));
	return n;
}
