tree.h

这是一个从音频信号里提取特征参量的程序

// 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
//