#ifndef FLEXISET_H_INCLUDED
#define FLEXISET_H_INCLUDED

// static const char FlexiSet_h_RcsId[] = "$Id: FlexiSet.h,v 1.13 2003/01/16 04:54:23 neutron Exp $";

//
// FlexiSet.h:
//	A set-like container that has different space characteristics.
//
// Design:
//      FlexiSet is intended as a replacement for the STL set template
//      class.  FlexiSet is an an example of the State Design Pattern.
//      It contains either a SortedVector or a set.  It initially
//      contains a SortedVector, and tries to stay in that state as long
//      as possible.  However, if user attempts to erase an element, or
//      insert out of order, and the SortedVector is larger that a
//      built-in maximum, the storage switches to a set.  It stays as a
//      set unless the method convert_to_vector() is called.
//
// Differences:
//      With a set, iterators are not invalidated when you insert or
//      erase an element.  With FlexiSet, iterators may be invalidated
//      if the FlexiSet is in the vector state.  It is best to assume
//      that iterators will always become invalidated.
//
//		       C O N F I D E N T I A L
//
// Copyright 2001 Hewlett-Packard
//
// No part of this file may be reproduced, stored in a retrieval system,
// or transmitted in any form or by any means--electronic, mechanical,
// photocopying, recording, or otherwise--without prior written permission
// of Hewlett-Packard.
//


#include "SortedVector.h"
#include "StatePatternPtr.h"
#include "StatePatternComposition.h"
#include <set>
#include <cstdlib>				// for getenv()

template<class T, class C> class ConstFlexiIter;  // Forward decl for friend
template<class T, class C> class FlexiSet;	  // Forward decl for friend

template<class T, class C>
class FlexiIterBase;

template<class T, class C>
bool operator==(const FlexiIterBase<T,C> &,
		const FlexiIterBase<T,C> &);

template<class T, class C>
class FlexiIterBase : protected StatePatternComposition <
				typename SortedVector<T,C>::iterator,
				typename std::set<T,C>::iterator
			> {
    protected:
	typedef std::set<T,C> set_t;
	typedef SortedVector<T,C> vector_t;
	typedef typename set_t::iterator set_iter_t;
	typedef typename vector_t::iterator vector_iter_t;

    public:
	typedef T				key_type;
	typedef T				value_type;
	typedef T *				pointer;
	typedef T &				reference;
	typedef typename set_t::size_type	size_type;
	typedef typename set_t::difference_type	difference_type;
	typedef std::bidirectional_iterator_tag	iterator_category;
	FlexiIterBase();
	// Default copy ctor, assignment, and dtor are ok.
	FlexiIterBase(const set_iter_t &);
	FlexiIterBase(const vector_iter_t &);
	FlexiIterBase &operator++();		// prefix
	FlexiIterBase operator++(int);		// postfix
	FlexiIterBase &operator--();		// prefix
	FlexiIterBase operator--(int);		// postfix
	const T &operator*() const;		// indirection
	const T *operator->() const;		// more indirection, kinda

    protected:
	friend bool operator==<T,C>(const FlexiIterBase<T,C> &,
				    const FlexiIterBase<T,C> &);
	friend class ConstFlexiIter<T,C>; // For non-const -> const conversion
	friend class FlexiSet<T,C>;	  // For erase method
};

template<class T, class C>
class FlexiIter : public FlexiIterBase<T,C> {
	typedef FlexiIterBase<T,C> base;
	typedef typename base::set_iter_t set_iter_t;
	typedef typename base::vector_iter_t vector_iter_t;
    public:
	// Default copy ctor, assignment, and dtor are ok.
	FlexiIter();
	FlexiIter(const vector_iter_t &);
	FlexiIter(const set_iter_t &);
	friend class ConstFlexiIter<T,C>; // For non-const -> const conversion
	friend class FlexiSet<T,C>;	  // For erase method
};

template<class T, class C>
bool operator==(const FlexiIterBase<T,C> &, const FlexiIterBase<T,C> &);

template<class T, class C>
class ConstFlexiIter : public FlexiIterBase<T,C> {
	typedef FlexiIterBase<T,C> base;
	typedef typename base::set_iter_t set_iter_t;
	typedef typename base::vector_iter_t vector_iter_t;
    public:
	// Default copy ctor, assignment, and dtor are ok.
	ConstFlexiIter();
	ConstFlexiIter(const vector_iter_t &);
	ConstFlexiIter(const set_iter_t &);

	// Conversion from FlexiIter to ConstFlexiIter
	ConstFlexiIter(const FlexiIter<T,C> &);
	ConstFlexiIter &operator=(const FlexiIter<T,C> &);
};

template <class T, class C = std::less<T> >
class FlexiSet : private StatePatternPtr <
				SortedVector<T,C>,
				std::set<T,C>
			> {
private:
	typedef std::set<T,C> set_t;
	typedef SortedVector<T,C> vector_t;
public:
	typedef T key_type;
	typedef T value_type;
	typedef FlexiIter<T,C> iterator;
	typedef ConstFlexiIter<T, C> const_iterator;
	typedef T &				reference;
	typedef const T &			const_reference;
	typedef typename set_t::size_type	size_type;
	typedef typename set_t::difference_type	difference_type;
	typedef typename set_t::pointer		pointer;
	typedef typename set_t::const_pointer	const_pointer;
	FlexiSet();
	template <class Iter> FlexiSet(Iter first, Iter last);

	// Default copy ctor, assignment operator, and dtor are fine.

	std::pair<iterator, bool> insert(const key_type &item);
	void clear();
	iterator find(const key_type &);
	const_iterator find(const key_type &) const;

	std::pair<iterator, iterator>
	equal_range(const key_type& x);

	std::pair<const_iterator, const_iterator>
	equal_range(const key_type& x) const;

	iterator erase(iterator pos);
	size_type erase(const T &item);
	void erase(iterator first, iterator last);

	size_type size() const;
	size_type max_size() const;
	bool empty() const;
	void convert_to_set();
	void convert_to_vector();
	iterator begin();
	iterator end();
	const_iterator begin() const;
	const_iterator end() const;
private:
	static const unsigned int MAX_VECTOR_ELEMENTS=128;   // WAG
};

//
// If the environment variable FLEXISET_FORCE_SET is set to “true” or “1”,
// then all FlexiSets will stay in set mode forever.  This is easy to do,
// because a FlexiSet starts as a vector, and switches to a set if certain
// conditions are met.  It never switches back to a vector (unless the method
// convert_to_vector() is called, which is never called from this code).
// So, if it's created as a set, it'll naturally stay as a set forever.
//
// This can be useful because an STL set is more predictable than
// an STL vector (or a SortedVector, which is built upon a vector).
// For example, when you erase an element from a set, all other iterators
// to the set remain valid.  However, when you erase an element from a vector,
// that invalidates iterators pointing to elements following the
// erased element, because the subsequent elements are moved.
//
// If you suspect such a problem, try setting FLEXISET_FORCE_SET=1.
// If that fixes the problem, then it's likely that a problem like that
// is occurring in code using a FlexiSet.
//


// Default constructor
template<class T, class C>
FlexiSet<T,C>::FlexiSet() {
	static bool force_set = getenv("FLEXISET_FORCE_SET");

	if (force_set)			// environment var override?
		this->SetB(new set_t);	// predictable, but bigger
	// Otherwise, you get a SortedVector by default
}

// Create a FlexiSet from two iterators into another container.
template<class T, class C>
template <class Iter>
FlexiSet<T,C>::FlexiSet(Iter first, Iter last) {
	static bool force_set = getenv("FLEXISET_FORCE_SET");

	if (force_set)
		SetB(new set_t(first, last));
	else
		SetA(new vector_t(first, last));
}

// How many elements does this FlexiSet contain?
template<class T, class C>
typename FlexiSet<T,C>::size_type FlexiSet<T,C>::size() const {
	return this->IsA() ? this->GetA()->size() : this->GetB()->size();
}

// How many elements can this FlexiSet possibly contain?
// I'm not convinced this is the correct implementation.
template<class T, class C>
typename FlexiSet<T,C>::size_type  FlexiSet<T,C>::max_size() const {
	return this->IsA() ? this->GetA()->max_size() : this->GetB()->max_size();
}

// Is this FlexiSet empty?
template<class T, class C>
bool FlexiSet<T,C>::empty() const {
	return this->IsA() ? this->GetA()->empty() : this->GetB()->empty();
}

// Make this FlexiSet empty.  This does NOT reset the type of the underlying
// container--if it was a set, it remains a set.  I figure that if it was
// big enough to warrant a set before, it will be big enough again.

template<class T, class C>
void FlexiSet<T,C>::clear() {
	if ( this->IsA() )
		this->GetA()->clear();
	else
		this->GetB()->clear();
}

// Insert an item into the FlexiSet.  If a vector gets too big,
// then turn it into a set, unless the item we're adding is in order.

template<class T, class C>
std::pair<typename FlexiSet<T,C>::iterator, bool>
FlexiSet<T,C>::insert(const key_type &item) {
	if (this->IsB())					// A set?
		return this->GetB()->insert(item);

	vector_t *v = this->GetA();

	if (v->size() < MAX_VECTOR_ELEMENTS)
		return v->insert(item);
	else if (v->size() && C()(*(v->end()-1), item)) {
		const iterator i = v->end();
		v->push_back(item);
		return std::make_pair(i, true);
	}
	else {
		convert_to_set();
		return this->GetB()->insert(item);
	}
}

// Make this FlexiSet contain a set.  If it already contains a set, fine.
template<class T, class C>
void FlexiSet<T,C>::convert_to_set() {
	if (!this->IsB()) {			// If it's not already a set:
		vector_t *v = this->GetA();
		this->SetB(new set_t(v->begin(), v->end()));
	}
}

// Make this FlexiSet contain a vector.  If it already does, fine.
template<class T, class C>
void FlexiSet<T,C>::convert_to_vector() {
	if (!this->IsA()) {			// If it's not already a vector:
		set_t *s = this->GetB();
		SetA(new vector_t(s->begin(), s->end()));
	}
}

// Return a non-const begin() for this FlexiSet.
template<class T, class C>
typename FlexiSet<T,C>::iterator FlexiSet<T,C>::begin() {
	if (this->IsA())
		return this->GetA()->begin();
	else
		return this->GetB()->begin();
}

// Return a non-const end() for this FlexiSet.
template<class T, class C>
typename FlexiSet<T,C>::iterator FlexiSet<T,C>::end() {
	if (this->IsA())
		return this->GetA()->end();
	else
		return this->GetB()->end();
}

// Return a const begin() for this FlexiSet.
template<class T, class C>
typename FlexiSet<T,C>::const_iterator FlexiSet<T,C>::begin() const {
	if (this->IsA())
		return this->GetA()->begin();
	else
		return this->GetB()->begin();
}

// Return a const end() for this FlexiSet.
template<class T, class C>
typename FlexiSet<T,C>::const_iterator FlexiSet<T,C>::end() const {
	if (this->IsA())
		return this->GetA()->end();
	else
		return this->GetB()->end();
}

// Find a given item by key in a non-const FlexiSet.
template<class T, class C>
typename FlexiSet<T,C>::iterator
FlexiSet<T,C>::find(const typename FlexiSet<T,C>::key_type &key) {
	if (this->IsA())
		return this->GetA()->find(key);
	else
		return this->GetB()->find(key);
}

// Find a given item by key in a const FlexiSet.
template<class T, class C>
typename FlexiSet<T,C>::const_iterator
FlexiSet<T,C>::find(const typename FlexiSet<T,C>::key_type &key) const {
	if (this->IsA())
		return this->GetA()->find(key);
	else
		return this->GetB()->find(key);
}

template<class T, class C>
std::pair<typename FlexiSet<T,C>::iterator, typename FlexiSet<T,C>::iterator>
FlexiSet<T,C>::equal_range(const typename FlexiSet<T,C>::key_type &key) {
	iterator i=find(key);
	if (i==end())
		return std::pair<iterator,iterator>(i,i);
	iterator j=i;
	++j;
	return std::pair<iterator,iterator>(i,j);
}


template<class T, class C>
std::pair<typename FlexiSet<T,C>::const_iterator,
	  typename FlexiSet<T,C>::const_iterator>
FlexiSet<T,C>::equal_range(const typename FlexiSet<T,C>::key_type &key) const {
	const_iterator i=find(key);
	if (i==end())
		return std::pair<const_iterator,const_iterator>(i,i);
	const_iterator j=i;
	++j;
	return std::pair<const_iterator,const_iterator>(i,j);
}


// Erase an item by key.
template<class T, class C>
typename FlexiSet<T,C>::size_type FlexiSet<T,C>::erase(const T &k) {
	iterator i = find(k);
	if (i==end())
		return 0;
	erase(i);
	return 1;
}

// Erase an item by position.  If removing from a too-big vector,
// convert it to a set.

template<class T, class C>
typename FlexiSet<T,C>::iterator FlexiSet<T,C>::erase(typename FlexiSet<T,C>::iterator pos) {
	// It would be cruel to invalidate their iterator here,
	// just as they're about to use it.
	if (this->IsB()) {				// A set?
		typename set_t::iterator i = *pos.GetB();
		i++;				// Point to next item in set
		this->GetB()->erase(*pos.GetB());	// Erase the doomed item
		return i;			// This iterator is still good.
	}
	else {
		vector_t *v = this->GetA();
		const int index = *pos.GetA() - v->begin();
		v->erase(*pos.GetA());	// Erase the doomed item.
		if (v->size() > MAX_VECTOR_ELEMENTS) {
			convert_to_set();
			typename set_t::iterator i = this->GetB()->begin();
			advance(i, index);
			return i;
		}
		else
			return v->begin()+index;
	}
}

// Remove a bunch of items from a FlexiSet.  If it's a too-big vector,
// turn it into a set.

template<class T, class C>
void FlexiSet<T,C>::erase(typename FlexiSet<T,C>::iterator first,
			  typename FlexiSet<T,C>::iterator last) {
	// If a vector got too big, make it a set.
	if (this->IsA() && this->GetA()->size() > MAX_VECTOR_ELEMENTS)
		convert_to_set();
	if (this->IsA())
		this->GetA()->erase(*first.GetA(), *last.GetA());
	else
		this->GetB()->erase(*first.GetB(), *last.GetB());
}



template<class T, class C>
inline
FlexiIterBase<T,C>::FlexiIterBase() {
}


template<class T, class C>
FlexiIterBase<T,C>::FlexiIterBase(const vector_iter_t &v) {
	this->SetA();
	*(this->GetA()) = v;
}

template<class T, class C>
FlexiIterBase<T,C>::FlexiIterBase(const set_iter_t &s) {
	this->SetB();
	*(this->GetB()) = s;
}

template<class T, class C>
const T &FlexiIterBase<T,C>::operator*() const {
	if (this->IsA())
		return **this->GetA();
	else
		return **this->GetB();
}

template<class T, class C>
inline
const T *FlexiIterBase<T,C>::operator->() const {
	return &operator*();
}

template<class T, class C>
FlexiIterBase<T,C> &FlexiIterBase<T,C>::operator++() {		// ++prefix
	if (this->IsA())
		++*this->GetA();
	else
		++*this->GetB();
	return *this;
}

template<class T, class C>
FlexiIterBase<T,C> FlexiIterBase<T,C>::operator++(int) {	// postfix++
	FlexiIterBase old = *this;
	if (this->IsA())
		++*this->GetA();
	else
		++*this->GetB();
	return old;
}

template<class T, class C>
FlexiIterBase<T,C> &FlexiIterBase<T,C>::operator--() {		// --prefix
	if (this->IsA())
		--*this->GetA();
	else
		--*this->GetB();
	return *this;
}

template<class T, class C>
FlexiIterBase<T,C> FlexiIterBase<T,C>::operator--(int) {	// postfix--
	FlexiIterBase old = *this;
	if (this->IsA())
		--*this->GetA();
	else
		--*this->GetB();
	return old;
}

template<class T, class C>
bool operator==(const FlexiIterBase<T,C> &a, const FlexiIterBase<T,C> &b) {
	if (a.IsA())
		return b.IsA() && *a.GetA()==*b.GetA();
	else
		return b.IsB() && *a.GetB()==*b.GetB();
}

template<class T, class C>
inline
bool operator!=(const FlexiIterBase<T,C> &a, const FlexiIterBase<T,C> &b) {
	return !(a==b);
}


template<class T, class C>
inline
FlexiIter<T,C>::FlexiIter() {}

template<class T, class C>
inline
FlexiIter<T,C>::FlexiIter(const vector_iter_t &sv)
	: base(sv) {}

template<class T, class C>
inline
FlexiIter<T,C>::FlexiIter(const set_iter_t &s)
	: base(s) {}

template<class T, class C>
inline
ConstFlexiIter<T,C>::ConstFlexiIter() {
}

template<class T, class C>
inline
ConstFlexiIter<T,C>::ConstFlexiIter(const FlexiIter<T,C> &f) : base(f) {
}

template<class T, class C>
inline
ConstFlexiIter<T,C>::ConstFlexiIter(const vector_iter_t &sv) : base(sv) {}

template<class T, class C>
inline
ConstFlexiIter<T,C>::ConstFlexiIter(const set_iter_t &s) : base(s) {}


#endif /* FLEXISET_H_INCLUDED */