list

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 "algorithm"

#ifndef __STD_HEADER_LIST
#define __STD_HEADER_LIST 1


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 typename list<T, Allocator>::iter_list & l): current(l.current) { }
		~iter_list(){ }

		iter_list & operator=(const typename 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 typename list<T, Allocator>::iter_list & right){
			return (current == right.current);
		}

		bool operator!=(const typename list<T, Allocator>::iter_list & right){
			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;
		delete list_start;
		list_start = 0;
		list_end = 0;
	}


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

		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;
			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;
			delete temp;
			--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;