/elec/propeller-clock

/*	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