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

#pragma GCC visibility push(default)

#ifndef __STD_HEADER_DEQUE

#define __STD_HEADER_DEQUE

namespace std{

	template <class T, class Allocator = allocator<T> > class deque;

	template <class T, class Allocator> bool operator==(const deque<T,Allocator>& x, const deque<T,Allocator>& y);

	template <class T, class Allocator> bool operator< (const deque<T,Allocator>& x, const deque<T,Allocator>& y);

	template <class T, class Allocator> bool operator!=(const deque<T,Allocator>& x, const deque<T,Allocator>& y);

	template <class T, class Allocator> bool operator> (const deque<T,Allocator>& x, const deque<T,Allocator>& y);

	template <class T, class Allocator> bool operator>=(const deque<T,Allocator>& x, const deque<T,Allocator>& y);

	template <class T, class Allocator> bool operator<=(const deque<T,Allocator>& x, const deque<T,Allocator>& y);

	template <class T, class Allocator> void swap(deque<T,Allocator>& x, deque<T,Allocator>& y);

	template <class T, class Allocator> class _UCXXEXPORT deque {

	public:

		friend bool operator==<>(const deque<T, Allocator>& x, const deque<T, Allocator>& y);

		friend class deque_iter;

		friend class deque_citer;

		class deque_iter;

		class deque_citer;

		typedef typename Allocator::reference		reference;

		typedef typename Allocator::const_reference	const_reference;

		typedef deque_iter				iterator;

		typedef deque_citer				const_iterator;

		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;

		typedef std::reverse_iterator<iterator>		reverse_iterator;

		typedef std::reverse_iterator<const_iterator>	const_reverse_iterator;

		explicit deque(const Allocator& al = Allocator());

		explicit deque(size_type n, const T& value = T(), const Allocator& al = Allocator());

		template <class InputIterator> deque(InputIterator first, InputIterator last, const Allocator& = Allocator());

		deque(const deque<T,Allocator>& x);

		~deque();

		deque<T,Allocator>& operator=(const deque<T,Allocator>& x);

		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;

		size_type		size() const;

		size_type		max_size() const;

		void			resize(size_type sz, T c = T());

		bool			empty() const;

		reference	operator[](size_type n);

		const_reference	operator[](size_type n) const;

		reference	at(size_type n);

		const_reference	at(size_type n) const;

		reference	front();

		const_reference	front() const;

		reference	back();

		const_reference	back() const;

		void push_front(const T& x);

		void push_back(const T& x);

		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);

		void pop_front();

		void pop_back();

		iterator erase(iterator position);

		iterator erase(iterator first, iterator last);

		void     swap(deque<T,Allocator>&);

		void     clear();

	protected:

		void reserve(size_type n);

		inline size_type array_element(size_type deque_element) const{

			if(deque_element < (data_size - first_element)){

				return first_element + deque_element;

			}

			return deque_element - (data_size - first_element);

		}

		inline size_type first_subtract(size_type sub_size) const{

			if(sub_size > first_element){

				return (data_size - first_element) - sub_size;

			}

			return first_element - sub_size;

		}

		T * data;

		size_type data_size;		//Physical size of array

		size_type elements;		//Elements in array

		size_type first_element;	//Element number of array 0..n

		size_type last_element;		//Element number of array 0..n

		Allocator a;

	};

	template<class T, class Allocator> class _UCXXEXPORT deque<T, Allocator>::deque_iter

		: public std::iterator<

			random_access_iterator_tag,

			T,

			typename Allocator::difference_type,

			typename Allocator::pointer,

			typename Allocator::reference

		>

	{

	friend class deque<T, Allocator>;

	protected:

		deque<T, Allocator> * container;

		typename Allocator::size_type element;

	public:

		deque_iter() : container(0), element(0) {  }

		deque_iter(const deque_iter & d) : container (d.container), element(d.element) {  }

		deque_iter(deque<T, Allocator> * c, typename Allocator::size_type e)

			: container(c), element(e)

		{

			return;

		}

		~deque_iter() {  }

		deque_iter & operator=(const deque_iter & d){

			container = d.container;

			element = d.element;

			return *this;

		}

		T & operator*(){

			return container->data[container->array_element(element)];

		}

		T * operator->(){

			return container->data + container->array_element(element);

		}

		const T & operator*() const{

			return container->data[container->array_element(element)];

		}

		const T * operator->() const{

			return container->data + container->array_element(element);

		}

		bool operator==(const deque_iter & d) const{

			if(container == d.container && element == d.element){

				return true;

			}

			return false;

		}

		bool operator==(const deque_citer & d) const{

			if(container == d.container && element == d.element){

				return true;

			}

			return false;

		}

		bool operator!=(const deque_iter & d) const{

			if(container != d.container || element  != d.element){

				return true;

			}

			return false;

		}

		bool operator!=(const deque_citer & d) const{

			if(container != d.container || element  != d.element){

				return true;

			}

			return false;

		}

		bool operator<(const deque_iter & d) const{

			if(element < d.element){

				return true;

			}

			return false;

		}

		bool operator<(const deque_citer & d) const{

			if(element < d.element){

				return true;

			}

			return false;

		}

		bool operator<=(const deque_iter & d) const{

			if(element <= d.element){

				return true;

			}

			return false;

		}

		bool operator<=(const deque_citer & d) const{

			if(element <= d.element){

				return true;

			}

			return false;

		}

		bool operator>(const deque_iter & d) const{

			if(element > d.element){

				return true;

			}

			return false;

		}

		bool operator>(const deque_citer & d) const{

			if(element > d.element){

				return true;

			}

			return false;

		}

		bool operator>=(const deque_iter & d) const{

			if(element >= d.element){

				return true;

			}

			return false;

		}

		bool operator>=(const deque_citer & d) const{

			if(element >= d.element){

				return true;

			}

			return false;

		}

		deque_iter & operator++(){

			++element;

			return *this;

		}

		deque_iter operator++(int){

			deque_iter temp(container, element);

			++element;

			return temp;

		}

		deque_iter operator+(typename Allocator::size_type n){

			deque_iter temp(container, element + n);

			return temp;

		}

		deque_iter & operator+=(typename Allocator::size_type n){

			element += n;

			return *this;

		}

		deque_iter & operator--(){

			--element;

			return *this;

		}

		deque_iter operator--(int){

			deque_iter temp(container, element);

			--element;

			return temp;

		}

		deque_iter operator-(typename Allocator::size_type n){

			deque_iter temp(container, element - n);

			return temp;

		}

		deque_iter & operator-=(typename Allocator::size_type n){

			element -= n;

			return *this;

		}

		typename Allocator::size_type operator-(const deque_iter & d){

			return element - d.element;

		}

	};

	template<class T, class Allocator> class _UCXXEXPORT deque<T, Allocator>::deque_citer

		: public std::iterator<

			random_access_iterator_tag,

			T,

			typename Allocator::difference_type,

			typename Allocator::const_pointer,

			typename Allocator::const_reference

		>

	{

	friend class deque<T, Allocator>;

	protected:

		const deque<T, Allocator> * container;

		typename Allocator::size_type element;

	public:

		deque_citer() : container(0), element(0) {  }

		deque_citer(const deque_citer & d) : container (d.container), element(d.element) {  }

		deque_citer(const deque_iter & d) : container (d.container), element(d.element) {  }

		deque_citer(const deque<T, Allocator> * c, typename Allocator::size_type e)

			: container(c), element(e)

		{

			return;

		}

		~deque_citer() {  }

		deque_citer & operator=(const deque_iter & d){

			container = d.container;

			element = d.element;

			return *this;

		}

		const T & operator*() const{

			return container->data[container->array_element(element)];

		}

		const T * operator->() const{

			return container->data + container->array_element(element);

		}

		bool operator==(const deque_citer & d) const{

			if(container == d.container && element == d.element){

				return true;

			}

			return false;

		}

		bool operator==(const deque_iter & d) const{

			if(container == d.container && element == d.element){

				return true;

			}

			return false;

		}

		bool operator!=(const deque_citer & d) const{

			if(container != d.container || element  != d.element){

				return true;

			}

			return false;

		}

		bool operator!=(const deque_iter & d) const{

			if(container != d.container || element  != d.element){

				return true;

			}

			return false;

		}

		bool operator<(const deque_citer & d) const{

			if(element < d.element){

				return true;

			}

			return false;

		}

		bool operator<(const deque_iter & d) const{

			if(element < d.element){

				return true;

			}

			return false;

		}

		bool operator<=(const deque_citer & d) const{

			if(element <= d.element){

				return true;

			}

			return false;

		}

		bool operator<=(const deque_iter & d) const{

			if(element <= d.element){

				return true;

			}

			return false;

		}

		bool operator>(const deque_citer & d) const{

			if(element > d.element){

				return true;

			}

			return false;

		}

		bool operator>(const deque_iter & d) const{

			if(element > d.element){

				return true;

			}

			return false;

		}

		bool operator>=(const deque_citer & d){

			if(element >= d.element){

				return true;

			}

			return false;

		}

		bool operator>=(const deque_iter & d){

			if(element >= d.element){

				return true;

			}

			return false;

		}

		deque_citer & operator++(){

			++element;

			return *this;

		}

		deque_citer operator++(int){

			deque_citer temp(container, element);

			++element;

			return temp;

		}

		deque_citer operator+(typename Allocator::size_type n){

			deque_citer temp(container, element + n);

			return temp;

		}

		deque_citer & operator+=(typename Allocator::size_type n){

			element += n;

			return *this;

		}

		deque_citer & operator--(){

			--element;

			return *this;

		}

		deque_citer operator--(int){

			deque_citer temp(container, element);

			--element;

			return temp;

		}

		deque_citer operator-(typename Allocator::size_type n){

			deque_citer temp(container, element - n);

			return temp;

		}

		deque_citer & operator-=(typename Allocator::size_type n){

			element -= n;

			return *this;

		}

		typename Allocator::size_type operator-(const deque_citer & d){

			return element - d.element;

		}

	};

	template<class T, class Allocator> deque<T, Allocator>::deque(const Allocator& al)

		: data(0), 

		data_size(0), elements(0), first_element(0), last_element(0), a(al)

	{

		data_size = __UCLIBCXX_STL_BUFFER_SIZE__;

		data = a.allocate(data_size);

		first_element = data_size /2;

		last_element = first_element;

	}

	template<class T, class Allocator> deque<T, Allocator>::deque(

		size_type n, const T& value, const Allocator& al)

		: data(0),

		elements(n), first_element(0), last_element(0), a(al)

	{

		data_size = elements + __UCLIBCXX_STL_BUFFER_SIZE__;

		data = a.allocate(data_size);

		first_element = (data_size - elements) / 2;

		last_element = first_element;

		for(n=first_element ; n < last_element; ++n ){

			a.construct(data+n, value);

		}

	}

	template<class T, class Allocator> template <class InputIterator> 

		deque<T, Allocator>::deque(InputIterator first, InputIterator last, const Allocator& al)

		: data(0),

		data_size(0), elements(0), first_element(0), last_element(0), a(al)

	{

		data_size = __UCLIBCXX_STL_BUFFER_SIZE__;

		data = a.allocate(data_size);

		first_element = data_size / 4;	//Note sure how big, but let's add a little space...

		last_element = first_element;

		while(first != last){

			push_back(*first);

			++first;

		}

	}

	template<class T, class Allocator> deque<T, Allocator>::deque(const deque<T,Allocator>& x)

		: data(0),

		elements(0), first_element(0), last_element(0), a(x.a)

	{

		data_size = x.elements + __UCLIBCXX_STL_BUFFER_SIZE__;

		data = a.allocate(data_size);

		first_element = (data_size - x.elements) / 2;

		last_element = first_element;

		for(size_type i=0; i < x.elements; ++i){

			push_back(x[i]);

		}

	}

	template<class T, class Allocator> deque<T, Allocator>::~deque(){

		clear();

		a.deallocate(data, data_size);

	}

	template<class T, class Allocator> deque<T,Allocator>& deque<T, Allocator>::

		operator=(const deque<T,Allocator>& x)

	{

		if(&x == this){

			return *this;

		}

		resize(x.elements);

		for(size_t i = 0; i < elements; ++i){

			data[array_element(i)] = x[i];

		}

		return *this;

	}

	template<class T, class Allocator> template <class InputIterator> void

		deque<T, Allocator>::assign(InputIterator first, InputIterator last)

	{

		clear();

		while(first !=last){

			push_back(*first);

			++first;

		}

	}

	template<class T, class Allocator> template <class Size, class U> void

		deque<T, Allocator>::assign(Size n, const U& u)

	{

		if(&u == this){

			return;

		}

		clear();

		for(size_type i = 0; i < n; ++i){

			push_back(u);

		}

	}

	template<class T, class Allocator> typename deque<T, Allocator>::allocator_type 

		deque<T, Allocator>::get_allocator() const

	{

		return a;

	}

	template<class T, class Allocator> typename

		deque<T, Allocator>::iterator deque<T, Allocator>::begin()

	{

		return deque_iter(this, 0);

	}

	template<class T, class Allocator> typename deque<T, Allocator>::const_iterator

		deque<T, Allocator>::begin() const

	{

		return deque_citer(this, 0);

	}

	template<class T, class Allocator> typename

		deque<T, Allocator>::iterator deque<T, Allocator>::end()

	{

		return deque_iter(this, elements);

	}

	template<class T, class Allocator> typename

		deque<T, Allocator>::const_iterator deque<T, Allocator>::end() const

	{

		return deque_citer(this, elements);

	}

	template<class T, class Allocator> typename

		deque<T, Allocator>::reverse_iterator deque<T, Allocator>::rbegin()

	{

		return reverse_iterator(end());

	}

	template<class T, class Allocator> typename

		deque<T, Allocator>::const_reverse_iterator deque<T, Allocator>::rbegin() const

	{

		return const_reverse_iterator(end());

	}

	template<class T, class Allocator> typename

		deque<T, Allocator>::reverse_iterator deque<T, Allocator>::rend()

	{

		return reverse_iterator(begin());

	}

	template<class T, class Allocator> typename

		deque<T, Allocator>::const_reverse_iterator deque<T, Allocator>::rend() const

	{

		return const_reverse_iterator(begin());

	}

	template<class T, class Allocator> typename

		deque<T, Allocator>::size_type deque<T, Allocator>::size() const

	{

		return elements;

	}

	template<class T, class Allocator> typename

		deque<T, Allocator>::size_type deque<T, Allocator>::max_size() const

	{

		return ((size_type)(-1)) / sizeof(T);

	}

	template<class T, class Allocator> void deque<T, Allocator>::resize(size_type sz, T c){

		reserve(sz);

		while(sz > size()){

			push_back(c);

		}

		while(sz < size()){

			pop_back();

		}

	}

	template<class T, class Allocator> bool deque<T, Allocator>::empty() const{

		return (elements == 0);

	}

	template<class T, class Allocator> typename

		deque<T, Allocator>::reference deque<T, Allocator>::operator[](size_type n)

	{

		return data[array_element(n)];

	}

	template<class T, class Allocator> typename

		deque<T, Allocator>::const_reference deque<T, Allocator>::operator[](size_type n) const

	{

		return data[array_element(n)];

	}

	template<class T, class Allocator> typename

		deque<T, Allocator>::reference deque<T, Allocator>::at(size_type n)

	{

		if(n > elements){

			__throw_out_of_range("Out of deque range");

		}

		return data[array_element(n)];

	}

	template<class T, class Allocator> typename

		deque<T, Allocator>::const_reference deque<T, Allocator>::at(size_type n) const

	{

		if(n > elements){

			__throw_out_of_range("Out of deque range");

		}

		return data[array_element(n)];

	}

	template<class T, class Allocator> typename

		deque<T, Allocator>::reference deque<T, Allocator>::front()

	{

		return data[first_element];

	}

	template<class T, class Allocator> typename

		deque<T, Allocator>::const_reference deque<T, Allocator>::front() const

	{

		return data[first_element];

	}

	template<class T, class Allocator> typename

		deque<T, Allocator>::reference deque<T, Allocator>::back()

	{

		return data[array_element(elements-1)];

	}

	template<class T, class Allocator> typename

		deque<T, Allocator>::const_reference deque<T, Allocator>::back() const

	{

		return data[array_element(elements-1)];

	}

	template<class T, class Allocator> void deque<T, Allocator>::push_front(const T& x){

		reserve(elements + 1);

		first_element = first_subtract(1);

		a.construct(data + first_element, x);

		++elements;

	}

	template<class T, class Allocator> void deque<T, Allocator>::push_back(const T& x){

		reserve(elements + 1);

		a.construct(data + last_element, x);

		++elements;

		last_element = array_element(elements);

	}

	template<class T, class Allocator> typename

		deque<T, Allocator>::iterator deque<T, Allocator>::insert(iterator position, const T& x)

	{

		reserve(elements+1);

		if(position.element > (elements/2)){

			//Push all elements back 1

			push_back(x);

			for(size_type i = elements-1; i > position.element; --i){

				at(i) = at(i-1);

			}

		}else{

			//Push all elements forward 1

			push_front(x);

			for(size_type i = 0; i < position.element; ++i){

				at(i) = at(i+1);

			}

		}

		at(position.element) = x;

		return deque_iter(this, position.element);

	}

	template<class T, class Allocator> void deque<T, Allocator>::

		insert(typename deque<T, Allocator>::iterator position, size_type n, const T& x)

	{

		reserve(elements + n);

		for(size_t i =0; i < n; ++i){

			position = insert(position, x);

		}

	}

	template<class T, class Allocator> template <class InputIterator> 

		void deque<T, Allocator>::insert (iterator position, InputIterator first, InputIterator last)

	{

		while(first != last){

			position = insert(position, *first);

			++first;

		}

	}

	template<class T, class Allocator> void deque<T, Allocator>::pop_front(){

		if(elements == 0){

			__throw_out_of_range("deque pop_front");

		}

		a.destroy(data + first_element);

		first_element = array_element(1);

		--elements;

	}

	template<class T, class Allocator> void deque<T, Allocator>::pop_back(){

		last_element = array_element(elements - 1);

		a.destroy(data + last_element);

		--elements;

	}

	template<class T, class Allocator> typename

		deque<T, Allocator>::iterator deque<T, Allocator>::erase(typename deque<T, Allocator>::iterator position)

	{

		if(position.element > (elements /2)){

			for(size_type i = position.element; i < elements - 1; ++i){

				at(i) = at(i+1);

			}

			pop_back();

		}else{

			for(size_type i = position.element; i > 0; --i){

				at(i) = at(i-1);

			}

			pop_front();

		}

		return deque_iter(this, position.element);

	}

	template<class T, class Allocator> typename deque<T, Allocator>::iterator 

		deque<T, Allocator>::

		erase(typename deque<T, Allocator>::iterator first, typename deque<T, Allocator>::iterator last)

	{

		//Shift backwards

		size_type num_move = last.element - first.element;

		if( first.element > (elements - last.element) ){

			for(size_type i = last.element; i < elements ; ++i){

				at(i-num_move) = at(i);

			}

			for(size_type i = 0; i < num_move ; ++i){

				pop_back();

			}

		}else{

			for(size_type i = 0; i < first.element ; ++i){

				at(last.element - i - 1) = at(first.element - i - 1);

			}

			for(size_type i = 0; i < num_move ; ++i){

				pop_front();

			}

		}

		return deque_iter(this, first.element);

	}

	template<class T, class Allocator> void deque<T, Allocator>::swap(deque<T,Allocator>& x)

	{

		T * temp_data;

		typename deque<T,Allocator>::size_type temp_size;

		//Swap data pointers

		temp_data = x.data;

		x.data = data;

		data = temp_data;

		//Swap array sizes

		temp_size = x.data_size;

		x.data_size = data_size;

		data_size = temp_size;

		//Swap num array elements

		temp_size  = x.elements;

		x.elements = elements;

		elements = temp_size;

		//Swap first_pointer

		temp_size = x.first_element;

		x.first_element = first_element;

		first_element = temp_size;

		//Swap last_pointer

		temp_size = x.last_element;

		x.last_element = last_element;

		last_element = temp_size;

	}

	template<class T, class Allocator> void deque<T, Allocator>::clear()

	{

		while(elements > 0 ){

			pop_back();

		}

	}

	template<class T, class Allocator> void deque<T, Allocator>::reserve(typename deque<T, Allocator>::size_type n)

	{

		if(data_size >= n){

			return;

		}

		size_type size_temp;

		size_type first_temp;

		T * data_temp;

		size_temp = n + __UCLIBCXX_STL_BUFFER_SIZE__;		//Reserve extra 'cause we can

		data_temp = a.allocate(size_temp);

		first_temp = (size_temp - elements) / 2;

		for(size_type i = 0; i < elements; ++i){

			a.construct(data_temp + first_temp + i, data[array_element(i)]);

			a.destroy(data + array_element(i));

		}

		//Now shuffle pointers

		a.deallocate(data, data_size);

		data = data_temp;

		data_size = size_temp;

		first_element = first_temp;

		last_element = first_element + elements;

	}

	template <class T, class Allocator> _UCXXEXPORT 

		bool

		operator==(const deque<T,Allocator>& x, const deque<T,Allocator>& y)

	{

		if(x.elements != y.elements){

			return false;

		}

		for(typename deque<T,Allocator>::size_type i = 0; i < x.elements; ++i){

			if(x[i] < y[i] || y[i] < x[i]){

				return false;

			}

		}

		return true;

	}

	template <class T, class Allocator> bool operator< (const deque<T,Allocator>& x, const deque<T,Allocator>& y);

	template <class T, class Allocator> _UCXXEXPORT

		bool

		operator!=(const deque<T,Allocator>& x, const deque<T,Allocator>& y)

	{

		if(x == y){

			return false;

		}

		return true;

	}

	template <class T, class Allocator> bool operator> (const deque<T,Allocator>& x, const deque<T,Allocator>& y);

	template <class T, class Allocator> bool operator>=(const deque<T,Allocator>& x, const deque<T,Allocator>& y);

	template <class T, class Allocator> bool operator<=(const deque<T,Allocator>& x, const deque<T,Allocator>& y);

	template <class T, class Allocator> _UCXXEXPORT void swap(deque<T,Allocator>& x, deque<T,Allocator>& y){

		x.swap(y);

	}

}

#pragma GCC visibility pop

#endif