// map standard header
#ifndef _MAP_
#define _MAP_

#pragma info(none)
#ifndef __CHKHDR__
#  pragma report(level, E)
#endif
#pragma info(restore)

#if __IBMCPP__ < 400
#error This file to be used only with IBM VisualAge C++ v4 and later compilers.
#endif /* __IBMCPP__ */

#pragma namemangling(ansi)

   /********************************************************************/
   /*  <map> header file                                               */
   /*                                                                  */
   /*  VisualAge C++, Version 4.0                                      */
   /*    Licensed Material - Property of IBM                           */
   /*                                                                  */
   /*  5801-AAR and Other Materials                                    */
   /*                                                                  */
   /*  (c) Copyright IBM Corp 1991, 1998. All rights reserved.         */
   /*                                                                  */
   /*                                                                  */
   /*  Licensed Materials.                                             */
   /*                                                                  */
   /*  Dinkum C++ Library                                              */
   /*  Copyright (c) 1998.  Licensed to IBM Corp. and its suppliers.   */
   /*                                                                  */
   /********************************************************************/

#include <functional>
#include <xtree>

_STD_BEGIN
		// TEMPLATE CLASS map
template<class _K, class _Ty, class _Pr _TDEF(less<_K>),
	class _A _TDEF2(allocator<pair<const _K, _Ty> >) >
	class map {
public:
	typedef map<_K, _Ty, _Pr, _A> _Myt;
	typedef pair<const _K, _Ty> value_type;
	struct _Kfn : public unary_function<value_type, _K> {
		const _K& operator()(const value_type& _X) const
		{return (_X.first); }
		};
	class value_compare
		: public binary_function<value_type, value_type, bool> {
		friend class map<_K, _Ty, _Pr, _A>;
	public:
		bool operator()(const value_type& _X,
			const value_type& _Y) const
			{return (comp(_X.first, _Y.first)); }
	_PROTECTED:
		value_compare(_Pr _Pred)
			: comp(_Pred) {}
		_Pr comp;
		};
	typedef _Tree<_K, value_type, _Kfn, _Pr, typename
		_A::template rebind<value_type>::other> _Imp;
	typedef _K key_type;
	typedef _Ty referent_type;
	typedef _Pr key_compare;
	typedef typename _Imp::allocator_type allocator_type;
	typedef typename _Imp::size_type size_type;
	typedef typename _Imp::difference_type difference_type;
	typedef typename _Imp::pointer pointer;
	typedef typename _Imp::const_pointer const_pointer;
	typedef typename _Imp::reference reference;
	typedef typename _Imp::const_reference const_reference;
	typedef typename _Imp::iterator iterator;
	typedef typename _Imp::const_iterator const_iterator;
	typedef typename _Imp::reverse_iterator reverse_iterator;
	typedef typename _Imp::const_reverse_iterator
		const_reverse_iterator;
	typedef pair<iterator, bool> _Pairib;
	typedef pair<iterator, iterator> _Pairii;
	typedef pair<const_iterator, const_iterator> _Paircc;
	map()
		: _Tr(_Pr(), false, _A()) {}
	explicit map(const _Pr& _Pred)
		: _Tr(_Pred, false, _A()) {}
	map(const _Pr& _Pred, const _A& _Al)
		: _Tr(_Pred, false, _Al) {}
	template<class _It>
	map(_It _F, _It _L)
		: _Tr(_Pr(), false, _A())
		{for (; _F != _L; ++_F)
			_Tr.insert(*_F); }
	template<class _It>
	map(_It _F, _It _L, const _Pr& _Pred)
		: _Tr(_Pred, false, _A())
		{for (; _F != _L; ++_F)
			_Tr.insert(*_F); }
	template<class _It>
	map(_It _F, _It _L, const _Pr& _Pred, const _A& _Al)
		: _Tr(_Pred, false, _Al)
		{for (; _F != _L; ++_F)
			_Tr.insert(*_F); }
	iterator begin()
		{return (_Tr.begin()); }
	const_iterator begin() const
		{return (_Tr.begin()); }
	iterator end()
		{return (_Tr.end()); }
	const_iterator end() const
		{return (_Tr.end()); }
	reverse_iterator rbegin()
		{return (_Tr.rbegin()); }
	const_reverse_iterator rbegin() const
		{return (_Tr.rbegin()); }
	reverse_iterator rend()
		{return (_Tr.rend()); }
	const_reverse_iterator rend() const
		{return (_Tr.rend()); }
	size_type size() const
		{return (_Tr.size()); }
	size_type max_size() const
		{return (_Tr.max_size()); }
	bool empty() const
		{return (_Tr.empty()); }
	allocator_type get_allocator() const
		{return (_Tr.get_allocator()); }
	_Ty& operator[](const key_type& _Kv)
		{iterator _P = insert(value_type(_Kv, _Ty())).first;
		return ((*_P).second); }
	_Pairib insert(const value_type& _X)
		{typename _Imp::_Pairib _Ans = _Tr.insert(_X);
		return (_Pairib(_Ans.first, _Ans.second)); }
	iterator insert(iterator _P, const value_type& _X)
		{return (_Tr.insert((typename _Imp::iterator&)_P, _X)); }
	template<class _It>
	void insert(_It _F, _It _L)
		{for (; _F != _L; ++_F)
			_Tr.insert(*_F); }
	iterator erase(iterator _P)
		{return (_Tr.erase((typename _Imp::iterator&)_P)); }
	iterator erase(iterator _F, iterator _L)
		{return (_Tr.erase((typename _Imp::iterator&)_F,
			(typename _Imp::iterator&)_L)); }
	size_type erase(const _K& _Kv)
		{return (_Tr.erase(_Kv)); }
	void clear()
		{_Tr.clear(); }
	void swap(_Myt& _X)
		{std::swap(_Tr, _X._Tr); }
	key_compare key_comp() const
		{return (_Tr.key_comp()); }
	value_compare value_comp() const
		{return (value_compare(_Tr.key_comp())); }
	iterator find(const _K& _Kv)
		{return (_Tr.find(_Kv)); }
	const_iterator find(const _K& _Kv) const
		{return (_Tr.find(_Kv)); }
	size_type count(const _K& _Kv) const
		{return (_Tr.count(_Kv)); }
	iterator lower_bound(const _K& _Kv)
		{return (_Tr.lower_bound(_Kv)); }
	const_iterator lower_bound(const _K& _Kv) const
		{return (_Tr.lower_bound(_Kv)); }
	iterator upper_bound(const _K& _Kv)
		{return (_Tr.upper_bound(_Kv)); }
	const_iterator upper_bound(const _K& _Kv) const
		{return (_Tr.upper_bound(_Kv)); }
	_Pairii equal_range(const _K& _Kv)
		{return (_Tr.equal_range(_Kv)); }
	_Paircc equal_range(const _K& _Kv) const
		{return (_Tr.equal_range(_Kv)); }
protected:
	_Imp _Tr;
	};
		// map TEMPLATE OPERATORS
template<class _K, class _Ty, class _Pr, class _A> inline
	void swap(map<_K, _Ty, _Pr, _A>& _X,
		map<_K, _Ty, _Pr, _A>& _Y)
	{_X.swap(_Y); }
template<class _K, class _Ty, class _Pr, class _A> inline
	bool operator==(const map<_K, _Ty, _Pr, _A>& _X,
		const map<_K, _Ty, _Pr, _A>& _Y)
	{return (_X.size() == _Y.size()
		&& equal(_X.begin(), _X.end(), _Y.begin())); }
template<class _K, class _Ty, class _Pr, class _A> inline
	bool operator!=(const map<_K, _Ty, _Pr, _A>& _X,
		const map<_K, _Ty, _Pr, _A>& _Y)
	{return (!(_X == _Y)); }
template<class _K, class _Ty, class _Pr, class _A> inline
	bool operator<(const map<_K, _Ty, _Pr, _A>& _X,
		const map<_K, _Ty, _Pr, _A>& _Y)
	{return (lexicographical_compare(_X.begin(), _X.end(),
		_Y.begin(), _Y.end())); }
template<class _K, class _Ty, class _Pr, class _A> inline
	bool operator>(const map<_K, _Ty, _Pr, _A>& _X,
		const map<_K, _Ty, _Pr, _A>& _Y)
	{return (_Y < _X); }
template<class _K, class _Ty, class _Pr, class _A> inline
	bool operator<=(const map<_K, _Ty, _Pr, _A>& _X,
		const map<_K, _Ty, _Pr, _A>& _Y)
	{return (!(_Y < _X)); }
template<class _K, class _Ty, class _Pr, class _A> inline
	bool operator>=(const map<_K, _Ty, _Pr, _A>& _X,
		const map<_K, _Ty, _Pr, _A>& _Y)
	{return (!(_X < _Y)); }
		// TEMPLATE CLASS multimap
template<class _K, class _Ty, class _Pr _TDEF(less<_K>),
	class _A _TDEF2(allocator<pair<const _K, _Ty> >) >
	class multimap {
public:
	typedef multimap<_K, _Ty, _Pr, _A> _Myt;
	typedef pair<const _K, _Ty> value_type;
	struct _Kfn : public unary_function<value_type, _K> {
		const _K& operator()(const value_type& _X) const
		{return (_X.first); }
		};
	class value_compare
		: public binary_function<value_type, value_type, bool> {
		friend class multimap<_K, _Ty, _Pr, _A>;
	public:
		bool operator()(const value_type& _X,
			const value_type& _Y) const
			{return (comp(_X.first, _Y.first)); }
	_PROTECTED:
		value_compare(_Pr _Pred)
			: comp(_Pred) {}
		_Pr comp;
		};
	typedef _Tree<_K, value_type, _Kfn, _Pr, typename
		_A::template rebind<value_type>::other> _Imp;
	typedef _K key_type;
	typedef _Ty referent_type;
	typedef _Pr key_compare;
	typedef typename _Imp::allocator_type allocator_type;
	typedef typename _Imp::size_type size_type;
	typedef typename _Imp::difference_type difference_type;
	typedef typename _Imp::pointer pointer;
	typedef typename _Imp::const_pointer const_pointer;
	typedef typename _Imp::reference reference;
	typedef typename _Imp::const_reference const_reference;
	typedef typename _Imp::iterator iterator;
	typedef typename _Imp::const_iterator const_iterator;
	typedef typename _Imp::reverse_iterator reverse_iterator;
	typedef typename _Imp::const_reverse_iterator
		const_reverse_iterator;
	typedef pair<iterator, iterator> _Pairii;
	typedef pair<const_iterator, const_iterator> _Paircc;
	multimap()
		: _Tr(_Pr(), true, _A()) {}
	explicit multimap(const _Pr& _Pred)
		: _Tr(_Pred, true, _A()) {}
	multimap(const _Pr& _Pred, const _A& _Al)
		: _Tr(_Pred, true, _Al) {}
	template<class _It>
	multimap(_It _F, _It _L)
		: _Tr(_Pr(), true, _A())
		{for (; _F != _L; ++_F)
			_Tr.insert(*_F); }
	template<class _It>
	multimap(_It _F, _It _L, const _Pr& _Pred)
		: _Tr(_Pred, true, _A())
		{for (; _F != _L; ++_F)
			_Tr.insert(*_F); }
	template<class _It>
	multimap(_It _F, _It _L, const _Pr& _Pred, const _A& _Al)
		: _Tr(_Pred, true, _Al)
		{for (; _F != _L; ++_F)
			_Tr.insert(*_F); }
	iterator begin()
		{return (_Tr.begin()); }
	const_iterator begin() const
		{return (_Tr.begin()); }
	iterator end()
		{return (_Tr.end()); }
	const_iterator end() const
		{return (_Tr.end()); }
	reverse_iterator rbegin()
		{return (_Tr.rbegin()); }
	const_reverse_iterator rbegin() const
		{return (_Tr.rbegin()); }
	reverse_iterator rend()
		{return (_Tr.rend()); }
	const_reverse_iterator rend() const
		{return (_Tr.rend()); }
	size_type size() const
		{return (_Tr.size()); }
	size_type max_size() const
		{return (_Tr.max_size()); }
	bool empty() const
		{return (_Tr.empty()); }
	allocator_type get_allocator() const
		{return (_Tr.get_allocator()); }
	iterator insert(const value_type& _X)
		{return (_Tr.insert(_X).first); }
	iterator insert(iterator _P, const value_type& _X)
		{return (_Tr.insert((typename _Imp::iterator&)_P, _X)); }
	template<class _It>
	void insert(_It _F, _It _L)
		{for (; _F != _L; ++_F)
			_Tr.insert(*_F); }
	iterator erase(iterator _P)
		{return (_Tr.erase((typename _Imp::iterator&)_P)); }
	iterator erase(iterator _F, iterator _L)
		{return (_Tr.erase((typename _Imp::iterator&)_F,
			(typename _Imp::iterator&)_L)); }
	size_type erase(const _K& _Kv)
		{return (_Tr.erase(_Kv)); }
	void clear()
		{_Tr.clear(); }
	void swap(_Myt& _X)
		{std::swap(_Tr, _X._Tr); }
	key_compare key_comp() const
		{return (_Tr.key_comp()); }
	value_compare value_comp() const
		{return (value_compare(_Tr.key_comp())); }
	iterator find(const _K& _Kv)
		{return (_Tr.find(_Kv)); }
	const_iterator find(const _K& _Kv) const
		{return (_Tr.find(_Kv)); }
	size_type count(const _K& _Kv) const
		{return (_Tr.count(_Kv)); }
	iterator lower_bound(const _K& _Kv)
		{return (_Tr.lower_bound(_Kv)); }
	const_iterator lower_bound(const _K& _Kv) const
		{return (_Tr.lower_bound(_Kv)); }
	iterator upper_bound(const _K& _Kv)
		{return (_Tr.upper_bound(_Kv)); }
	const_iterator upper_bound(const _K& _Kv) const
		{return (_Tr.upper_bound(_Kv)); }
	_Pairii equal_range(const _K& _Kv)
		{return (_Tr.equal_range(_Kv)); }
	_Paircc equal_range(const _K& _Kv) const
		{return (_Tr.equal_range(_Kv)); }
protected:
	_Imp _Tr;
	};
		// multimap TEMPLATE OPERATORS
template<class _K, class _Ty, class _Pr, class _A> inline
	void swap(multimap<_K, _Ty, _Pr, _A>& _X,
		multimap<_K, _Ty, _Pr, _A>& _Y)
	{_X.swap(_Y); }
template<class _K, class _Ty, class _Pr, class _A> inline
	bool operator==(const multimap<_K, _Ty, _Pr, _A>& _X,
		const multimap<_K, _Ty, _Pr, _A>& _Y)
	{return (_X.size() == _Y.size()
		&& equal(_X.begin(), _X.end(), _Y.begin())); }
template<class _K, class _Ty, class _Pr, class _A> inline
	bool operator!=(const multimap<_K, _Ty, _Pr, _A>& _X,
		const multimap<_K, _Ty, _Pr, _A>& _Y)
	{return (!(_X == _Y)); }
template<class _K, class _Ty, class _Pr, class _A> inline
	bool operator<(const multimap<_K, _Ty, _Pr, _A>& _X,
		const multimap<_K, _Ty, _Pr, _A>& _Y)
	{return (lexicographical_compare(_X.begin(), _X.end(),
		_Y.begin(), _Y.end())); }
template<class _K, class _Ty, class _Pr, class _A> inline
	bool operator>(const multimap<_K, _Ty, _Pr, _A>& _X,
		const multimap<_K, _Ty, _Pr, _A>& _Y)
	{return (_Y < _X); }
template<class _K, class _Ty, class _Pr, class _A> inline
	bool operator<=(const multimap<_K, _Ty, _Pr, _A>& _X,
		const multimap<_K, _Ty, _Pr, _A>& _Y)
	{return (!(_Y < _X)); }
template<class _K, class _Ty, class _Pr, class _A> inline
	bool operator>=(const multimap<_K, _Ty, _Pr, _A>& _X,
		const multimap<_K, _Ty, _Pr, _A>& _Y)
	{return (!(_X < _Y)); }
_STD_END

#pragma namemangling()

#pragma info(none)
#ifndef __CHKHDR__
#  pragma report(pop)
#endif
#pragma info(restore)

#endif /* _MAP_ */

/*
 * Copyright (c) 1995 by P.J. Plauger.  ALL RIGHTS RESERVED. 
 * Consult your license regarding permissions and restrictions.
 */

/*
 * This file is derived from software bearing the following
 * restrictions:
 *
 * Copyright (c) 1994
 * Hewlett-Packard Company
 *
 * Permission to use, copy, modify, distribute and sell this
 * software and its documentation for any purpose is hereby
 * granted without fee, provided that the above copyright notice
 * appear in all copies and that both that copyright notice and
 * this permission notice appear in supporting documentation.
 * Hewlett-Packard Company makes no representations about the
 * suitability of this software for any purpose. It is provided
 * "as is" without express or implied warranty.
V2.2:0081 */
