/elec/propeller-clock : contents of src/utility/associative

: (revision 57)

To get this branch, use:

bzr branch
http://bzr.ed.am/elec/propeller-clock

/*	Copyright (C) 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.h>
#include<iterator>
#include<functional>
#include<list>


#ifndef __STD_HEADER_ASSOCIATIVE_BASE
#define __STD_HEADER_ASSOCIATIVE_BASE

#pragma GCC visibility push(default)

namespace std{


/*
 *	The basic premise here is that most of the code used by map, multimap, set and
 *	multiset is really common.  There are a number of interface additions, and
 *	considerations about how to address multiple entries with the same key.
 *	The goal is that the tree/storage code should be here, and managing
 *	single or multiple counts will be left to subclasses.
 *	Yes, inheritence for the purpose of code sharing is usually a bad idea.
 *	However, since our goal is to reduce the total amount of code written
 *	and the overall binary size, this seems to be the best approach possible.
 */

template<class Key, class ValueType, class Compare = less<Key>, class Allocator = allocator<ValueType> > class __base_associative;
template<class ValueType, class Compare, class Allocator> class _associative_iter;
template<class ValueType, class Compare, class Allocator> class _associative_citer;

template<class Key, class ValueType, class Compare = less<Key>, class Allocator = allocator<ValueType> > class __single_associative;
template<class Key, class ValueType, class Compare = less<Key>, class Allocator = allocator<ValueType> > class __multi_associative;

template<class Key, class ValueType, class Compare, class Allocator> class _UCXXEXPORT __base_associative{

protected:

public:
	typedef Key							key_type;
	typedef ValueType						value_type;
	typedef Compare							key_compare;
	typedef Allocator						allocator_type;
	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 typename Allocator::pointer				pointer;
	typedef typename Allocator::const_pointer			const_pointer;
	typedef __base_associative<Key, ValueType, Compare, Allocator>	associative_type;

	typedef _associative_iter<value_type, Compare, Allocator>	iterator;
	typedef _associative_citer<value_type, Compare, Allocator>	const_iterator;
	typedef typename std::reverse_iterator<iterator>		reverse_iterator;
	typedef typename std::reverse_iterator<const_iterator>		const_reverse_iterator;


	explicit __base_associative(const Compare& comp, const Allocator& A, const key_type (*v_to_k)(const value_type))
		: c(comp), value_to_key(v_to_k) { }
protected:
	__base_associative(const associative_type& x)
		: c(x.c), backing(x.backing), value_to_key(x.value_to_key) { }

public:
	~__base_associative(){
	}

	bool empty() const{
		return backing.empty();
	}
	size_type size() const{
		return backing.size();
	}
	size_type max_size() const{
		return backing.max_size();
	}

	iterator begin(){
		return iterator(backing.begin());
	}

	const_iterator begin() const{
		return const_iterator(backing.begin());
	}

	iterator end() {
		return iterator(backing.end());
	}

	const_iterator end() const{
		return const_iterator(backing.end());
	}

	reverse_iterator rbegin(){
		return reverse_iterator(end());
	}

	const_reverse_iterator rbegin() const{
		return const_reverse_iterator(end());
	}

	reverse_iterator rend(){
		return reverse_iterator(begin());
	}

	const_reverse_iterator rend() const{
		return const_reverse_iterator(begin());
	}


	iterator lower_bound(const key_type &x);
	const_iterator lower_bound(const key_type &x) const;
	iterator upper_bound(const key_type &x);
	const_iterator upper_bound(const key_type &x) const;

	pair<iterator,iterator> equal_range(const key_type& x){
		pair<iterator, iterator> retval;
		retval.first = lower_bound(x);
		retval.second = retval.first;
		while(retval.second != end() && !c(x, value_to_key(*retval.second))){
			++retval.second;
		}
		return retval;
	}
	pair<const_iterator,const_iterator> equal_range(const key_type& x) const{
		pair<const_iterator, const_iterator> retval;
		retval.first = lower_bound(x);
		retval.second = retval.first;
		while(retval.second != end() && !c(x, value_to_key(*retval.second))){
			++retval.second;
		}
		return retval;
	}

	iterator find(const key_type& x){
		iterator retval = lower_bound(x);
		if(retval == end()){
			return retval;
		}
		if(c(x, value_to_key(*retval))){
			return end();
		}
		return retval;
	}
        const_iterator find(const key_type& x) const{
		const_iterator retval = lower_bound(x);
		if(retval == end()){
			return retval;
		}
		if(c(x, value_to_key(*retval))){
			return end();
		}
		return retval;
	}
        size_type count(const key_type& x) const{
		size_type retval(0);
		const_iterator first = lower_bound(x);
		while(first != end() && !c(x, value_to_key(*first))){
			++retval;
			++first;
		}
		return retval;
	}

	void clear(){
		backing.clear();
	}

	void erase(iterator pos){
		backing.erase(pos.base_iterator());
	}
        size_type erase(const key_type& x){
		size_type count(0);
		iterator start = lower_bound(x);
		iterator end = upper_bound(x);
		while(start != end){
			start = backing.erase(start.base_iterator());
			++count;
		}
		return count;
	}
        void erase(iterator first, iterator last){
		while(first != last){
			backing.erase(first.base_iterator());
			++first;
		}
	}

	key_compare key_comp() const{
		return c;
	}

	__base_associative &operator=(const __base_associative & x){
		c = x.c;
		backing = x.backing;
		value_to_key = x.value_to_key;
		return *this;
	}
	bool operator==(const __base_associative & x){
		return x.backing == backing;
	}
	bool operator!=(const __base_associative & x){
		return !(x.backing == backing);
	}

protected:
	void swap(__base_associative & x);

	Compare c;
	std::list<value_type> backing;

	const key_type (*value_to_key)(const value_type);

};


/*
 * Tree iterators for the base associative class
 */

template<class ValueType, class Compare, class Allocator> class _associative_citer
	: public std::iterator<
		bidirectional_iterator_tag,
		ValueType,
		typename Allocator::difference_type,
		ValueType*,
		ValueType&
	>
{
protected:
	typedef std::list<ValueType> listtype;

	typename listtype::const_iterator base_iter;
	friend class _associative_iter<ValueType, Compare, Allocator>;
public:
	_associative_citer() { }
	_associative_citer(const _associative_citer & m)
		: base_iter(m.base_iter) { }
	_associative_citer(const typename listtype::const_iterator & m)
		: base_iter(m) { }
	~_associative_citer() { }
	ValueType operator*() const{
		return *base_iter;
	}
	const ValueType * operator->() const{
		return &(*base_iter);
	}
	_associative_citer & operator=(const _associative_citer & m){
		base_iter = m.base_iter;
		return *this;
	}
	bool operator==(const _associative_citer & m) const{
		return m.base_iter == base_iter;
	}
	bool operator!=(const _associative_citer & m) const{
		return m.base_iter != base_iter;
	}
	_associative_citer & operator++(){
		++base_iter;
		return *this;
	}
	_associative_citer operator++(int){
		//The following approach ensures that we only need to
		//provide code for ++ in one place (above)
		_associative_citer temp(base_iter);
		++base_iter;
		return temp;
	}
	_associative_citer & operator--(){
		--base_iter;
		return *this;
	}
	_associative_citer operator--(int){
		//The following approach ensures that we only need to
		//provide code for -- in one place (above)
		_associative_citer temp(base_iter);
		--base_iter;
		return temp;
	}

	//This is an implementation-defined function designed to make internals work correctly
	typename listtype::const_iterator base_iterator(){
		return base_iter;
	}
};


template<class ValueType, class Compare, class Allocator> class _associative_iter
	: public std::iterator<
		bidirectional_iterator_tag,
		ValueType,
		typename Allocator::difference_type,
		ValueType*,
		ValueType&
	>
{
protected:
	typedef std::list<ValueType> listtype;

	typename listtype::iterator base_iter;
	typedef _associative_citer<ValueType, Compare, Allocator> __associative_citer;

public:
	_associative_iter() { }
	_associative_iter(const _associative_iter & m)
		: base_iter(m.base_iter) { }
	_associative_iter(const typename listtype::iterator & m)
		: base_iter(m) { }
	~_associative_iter() { }
	const ValueType & operator*() const{
		return *base_iter;
	}
	ValueType & operator*(){
		return *base_iter;
	}
	ValueType * operator->(){
		return &(*base_iter);
	}
	const ValueType * operator->() const{
		return &(*base_iter);
	}
	_associative_iter & operator=(const _associative_iter & m){
		base_iter = m.base_iter;
		return *this;
	}
	bool operator==(const _associative_iter & m) const{
		return m.base_iter == base_iter;
	}
	bool operator==(const __associative_citer & m) const{
		return m.base_iter == base_iter;
	}
	bool operator!=(const _associative_iter & m) const{
		return m.base_iter != base_iter;
	}
	bool operator!=(const __associative_citer & m) const{
		return m.base_iter != base_iter;
	}
	_associative_iter & operator++(){
		++base_iter;
		return *this;
	}
	_associative_iter operator++(int){
		//The following approach ensures that we only need to
		//provide code for ++ in one place (above)
		_associative_iter temp(base_iter);
		++base_iter;
		return temp;
	}
	_associative_iter & operator--(){
		--base_iter;
		return *this;
	}
	_associative_iter operator--(int){
		//The following approach ensures that we only need to
		//provide code for -- in one place (above)
		_associative_iter temp(base_iter);
		--base_iter;
		return temp;
	}
	operator __associative_citer() const{
		return __associative_citer(base_iter);
	}
	typename listtype::iterator base_iterator(){
		return base_iter;
	}
	const typename listtype::iterator base_iterator() const{
		return base_iter;
	}

};


	// The lower_bound code is really crappy linear search.  However, it is a dead
	// simple implementation (easy to audit).  It can also be easily replaced.


	template <class Key, class ValueType, class Compare, class Allocator>
		typename __base_associative<Key, ValueType, Compare, Allocator>::iterator
		__base_associative<Key, ValueType, Compare, Allocator>::lower_bound(const key_type &x)
	{
		iterator retval = begin();
		while(retval != end() && c(value_to_key(*retval), x)){
			++retval;
		}
		return retval;
	}

	template <class Key, class ValueType, class Compare, class Allocator>
		typename __base_associative<Key, ValueType, Compare, Allocator>::const_iterator
		__base_associative<Key, ValueType, Compare, Allocator>::lower_bound(const key_type &x) const
	{
		const_iterator retval = begin();
		while(retval != end() && c(value_to_key(*retval), x)){
			++retval;
		}
		return retval;
	}

	// Upper bound search is linear from the point of lower_bound.  This is likely the best solution
	// in all but the most pathological of cases.

	template <class Key, class ValueType, class Compare, class Allocator>
		typename __base_associative<Key, ValueType, Compare, Allocator>::iterator
		__base_associative<Key, ValueType, Compare, Allocator>::upper_bound(const key_type &x)
	{
		iterator retval = lower_bound(x);
		while(retval != end() && !c(x, value_to_key(*retval))){
			++retval;
		}
		return retval;
	}

	template <class Key, class ValueType, class Compare, class Allocator>
		typename __base_associative<Key, ValueType, Compare, Allocator>::const_iterator
		__base_associative<Key, ValueType, Compare, Allocator>::upper_bound(const key_type &x) const
	{
		const_iterator retval = begin();
		while(retval != end() && !c(x, value_to_key(*retval))){
			++retval;
		}
		return retval;
	}


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

		m.backing.swap(backing);
	}


template<class Key, class ValueType, class Compare, class Allocator> class _UCXXEXPORT __single_associative :
	public __base_associative<Key, ValueType, Compare, Allocator>
{
protected:
	typedef __base_associative<Key, ValueType, Compare, Allocator> base;
	using base::backing;

	using base::c;

public:
	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;

	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;

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

	explicit __single_associative(const Compare& comp, const Allocator& A, const key_type (*v_to_k)(const value_type))
		: base(comp, A, v_to_k) { }

	template <class InputIterator> __single_associative(
		InputIterator first,
		InputIterator last,
		const Compare& comp,
		const Allocator& A,
		const key_type (*v_to_k)(const value_type)
	) : base(comp, A, v_to_k) {
		insert(first, last);
	}

	pair<iterator, bool> insert(const value_type& x){
		pair<iterator, bool> retval;
		iterator location = lower_bound(value_to_key(x));
		retval.second = true;
		//Empty list or need to insert at end
		if(end() == location){
			backing.push_back(x);
			retval.first = --(end());
			return retval;
		}
		//Something in the list
		if(c(value_to_key(x), value_to_key(*location))){
			location = backing.insert(location.base_iterator(), x);
			retval.first = location;
		}else{
			retval.second = false;
			retval.first = location;
		}
		return retval;
	}

	iterator insert(iterator position, const value_type& x){
		// FIXME - this is cheating and probably should be more efficient since we are
		// now log(n) to find for inserts
		return insert(x).first;
	}

	template <class InputIterator> void insert(InputIterator first, InputIterator last){
		while(first != last){
			insert(*first);
			++first;
		}
	}

};


template<class Key, class ValueType, class Compare, class Allocator> class _UCXXEXPORT __multi_associative :
	public __base_associative<Key, ValueType, Compare, Allocator>
{
protected:
	typedef __base_associative<Key, ValueType, Compare, Allocator> base;
	using base::backing;

	using base::c;

public:
	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;

	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;

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


	explicit __multi_associative(const Compare& comp, const Allocator& A, const key_type (*v_to_k)(const value_type))
		: base(comp, A, v_to_k) { }

	template <class InputIterator> __multi_associative(
		InputIterator first,
		InputIterator last,
		const Compare& comp,
		const Allocator& A,
		const key_type (*v_to_k)(const value_type)
	) : base(comp, A, v_to_k) {
		insert(first, last);
	}

	iterator insert(const value_type& x){
		iterator location = lower_bound(value_to_key(x));

		if(location == begin()){
			backing.push_front(x);
			location = begin();
		}else{
			location = backing.insert(location.base_iterator(), x);
		}
		return location;
	}

	iterator insert(iterator position, const value_type& x){
		// FIXME - this is cheating and probably should be more efficient since we are
		// now log(n) to find for inserts
		return insert(x);
	}

	template <class InputIterator> void insert(InputIterator first, InputIterator last){
		while(first != last){
			insert(*first);
			++first;
		}
	}
};




}

#pragma GCC visibility pop

#endif	//__STD_HEADER_ASSOCIATIVE_BASE


57 by edam added ulibc	1	/* Copyright (C) 2007 Garrett A. Kajmowicz
	2	This file is part of the uClibc++ Library.
	3
	4	This library is free software; you can redistribute it and/or
	5	modify it under the terms of the GNU Lesser General Public
	6	License as published by the Free Software Foundation; either
	7	version 2.1 of the License, or (at your option) any later version.
	8
	9	This library is distributed in the hope that it will be useful,
	10	but WITHOUT ANY WARRANTY; without even the implied warranty of
	11	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
	12	Lesser General Public License for more details.
	13
	14	You should have received a copy of the GNU Lesser General Public
	15	License along with this library; if not, write to the Free Software
	16	Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
	17	*/
	18
	19
	20
	21	#include<memory>
	22	#include<utility.h>
	23	#include<iterator>
	24	#include<functional>
	25	#include<list>
	26
	27
	28	#ifndef __STD_HEADER_ASSOCIATIVE_BASE
	29	#define __STD_HEADER_ASSOCIATIVE_BASE
	30
	31	#pragma GCC visibility push(default)
	32
	33	namespace std{
	34
	35
	36	/*
	37	* The basic premise here is that most of the code used by map, multimap, set and
	38	* multiset is really common. There are a number of interface additions, and
	39	* considerations about how to address multiple entries with the same key.
	40	* The goal is that the tree/storage code should be here, and managing
	41	* single or multiple counts will be left to subclasses.
	42	* Yes, inheritence for the purpose of code sharing is usually a bad idea.
	43	* However, since our goal is to reduce the total amount of code written
	44	* and the overall binary size, this seems to be the best approach possible.
	45	*/
	46
	47	template<class Key, class ValueType, class Compare = less<Key>, class Allocator = allocator<ValueType> > class __base_associative;
	48	template<class ValueType, class Compare, class Allocator> class _associative_iter;
	49	template<class ValueType, class Compare, class Allocator> class _associative_citer;
	50
	51	template<class Key, class ValueType, class Compare = less<Key>, class Allocator = allocator<ValueType> > class __single_associative;
	52	template<class Key, class ValueType, class Compare = less<Key>, class Allocator = allocator<ValueType> > class __multi_associative;
	53
	54	template<class Key, class ValueType, class Compare, class Allocator> class _UCXXEXPORT __base_associative{
	55
	56	protected:
	57
	58	public:
	59	typedef Key key_type;
	60	typedef ValueType value_type;
	61	typedef Compare key_compare;
	62	typedef Allocator allocator_type;
	63	typedef typename Allocator::reference reference;
	64	typedef typename Allocator::const_reference const_reference;
65	typedef typename Allocator::size_type size_type;
66	typedef typename Allocator::difference_type difference_type;
67	typedef typename Allocator::pointer pointer;
68	typedef typename Allocator::const_pointer const_pointer;
69	typedef __base_associative<Key, ValueType, Compare, Allocator> associative_type;
70
71	typedef _associative_iter<value_type, Compare, Allocator> iterator;
72	typedef _associative_citer<value_type, Compare, Allocator> const_iterator;
73	typedef typename std::reverse_iterator<iterator> reverse_iterator;
74	typedef typename std::reverse_iterator<const_iterator> const_reverse_iterator;
75
76
77	explicit __base_associative(const Compare& comp, const Allocator& A, const key_type (*v_to_k)(const value_type))
78	: c(comp), value_to_key(v_to_k) { }
79	protected:
80	__base_associative(const associative_type& x)
81	: c(x.c), backing(x.backing), value_to_key(x.value_to_key) { }
82
83	public:
84	~__base_associative(){
85	}
86
87	bool empty() const{
88	return backing.empty();
89	}
90	size_type size() const{
91	return backing.size();
92	}
93	size_type max_size() const{
94	return backing.max_size();
95	}
96
97	iterator begin(){
98	return iterator(backing.begin());
99	}
100
101	const_iterator begin() const{
102	return const_iterator(backing.begin());
103	}
104
105	iterator end() {
106	return iterator(backing.end());
107	}
108
109	const_iterator end() const{
110	return const_iterator(backing.end());
111	}
112
113	reverse_iterator rbegin(){
114	return reverse_iterator(end());
115	}
116
117	const_reverse_iterator rbegin() const{
118	return const_reverse_iterator(end());
119	}
120
121	reverse_iterator rend(){
122	return reverse_iterator(begin());
123	}
124
125	const_reverse_iterator rend() const{
126	return const_reverse_iterator(begin());
127	}
128
129
130	iterator lower_bound(const key_type &x);
131	const_iterator lower_bound(const key_type &x) const;
132	iterator upper_bound(const key_type &x);
133	const_iterator upper_bound(const key_type &x) const;
134
135	pair<iterator,iterator> equal_range(const key_type& x){
136	pair<iterator, iterator> retval;
137	retval.first = lower_bound(x);
138	retval.second = retval.first;
139	while(retval.second != end() && !c(x, value_to_key(*retval.second))){
140	++retval.second;
141	}
142	return retval;
143	}
144	pair<const_iterator,const_iterator> equal_range(const key_type& x) const{
145	pair<const_iterator, const_iterator> retval;
146	retval.first = lower_bound(x);
147	retval.second = retval.first;
148	while(retval.second != end() && !c(x, value_to_key(*retval.second))){
149	++retval.second;
150	}
151	return retval;
152	}
153
154	iterator find(const key_type& x){
155	iterator retval = lower_bound(x);
156	if(retval == end()){
157	return retval;
158	}
159	if(c(x, value_to_key(*retval))){
160	return end();
161	}
162	return retval;
163	}
164	const_iterator find(const key_type& x) const{
165	const_iterator retval = lower_bound(x);
166	if(retval == end()){
167	return retval;
168	}
169	if(c(x, value_to_key(*retval))){
170	return end();
171	}
172	return retval;
173	}
174	size_type count(const key_type& x) const{
175	size_type retval(0);
176	const_iterator first = lower_bound(x);
177	while(first != end() && !c(x, value_to_key(*first))){
178	++retval;
179	++first;
180	}
181	return retval;
182	}
183
184	void clear(){
185	backing.clear();
186	}
187
188	void erase(iterator pos){
189	backing.erase(pos.base_iterator());
190	}
191	size_type erase(const key_type& x){
192	size_type count(0);
193	iterator start = lower_bound(x);
194	iterator end = upper_bound(x);
195	while(start != end){
196	start = backing.erase(start.base_iterator());
197	++count;
198	}
199	return count;
200	}
201	void erase(iterator first, iterator last){
202	while(first != last){
203	backing.erase(first.base_iterator());
204	++first;
205	}
206	}
207
208	key_compare key_comp() const{
209	return c;
210	}
211
212	__base_associative &operator=(const __base_associative & x){
213	c = x.c;
214	backing = x.backing;
215	value_to_key = x.value_to_key;
216	return *this;
217	}
218	bool operator==(const __base_associative & x){
219	return x.backing == backing;
220	}
221	bool operator!=(const __base_associative & x){
222	return !(x.backing == backing);
223	}
224
225	protected:
226	void swap(__base_associative & x);
227
228	Compare c;
229	std::list<value_type> backing;
230
231	const key_type (*value_to_key)(const value_type);
232
233	};
234
235
236	/*
237	* Tree iterators for the base associative class
238	*/
239
240	template<class ValueType, class Compare, class Allocator> class _associative_citer
241	: public std::iterator<
242	bidirectional_iterator_tag,
243	ValueType,
244	typename Allocator::difference_type,
245	ValueType*,
246	ValueType&
247	>
248	{
249	protected:
250	typedef std::list<ValueType> listtype;
251
252	typename listtype::const_iterator base_iter;
253	friend class _associative_iter<ValueType, Compare, Allocator>;
254	public:
255	_associative_citer() { }
256	_associative_citer(const _associative_citer & m)
257	: base_iter(m.base_iter) { }
258	_associative_citer(const typename listtype::const_iterator & m)
259	: base_iter(m) { }
260	~_associative_citer() { }
261	ValueType operator*() const{
262	return *base_iter;
263	}
264	const ValueType * operator->() const{
265	return &(*base_iter);
266	}
267	_associative_citer & operator=(const _associative_citer & m){
268	base_iter = m.base_iter;
269	return *this;
270	}
271	bool operator==(const _associative_citer & m) const{
272	return m.base_iter == base_iter;
273	}
274	bool operator!=(const _associative_citer & m) const{
275	return m.base_iter != base_iter;
276	}
277	_associative_citer & operator++(){
278	++base_iter;
279	return *this;
280	}
281	_associative_citer operator++(int){
282	//The following approach ensures that we only need to
283	//provide code for ++ in one place (above)
284	_associative_citer temp(base_iter);
285	++base_iter;
286	return temp;
287	}
288	_associative_citer & operator--(){
289	--base_iter;
290	return *this;
291	}
292	_associative_citer operator--(int){
293	//The following approach ensures that we only need to
294	//provide code for -- in one place (above)
295	_associative_citer temp(base_iter);
296	--base_iter;
297	return temp;
298	}
299
300	//This is an implementation-defined function designed to make internals work correctly
301	typename listtype::const_iterator base_iterator(){
302	return base_iter;
303	}
304	};
305
306
307	template<class ValueType, class Compare, class Allocator> class _associative_iter
308	: public std::iterator<
309	bidirectional_iterator_tag,
310	ValueType,
311	typename Allocator::difference_type,
312	ValueType*,
313	ValueType&
314	>
315	{
316	protected:
317	typedef std::list<ValueType> listtype;
318
319	typename listtype::iterator base_iter;
320	typedef _associative_citer<ValueType, Compare, Allocator> __associative_citer;
321
322	public:
323	_associative_iter() { }
324	_associative_iter(const _associative_iter & m)
325	: base_iter(m.base_iter) { }
326	_associative_iter(const typename listtype::iterator & m)
327	: base_iter(m) { }
328	~_associative_iter() { }
329	const ValueType & operator*() const{
330	return *base_iter;
331	}
332	ValueType & operator*(){
333	return *base_iter;
334	}
335	ValueType * operator->(){
336	return &(*base_iter);
337	}
338	const ValueType * operator->() const{
339	return &(*base_iter);
340	}
341	_associative_iter & operator=(const _associative_iter & m){
342	base_iter = m.base_iter;
343	return *this;
344	}
345	bool operator==(const _associative_iter & m) const{
346	return m.base_iter == base_iter;
347	}
348	bool operator==(const __associative_citer & m) const{
349	return m.base_iter == base_iter;
350	}
351	bool operator!=(const _associative_iter & m) const{
352	return m.base_iter != base_iter;
353	}
354	bool operator!=(const __associative_citer & m) const{
355	return m.base_iter != base_iter;
356	}
357	_associative_iter & operator++(){
358	++base_iter;
359	return *this;
360	}
361	_associative_iter operator++(int){
362	//The following approach ensures that we only need to
363	//provide code for ++ in one place (above)
364	_associative_iter temp(base_iter);
365	++base_iter;
366	return temp;
367	}
368	_associative_iter & operator--(){
369	--base_iter;
370	return *this;
371	}
372	_associative_iter operator--(int){
373	//The following approach ensures that we only need to
374	//provide code for -- in one place (above)
375	_associative_iter temp(base_iter);
376	--base_iter;
377	return temp;
378	}
379	operator __associative_citer() const{
380	return __associative_citer(base_iter);
381	}
382	typename listtype::iterator base_iterator(){
383	return base_iter;
384	}
385	const typename listtype::iterator base_iterator() const{
386	return base_iter;
387	}
388
389	};
390
391
392	// The lower_bound code is really crappy linear search. However, it is a dead
393	// simple implementation (easy to audit). It can also be easily replaced.
394
395
396	template <class Key, class ValueType, class Compare, class Allocator>
397	typename __base_associative<Key, ValueType, Compare, Allocator>::iterator
398	__base_associative<Key, ValueType, Compare, Allocator>::lower_bound(const key_type &x)
399	{
400	iterator retval = begin();
401	while(retval != end() && c(value_to_key(*retval), x)){
402	++retval;
403	}
404	return retval;
405	}
406
407	template <class Key, class ValueType, class Compare, class Allocator>
408	typename __base_associative<Key, ValueType, Compare, Allocator>::const_iterator
409	__base_associative<Key, ValueType, Compare, Allocator>::lower_bound(const key_type &x) const
410	{
411	const_iterator retval = begin();
412	while(retval != end() && c(value_to_key(*retval), x)){
413	++retval;
414	}
415	return retval;
416	}
417
418	// Upper bound search is linear from the point of lower_bound. This is likely the best solution
419	// in all but the most pathological of cases.
420
421	template <class Key, class ValueType, class Compare, class Allocator>
422	typename __base_associative<Key, ValueType, Compare, Allocator>::iterator
423	__base_associative<Key, ValueType, Compare, Allocator>::upper_bound(const key_type &x)
424	{
425	iterator retval = lower_bound(x);
426	while(retval != end() && !c(x, value_to_key(*retval))){
427	++retval;
428	}
429	return retval;
430	}
431
432	template <class Key, class ValueType, class Compare, class Allocator>
433	typename __base_associative<Key, ValueType, Compare, Allocator>::const_iterator
434	__base_associative<Key, ValueType, Compare, Allocator>::upper_bound(const key_type &x) const
435	{
436	const_iterator retval = begin();
437	while(retval != end() && !c(x, value_to_key(*retval))){
438	++retval;
439	}
440	return retval;
441	}
442
443
444	template <class Key, class ValueType, class Compare, class Allocator>
445	void __base_associative<Key, ValueType, Compare, Allocator>::swap(__base_associative<Key, ValueType, Compare, Allocator>& m)
446	{
447	Compare n = c;
448	c = m.c;
449	m.c = n;
450
451	m.backing.swap(backing);
452	}
453
454
455	template<class Key, class ValueType, class Compare, class Allocator> class _UCXXEXPORT __single_associative :
456	public __base_associative<Key, ValueType, Compare, Allocator>
457	{
458	protected:
459	typedef __base_associative<Key, ValueType, Compare, Allocator> base;
460	using base::backing;
461
462	using base::c;
463
464	public:
465	typedef typename base::key_type key_type;
466	typedef typename base::value_type value_type;
467	typedef typename base::key_compare key_compare;
468	typedef typename base::allocator_type allocator_type;
469	typedef typename base::reference reference;
470	typedef typename base::const_reference const_reference;
471	typedef typename base::iterator iterator;
472	typedef typename base::const_iterator const_iterator;
473	typedef typename base::size_type size_type;
474	typedef typename base::difference_type difference_type;
475	typedef typename base::pointer pointer;
476	typedef typename base::const_pointer const_pointer;
477	typedef typename base::reverse_iterator reverse_iterator;
478	typedef typename base::const_reverse_iterator const_reverse_iterator;
479
480	using base::begin;
481	using base::end;
482	using base::rbegin;
483	using base::rend;
484
485	using base::empty;
486	using base::size;
487	using base::max_size;
488
489	using base::find;
490	using base::count;
491	using base::lower_bound;
492	using base::upper_bound;
493	using base::equal_range;
494
495	using base::operator=;
496	using base::operator==;
497	using base::operator!=;
498
499	explicit __single_associative(const Compare& comp, const Allocator& A, const key_type (*v_to_k)(const value_type))
500	: base(comp, A, v_to_k) { }
501
502	template <class InputIterator> __single_associative(
503	InputIterator first,
504	InputIterator last,
505	const Compare& comp,
506	const Allocator& A,
507	const key_type (*v_to_k)(const value_type)
508	) : base(comp, A, v_to_k) {
509	insert(first, last);
510	}
511
512	pair<iterator, bool> insert(const value_type& x){
513	pair<iterator, bool> retval;
514	iterator location = lower_bound(value_to_key(x));
515	retval.second = true;
516	//Empty list or need to insert at end
517	if(end() == location){
518	backing.push_back(x);
519	retval.first = --(end());
520	return retval;
521	}
522	//Something in the list
523	if(c(value_to_key(x), value_to_key(*location))){
524	location = backing.insert(location.base_iterator(), x);
525	retval.first = location;
526	}else{
527	retval.second = false;
528	retval.first = location;
529	}
530	return retval;
531	}
532
533	iterator insert(iterator position, const value_type& x){
534	// FIXME - this is cheating and probably should be more efficient since we are
535	// now log(n) to find for inserts
536	return insert(x).first;
537	}
538
539	template <class InputIterator> void insert(InputIterator first, InputIterator last){
540	while(first != last){
541	insert(*first);
542	++first;
543	}
544	}
545
546	};
547
548
549	template<class Key, class ValueType, class Compare, class Allocator> class _UCXXEXPORT __multi_associative :
550	public __base_associative<Key, ValueType, Compare, Allocator>
551	{
552	protected:
553	typedef __base_associative<Key, ValueType, Compare, Allocator> base;
554	using base::backing;
555
556	using base::c;
557
558	public:
559	typedef typename base::key_type key_type;
560	typedef typename base::value_type value_type;
561	typedef typename base::key_compare key_compare;
562	typedef typename base::allocator_type allocator_type;
563	typedef typename base::reference reference;
564	typedef typename base::const_reference const_reference;
565	typedef typename base::iterator iterator;
566	typedef typename base::const_iterator const_iterator;
567	typedef typename base::size_type size_type;
568	typedef typename base::difference_type difference_type;
569	typedef typename base::pointer pointer;
570	typedef typename base::const_pointer const_pointer;
571	typedef typename base::reverse_iterator reverse_iterator;
572	typedef typename base::const_reverse_iterator const_reverse_iterator;
573
574	using base::begin;
575	using base::end;
576	using base::rbegin;
577	using base::rend;
578
579	using base::empty;
580	using base::size;
581	using base::max_size;
582
583	using base::find;
584	using base::count;
585	using base::lower_bound;
586	using base::upper_bound;
587	using base::equal_range;
588
589	using base::operator=;
590	using base::operator==;
591
592
593	explicit __multi_associative(const Compare& comp, const Allocator& A, const key_type (*v_to_k)(const value_type))
594	: base(comp, A, v_to_k) { }
595
596	template <class InputIterator> __multi_associative(
597	InputIterator first,
598	InputIterator last,
599	const Compare& comp,
600	const Allocator& A,
601	const key_type (*v_to_k)(const value_type)
602	) : base(comp, A, v_to_k) {
603	insert(first, last);
604	}
605
606	iterator insert(const value_type& x){
607	iterator location = lower_bound(value_to_key(x));
608
609	if(location == begin()){
610	backing.push_front(x);
611	location = begin();
612	}else{
613	location = backing.insert(location.base_iterator(), x);
614	}
615	return location;
616	}
617
618	iterator insert(iterator position, const value_type& x){
619	// FIXME - this is cheating and probably should be more efficient since we are
620	// now log(n) to find for inserts
621	return insert(x);
622	}
623
624	template <class InputIterator> void insert(InputIterator first, InputIterator last){
625	while(first != last){
626	insert(*first);
627	++first;
628	}
629	}
630	};
631
632
633
634
635	}
636
637	#pragma GCC visibility pop
638
639	#endif //__STD_HEADER_ASSOCIATIVE_BASE
640