// Fig. 15.16: tree.h
// Definition of template class Tree

#ifndef TREE_H
#define TREE_H

#include <iostream>
using std::cout;
using std::endl;
using std::ostream;
#include <iomanip>

#include <cassert>

#include <fstream>
using std::ofstream;
using std::ifstream;
using std::ios;

#include "Treenode.h"

template< class NODETYPE >
class Tree {
public:
   Tree();
   void insertNode( const NODETYPE & );
   void preOrderTraversal() const;
   void inOrderTraversal() const;
   void postOrderTraversal() const;
   int gettreeElementCount();
private:
   TreeNode< NODETYPE > *rootPtr;
   int treeElementCount;

   // utility functions
   void insertNodeHelper( 
           TreeNode< NODETYPE > **, const NODETYPE & );
   void preOrderHelper( TreeNode< NODETYPE > * ) const;
   void inOrderHelper( TreeNode< NODETYPE > * ) const;
   void postOrderHelper( TreeNode< NODETYPE > * ) const;
};

template< class NODETYPE >
Tree< NODETYPE >::Tree() { rootPtr = 0; treeElementCount=0; }

template< class NODETYPE >
void Tree< NODETYPE >::insertNode( const NODETYPE &value )
   { insertNodeHelper( &rootPtr, value ); }

// This function receives a pointer to a pointer so the
// pointer can be modified.
template< class NODETYPE >
void Tree< NODETYPE >::insertNodeHelper( 
        TreeNode< NODETYPE > **ptr, const NODETYPE &value )
{
   if ( *ptr == 0 ) {                   // tree is empty
      *ptr = new TreeNode< NODETYPE >( value );
      (*ptr)->frequency++;
      ++treeElementCount;
      assert( *ptr != 0 );
   }
   else                              // tree is not empty
      if ( value < ( *ptr )->data )
         insertNodeHelper( &( ( *ptr )->leftPtr ), value );
      else
         if ( value > ( *ptr )->data )
            insertNodeHelper( &( ( *ptr )->rightPtr ), value );
         else
            (*ptr)->frequency++;
}

template< class NODETYPE > 
void Tree< NODETYPE >::preOrderTraversal() const
   { preOrderHelper( rootPtr ); }

template< class NODETYPE >
void Tree< NODETYPE >::preOrderHelper( 
                          TreeNode< NODETYPE > *ptr ) const
{
   if ( ptr != 0 ) {
      cout << ptr->data << ' ';
      preOrderHelper( ptr->leftPtr );
      preOrderHelper( ptr->rightPtr );
   }
}

template< class NODETYPE >
void Tree< NODETYPE >::inOrderTraversal() const
   { inOrderHelper( rootPtr ); }

template< class NODETYPE >
void Tree< NODETYPE >::inOrderHelper( 
                          TreeNode< NODETYPE > *ptr ) const
{
	ofstream outFile("output.txt",ios::app);
	if( !outFile ) {
       cerr << "Output-Datei konnte nicht geoeffnet werden." << endl;
       exit( 1 );
   }
   if ( ptr != 0 ) {
      inOrderHelper( ptr->leftPtr );
      outFile << std::setw(30) << std::left << std::setfill('.') << ptr->data  
        << ptr->frequency << endl;
      inOrderHelper( ptr->rightPtr );
   }
   outFile.close();
}

template< class NODETYPE >
void Tree< NODETYPE >::postOrderTraversal() const
   { postOrderHelper( rootPtr ); }

template< class NODETYPE >
void Tree< NODETYPE >::postOrderHelper( 
                          TreeNode< NODETYPE > *ptr ) const
{
   if ( ptr != 0 ) {
      postOrderHelper( ptr->leftPtr );
      postOrderHelper( ptr->rightPtr );
      cout << ptr->data << ' ';
   }
}

template <class NODETYPE>
int Tree<NODETYPE>::gettreeElementCount()
{
	return treeElementCount;
}

#endif