deque

mpeg4 video codec mpeg4 video codec

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



#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;
//		T defaultValue;
		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){
			if(container == d.container && element == d.element){
				return true;
			}
			return false;
		}
		bool operator!=(const deque_iter & d){
			if(container != d.container || element  != d.element){
				return true;
			}
			return false;
		}
		bool operator<(const deque_iter & d){
			if(element < d.element){
				return true;
			}
			return false;
		}
		bool operator<=(const deque_iter & d){
			if(element <= d.element){
				return true;
			}
			return false;
		}
		bool operator>(const deque_iter & d){
			if(element > d.element){
				return true;
			}
			return false;
		}
		bool operator>=(const deque_iter & d){
			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<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){
			if(container == d.container && element == d.element){
				return true;
			}
			return false;
		}
		bool operator!=(const deque_citer & d){
			if(container != d.container || 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_citer & d){
			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_citer & 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), 
//		defaultValue(T()),
		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),
//		defaultValue(value),
		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),
//		defaultValue(T()),
		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),
//		defaultValue(x.defaultValue),
		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;