associative_base

/*	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& , 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(this->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(this->value_to_key(x), this->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