list

/*	Copyright (C) 2004 Garrett A. Kajmowicz

	This file is part of the uClibc++ Library.

	This library is free software; you can redistribute it and/or
	modify it under the terms of the GNU Lesser General Public
	License as published by the Free Software Foundation; either
	version 2.1 of the License, or (at your option) any later version.

	This library is distributed in the hope that it will be useful,
	but WITHOUT ANY WARRANTY; without even the implied warranty of
	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
	Lesser General Public License for more details.

	You should have received a copy of the GNU Lesser General Public
	License along with this library; if not, write to the Free Software
	Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
*/

#include <memory>
#include <iterator>
#include <algorithm>

#ifndef __STD_HEADER_LIST
#define __STD_HEADER_LIST 1

#pragma GCC visibility push(default)

namespace std{

	template <class T, class Allocator = allocator<T> > class _UCXXEXPORT list {
	public:
		typedef typename Allocator::reference		reference;
		typedef typename Allocator::const_reference	const_reference;
		typedef typename Allocator::size_type		size_type;
		typedef typename Allocator::difference_type	difference_type;
		typedef T					value_type;
		typedef Allocator				allocator_type;
		typedef typename Allocator::pointer		pointer;
		typedef typename Allocator::const_pointer	const_pointer;

	protected:
		class node;
		class iter_list;

		node * list_start;
		node * list_end;
		size_type elements;
		Allocator a;

	public:

		typedef iter_list				iterator;
		typedef iter_list				const_iterator;
		typedef std::reverse_iterator<iterator>		reverse_iterator;
		typedef std::reverse_iterator<const_iterator>	const_reverse_iterator;

		explicit list(const Allocator& = Allocator());
		explicit list(size_type n, const T& value = T(), const Allocator& = Allocator());
		template <class InputIterator> list(InputIterator first, InputIterator last, 
			const Allocator& al= Allocator());
		list(const list<T,Allocator>& x);
		~list();

		list<T,Allocator>& operator=(const list<T,Allocator>& x){
			if(&x == this){
				return *this;
			}
			clear();
			iterator i = x.begin();
			while(i != x.end()){
				push_back(*i);
				++i;
			}
			return *this;
		}

		template <class InputIterator> void assign(InputIterator first, InputIterator last);
		template <class Size, class U> void assign(Size n, const U& u = U());
		allocator_type get_allocator() const;

		iterator		begin();
		const_iterator		begin() const;
		iterator		end();
		const_iterator		end() const;
		reverse_iterator	rbegin();
		const_reverse_iterator	rbegin() const;
		reverse_iterator	rend();
		const_reverse_iterator	rend() const;

		bool      empty() const;
		size_type size() const;
		size_type max_size() const;
		void      resize(size_type sz, T c = T());

		reference       front();
		const_reference front() const;
		reference       back();
		const_reference back() const;

		void push_front(const T& x);
		void pop_front();
		void push_back(const T& x);
		void pop_back();
		iterator insert(iterator position, const T& x = T());
		void     insert(iterator position, size_type n, const T& x);
		template <class InputIterator> void insert(iterator position, InputIterator first, InputIterator last);
		iterator erase(iterator position);
		iterator erase(iterator position, iterator last);
		void     swap(list<T,Allocator>&);
		void     clear();

		void splice(iterator position, list<T,Allocator>& x);
		void splice(iterator position, list<T,Allocator>& x, iterator i);
		void splice(iterator position, list<T,Allocator>& x, iterator first, iterator last);
		void remove(const T& value);
		template <class Predicate> void remove_if(Predicate pred);
		void unique();
		template <class BinaryPredicate> void unique(BinaryPredicate binary_pred);
		void merge(list<T,Allocator>& x);
		template <class Compare> void merge(list<T,Allocator>& x, Compare comp);
		void sort();
		template <class Compare> void sort(Compare comp);
		void reverse();
	protected:
		void swap_nodes(node * x, node * y);
	};


	//Implementations of List

	//List node
	template <class T, class Allocator> class _UCXXEXPORT list<T, Allocator>::node{
	public:
		node * previous;
		node * next;
		T * val;

		node(): previous(0), next(0), val(0){ }
		node(const T & t ): previous(0), next(0), val(0) {
			val = new T(t);
			//FIXME use allocator somehow but only call constructor once
		}
		node(const T & t, node * p, node * n): previous(p), next(n), val(0) {
			val = new T(t);
		}
		~node(){ }
	};

	//List iterator
	template <class T, class Allocator> class _UCXXEXPORT list<T, Allocator>::iter_list
		: public std::iterator<
			bidirectional_iterator_tag, 
			T, 
			typename Allocator::difference_type, 
			typename Allocator::pointer, 
			typename Allocator::reference
		>
	{
	private:
		node * current;
	public:
		iter_list():current(0) { }
		iter_list( typename list<T, Allocator>::node * n): current(n) { }
		iter_list(const list<T, Allocator>::iter_list & l): current(l.current) { }
		~iter_list(){ }

		iter_list & operator=(const list<T, Allocator>::iter_list & right ){
			current = right.current;
			return *this;
		}

		T & operator*(){
			return *(current->val);
		}
		T * operator->(){
			return current->val;
		}
		const T & operator*() const{
			return *current->val;
		}
		const T * operator->() const{
			return current->val;
		}

		bool operator==(const list<T, Allocator>::iter_list & right) const {
			return (current == right.current);
		}

		bool operator!=(const list<T, Allocator>::iter_list & right) const {
			return (current != right.current);
		}

		iter_list & operator++(){
			current = current->next;
			return *this;
		}

		iter_list operator++(int){
			iter_list temp(current);
			current = current->next;
			return temp;
		}		
		iter_list & operator--(){
			current = current->previous;
			return *this;
		}

		iter_list operator--(int){
			iter_list temp(current);
			current = current->previous;
			return temp;
		}
		node * link_struct(){
			return current;
		}
		iter_list & operator+=(unsigned int n){
			for(unsigned int i = 0; i < n; ++i){
				current = current->next;
			}
			return *this;
		}
		iter_list & operator-=(unsigned int n){
			for(unsigned int i = 0; i < n; ++i){
				current = current->previous;
			}
			return *this;
		}
	};


	template<class T, class Allocator> list<T, Allocator>::list(const Allocator& al)
		:list_start(0), list_end(0), elements(0), a(al)
	{
		//End node
		list_start = new node();
		list_end = list_start;
		return;
	}

	template<class T, class Allocator> list<T, Allocator>::list
		(typename Allocator::size_type n, const T& value, const Allocator& al)
		:list_start(0), list_end(0), elements(0), a(al)
	{
		//End node
		list_start = new node();
		list_end = list_start;

		for(typename Allocator::size_type i = 0; i < n ; ++i){
			push_back(value);
		}
	}

	template<class T, class Allocator> template <class InputIterator>
		list<T, Allocator>::list
		(InputIterator first, InputIterator last, const Allocator& al)
		: list_start(0), list_end(0), elements(0), a(al)
	{
		list_start = new node();
		list_end = list_start;
		while(first != last){
			push_back(*first);
			++first;
		}
	}

	template<class T, class Allocator> list<T, Allocator>::list(const list<T,Allocator>& x)
		: list_start(0), list_end(0), elements(0), a(x.a)
	{
		list_start = new node();
		list_end = list_start;

		iterator i = x.begin();
		while(i != x.end()){
			push_back( *i);
			++i;
		}
	}

	template<class T, class Allocator> list<T, Allocator>::~list(){
		while(elements > 0){
			pop_front();
		}
		delete list_start->val;
#if UCLIBCXX_DEBUG
		list_start->val = 0;
#endif
		delete list_start;
#if UCLIBCXX_DEBUG
		list_start = 0;
		list_end = 0;
#endif
	}


	template<class T, class Allocator> void list<T, Allocator>::swap_nodes(node * x, node * y){
		T * v = x->val;
		x->val = y->val;
		y->val = v;
	}

	template<class T, class Allocator> typename list<T, Allocator>::iterator 
		list<T, Allocator>::begin()
	{
		return iterator(list_start);
	}

	
	template<class T, class Allocator> typename list<T, Allocator>::const_iterator
		list<T, Allocator>::begin() const
	{
		return const_iterator(list_start);
	}

	
	template<class T, class Allocator> typename list<T, Allocator>::iterator
		list<T, Allocator>::end()
	{
		return iterator(list_end);
	}

	template<class T, class Allocator> typename list<T, Allocator>::const_iterator
		list<T, Allocator>::end() const
	{
		return const_iterator(list_end);
	}

	template<class T, class Allocator> typename list<T, Allocator>::reverse_iterator
		list<T, Allocator>::rbegin()
	{
		return reverse_iterator(end());
	}

	template<class T, class Allocator> typename list<T, Allocator>::const_reverse_iterator
		list<T, Allocator>::rbegin() const
	{
		return const_reverse_iterator(end());
	}

	template<class T, class Allocator> typename list<T, Allocator>::reverse_iterator
		list<T, Allocator>::rend()
	{
		return reverse_iterator(begin());
	}

	template<class T, class Allocator> typename list<T, Allocator>::const_reverse_iterator
		list<T, Allocator>::rend() const
	{
		return const_reverse_iterator(begin());
	}

	template<class T, class Allocator> bool list<T, Allocator>::empty() const{
		return (elements == 0);
	}
	template<class T, class Allocator> typename list<T, Allocator>::size_type list<T, Allocator>::size() const{
		return elements;
	}
	template<class T, class Allocator> typename list<T, Allocator>::size_type list<T, Allocator>::max_size() const{
		return ((size_type)(-1)) / (sizeof(T) + sizeof(node));
	}
	template<class T, class Allocator> void list<T, Allocator>::resize(typename Allocator::size_type sz, T c){
//		if(sz > elements){
			for(typename Allocator::size_type i = elements; i < sz; ++i){
				push_back(c);
			}
//		}
//		if(sz < elements){
			for(typename Allocator::size_type i = elements; i > sz; --i){
				pop_back();
			}
//		}
	}

	template<class T, class Allocator> typename list<T, Allocator>::reference list<T, Allocator>::front(){
		return *(list_start->val);
	}
	template<class T, class Allocator> typename list<T, Allocator>::const_reference list<T, Allocator>::front() const{
		return *(list_start->val);
	}
	template<class T, class Allocator> typename list<T, Allocator>::reference list<T, Allocator>::back(){
		return *(list_end->previous->val);
	}
	template<class T, class Allocator> typename list<T, Allocator>::const_reference list<T, Allocator>::back() const{
		return *(list_end->previous->val);
	}


	template<class T, class Allocator> void list<T, Allocator>::push_front(const T& x){
		node * temp = new node(x);
		list_start->previous = temp;
		temp->previous = 0;
		temp->next = list_start;
		list_start = temp;
		++elements;
	}

	template<class T, class Allocator> void list<T, Allocator>::pop_front(){
		if(elements > 0){
			list_start = list_start->next;
			delete list_start->previous->val;
#if UCLIBCXX_DEBUG
			list_start->previous->val = 0;
			list_start->previous->next = 0;
			list_start->previous->previous = 0;
#endif
			delete list_start->previous;
			list_start->previous = 0;
			--elements;
		}
	}

	template<class T, class Allocator> void list<T, Allocator>::push_back(const T& x){
		if(elements == 0){
			//The list is completely empty
			list_start = new node(x);
			list_end->previous = list_start;
			list_start->previous = 0;
			list_start->next = list_end;
			elements = 1;
		}else{
			node * temp = new node(x);
			temp->previous = list_end->previous;
			temp->next = list_end;
			list_end->previous->next = temp;
			list_end->previous = temp;
			++elements;
		}
	}

	template<class T, class Allocator> void list<T, Allocator>::pop_back(){
		if(elements > 0){
			node * temp = list_end->previous;
			if(temp == list_start){
				list_end->previous = 0;
				list_start = list_end;
			}else{
				temp->previous->next = temp->next;
				list_end->previous = temp->previous;
			}
			delete temp->val;
#if UCLIBCXX_DEBUG
			temp->val = 0;
			temp->next = 0;
			temp->previous = 0;
#endif
			delete temp;
#if UCLIBCXX_DEBUG
			temp = 0;
#endif
			--elements;
		}
	}


	template<class T, class Allocator> typename list<T, Allocator>::iterator 
		list<T, Allocator>::insert(iterator position, const T& x)
	{
		node * temp = new node(x);

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

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

		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;
				temp->next->previous = 0;
				list_start = temp->next;
			}else{
				--position;
				temp->next->previous = temp->previous;
				temp->previous->next = temp->next;
				++position;
			}
			delete temp->val;
#if UCLIBCXX_DEBUG
			temp->next = 0;
			temp->previous = 0;
			temp->val = 0;
#endif
			delete temp;
#if UCLIBCXX_DEBUG
			temp = 0;
#endif
			--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){
				temp = erase(temp);
			}else{
				++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) ){
				temp = erase(temp);
			}else{
				++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);
	}

}

#pragma GCC visibility pop

#endif