// file: $isip/class/dstr/Tree/Tree.h// version: $Id: Tree.h,v 1.4 2002/12/22 20:46:07 parihar Exp $//// make sure definitions are made only once//#ifndef ISIP_TREE#define ISIP_TREE// isip include files//#ifndef ISIP_DSTR_BASE#include <DstrBase.h>#endif#ifndef ISIP_SINGLE_LINKED_LIST#include <SingleLinkedList.h>#endif#ifndef ISIP_HASH_TABLE#include <HashTable.h>#endif#ifndef ISIP_STACK#include <Stack.h>#endif#ifndef ISIP_QUEUE#include <Queue.h>#endif#ifndef ISIP_HASH_KEY#include <HashKey.h>#endif#ifndef ISIP_TREE_NODE#include <TreeNode.h>#endif#ifndef ISIP_VECTOR#include <Vector.h>#endif#ifndef ISIP_CONSOLE#include <Console.h>#endif// forward class definitions//template<class TObject> class TreeNode;template<class TObject> class TreeDiagnose;// Tree: this class implements a Tree data structure using the left child// right sibling representation.//template<class TObject>class Tree : private DoubleLinkedList< TreeNode<TObject> > {      //---------------------------------------------------------------------------  //  // public constants  //  //---------------------------------------------------------------------------public:    // define the class name  //  static const String CLASS_NAME;  //----------------------------------------  //  // i/o related constants  //  //----------------------------------------      static const String DEF_PARAM;  static const String PARAM_ROOT_ITEM;  static const String PARAM_ROOT_ADJACENT;  static const String PARAM_NODE_ITEMS;  static const String PARAM_NODE_ADJACENT;    //----------------------------------------  //  // default values and arguments  //  //----------------------------------------    // default values  //    // default arguments to methods  //    //----------------------------------------  //  // error codes  //  //----------------------------------------      //---------------------------------------------------------------------------  //  // protected data  //  //---------------------------------------------------------------------------protected:  // the allocation mode  //  DstrBase::ALLOCATION alloc_d;    // define the root of the tree  //  TreeNode<TObject> root_d;  // debugging parameters  //  static Integral::DEBUG debug_level_d;  // define the memory manager  //    static MemoryManager mgr_d;    //---------------------------------------------------------------------------  //  // required public methods  //  //---------------------------------------------------------------------------public:    // static methods:  //  the diagnose method is moved outside the class header file and  //  defined in the TreeDiagnose.h in order to avoid issues  //  with preprocessing of the diagnose code.  //  static const String& name();    // method: setDebug  //  static boolean setDebug(Integral::DEBUG debug_level) {    debug_level_d = debug_level;    return true;  }  // other debug methods  //  boolean debug(const unichar* msg) const;       // destructor/constructor(s)  //  ~Tree();  Tree(DstrBase::ALLOCATION alloc = DstrBase::DEF_ALLOCATION);  Tree(const Tree<TObject>& copy_Tree);  // assign method  //  boolean assign(const Tree<TObject>& copy_stack);    // method: operator=  //  Tree<TObject>& operator=(const Tree<TObject>& arg) {    assign(arg);    return *this;  }  // equality method  //  boolean eq(const Tree<TObject>& arg) const;    // sofSize method  //  long sofSize() const;  // method: read  //  boolean read(Sof& sof, long tag) {    return read(sof, tag, name());  }    // method: write  //  boolean write(Sof& sof, long tag) const {    return write(sof, tag, name());  }    // other read methods  //  boolean read(Sof& sof, long tag, const String& name);  boolean readData(Sof& sof, const String& pname = DEF_PARAM,		   long size = SofParser::FULL_OBJECT, boolean param = true,                   boolean nested = false);    // other write methods  //  boolean write(Sof& sof, long tag, const String& name) const;  boolean writeData(Sof& sof, const String& pname = DEF_PARAM) const;  // method: new  //  static void* operator new(size_t size) {    return mgr_d.get();  }  // method: new[]  //  static void* operator new[](size_t size) {    return mgr_d.getBlock(size);  }  // method: delete  //  static void operator delete(void* ptr) {    mgr_d.release(ptr);  }  // method: delete[]  //  static void operator delete[](void* ptr) {    mgr_d.releaseBlock(ptr);  }  // method: setGrowSize  //  static boolean setGrowSize(long grow_size) {    return mgr_d.setGrow(grow_size);  }      // clear method  //  boolean clear(Integral::CMODE cmode = Integral::DEF_CMODE);    //---------------------------------------------------------------------------  //  // class-specific public methods:  //  tree manipulation methods  //  //---------------------------------------------------------------------------  // method: getRoot  //  TreeNode<TObject>* getRoot() const {    return (TreeNode<TObject>*)&root_d;  }  // method to set the root item  //  boolean setRootItem(TObject* obj);    // insert methods  //  TreeNode<TObject>* insert(TObject* obj);  boolean insertChild(TreeNode<TObject>* pnode, TreeNode<TObject>* cnode);  // remove methods  //    boolean remove();      boolean remove(TObject*& obj);  // item containment methods  //  boolean find(const TObject* obj);  boolean find(const TreeNode<TObject>* node);  boolean contains(const TObject* obj) const;  boolean contains(const TreeNode<TObject>* node) const;  // this method extracts the structure of the tree and places them  // in two lists. the first list contains the tree node and the second  // list contains its corresponding children  //  boolean get(Vector<Ulong>& root_adj,	      SingleLinkedList<TObject>& node_obj,	      SingleLinkedList<Vector<Ulong> >& node_adj);	        // this method uses the extracted structure of the tree in the two  // lists as a blue print to reconstruct the tree structure  //  boolean set(Vector<Ulong>& root_adj,	      SingleLinkedList<TObject>& node_obj,	      SingleLinkedList<Vector<Ulong> >& node_adj);    //---------------------------------------------------------------------------  //  // class-specific public methods:  //  tree allocation mode methods  //  //---------------------------------------------------------------------------    // method: getAllocationMode  //  DstrBase::ALLOCATION getAllocationMode() const {    return alloc_d;  }  // method: setAllocationMode  //  boolean setAllocationMode(DstrBase::ALLOCATION alloc) {    alloc_d = alloc;    return true;  }      //---------------------------------------------------------------------------  //  // class-specific public methods:  //  tree traversal methods  //  //---------------------------------------------------------------------------  // post-order traversal visits the left child first, then the right child,  // and finally visits the parent node  //  boolean postorderTreeTraversal(SingleLinkedList<TreeNode<TObject> >& arg);  // pre-order traversal visits parent node first, then the left child,  // and finally visits the right child    //  boolean preorderTreeTraversal(SingleLinkedList<TreeNode<TObject> >& arg);  // in-order traversal visits left child first, then the parent node,  // and finally visits the right child    //     boolean inorderTreeTraversal(SingleLinkedList<TreeNode<TObject> >& arg);  // level-order traversal visits all nodes at level one (namely the root)  // before visiting all nodes at level two and so on...  //  boolean levelorderTreeTraversal(SingleLinkedList<TreeNode<TObject> >& arg);  //---------------------------------------------------------------------------  //  // class-specific public methods:  //  double linked list methods  //  //---------------------------------------------------------------------------    // the Tree class derives the DoubleLinkedList bases class which  // is used as the primary underlying container class. to prevent the  // user from circumventing the Tree's interface and interacting  // directly with the DoubleLinkedList we use private inheritance.  // we define here the methods of the DoubleLinkedList interface that  // the user is permitted access to.  //  using DoubleLinkedList< TreeNode<TObject> >::length;  using DoubleLinkedList< TreeNode<TObject> >::gotoFirst;  using DoubleLinkedList< TreeNode<TObject> >::gotoNext;  using DoubleLinkedList< TreeNode<TObject> >::gotoPrev;  using DoubleLinkedList< TreeNode<TObject> >::getCurr;  using DoubleLinkedList< TreeNode<TObject> >::getFirst;  using DoubleLinkedList< TreeNode<TObject> >::getLast;  using DoubleLinkedList< TreeNode<TObject> >::gotoMark;  using DoubleLinkedList< TreeNode<TObject> >::setMark;  using DoubleLinkedList< TreeNode<TObject> >::gotoPosition;  using DoubleLinkedList< TreeNode<TObject> >::getPosition;  using DoubleLinkedList< TreeNode<TObject> >::isLast;  using DoubleLinkedList< TreeNode<TObject> >::isEmpty;  using DoubleLinkedList< TreeNode<TObject> >::isMarkedElement;    //---------------------------------------------------------------------------  //  // private methods  //  //---------------------------------------------------------------------------private:  // tree traversal iterators  //  boolean postorderTreeIterator(Stack<TreeNode<TObject> >& stack);  boolean preorderTreeIterator(Stack<TreeNode<TObject> >& stack);  boolean inorderTreeIterator(TreeNode<TObject>* parent,			      Queue<TreeNode<TObject> >& queue);  boolean levelorderTreeIterator(SingleLinkedList<TreeNode<TObject> >& arg,				 Queue<TreeNode<TObject> >& queue);        // declare friend classes  //    template <class TObject_diagnose>   friend class TreeDiagnose;  };//-----------------------------------------------------------------------------//// we define non-integral constants at the end of class definition for// templates (for non-templates these are defined in the default constructor)//      //-----------------------------------------------------------------------------// constants: required constants such as the class name//template <class TObject>const String Tree<TObject>::CLASS_NAME(L"Tree");template <class TObject>const String Tree<TObject>::DEF_PARAM(L"values");template <class TObject>const String Tree<TObject>::PARAM_ROOT_ITEM(L"root_item");template <class TObject>const String Tree<TObject>::PARAM_ROOT_ADJACENT(L"root_adjacent");template <class TObject>const String Tree<TObject>::PARAM_NODE_ITEMS(L"node_items");template <class TObject>const String Tree<TObject>::PARAM_NODE_ADJACENT(L"node_adjacent");// static instantiations: debug level//template <class TObject>Integral::DEBUG Tree<TObject>::debug_level_d = Integral::NONE;// static instantiations: the memory manager//template <class TObject>MemoryManager Tree<TObject>::mgr_d(sizeof(Tree<TObject>), CLASS_NAME);// below are all the methods for the Tree template class//      // ---------------------------------------------------------------------//// required static methods////----------------------------------------------------------------------// method: name//// arguments: none//// return: a static String& containing the class name//// this method returns the class name//template<class TObject>const String& Tree<TObject>::name() {    // create the static name string for this class and return it  //  static String cname(CLASS_NAME);  cname.clear();  cname.concat(CLASS_NAME);  cname.concat(L"<");  cname.concat(TObject::name());  cname.concat(L">");    // return the name  //  return cname;}// ---------------------------------------------------------------------//// required debug methods////----------------------------------------------------------------------// method: debug//// arguments://  unichar* msg: (input) information message//// return: a boolean value indicating status//// this method dumps the contents of an object to the console// template<class TObject>boolean Tree<TObject>::debug(const unichar* msg_a) const {  // dump the root node  //  root_d.debug(L"root_d");  // dump the remaining nodes  //  DoubleLinkedList< TreeNode<TObject> >::debug(L"nodes");      // exit gracefully  //   return true;}//------------------------------------------------------------------------//// required destructor/constructor(s)////-----------------------------------------------------------------------// method: destructor//// arguments: none//// return: none//