/************************************************************/
/* ADAPTED FROM:                                               */
/* http://www.cs.colorado.edu/~main/chapter10/bintree.template */
/*                                                             */
/* Main and Savitch, "Data Structures and Other Objects     */
/*    using C++", 2nd edition, Addison-Wesley, Ch.10        */
/************************************************************/

//-----------------------------------------------------------
// File: binary_tree_node.template
// Name: Savitch and Main
//       (adapted by Sharon Tuttle)
// last modified: 3-31-05
//
// Template Class: binary_tree_node<Item> (a node for a binary
//    tree whose data is an Item)
//    See binary_tree_node.h for documentation.
//
// Because this is a template class, it is included in
//    the header file, and not compiled separately.
//----------------------------------------------------------

#include <cassert>    // Provides assert
#include <cstdlib>    // Provides NULL, size_t
#include <iomanip>    // Provides setw
#include <iostream>   // Provides cout
using namespace std;

/****************************************************/
/* CONSTRUCTOR                                      */
/****************************************************/
        
// postcondition: creates a new node with data equal
//    to init_data, and its child pointers equal to
//    init_left and init_right.   
//
template <typename Item>
binary_tree_node<Item>::binary_tree_node(const Item& init_data/* = Item( )*/,
                 binary_tree_node<Item>* init_left/* = NULL*/,
                 binary_tree_node<Item>* init_right/* = NULL*/)
{ 
    data_field = init_data; 
    left_field = init_left; 
    right_field = init_right;
}
        
/*******************************************************/
/* ACCESSORS and other constant member functions       */
/*    (observers)                                      */
/*******************************************************/

// get_data
//
// postcondition: returns a reference to the data from 
//    this binary_tree_node
//
template <typename Item>
const Item& binary_tree_node<Item>::get_data( ) const 
{ 
    return data_field; 
}

// get_left
//
// postcondition: returns a pointer to the left child
//    (which will be NULL if there is no child)
//
template <typename Item>
const binary_tree_node<Item>* binary_tree_node<Item>::get_left( ) const 
{ 
    return left_field; 
}

// get_right
//
// postcondition: returns a pointer to the right child
//    (which will be NULL if there is no child)
//
template <typename Item>
const binary_tree_node<Item>* binary_tree_node<Item>::get_right( ) const 
{ 
    return right_field; 
}

// WHY are these slightly-different versions here,
//    also?! BECAUSE, as mentioned in an earlier chapter,
//    we need one version when we are permitted to change
//    a node, and another versons for when we are not
//    permitted to change a node (p. 464, p. 306, p. 304)
template <typename Item>
Item& binary_tree_node<Item>::get_data( ) 
{ 
    return data_field; 
}

template <typename Item>
binary_tree_node<Item>*& binary_tree_node<Item>::get_left( ) 
{ 
    return left_field; 
}

template <typename Item>
binary_tree_node<Item>*& binary_tree_node<Item>::get_right( ) 
{ 
    return right_field; 
}

// is_leaf
//
// postcondition: returns true if the node is a leaf;
//    otherwise returns false.
//
template <typename Item>
bool binary_tree_node<Item>::is_leaf( ) const 
{ 
    return (left_field == NULL) && 
   (right_field == NULL); 
}

/****************************************************/
/* MODIFIERS and other modifying member functions   */
/****************************************************/

// set_data
//
// postcondition: the binary_tree_node now contains
//    the specified new data.
//
template <typename Item>
void binary_tree_node<Item>::set_data(const Item& new_data) 
{ 
    data_field = new_data; 
}

// set_left
//
// postcondition: the binary_tree_node now contains
//    the specified new link to a left child.
//
template <typename Item>
void binary_tree_node<Item>::set_left(binary_tree_node<Item>* new_left) 
{ 
    left_field = new_left; 
}

// set_right
//
// postcondition: the binary_tree_node now contains
//    the specified new link to a right child.
//
template <typename Item>
void binary_tree_node<Item>::set_right(binary_tree_node<Item>* new_right) 
{ 
    right_field = new_right; 
}
        
// print
//
// Library facilities used: iomanip, iostream, stdlib
//
template <typename Item, typename SizeType>
void print(const binary_tree_node<Item>* node_ptr, SizeType depth)
{
    if (node_ptr != NULL)
    {
        print(node_ptr->get_right( ), depth+1);

        // Indent 4*depth spaces.
        std::cout << std::setw(4*depth) << ""; 
        std::cout << node_ptr->get_data( ) << std::endl;
        print(node_ptr->get_left( ),  depth+1);
    }
}    
        
// tree_clear
//
// Library facilities used: cstdlib
//
template <typename Item>
void tree_clear(binary_tree_node<Item>*& root_ptr)
{
    if (root_ptr != NULL)
    {
        tree_clear( root_ptr->get_left( ) );
        tree_clear( root_ptr->get_right( ) );
        delete root_ptr;
        root_ptr = NULL;
    }
}

// tree_copy
//
// Library facilities used: cstdlib
//
template <typename Item>
binary_tree_node<Item>* tree_copy(
    const binary_tree_node<Item>* root_ptr)
{
    binary_tree_node<Item> *l_ptr;
    binary_tree_node<Item> *r_ptr;

    if (root_ptr == NULL)
        return NULL;
    else
    {
        l_ptr = tree_copy( root_ptr->get_left( ) );
        r_ptr = tree_copy( root_ptr->get_right( ) );
        return
            new binary_tree_node<Item>( 
                root_ptr->get_data( ), l_ptr, r_ptr);
    }
}

// tree_size
//
// Library facilities used: cstdlib
//
template <typename Item>
size_t tree_size(const binary_tree_node<Item>* node_ptr)
{
    if (node_ptr == NULL)
        return 0;
    else 
        return 1 + tree_size(node_ptr->get_left( )) + 
                   tree_size(node_ptr->get_right( ));
}