Template Container					BS_Tree class

NAME
	BS_Tree - store data in a binary search tree

FILE
	BS_Tree.h

SYNOPSIS
	template<class T, class Cmp = less<T> > 
	class BS_Tree;

DESCRIPTION
	The BS_Tree container stores T values in a binary search
	tree. The user can insert and delete values from the BS_Tree
	using the methods insert() and remove(). The container also
	offers iterators for access only and methods for finding a
	value in the container. The user needs to specify the type 
	of objects that have to be stored in the BS_Tree and 
	optionally give a class that can be used for comparing objects
	of type T. The default is to compare using the less than (<) 
	operator.
	
METHODS
	Special methods:
		BS_Tree();
			default constructor; no parameters.

		BS_Tree(BS_Tree& bst);
			copy constructor. We can therefore write:
			BS_Tree<int> bsti2(bsti1);

		BS_Tree& operator= (BS_Tree& bst);
			assignment operator. We can therefore write:
			bsti2 = bsti1;

		~BS_Tree();
			destructor.

	Methods:
		int size();
			returns the size of the BS_Tree;

		bool empty();
			returns true if size is 0;

		static void swap(BS_Tree& bst1, BS_Tree& bst2);
			a static function that interchanges the
			contents of two BS_Tree objects.

		void swap(BS_Tree& bst);
			a function that interchanges the contents
			of the object on which it is called with
			the contents of the object that is taken
			as a parameter.

		void insert(const T& value);
			inserts a new value in the BS_Tree. 
			Duplicates are allowed.

		bool remove(const T& value);
			removes a value from the tree. Returns
			true if value was found and removed,
			false if the value wasn't found.

		bool contains(const T& value);
			returns true if the BS_Tree contains 
			the value, false otherwise.

		const_iterator find(const T& value);
			returns a constant iterator to the first
			element with the given value found in the
			BS_Tree. Returns the same iterator as
			end() if such element is not found.

		const_iterator begin();
			returns a constant iterator to the
			first value in the BS_Tree. The iterator
			allows the user to move inorder over the 
			values in the tree.
			
		const_iterator end();
			returns a constant iterator past the last
			element in the BS_Tree.

	Complexity:
		Most of the methods need O(N) time in the worst 
		case and O(log N) time in the best case where N 
		is the number of elements contained in the 
		BS_Tree.

	Comments:
		The iterators behave like any other STL iterators 
		so you can use them with any STL algorithm that
		requires iterators. They are constant which means
		you cannot change the contents of the BS_Tree by
		using them. The only functions that change the
		contents of the BS_Tree are insert(), delete() and
		swap(). The rest of the functions just provide
		facilities for walking through the values stored
		in the BS_Tree or for looking for a certain value.

		IMPORTANT: Only classes that define an equality
		operator can be stored in a BS_Tree object. This
		is what STL expects from any object and since I
		tried to immitate STL's behavior this is what
		BS_Tree expects also.

		For user defined classes you will have to provide
		a class that can be used to create a function
		object that can compare two objects of the user
		defined class.

EXAMPLES
	#include "BS_Tree.h"
	int main(void)
	{
	  BS_Tree<int> bsti;
	  BS_Tree<int>::const_iterator iter;

	  bsti.insert(16);
	  bsti.insert(8);
	  bsti.insert(24);
	  cout << "Size is: " << bsti.size() << endl;

	  BSTree<int> bsti2(bsti);

	  cout << "look for 7... ";
	  if (bsti.contains(7))
	    {
	      iter = bsti.find(7);
	      cout << "found " << *iter << endl;
	    }
	  else
	    cout << "not found\n";

	  for (iter = bsti.begin(); iter != bsti.end(); iter++)
	    cout << *iter << " ";
	  cout << endl;

	  bsti.swap(bsti2);

	  for (iter = bsti.begin(); iter != bsti.end(); iter++)
	    cout << *iter << " ";
	  cout << endl;

	  if (bsti.remove(8))
	    cout << "8 successfully removed\n";
	  else
	    cout << "8 not found\n";
	}

BUGS
	No known bugs at this time.

	There are several things that I should have done but 
	I didn't because I was lazy. One of them was to check
	for out of memory exceptions throwed when inserting
	new data. The main reason for not doing this is that
	this is just an example of how to write a STL container
	and I don't expect it to be used in a real application.

Laurentiu Cristofor	Last Change: November 4th, 1998