//
//	simplified implementation of set data type
//
//	Described in Chapter 12 of
//	Data Structures in C++ using the STL
//	Published by Addison-Wesley, 1997
//	Written by Tim Budd, budd@cs.orst.edu
//	Oregon State University
//


template <class T>
class node {
public:
	node (T & v, node<T> * par, node<T> * left, node<T> * right)
		: value(v), parent(par), leftChild(left), rightChild(right) { }

		// operations
	node<T> * copy ( node<T> *);
	void release ();
	int count (T & testElement);
	void insert (node<T> *);
	int size ();
	node<T> * merge (node<T> *, node<T> *);
	inorderTreeTraversal<T> lower_bound(T &, inorderTreeTraversal<T> &);
	inorderTreeTraversal<T> upper_bound(T &, inorderTreeTraversal<T> &);

		// data fields
	T value;
	node<T> * parent;
	node<T> * leftChild;
	node<T> * rightChild;
};

template <class T>
class inorderTreeTraversal {
public:
	typedef inorderTreeTraversal<T> iterator;

		// constructor
	inorderTreeTraversal (node<T> * s);
	inorderTreeTraversal (iterator & itr)
		: current (itr.current) { }

		// iterator protocol
	inorderTreeTraversal<T> & operator ++();
	inorderTreeTraversal<T> operator ++(int);
	T & operator * ()
		{ return current->value; }
	void operator = (iterator & itr)
		{ current = itr.current; }
	bool operator == (iterator & rhs)
		{ return current == rhs.current; }

protected:
	node<T> * current;
};

# if 0
template <class T>
inorderTreeTraveral<T> inorderTreeTraversal<T>::operator ++ (int)
{
		// clone ourselves using the copy constructor
	inorderTreeTraversal<T> clone (*this);
	operator ++ ();		// increment ourselves
	return clone; 		// return copy
}
# endif

template <class T>
inorderTreeTraversal<T>::inorderTreeTraversal (node<T> * root)
	// initialize inorder traversal
{
	current = root;
		// perform a left slide
	while (current && current->leftChild)
		current = current->leftChild;
}

template <class T>
class set {
public:
	typedef inorderTreeTraversal<T> iterator;

		// constructor
	set () 
			{ root = 0; }

		// tree traversing operations
	void insert (T &);
	void erase (T & testElement)
			{ root = remove (root, testElement); }
	int count (T & testElement);
	iterator lower_bound (T & testElement);
	iterator upper_bound (T & testElement);

		// other operations
	bool empty () { return root == 0; }
	int size ();
	void swap (set<T> & right) { ::swap (root, right.root); }

protected:
		// root of binary search tree
	node<T> * root;

		// internal method used in removal
	node<T> * remove (node<T> *, T &);
};


template <class T> int set<T>::size()
	// count the number of elements in set
{
	if (root == 0)
		return 0;
	else
		return root->size();
}

template <class T> int node<T>::size()
	// count number of elements in subtree rooted at node
{
	int count = 1;
	if (leftChild != 0)
		count += leftChild.size();
	if (rightChild != 0)
		count += rightChild.size();
	return count;
}


template <class T> inorderTreeTraversal<T> set<T>::lower_bound (T & element)
	// find first occurrence of element in collection
{
	if (root == 0)
		return end();
	else
		return root->lower_bound(element, end());
}

template <class T> inorderTreeTraversal<T> node<T>::lower_bound (T & element, inorderTreeTraversal<T> & end)
{
	if (value < element)
		if (rightChild != 0)
			return rightChild->lower_bound (element, end);
		else
			return end; // not found at all
	// check left child
	if (leftChild != 0) {
			// see if it is found along left child
		set<T>::iterator result = leftChild->lower_bound (element, end);
		if (result != end) // found it, must be first
			return result;
		}
	// not found in left child, either we are it or not found at all
	if (element < value)
		return end;	// not found at all
	else
		return setIterator(this); // make iterator that points to us
}

template <class T> inorderTreeTraversal<T> node<T>::upper_bound (T & element, inorderTreeTraversal<T> & end)
{
	if (value < element)
		if (rightChild != 0)
			return rightChild->upper_bound (element, end);
		else
			return end; // not found at all
	if (leftChild != 0) {
		iterator result = leftChild->upper_bound (element, end);
		if (result != end) return result;
		}
	if (element < value)
		return setIterator (this);
	return end;
}

template <class T> int set<T>::count (T & element)
	// count number of occurrences of element
{
	iterator first = lower_bound(element);
	iterator last = upper_bound(element);
	int counter = 0;
		// count number of elements between lower and upper
	while (first != last) {
		counter++;
		first++;
		}
	return counter;
}

template <class T> void set<T>::insert (T & newElement)
	// insert a new element into a set
{
		// do not insert if already in set
	if (count(newElement) > 0)
		return;
		// create a new node
	node<T> * newNode = new node<T> (newElement, 0, 0, 0);
		// see if collection is empty
	if (root == 0)
		root = newNode;
	else
		root->insert (newNode);
}

template <class T> void node<T>::insert (node<T> * newNode)
	// insert a new element into a binary search tree
{
	if (newElement < value)
		if (leftChild != 0)
			leftChild->insert (newNode);
		else {
			newNode->parent = this;
			leftChild = newNode;
			}
	else
		if (rightChild != 0)
			rightChild->insert (newNode);
		else {
			newNode->parent = this;
			rightChild = newNode;
			}
}

template <class T> 
node<T> * node<T>::merge (node<T> * left, node<T> * right)
	// merge two subtrees into one
{
	if (left == 0)
		return right;
	if (right == 0)
		return left;
	node<T> * child = merge(left, right->leftChild);
	child->parent = right;
	right->leftChild = child;
	return right;
}

template <class T>
node<T> * set<T>::remove (node<T> * current, T & testElement)
	// remove all instances of testElement from collection
{
	if (current != 0) {
		node<T> * pa = current->parent;
		if (testElement < current->value)
			current->leftChild = 
				remove (current->leftChild, testElement);
		else if (current->value < testElement)
			current->rightChild = 
				remove (current->rightChild, testElement);
		else { 		// found an item to remove
			node<T> * result = current->merge(current->leftChild, 
				remove (current->rightChild, testElement));
			delete current;
			result->parent = pa;
			return result;
			}
		}
	return current;
}