//treesort.h
//header file for treesort fnc

#include<iostream>
#include <iterator>

#ifndef FILE_TREESORT_H_INCLUDED
#define FILE_TREESORT_H_INCLUDED

template <typename T>

struct node
{
	T data;
	node *left;
	node *right;

	//node ctor
	node(T item)
	{
		data = item;
		left = NULL;
		right = NULL;
	}

	~node()
	{
		delete left;
		delete right;
	}
};

//insert fnc
template <typename T>
void insert(node<T> *&root, T newItem)
{
	if(root == NULL)
	{
		root = new node<T>(newItem);
		return;
	}

	else if(newItem < root->data)
	{
		insert(root->left, newItem);
	}
	else
	{
		insert(root->right, newItem);
	}
}

//postOrderPrint fnc
//prints tree in post-order
template <typename T, typename FDIter>
void traverse (node<T> *root, FDIter iter)
{
	if(root != NULL)
	{
		traverse(root->left, iter);
		*iter++ = root->data;
		traverse(root->right, iter);
	}
}

//treesort fnc
template <typename FDIter>
void treesort(FDIter first, FDIter last)
{
	typedef typename std::iterator_traits<FDIter>::value_type ValueType;
	node<ValueType> *root;
	root = NULL;
	int ctr = 0;
	try
	{
		for (FDIter it = first; it != last; ++it)
		{
			insert(root, *first);
		}
		traverse(root, first);

	}
	
	catch(...)
	{
		delete root;
		throw;
	}
	delete root;
}


#endif;

// treesort_test.cpp


#include "treesort.h"   // For treesort
// Include above BEFORE system files, to make sure it works by itself
#include "treesort.h"   // Double inclusion test

// Includes for testing package
#include <iostream>     // for std::cout, std::endl
#include <string>       // for std::string

// Includes for this testing program
#include <vector>       // for std::vector
#include <list>         // for std::list
#include <deque>        // for std::deque
#include <algorithm>    // for std::stable_sort, std::equal

// ************************************************************************
// Testing class
// ************************************************************************


// class Tester
// For extremely simple unit testing.
// Keeps track of number of tests and number of passes.
// Use test (with success/failure parameter) to do a test.
// Get results with numTests, numPassed, numFailed, allPassed.
// Restart testing with reset.
// Invariants:
//     countTests_ == number of tests (calls to test) since last reset.
//     countPasses_ == number of times function test called with true param
//      since last reset.
//     0 <= countPasses_ <= countTests_.
//     tolerance_ >= 0.
class Tester {

// ***** Tester: ctors, dctor, op= *****
public:

    // Default ctor
    // Sets countTests_, countPasses_ to zero, tolerance_ to given value
    // Pre: None.
    // Post:
    //     numTests == 0, countPasses == 0, tolerance_ == abs(theTolerance)
    Tester(double theTolerance = 0.0000001)
        :countTests_(0),
         countPasses_(0),
         tolerance_(theTolerance >= 0 ? theTolerance : -theTolerance)
    {}

    // Compiler-generated copy ctor, copy op=, dctor are used

// ***** Tester: general public functions *****
public:

    // test
    // Handles single test, param indicates pass/fail
    // Pre: None.
    // Post:
    //     countTests_ incremented
    //     countPasses_ incremented if (success)
    //     Message indicating test name (if given)
    //      and pass/fail printed to cout
    void test(bool success,
              const std::string & testName = "")
    {
        ++countTests_;
        if (success) ++countPasses_;

        std::cout << "    ";
        if (testName != "")
        {
            std::cout << "Test: "
                      << testName
                      << " - ";
        }
        std::cout << (success ? "passed" : "********** FAILED **********")
                  << std::endl;
    }

    // ftest
    // Does single floating-point test.
    // Tests passes iff difference of first two values is <= tolerance.
    // Pre: None.
    // Post:
    //     countTests_ incremented
    //     countPasses_ incremented if (abs(val1-val2) <= tolerance_)
    //     Message indicating test name (if given)
    //      and pass/fail printed to cout
    void ftest(double val1,
               double val2,
               const std::string & testName = "")
    { test(val1-val2 <= tolerance_ && val2-val1 <= tolerance_, testName); }

    // reset
    // Resets *this to default constructed state
    // Pre: None.
    // Post:
    //     countTests_ == 0, countPasses_ == 0
    void reset()
    {
        countTests_ = 0;
        countPasses_ = 0;
    }

    // numTests
    // Returns the number of tests that have been done since last reset 
    // Pre: None.
    // Post:
    //     return == countTests_
    int numTests() const
    { return countTests_; }

    // numPassed
    // Returns the number of tests that have passed since last reset
    // Pre: None.
    // Post:
    //     return == countPasses_
    int numPassed() const
    { return countPasses_; }

    // numFailed
    // Returns the number of tests that have not passed since last reset
    // Pre: None.
    // Post:
    //     return + countPasses_ == numTests_
    int numFailed() const
    { return countTests_ - countPasses_; }

    // allPassed
    // Returns true if all tests since last reset have passed
    // Pre: None.
    // Post:
    //     return == (countPasses_ == countTests_)
    bool allPassed() const
    { return countPasses_ == countTests_; }

    // setTolerance
    // Sets tolerance_ to given value
    // Pre: None.
    // Post:
    //     tolerance_ = abs(theTolerance)
    void setTolerance(double theTolerance)
    { tolerance_ = (theTolerance >= 0 ? theTolerance : -theTolerance); }

// ***** Tester: data members *****
private:

    int countTests_;    // Number of tests done since last reset
    int countPasses_;   // Number of tests passed since last reset
    double tolerance_;  // Tolerance for floating-point near-equality tests

};  // end class Tester


// ************************************************************************
// Class for type requirements checking
// ************************************************************************

// class OnlyLessThan
// For objects with limited operator availability.
// Has only default ctor, big 3, and operator< (always returns false).
// In particular, does not have operators ==, !=, >, >=.
// Invariants: None.
class OnlyLessThan {

    // Compiler-generated default ctor, copy ctor, copy =, dctor used

};  // End class OnlyLessThan

// operator< (OnlyLessThan)
// Fake operator< for OnlyLessThan class
// Returns false - which is legal, if all objects of type OnlyLessThan
// represent the same numeric value.
// Pre: None.
// Post:
//     Return is false.
// Does not throw (No-Throw Guarantee)
bool operator<(const OnlyLessThan & a,
               const OnlyLessThan & b)
{ return false; }


// ************************************************************************
// Item class for checking number of existing objects
// ************************************************************************


// class Counter
// Item type for counting number of existing objects and operations
// performed.
// Invariants:
//     Counter::exist_ is number of objects of type Counter
//      that currently exist.
//     Counter::maxExist_ is max number of objects of type Counter
//      that have ever existing at one time, since last call to
//      Counter::reset or start of program.
//     Counter::ops_ is total number of calls to Counter default ctor,
//      copy ctor, copy assignment, dctor, since last call to
//      Counter::reset or start of program.
class Counter {

// ***** Counter: Ctors, dctor, op= *****
public:

    // Default ctor
    // Pre: None.
    // Post: None.
    Counter()
    {
        ++exist_;
        if (exist_ > maxExist_)
            maxExist_ = exist_; 
        ++ops_;
    }

    // Copy ctor
    // Pre: None.
    // Post: None.
    Counter(const Counter & other)
    {
        ++exist_;
        if (exist_ > maxExist_)
            maxExist_ = exist_; 
        ++ops_;
    }

    // Copy assignment
    // Pre: None.
    // Post: None.
    Counter & operator=(const Counter & rhs)
    {
        ++ops_;
        return *this;
    }

    // Dctor
    // Pre: None.
    // Post: None.
    ~Counter()
    {
        --exist_;
        ++ops_;
    }

// ***** Counter: General public functions *****
public:

    static void reset()
    {
        maxExist_ = exist_;
        ops_ = 0;
    }

    // getExisting
    // Returns value of exist_
    // Pre: None.
    // Post:
    //     Return value == exist_.
    static int getExisting()
    { return exist_; }

    // getMaxExisting
    // Returns value of maxExist_
    // Pre: None.
    // Post:
    //     Return value == maxExist_.
    static int getMaxExisting()
    { return maxExist_; }

    // getOps
    // Returns value of ops_
    // Pre: None.
    // Post:
    //     Return value == ops_.
    static int getOps()
    { return ops_; }

// ***** Counter: Data members *****
private:

    static int exist_;     // # of existing objects
    static int maxExist_;  // Max # of existing objects since last reset
    static int ops_;       // # of operations performed so far

};  // End class Counter

// Definition of static data members of class Counter
int Counter::exist_ = 0;
int Counter::maxExist_ = 0;
int Counter::ops_ = 0;

bool operator<(const Counter & a,
               const Counter & b)
{ return false; }


// ************************************************************************
// Special "pair" item class
// ************************************************************************


// class MyPair
// Holds pair of ints
// operator== is as usual, operator< only compairs first item in each pair
// Invariants: None.
class MyPair {

public:

    MyPair(int theX = 0,
           int theY = 0)
        :x_(theX),
         y_(theY)
    {}

    // Compiler-generated copy ctor, copy =, dctor used

    // getX
    // returns x_
    // Pre: None.
    // Post:
    //     Return value == x_.
    // Does not throw (No-Throw Guarantee)
    int getX() const
    { return x_; }

    // getY
    // returns y_
    // Pre: None.
    // Post:
    //     Return value == y_.
    // Does not throw (No-Throw Guarantee)
    int getY() const
    { return y_; }

private:

    int x_;  // First item in pair
    int y_;  // Second item in pair

};  // End class MyPair


bool operator==(const MyPair & a,
                const MyPair & b)
{ return a.getX() == b.getX() && a.getY() == b.getY(); }

bool operator<(const MyPair & a,
               const MyPair & b)
{ return a.getX() < b.getX(); }


// ************************************************************************
// Test Suite Functions
// ************************************************************************


// test_treesort_type_requirements
// Test suite for function treesort, type requirements
// Pre: None.
// Post:
//     Pass/fail status of tests have been registered with t.
//     Appropriate have been messages printed to cout.
// Does not throw (No-Throw Guarantee)
void test_treesort_type_requirements(Tester & t)
{
    std::cout << "Test Suite: function treesort, type requirements" << std::endl;

    // Works with minimal-functionality type (passes if it compiles)
    std::vector<OnlyLessThan> v(100);
    treesort(v.begin(), v.end());
    t.test(true, "Compiles with value type having minimal functionality");
}


// test_treesort_basic_int
// Test suite for function treesort, basic functionality, sorting ints
// Pre: None.
// Post:
//     Pass/fail status of tests have been registered with t.
//     Appropriate have been messages printed to cout.
// Does not throw (No-Throw Guarantee)
void test_treesort_basic_int(Tester & t)
{
    std::cout << "Test Suite: function treesort, basic functionality - sorting ints" << std::endl;

    // Value type for this test suite
    typedef int val;

    const int DATASIZE = 20;
    val data[DATASIZE] = { 3, 6, 19, -2, 8, 6, 7, 1, 141, -2, -200, 4, 6, 6, 11, -5, 32, 2, 7, 0 };
    // Make copies of data
    const std::vector<val> dataCheck(data, data+DATASIZE);
    std::vector<val> data_v(data, data+DATASIZE);
    std::deque<val> data_d(data, data+DATASIZE);
    std::list<val> data_l(data, data+DATASIZE);

    // Sorted data (all but first, last)
    std::vector<val> dataSorted1(data, data+DATASIZE);
    std::stable_sort(dataSorted1.begin()+1, dataSorted1.end()-1);

    // Sorted data (all)
    std::vector<val> dataSorted2(data, data+DATASIZE);
    std::stable_sort(dataSorted2.begin(), dataSorted2.end());

    // Test: vector empty range
    treesort(data_v.begin()+7, data_v.begin()+7);
    t.test(std::equal(data_v.begin(), data_v.end(), dataCheck.begin()), "vector: empty range");

    // Test: vector one item
    treesort(data_v.begin()+7, data_v.begin()+8);
    t.test(std::equal(data_v.begin(), data_v.end(), dataCheck.begin()), "vector: one item");

    // Test: vector nearly all
    treesort(data_v.begin()+1, data_v.end()-1);
    t.test(std::equal(data_v.begin(), data_v.end(), dataSorted1.begin()), "vector: nearly all");

    // Test: vector all
    treesort(data_v.begin(), data_v.end());
    t.test(std::equal(data_v.begin(), data_v.end(), dataSorted2.begin()), "vector: all");

    // Test: deque empty range
    treesort(data_d.begin()+7, data_d.begin()+7);
    t.test(std::equal(data_d.begin(), data_d.end(), dataCheck.begin()), "deque: empty range");

    // Test: deque one item
    treesort(data_d.begin()+7, data_d.begin()+8);
    t.test(std::equal(data_d.begin(), data_d.end(), dataCheck.begin()), "deque: one item");

    // Test: deque nearly all
    treesort(data_d.begin()+1, data_d.end()-1);
    t.test(std::equal(data_d.begin(), data_d.end(), dataSorted1.begin()), "deque: nearly all");

    // Test: deque all
    treesort(data_d.begin(), data_d.end());
    t.test(std::equal(data_d.begin(), data_d.end(), dataSorted2.begin()), "deque: all");

    std::list<val>::iterator it1, it2;

    // Test: list empty range
    it1 = data_l.begin();
    std::advance(it1, 3);
    it2 = data_l.begin();
    std::advance(it2, 3);
    treesort(it1, it2);
    t.test(std::equal(data_l.begin(), data_l.end(), dataCheck.begin()), "list: empty range");

    // Test: list one item
    ++it2;
    treesort(it1, it2);
    t.test(std::equal(data_l.begin(), data_l.end(), dataCheck.begin()), "list: one item");

    // Test: list nearly all
    it1 = data_l.begin();
    ++it1;
    it2 = data_l.end();
    --it2;
    treesort(it1, it2);
    t.test(std::equal(data_l.begin(), data_l.end(), dataSorted1.begin()), "list: nearly all");

    // Test: list all
    treesort(data_l.begin(), data_l.end());
    t.test(std::equal(data_l.begin(), data_l.end(), dataSorted2.begin()), "list: all");
}


// test_treesort_basic_double
// Test suite for function treesort, basic functionality, sorting doubles
// Pre: None.
// Post:
//     Pass/fail status of tests have been registered with t.
//     Appropriate have been messages printed to cout.
// Does not throw (No-Throw Guarantee)
void test_treesort_basic_double(Tester & t)
{
    std::cout << "Test Suite: function treesort, basic functionality - sorting doubles" << std::endl;

    // Value type for this test suite
    typedef double val;

    const int DATASIZE = 20;
    val data[DATASIZE] = { 3.1, 6.2, 19.3, -2.4, 8.5, 6.6, 7.7, 1.8, 141.9, -2.0, -200.1, 4.2, 6.3, 6.4, 11.5, -5.6, 32.7, 2.8, 7.9, 0.0 };
    // Make copies of data
    const std::vector<val> dataCheck(data, data+DATASIZE);
    std::vector<val> data_v(data, data+DATASIZE);
    std::deque<val> data_d(data, data+DATASIZE);
    std::list<val> data_l(data, data+DATASIZE);

    // Sorted data (all but first, last)
    std::vector<val> dataSorted1(data, data+DATASIZE);
    std::stable_sort(dataSorted1.begin()+1, dataSorted1.end()-1);

    // Sorted data (all)
    std::vector<val> dataSorted2(data, data+DATASIZE);
    std::stable_sort(dataSorted2.begin(), dataSorted2.end());

    // Test: vector empty range
    treesort(data_v.begin()+7, data_v.begin()+7);
    t.test(std::equal(data_v.begin(), data_v.end(), dataCheck.begin()), "vector: empty range");

    // Test: vector one item
    treesort(data_v.begin()+7, data_v.begin()+8);
    t.test(std::equal(data_v.begin(), data_v.end(), dataCheck.begin()), "vector: one item");

    // Test: vector nearly all
    treesort(data_v.begin()+1, data_v.end()-1);
    t.test(std::equal(data_v.begin(), data_v.end(), dataSorted1.begin()), "vector: nearly all");

    // Test: vector all
    treesort(data_v.begin(), data_v.end());
    t.test(std::equal(data_v.begin(), data_v.end(), dataSorted2.begin()), "vector: all");

    // Test: deque empty range
    treesort(data_d.begin()+7, data_d.begin()+7);
    t.test(std::equal(data_d.begin(), data_d.end(), dataCheck.begin()), "deque: empty range");

    // Test: deque one item
    treesort(data_d.begin()+7, data_d.begin()+8);
    t.test(std::equal(data_d.begin(), data_d.end(), dataCheck.begin()), "deque: one item");

    // Test: deque nearly all
    treesort(data_d.begin()+1, data_d.end()-1);
    t.test(std::equal(data_d.begin(), data_d.end(), dataSorted1.begin()), "deque: nearly all");

    // Test: deque all
    treesort(data_d.begin(), data_d.end());
    t.test(std::equal(data_d.begin(), data_d.end(), dataSorted2.begin()), "deque: all");

    std::list<val>::iterator it1, it2;

    // Test: list empty range
    it1 = data_l.begin();
    std::advance(it1, 3);
    it2 = data_l.begin();
    std::advance(it2, 3);
    treesort(it1, it2);
    t.test(std::equal(data_l.begin(), data_l.end(), dataCheck.begin()), "list: empty range");

    // Test: list one item
    ++it2;
    treesort(it1, it2);
    t.test(std::equal(data_l.begin(), data_l.end(), dataCheck.begin()), "list: one item");

    // Test: list nearly all
    it1 = data_l.begin();
    ++it1;
    it2 = data_l.end();
    --it2;
    treesort(it1, it2);
    t.test(std::equal(data_l.begin(), data_l.end(), dataSorted1.begin()), "list: nearly all");

    // Test: list all
    treesort(data_l.begin(), data_l.end());
    t.test(std::equal(data_l.begin(), data_l.end(), dataSorted2.begin()), "list: all");
}


// test_treesort_object_count
// Test suite for function treesort, object counts
// Pre: None.
// Post:
//     Pass/fail status of tests have been registered with t.
//     Appropriate have been messages printed to cout.
// Does not throw (No-Throw Guarantee)
void test_treesort_object_count(Tester & t)
{
    std::cout << "Test Suite: function treesort, object counts" << std::endl;

    const int SIZE = 100;
    std::vector<Counter> vc(SIZE);
    Counter::reset();

    treesort(vc.begin(), vc.end());
    t.test(Counter::getMaxExisting() >= 2*SIZE, "at least n additional objects used in sorting");
    t.test(Counter::getExisting() == SIZE, "all additional objects destroyed");

}


// test_treesort_stability
// Test suite for function treesort, stability
// Pre: None.
// Post:
//     Pass/fail status of tests have been registered with t.
//     Appropriate have been messages printed to cout.
// Does not throw (No-Throw Guarantee)
void test_treesort_stability(Tester & t)
{
    std::cout << "Test Suite: function treesort, stability" << std::endl;

    const int SIZE = 16;

    int dataX[SIZE] = { 8, 7, 7, 6, 2, 3, 2, 4, 8, 3, 1, 1, 4, 5, 6, 5 };
    int dataY[SIZE] = { 1, 1, 2, 1, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 2, 2 };

    std::vector<MyPair> vp1(SIZE);
    for (int i = 0; i < SIZE; ++i)
        vp1[i] = MyPair(dataX[i], dataY[i]);

    std::vector<MyPair> vp2(vp1);

    treesort(vp1.begin(), vp1.end());
    std::stable_sort(vp2.begin(), vp2.end());
    t.test(std::equal(vp1.begin(), vp1.end(), vp2.begin()), "treesort is stable");
}


// test_treesort
// Test suite for function treesort
// Uses other test-suite functions
// Pre: None.
// Post:
//     Pass/fail status of tests have been registered with t.
//     Appropriate have been messages printed to cout.
// Does not throw (No-Throw Guarantee)
void test_treesort(Tester & t)
{
    // Do all the test suites
    std::cout << "TEST SUITES FOR FUNCTION treesort" << std::endl;
    test_treesort_type_requirements(t);
    test_treesort_basic_int(t);
    test_treesort_basic_double(t);
    test_treesort_object_count(t);
    test_treesort_stability(t);
}


// ************************************************************************
// Main program
// ************************************************************************


// main
// Runs function treesort test suite, prints results to cout.
int main()
{
    Tester t;
    test_treesort(t);

    std::cout << std::endl;
    if (t.allPassed())
    {
        std::cout << "All tests successful" 
                  << std::endl;
    }
    else
    {
        std::cout << "Tests ********** UNSUCCESSFUL **********"
                  << std::endl;
    }
    std::cout << std::endl;
}