map

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 "utility"
#include "iterator"
#include "deque"
#include "functional"


#ifndef __STD_HEADER_MAP
#define __STD_HEADER_MAP


namespace std{


template<class Key, class T, class Compare = less<Key>, class Allocator = allocator<T> > class __base_map;
template<class Key, class T, class Compare = less<Key>, class Allocator = allocator<T> > class map;
template<class Key, class T, class Compare = less<Key>, class Allocator = allocator<T> > class multimap;

template<class Key, class T, class Compare, class Allocator> class __map_iter;
template<class Key, class T, class Compare, class Allocator> class __map_citer;

/* The code for the map containers is split up into two classes.
 * The first class, __base_map holds all of the data and does much of the iterator-based
 * work.  Then the classes map and multimap inherit from there.  This was done to reduce
 * the redundancy of code (And thus errors which might crop up), as well as possibly
 * reducing the size of binaries if both map and multimap are used, along with the same
 * template parameters.
 */



//All base classes first (__base_map, iterators, value_compare) and it's associated code


template<class Key, class T, class Compare, class Allocator> class _UCXXEXPORT __base_map{

protected:
	friend class __map_iter<Key, T, Compare, Allocator>;
	friend class __map_citer<Key, T, Compare, Allocator>;

public:
	typedef __base_map<Key,T,Compare,Allocator>			map_type;
	typedef Key							key_type;
	typedef T							mapped_type;
	typedef pair<Key, T>						value_type;
	typedef Compare							key_compare;
	typedef Allocator						allocator_type;
	typedef typename Allocator::reference				reference;
	typedef typename Allocator::const_reference			const_reference;
	typedef __map_iter<Key, T, Compare, Allocator>			iterator;
	typedef __map_citer<Key, T, Compare, Allocator>			const_iterator;
	typedef typename Allocator::size_type				size_type;
	typedef typename Allocator::difference_type			difference_type;
	typedef typename Allocator::pointer				pointer;
	typedef typename Allocator::const_pointer			const_pointer;
	typedef typename std::reverse_iterator<iterator>		reverse_iterator;
	typedef typename std::reverse_iterator<const_iterator>		const_reverse_iterator;

	class value_compare;

	explicit __base_map(const Compare& comp = Compare(), const Allocator& al = Allocator());
	__base_map(const map_type& x);
	~__base_map();

	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 swap(map_type & x);
	void clear();

	key_compare   key_comp() const;
//	value_compare value_comp() const;

protected:

	deque<pair<Key, T>, allocator<pair<Key, T> > > data;
	Compare c;

};


	//Implementations

	template<class Key, class T, class Compare, class Allocator> class _UCXXEXPORT __map_citer
		: public std::iterator<
			bidirectional_iterator_tag,
			std::pair<Key, T>,
			typename Allocator::difference_type,
			std::pair<Key, T>*,
			std::pair<Key, T>&
		>
	{
	public:
		typedef class __base_map<Key, T, Compare, Allocator> Map;

		friend class __base_map<Key, T, Compare, Allocator>;
		//friend class __base_map<Key, T, Compare, Allocator>::iterator;

		friend class map<Key, T, Compare, Allocator>;
		friend class multimap<Key, T, Compare, Allocator>;

		typename Map::size_type element;
		const Map * container;
	public:
		__map_citer() : element(0), container(0) {  }
		__map_citer(const typename Map::const_iterator & m) 
			: element(m.element), container(m.container) {  }
		__map_citer(typename Map::size_type e, const Map * const c) 
			: element(e), container(c) {  }
		~__map_citer() {  }
		
		typename Map::value_type operator*() const{
			return container->data[element];
		}
		const typename Map::value_type * operator->() const{
			return &(container->data[element]);
		}
		__map_citer & operator=(const typename Map::const_iterator & m){
			element = m.element;
			container = m.container;
			return *this;
		}
		bool operator==(const typename Map::const_iterator & m) const {
			return (m.element == element && m.container == container);
		}
		bool operator!=(const typename Map::const_iterator & m) const {
			return (m.element != element || m.container != container);
		}
		__map_citer & operator++(){
			++element;
			return *this;
		}
		__map_citer operator++(int){
			__map_citer temp(*this);
			++element;
			return temp;
		}
		__map_citer & operator--(){
			--element;
			return *this;
		}
		__map_citer operator--(int){
			__map_citer temp(*this);
			--element;
			return temp;
		}

	};


	template<class Key, class T, class Compare, class Allocator> class _UCXXEXPORT __map_iter
		: public std::iterator<
			bidirectional_iterator_tag,
			std::pair<Key, T>,
			typename Allocator::difference_type,
			std::pair<Key, T>*,
			std::pair<Key, T>&
		>
	{
	protected:
		typedef class __base_map<Key, T, Compare, Allocator> Map;

		//FIXME - Find a way to use template parameters or something.  This will do for now
		friend class __base_map<Key, T, Compare, Allocator>;
		//friend class __base_map<Key, T, Compare, Allocator>::const_iterator;

		friend class map<Key, T, Compare, Allocator>;
		friend class multimap<Key, T, Compare, Allocator>;

		typename Map::size_type element;
		Map * container;
	public:
		__map_iter() : element(0), container(0) {  }
		__map_iter(const typename Map::iterator & m) 
			: element(m.element), container(m.container) {  }
		__map_iter(typename Map::size_type e, Map * c) 
			: element(e), container(c) {  }
		~__map_iter() {  }
		
		typename Map::value_type & operator*(){
			return container->data[element];
		}
		const typename Map::value_type & operator*() const{
			return container->data[element];
		}
		typename Map::value_type * operator->(){
			return &(container->data[element]);
		}
		__map_iter & operator=(const typename Map::iterator & m){
			element = m.element;
			container = m.container;
			return *this;
		}
		bool operator==(const typename Map::iterator & m) const {
			return (m.element == element && m.container == container);
		}
		bool operator!=(const typename Map::iterator & m) const {
			return (m.element != element || m.container != container);
		}
		bool operator==(const typename Map::const_iterator & m) const {
			return (m.element == element && m.container == container);
		}
		bool operator!=(const typename Map::const_iterator & m) const {
			return (m.element != element || m.container != container);
		}
		__map_iter & operator++(){
			++element;
			return *this;
		}
		__map_iter operator++(int){
			__map_iter temp(*this);
			++element;
			return temp;
		}
		__map_iter & operator--(){
			--element;
			return *this;
		}
		__map_iter operator--(int){
			__map_iter temp(*this);
			--element;
			return temp;
		}

		operator typename Map::const_iterator() const{
			return typename Map::const_iterator(element, container);
		}

	};


	//Compare the keys of the two items
	template<class Key, class T, class Compare, class Allocator> class _UCXXEXPORT 
		__base_map<Key, T, Compare, Allocator>::value_compare : public binary_function<
			typename map<Key, T, Compare, Allocator>::value_type,
			typename map<Key, T, Compare, Allocator>::value_type,
		bool>
	{
		friend class __base_map<Key, T, Compare, Allocator>;
	protected:
		Compare comp;
		value_compare(Compare c) : comp(c) { }
		~value_compare() {  }
	public:
		bool operator()(const value_type& x, const value_type& y) const {
			return comp(x.first, y.first);
		}
	};

	template <class Key, class T, class Compare, class Allocator> 
		__base_map<Key, T, Compare, Allocator>::__base_map(const Compare& comp, const Allocator&)
		: data(), c(comp)
	{
		
	}

	template <class Key, class T, class Compare, class Allocator>
		__base_map<Key, T, Compare, Allocator>::__base_map(const __base_map<Key,T,Compare,Allocator>& x)
		: data(x.data), c(x.c)
	{

	}

	template <class Key, class T, class Compare, class Allocator>
		__base_map<Key, T, Compare, Allocator>::~__base_map()
	{
		
	}


	template <class Key, class T, class Compare, class Allocator>
		typename __base_map<Key, T, Compare, Allocator>::iterator
		__base_map<Key, T, Compare, Allocator>::begin()
	{
		return iterator(0, this);
	}

	template <class Key, class T, class Compare, class Allocator>
		typename __base_map<Key, T, Compare, Allocator>::const_iterator
		__base_map<Key, T, Compare, Allocator>::begin() const
	{
		return const_iterator(0, this);

	}
	
	template <class Key, class T, class Compare, class Allocator>
		typename __base_map<Key, T, Compare, Allocator>::iterator
		__base_map<Key, T, Compare, Allocator>::end()
	{
		return iterator(data.size(), this);
	}

	template <class Key, class T, class Compare, class Allocator>
		typename __base_map<Key, T, Compare, Allocator>::const_iterator
		__base_map<Key, T, Compare, Allocator>::end() const
	{
		return const_iterator(data.size(), this);
	}

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

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

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

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

	template <class Key, class T, class Compare, class Allocator>
		bool __base_map<Key, T, Compare, Allocator>::empty() const
	{
		return (data.size() == 0);
	}

	template <class Key, class T, class Compare, class Allocator>
		typename __base_map<Key, T, Compare, Allocator>::size_type
		__base_map<Key, T, Compare, Allocator>::size() const
	{
		return data.size();
	}

	template <class Key, class T, class Compare, class Allocator>
		typename __base_map<Key, T, Compare, Allocator>::size_type 
		__base_map<Key, T, Compare, Allocator>::max_size() const
	{
		return data.max_size();
	}


	template <class Key, class T, class Compare, class Allocator>
		void __base_map<Key, T, Compare, Allocator>::swap(__base_map<Key,T,Compare,Allocator>& m)
	{
		Compare n = c;
		c = m.c;
		m.c = n;

		data.swap(m.data);
	}


	template <class Key, class T, class Compare, class Allocator>
		void __base_map<Key, T, Compare, Allocator>::clear()
	{
		data.clear();
	}


	template <class Key, class T, class Compare, class Allocator>
		typename __base_map<Key, T, Compare, Allocator>::key_compare
		__base_map<Key, T, Compare, Allocator>::key_comp() const
	{
		return c;
	}

//	value_compare value_comp() const;





/* This is the implementation for the map container.  As noted above, it deviates
 * from ISO spec by deriving from a base class in order to reduce code redundancy.
 * More code could be reduced by convirting to virtual functions (thus allowing
 * much of the erase and insert code to be duplicated), but that would deviate from
 * the specifications too much to be worth the risk.
 */





//Implementation of map


template<class Key, class T, class Compare, class Allocator> class _UCXXEXPORT map
	: public __base_map<Key, T, Compare, Allocator>
{
		//Default value of allocator does not meet C++ standard specs, but it works for this library
		//Deal with it
public:

	typedef	__base_map<Key, T, Compare, Allocator>		base;
	typedef typename base::key_type				key_type;
	typedef typename base::mapped_type			mapped_type;
	typedef typename base::value_type			value_type;
	typedef typename base::key_compare			key_compare;
	typedef typename base::allocator_type			allocator_type;
	typedef typename base::reference			reference;
	typedef typename base::const_reference			const_reference;
	typedef typename base::iterator				iterator;
	typedef typename base::const_iterator			const_iterator;
	typedef typename base::size_type			size_type;
	typedef typename base::difference_type			difference_type;
	typedef typename base::pointer				pointer;
	typedef typename base::const_pointer			const_pointer;
	typedef typename base::reverse_iterator			reverse_iterator;
	typedef typename base::const_reverse_iterator		const_reverse_iterator;

	using base::value_compare;

	explicit map(const Compare& comp = Compare(), const Allocator& al = Allocator())
		: base(comp, al) {  }

	template <class InputIterator> map(InputIterator first, InputIterator last,
		const Compare& comp = Compare(), const Allocator& = Allocator());

	map(const map<Key,T,Compare,Allocator>& x) : base(x) {  }
	~map() {  }