/*	Copyright (C) 2004-2007 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>
#include <associative_base>


#ifndef __STD_HEADER_MAP
#define __STD_HEADER_MAP

namespace std{


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;


	//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);
		}
	};
*/

//	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 __single_associative<Key, pair<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	__single_associative<Key, pair<Key, T>, Compare, Allocator>	base;
	typedef T 								mapped_type;
	typedef typename base::key_type						key_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;

	static const key_type v_t_k(const value_type v){
		return v.first;
	}

//	using base::value_compare;

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

	template <class InputIterator> map(InputIterator first, InputIterator last,
		const Compare& comp = Compare(), const Allocator& al = Allocator())
		: base(first, last, comp, al, v_t_k) {  }

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

	using base::operator=;
	using base::operator==;
	using base::operator!=;

	using base::insert;
	using base::erase;

	using base::begin;
	using base::end;
	using base::rbegin;
	using base::rend;

	using base::empty;
	using base::size;
	using base::max_size;

	using base::find;
	using base::count;
	using base::lower_bound;
	using base::upper_bound;
	using base::equal_range;

	reference operator[](const key_type& k){
		//This is from the spec and is quite ugly.
		return (*((insert(make_pair(k, T()))).first)).second;
	}

protected:
	using base::backing;
};


//Implementation of multimap


template<class Key, class T, class Compare, class Allocator> class _UCXXEXPORT multimap
	: public __multi_associative<Key, pair<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	__multi_associative<Key, pair<Key, T>, Compare, Allocator>	base;
	typedef T 								mapped_type;
	typedef typename base::key_type						key_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;

	static const key_type v_t_k(const value_type v){
		return v.first;
	}

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

	template <class InputIterator> multimap(InputIterator first, InputIterator last,
		const Compare& comp = Compare(), const Allocator& al = Allocator())
		: base(first, last, comp, al, v_t_k) {  }


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

	using base::operator=;
	using base::operator==;
	using base::operator!=;

	using base::insert;
	using base::erase;

	using base::begin;
	using base::end;
	using base::rbegin;
	using base::rend;

	using base::empty;
	using base::size;
	using base::max_size;

	using base::find;
	using base::count;
	using base::lower_bound;
	using base::upper_bound;
	using base::equal_range;

protected:

	using base::c;

};


/* Non-member functions.  These are at the end because they are not associated with any
   particular class.  These will be implemented as I figure out exactly what all of 
   them are supposed to do, and I have time.
 */

	template <class Key, class T, class Compare, class Allocator> _UCXXEXPORT bool operator< 
		(const map<Key,T,Compare,Allocator>& x, const map<Key,T,Compare,Allocator>& y);
	template <class Key, class T, class Compare, class Allocator> _UCXXEXPORT bool operator!=
		(const map<Key,T,Compare,Allocator>& x, const map<Key,T,Compare,Allocator>& y);
	template <class Key, class T, class Compare, class Allocator> _UCXXEXPORT bool operator>
		(const map<Key,T,Compare,Allocator>& x, const map<Key,T,Compare,Allocator>& y);
	template <class Key, class T, class Compare, class Allocator> _UCXXEXPORT bool operator>=
		(const map<Key,T,Compare,Allocator>& x, const map<Key,T,Compare,Allocator>& y);
	template <class Key, class T, class Compare, class Allocator> _UCXXEXPORT bool operator<=
		(const map<Key,T,Compare,Allocator>& x, const map<Key,T,Compare,Allocator>& y);
	template <class Key, class T, class Compare, class Allocator> _UCXXEXPORT void swap
		(map<Key,T,Compare,Allocator>& x, map<Key,T,Compare,Allocator>& y);


	template <class Key, class T, class Compare, class Allocator> _UCXXEXPORT bool operator==
		(const multimap<Key,T,Compare,Allocator>& x, const multimap<Key,T,Compare,Allocator>& y);
	template <class Key, class T, class Compare, class Allocator> _UCXXEXPORT bool operator< 
		(const multimap<Key,T,Compare,Allocator>& x, const multimap<Key,T,Compare,Allocator>& y);
	template <class Key, class T, class Compare, class Allocator> _UCXXEXPORT bool operator!=
		(const multimap<Key,T,Compare,Allocator>& x, const multimap<Key,T,Compare,Allocator>& y);
	template <class Key, class T, class Compare, class Allocator> _UCXXEXPORT bool operator> 
		(const multimap<Key,T,Compare,Allocator>& x, const multimap<Key,T,Compare,Allocator>& y);
	template <class Key, class T, class Compare, class Allocator> _UCXXEXPORT bool operator>=
		(const multimap<Key,T,Compare,Allocator>& x, const multimap<Key,T,Compare,Allocator>& y);
	template <class Key, class T, class Compare, class Allocator> _UCXXEXPORT bool operator<=
		(const multimap<Key,T,Compare,Allocator>& x, const multimap<Key,T,Compare,Allocator>& y);
	template <class Key, class T, class Compare, class Allocator> _UCXXEXPORT void swap
		(multimap<Key,T,Compare,Allocator>& x, multimap<Key,T,Compare,Allocator>& y);

}

#endif