list

mpeg4 video codec mpeg4 video codec

		}

		position.link_struct()->previous = temp;

		++elements;
		--position;
		return position;
	}

	template<class T, class Allocator> void list<T, Allocator>::insert(iterator position, size_type n, const T& x){
		for(typename list<T, Allocator>::size_type i = 0; i < n; ++i){
			position = insert(position, x);
		}
	}

	template<class T, class Allocator> template <class InputIterator> void
		list<T, Allocator>::insert(iterator position, InputIterator first, InputIterator last)
	{
		while(first !=last){
			insert(position, *first);
			++first;
		}
	}
	template<class T, class Allocator> typename list<T, Allocator>::iterator
		list<T, Allocator>::erase(iterator position)
	{
		if(position != end() ){
			node * temp = position.link_struct();
			if(temp == list_start){
				position = end();
				temp->next->previous = 0;
				list_start = temp->next;
			}else{
				--position;
				temp->next->previous = temp->previous;
				temp->previous->next = temp->next;
				++position;
			}
			delete temp->val;
			delete temp;
			--elements;
		}
		return position;
	}
	template<class T, class Allocator> typename list<T, Allocator>::iterator
		list<T, Allocator>::erase(iterator position, iterator last)
	{
		iterator temp = position;
		while(position !=last){
			position = erase(position);
		}
		return position;
	}
	template<class T, class Allocator> void list<T, Allocator>::swap(list<T,Allocator>& l){
		node * temp;
		size_type tempel;

		temp = list_start;
		list_start = l.list_start;
		l.list_start = temp;

		temp = list_end;
		list_end = l.list_end;
		l.list_end = temp;

		tempel = elements;
		elements = l.elements;
		l.elements = tempel;
	}
	template<class T, class Allocator> void list<T, Allocator>::clear(){
		while(elements > 0){
			pop_front();
		}
	}

	template<class T, class Allocator>
		void list<T, Allocator>::splice(iterator position, list<T,Allocator>& x)
	{

		//Can't add non-existant elements
		if(x.elements == 0){
			return;
		}

		elements += x.elements;
		x.elements = 0;


		//Chaining to the begining
		if(position == begin()){
			x.list_end->previous->next = list_start;
			list_start->previous = x.list_end->previous;

			list_start = x.list_start;

			x.list_start = x.list_end;
			x.list_end->previous = 0;

			return;
		}

		//Link everything we need
		x.list_start->previous = position.link_struct()->previous;
		position.link_struct()->previous->next = x.list_start;
	
		position.link_struct()->previous = x.list_end->previous;
		x.list_end->previous->next = position.link_struct();

		//Clean up the other list
		
		x.list_start = x.list_end;
		x.list_end->previous=0;

	}

	template<class T, class Allocator>
                void list<T, Allocator>::splice(iterator position, list<T,Allocator>& x, iterator i)
	{
		//Invalid conditions
		if( x.elements == 0 || i == position || position.link_struct() == i.link_struct()->next ){
			return;
		}


		//Do we need to adjust the begining pointer?
		if(i == x.begin()){
			x.list_start = x.list_start->next;
			x.list_start->previous = 0;
		}


		//Insert at begining special case
		if(position == begin()){

			i.link_struct()->previous->next = i.link_struct()->next;
			i.link_struct()->next->previous = i.link_struct()->previous;

			i.link_struct()->previous = 0;
			i.link_struct()->next = position.link_struct();
			position.link_struct()->previous = i.link_struct();

			list_start = i.link_struct();

			--x.elements;
			++elements;
			return;
		}

		if( i.link_struct()->previous != 0){
			i.link_struct()->previous->next = i.link_struct()->next;
			i.link_struct()->next->previous = i.link_struct()->previous;
		}else{
			i.link_struct()->next->previous = 0;
			x.list_start = i.link_struct()->next;
		}
		
		i.link_struct()->previous = position.link_struct()->previous;
		position.link_struct()->previous->next = i.link_struct();

		i.link_struct()->next = position.link_struct();
		position.link_struct()->previous = i.link_struct();

		--x.elements;
		++elements;
	}

	template<class T, class Allocator>
		void list<T, Allocator>::splice(iterator position, list<T,Allocator>& x,
			iterator first, iterator last)
	{
		if(x.elements == 0){
			return;
		}

		iterator temp;
		while(first != last){
			temp = first;
			++first;
			splice(position, x, temp);
	}		
	}


	template<class T, class Allocator> void list<T, Allocator>::remove(const T& value){
		iterator temp = begin();
		while( temp != end() ){
			if(*temp == value){
				erase(temp);
			}
			++temp;
		}
	}


	template<class T, class Allocator> template <class Predicate> void list<T, Allocator>::remove_if(Predicate pred){
		iterator temp = begin();
		while( temp != end() ){
			if( pred(*temp) ){
				erase(temp);
			}
			++temp;
		}
	}


	template<class T, class Allocator> void list<T, Allocator>::unique(){
		equal_to<typename iterator_traits<iterator>::value_type> p;
		unique(p);
	}

	template<class T, class Allocator> template <class BinaryPredicate>
		void list<T, Allocator>::unique(BinaryPredicate binary_pred)
	{
		iterator temp1 = begin();
		iterator temp2;
		++temp1;
		while( temp1 != end() ){
			temp2 = temp1;
			--temp2;
			if( binary_pred(*temp1, *temp2) ){
				erase(temp1);
				temp1 = temp2;
			}
			++temp1;
		}
	}

	template<class T, class Allocator> void list<T, Allocator>::merge(list<T,Allocator>& x){
		less<typename iterator_traits<typename list<T, Allocator>::iterator>::value_type> c;
		merge(x, c);
	}

	template<class T, class Allocator> template <class Compare> 
		void list<T, Allocator>::merge(list<T,Allocator>& x, Compare comp)
	{
		iterator source = x.begin();
		iterator temp;
		iterator dest  = begin();

		while(source != x.end()){
			while( dest != end() && comp (*dest, *source) ){
				++dest;
			}
			++elements;
			--x.elements;

			temp = source;
			++temp;

			if(dest == begin()){
				dest.link_struct()->previous = source.link_struct();
				source.link_struct()->next = dest.link_struct();
				source.link_struct()->previous = 0;
				list_start = source.link_struct();
			}else{
				source.link_struct()->previous = dest.link_struct()->previous;
				dest.link_struct()->previous->next = source.link_struct();
				source.link_struct()->next = dest.link_struct();
				dest.link_struct()->previous = source.link_struct();
			}
			source = temp;
		}

		//Fix up x;
		x.list_start = x.list_end;
		x.list_start->previous = 0;
	}

	template<class T, class Allocator> void list<T, Allocator>::sort(){
		less<typename iterator_traits<typename list<T, Allocator>::iterator>::value_type> c;
		sort(c);
	}

	template<class T, class Allocator> template <class Compare>
		void list<T, Allocator>::sort(Compare comp)
	{
		typename list<T, Allocator>::iterator i, j, k;

		//FIXME - bubble sort

		if(elements == 0){
			return;
		}

		i = end();
		--i;
		while(i != begin()){
			j = begin();
			k = j;
			++k;
			while(j != i){
				if( comp(*k, *j) ){
					swap_nodes(k.link_struct(), j.link_struct());
				}
				++j;
				++k;
			}
			--i;
		}
	}


	template<class T, class Allocator> void list<T, Allocator>::reverse(){
		if(elements == 0){
			return;
		}

		node * current;
		node * following;
		node * temp;

		//Need to move the list_end element to the begining

		temp = list_end;
		list_end = temp->previous;
		list_end->next = 0;

		list_start->previous = temp;
		temp->previous = 0;
		temp->next = list_start;
		list_start = temp;

		current = list_start;

		while( current != list_end ){
			following = current->next;

			//Swap the values pointed to/at with the current node
			temp = current->next;
			current->next = current->previous;
			current->previous = temp;

			current = following;
		}

		//Swap pointers on the end node
		temp = list_end->next;
		list_end->next = list_end->previous;
		list_end->previous = temp;


		//Swap the fixed pointers
		temp = list_start;
		list_start = list_end;
		list_end = temp;

	}

	template <class T, class Allocator>
	bool operator==(const list<T,Allocator>& x, const list<T,Allocator>& y){
		if(x.size() != y.size()){
			return false;
		}
		typename list<T,Allocator>::const_iterator i = x.begin();
		typename list<T,Allocator>::const_iterator j = y.begin();

		while(i != x.end()){
			if( *i != *j){
				return false;
			}
			++i;
			++j;
		}
		return true;
	}

	template <class T, class Allocator>
	bool operator< (const list<T,Allocator>& x, const list<T,Allocator>& y){
		typename list<T,Allocator>::const_iterator i = x.begin();
		typename list<T,Allocator>::const_iterator j = y.begin();
		while(i != x.end() && j != y.end()){
			if( *i < *j){
				return true;
			}
			if(*j < *i){
				return false;
			}
			++i;
			++j;
		}
		return (i == x.end() && j != y.end());
	}

	template <class T, class Allocator>
	bool operator!=(const list<T,Allocator>& x, const list<T,Allocator>& y){
		return !(x == y);
	}

	template <class T, class Allocator>
	bool operator> (const list<T,Allocator>& x, const list<T,Allocator>& y){
		typename list<T,Allocator>::const_iterator i = x.begin();
		typename list<T,Allocator>::const_iterator j = y.begin();
		while(i != x.end() && j != y.end()){
			if( *i > *j){
				return true;
			}
			if( *j > *i){
				return false;
			}
			++i;
			++j;
		}
		return (i != x.end() && j == y.end());
	}

	template <class T, class Allocator>
	bool operator>=(const list<T,Allocator>& x, const list<T,Allocator>& y){
		typename list<T,Allocator>::const_iterator i = x.begin();
		typename list<T,Allocator>::const_iterator j = y.begin();
		while(i != x.end() && j != y.end()){
			if( *i >= *j){
				return true;
			}
			if(*j >= *i){
				return false;
			}
			++i;
			++j;
		}
		return (i != x.end() && j == y.end());
	}

	template <class T, class Allocator>
	bool operator<=(const list<T,Allocator>& x, const list<T,Allocator>& y){
		typename list<T,Allocator>::const_iterator i = x.begin();
		typename list<T,Allocator>::const_iterator j = y.begin();
		while(i != x.end() && j != y.end()){
			if( *i <= *j){
				return true;
			}
			if(*j <= *i){
				return false;
			}
			++i;
			++j;
		}
		return (i == x.end());
	}

	template <class T, class Allocator>
	void swap(list<T,Allocator>& x, list<T,Allocator>& y){
		x.swap(y);
	}

}


#endif