#ifndef DS_EXCEPTIONS_H
#define DS_EXCEPTIONS_H

class UnderflowException { };
class IllegalArgumentException { };
class ArrayIndexOutOfBoundsException { };
class IteratorOutOfBoundsException { };
class IteratorMismatchException { };
class IteratorUninitializedException { };

#endif

#ifndef BINARY_SEARCH_TREE_H
#define BINARY_SEARCH_TREE_H

#include "dsexceptions.h"
#include <iostream>    // For NULL
using namespace std;

// BinarySearchTree class
//
// CONSTRUCTION: with ITEM_NOT_FOUND object used to signal failed finds
//
// ******************PUBLIC OPERATIONS*********************
// void insert( x )       --> Insert x
// void remove( x )       --> Remove x
// bool contains( x )     --> Return true if x is present
// Comparable findMin( )  --> Return smallest item
// Comparable findMax( )  --> Return largest item
// boolean isEmpty( )     --> Return true if empty; else false
// void makeEmpty( )      --> Remove all items
// void printTree( )      --> Print elements of the tree in order
// ******************ERRORS********************************
// Throws UnderflowException as warranted

template <typename Comparable>
class BinarySearchTree
{
  public:

BinarySearchTree( ) :root( NULL )
{ }

BinarySearchTree(const BinarySearchTree & rhs) : root(NULL)
{ *this = rhs; }

/**
 * Destructor for the tree
 */
~BinarySearchTree( )
{ makeEmpty( ); }

/**
 * Find the smallest item in the tree.
 * Throw UnderflowException if empty.
 */
const Comparable & findMin( ) const
{
    if (isEmpty( ))
        throw UnderflowException( );
    return findMin(root)->element;
}

/**
 * Find the largest item in the tree.
 * Throw UnderflowException if empty.
 */
const Comparable & findMax( ) const
{
    if(isEmpty( ))
        throw UnderflowException( );
    return findMax( root )->element;
}

/**
 * Returns true if x is found in the tree.
 */
bool contains(const Comparable & x) const
{ return contains(x, root); }

/**
 * Test if the tree is logically empty.
 * Return true if empty, false otherwise.
 */
bool isEmpty( ) const
{ return root == NULL; }

/**
 * Print the tree contents in sorted order.
 */
void printTree(ostream & out = cout) const
{
    if (isEmpty( ))
        out << "Empty tree" << endl;
    else
        printTree(root, out); /**********************************************************************************************************************/
        // As part of the assignment, students
        // must provide the code for the
        // overloaded private member function.
}

void treeToList(ostream & out = cout) //to populate the linked list from the Binary Tree.
{
    if(isEmpty())
        out << "Empty Tree." << endl;
    else
    {
        listInitial(head);            //initializes the linked list 'head' element to be NULL.
        treeToList(head, root);       //overloaded function of treeToList.
    }
}

void displayList(ostream & out = cout) //public call to display the doubly linked list if there are values within.
{
    if(head == NULL)
        out << "List is Empty." << endl;
    else
    {
        displayList(head);
    }
}

/**
 * Make the tree logically empty.
 */
void makeEmpty( )
{ makeEmpty(root); }

/**
 * Insert x into the tree; duplicates are ignored.
 */
void insert(const Comparable & x)
{ insert(x, root); }

/**
 * Remove x from the tree. Nothing is done if x is not found.
 */
void remove(const Comparable & x)
{ remove(x, root); }

/**
 * Deep copy.
 */
const BinarySearchTree & operator=(const BinarySearchTree & rhs)
{
    if (this != &rhs)
    {
        makeEmpty( );
        root = clone(rhs.root);
    }
    return *this;
}

  private:
struct BinaryNode
{
    Comparable element;
    BinaryNode *left;
    BinaryNode *right;

    BinaryNode(const Comparable & theElement, BinaryNode *lt, BinaryNode *rt)
        : element(theElement), left(lt), right(rt) { }
};

BinaryNode *root; /*******************************************************************************************************************************************/

struct Node //node for linked list
{
    int data;
    Node *next;
};

Node *head;

/**
 * Internal method to insert into a subtree.
 * x is the item to insert.
 * t is the node that roots the subtree.
 * Set the new root of the subtree.
 */
void insert(const Comparable & x, BinaryNode * & t)
{
    if (t == NULL)
        t = new BinaryNode(x, NULL, NULL);
    else if (x < t->element)
        insert(x, t->left);
    else if (t->element < x)
        insert(x, t->right);
    else;  // Duplicate; do nothing
}

/**
 * Internal method to remove from a subtree.
 * x is the item to remove.
 * t is the node that roots the subtree.
 * Set the new root of the subtree.
 */
void remove(const Comparable & x, BinaryNode * & t)
{
    if (t == NULL)
        return;   // Item not found; do nothing
    if (x < t->element)
        remove(x, t->left);
    else if (t->element < x)
        remove(x, t->right);
    else if (t->left != NULL && t->right != NULL) // Two children
    {
        t->element = findMin(t->right)->element;
        remove(t->element, t->right);
    }
    else
    {
        BinaryNode *oldNode = t;
        t = (t->left != NULL) ? t->left : t->right;
        delete oldNode;
    }
}

/**
 * Internal method to find the smallest item in a subtree t.
 * Return node containing the smallest item.
 */
BinaryNode * findMin(BinaryNode *t) const
{
    if (t == NULL)
        return NULL;
    if (t->left == NULL)
        return t;
    return findMin(t->left);
}

/**
 * Internal method to find the largest item in a subtree t.
 * Return node containing the largest item.
 */
BinaryNode * findMax(BinaryNode *t) const
{
    if (t != NULL)
        while (t->right != NULL)
            t = t->right;
    return t;
}

/**
 * Internal method to test if an item is in a subtree.
 * x is item to search for.
 * t is the node that roots the subtree.
 */
bool contains(const Comparable & x, BinaryNode *t) const
{
    if (t == NULL)
        return false;
    else if (x < t->element)
        return contains(x, t->left);
    else if (t->element < x)
        return contains(x, t->right);
    else
        return true;    // Match
}

/**
 * Internal method to make subtree empty.
 */
void makeEmpty(BinaryNode * & t)
{
    if (t != NULL)
    {
        makeEmpty(t->left);
        makeEmpty(t->right);
        delete t;
    }
    t = NULL;
}


/***********************************************
 * Internal method to print a subtree rooted.
 */
// Students provide the code for this function
/**************************************************************************************************************************************************************
*/
void printTree(BinaryNode *t, ostream & out = cout) const
{
    if(t)
    {
        printTree(t->left, out);
        out << t->element << " ";
        printTree(t->right, out);
    }
}

/*
*Sets the list head to NULL.
*/
void listInitial(Node *&head)
{
    cout << "listInitial function has been called." << endl;
    head = NULL;
}

/*
* Method to populate the linked list with the BinaryTree printTree function.************************************************************************************
*/
void treeToList(Node *&head, BinaryNode* t)
{
    cout << "treeToList function has been called." << endl;
    if(t)
    {
        treeToList(head, t->left);
        insertToList(head, t->element);
        treeToList(head, t->right);
    }
}


void insertToList(Node *&head, int value) //this function inserts the node to the end of the linked list since inserts from the tree are already in order.******************
{
    cout << "insertToList function has been called." << endl;
    Node *tempNode;                         //temporary node for the locating of the end-node's placement.
    tempNode = (Node*)malloc(sizeof(Node)); //allocating space for the node.
    tempNode = head;                        //give the address of the 'head' to 'tempNode'.
    while(tempNode->next != NULL)           //goes to the last node in the list by searching until the node without a 'next' is found.
        tempNode = tempNode->next;                //the address of 'temp1->next' is moved to temp1.
//*************************************************************************************************************************************
    Node *temp2;                            //another temporary node, this time for the actual insert.
    temp2 = (Node*)malloc(sizeof(Node));    //allocating space for the node.
    temp2->data = value;                    //set the value field of the Node.
    temp2->next = NULL;                     //since this inserted node will be the new end of list, logically it's 'next' pointer is null.
    tempNode->next = temp2;                 //makes the node the last in list.
}

void displayList(Node *head) //this function is from Professor Tim Hartley's code on his website: www.timhartley.com/mcc/DataStructures/swap.cpp ***********
{
     Node *nodePtr;    // Pointer to move through the list
     nodePtr = head;   // Position nodePtr at head of the list
    if (head == NULL)
        cout << "list is empty" << endl;
    else
    {
        while (nodePtr) // Follow pointers through the list
        {
            cout << nodePtr->data << endl; // Display value in this node
            nodePtr = nodePtr->next;       // Advance to next node
        }
     }
}

/**
 * Internal method to clone subtree.
 */
BinaryNode * clone(BinaryNode *t) const
{
    if (t == NULL)
        return NULL;
    else
        return new BinaryNode(t->element, clone(t->left), clone(t->right));
}
};

#endif

#include <iostream>
#include "BinarySearchTree.h"
using namespace std;

int main( )
{
BinarySearchTree<int> t;
int i;

cout << "inserting nodes into tree" << endl;
t.insert(50);
t.insert(60);
t.insert(30);
t.insert(20);
t.insert(40);
t.insert(70);
t.insert(55);
t.insert(65);
t.insert(25);
t.insert(35);
t.insert(85);
t.insert(100);
t.insert(15);
t.insert(45);
t.insert(95);
t.insert(105);
t.insert(10);
t.insert(75);
t.insert(110);
t.insert(12);
t.insert(92);
t.insert(32);
t.insert(82);
t.insert(22);
t.insert(32);

t.printTree( );

cout << endl;
cout << "Finished processing Binary Tree inserts.n" << endl;

cout << "********************************************n" << endl;

cout <<"Below is the linked list with data from least to greatest from the Binary Tree." << endl;

t.treeToList();

system("pause");
return 0;
}

inserting nodes into tree
10 12 15 20 22 25 30 32 35 40 45 50 55 60 65 70 75 82 85 92 95 100 105 110
Finished processing Binary Tree inserts.

********************************************

Below is the linked list with data from least to greatest from the Binary Tree.
listInitial function was called.
treeToList function was called.
treeToList function was called.
treeToList function was called.
treeToList function was called.
treeToList function was called.
treeToList function was called.
insertToList function was called.
Segmentation fault (core dumped)