//
//	test of tree sort routine
//
//	Described in Chapter 14 of
//	Data Structures in C++ using the STL
//	Published by Addison-Wesley, 1997
//	Written by Tim Budd, budd@cs.orst.edu
//	Oregon State University
//

# include <vector.h>
# include <iostream.h>
# include <multiset.h>
# include <algo.h>

//
//	see section 3 of appendix a wrt to
//	second argument in declaration of multiset
//

template <class T> 
void treeSort(vector<T> & data)
{
	// declare a search tree of the correct type
	multiset<T, less<T> > sorter;
	vector<T>::iterator itr, stop;
	stop = data.end();

	// copy the entire vector into the tree
	for (itr = data.begin(); itr != stop; ++itr)
		sorter.insert(*itr);

	// now copy the values back into the array
	multiset<T, less<T> >::iterator tree;
	for (itr = data.begin(); itr != stop; ++itr)
		*itr = *tree++;
}

void main() {
	vector<int> v(100);
	for (int i = 0; i < 100; i++)
		v[i] = rand();
	treeSort(v);
	vector<int>::iterator itr = v.begin();
	while (itr != v.end()) {
		cout << *itr << " ";
		itr++;
		}
	// copy (v.begin(), v.end(), ostream_iterator<int>(cout, ":"));
	cout << "\n";
}