tree.h

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

template<class TObject>
Tree<TObject>::~Tree() {

  // free memory
  //
  clear();
}

// method: default constructor
//
// arguments:
//  DstrBase::ALLOCATION alloc: (input) the flag to specify whether or not the
//                              item memory is allocated by the node itself
//
// return: none
//
template<class TObject>
Tree<TObject>::Tree(DstrBase::ALLOCATION alloc_a) {

  // set the allocation flag
  //
  alloc_d = alloc_a;

  // set the allocation mode for the underlying container
  //
  DoubleLinkedList< TreeNode<TObject> >::setAllocationMode(DstrBase::USER);
}

// method: copy constructor
//
// arguments:
//  const Tree<TObject>& copy_tree: (input) the Tree to copy
//
// return: none
//
template<class TObject>
Tree<TObject>::Tree(const Tree<TObject>& copy_tree_a) {

  // set the allocation mode for the underlying container
  //
  DoubleLinkedList< TreeNode<TObject> >::setAllocationMode(DstrBase::USER);
  
  // call the assign method to copy the Tree
  //
  assign(copy_tree_a);
}

//------------------------------------------------------------------------
//
// required assign methods
//
//-------------------------------------------------------------------------

// method: assign
//
// arguments:
//  const Tree<TObject>& copy_tree: (input) the Tree to copy
//
// return: a boolean value indicating status
//
// this method copies the contents of the input to this Tree
//
template<class TObject>
boolean Tree<TObject>::assign(const Tree<TObject>& copy_tree_a) {

  // declare local variables
  //
  Vector<Ulong> root_adj;
  SingleLinkedList<TObject> node_obj;
  SingleLinkedList<Vector<Ulong> > node_adj;

  // set the root item
  //
  root_d.assign(copy_tree_a.root_d);
  
  // get the structure of the input tree
  //
  const_cast<Tree<TObject> &>(copy_tree_a).get(root_adj, node_obj, node_adj);

  // set the structure of the current tree
  //
  this->set(root_adj, node_obj, node_adj);
  
  // exit gracefully
  //
  return true;
}

//------------------------------------------------------------------------
//
// required equality methods
//
//------------------------------------------------------------------------

// method: eq
//
// arguments:
//  const Tree<TObject>& compare_tree: (input) the Tree to compare
//
// return: a boolean value indicating status
//
// this method compares two Trees for equivalence. two Trees are equivalent
// if all corresponding items are equivalent
//
template<class TObject>
boolean Tree<TObject>::eq(const Tree<TObject>& compare_tree_a) const {

  // declare local variables
  //
  Vector<Ulong> root_adj_00;
  SingleLinkedList<TObject> node_obj_00;
  SingleLinkedList<Vector<Ulong> > node_adj_00;

  Vector<Ulong> root_adj_01;
  SingleLinkedList<TObject> node_obj_01;
  SingleLinkedList<Vector<Ulong> > node_adj_01;  
  
  // compare the root item
  //
  if (!root_d.eq(compare_tree_a.root_d)) {
    return false;
  }

  // extract the structure of this tree
  //
  const_cast<Tree<TObject> *>(this)->get(root_adj_00, node_obj_00, node_adj_00);
  
  // extract the structure of the input tree
  //  
  const_cast<Tree<TObject> &>(compare_tree_a).get(root_adj_01, node_obj_01, node_adj_01);

  // test the structure for equavalence
  //
  if (!root_adj_00.eq(root_adj_01)) {
    return false;
  }

  if (!node_obj_00.eq(node_obj_01)) {
    return false;
  }

  if (!node_adj_00.eq(node_adj_01)) {
    return false;
  }
  
  // if we have reached this far then they must be equal
  //
  return true;
}

//-------------------------------------------------------------------------
//
// required memory management methods
//
//-------------------------------------------------------------------------

// method: clear
//
// arguments: 
// Integral::CMODE cmode_a: (input) clear mode
//  
// return: a boolean value indicating status
//
// this method clears the contents of the list by the setting of cmode_a
//
template<class TObject>
boolean Tree<TObject>::clear(Integral::CMODE cmode_a) {

  // for RETAIN mode, call clear on every object but do not change
  // topology. for FREE mode we also need to call clear(FREE) on all
  // TObjects, but we will also delete the topology below.
  //
  if ((cmode_a == Integral::RETAIN) || (cmode_a == Integral::FREE)) {
    for (boolean more = gotoFirst(); more; more = gotoNext()) {
      ((TObject*)(getCurr()->getItem()))->clear(cmode_a);
    }

    if (root_d.getItem() != (TObject*)NULL) {
      root_d.getItem()->clear(cmode_a);
    }
  }

  // for RETAIN mode we are done, make no changes to topology
  //
  if (cmode_a == Integral::RETAIN) {
    return true;
  }

  // when the graph is in SYSTEM-allocation mode or the clear mode is
  // free we need to delete the TObject
  //
  for (boolean more = gotoFirst(); more; more = gotoNext()) {
    if ((alloc_d == SYSTEM) || (cmode_a == Integral::FREE)) {
      
      // delete the TObject
      //
      delete getCurr()->getItem();
    }
    
    // set the pointer to null
    //
    ((TreeNode<TObject>*)getCurr())->setItem((TObject*)NULL);
  }

  if ((alloc_d == SYSTEM) || (cmode_a == Integral::FREE)) {

    // delete the TObject
    //
    if (root_d.getItem() != (TObject*)NULL) {    
      delete root_d.getItem();
    }
  }

  // set the pointer to null
  //
  root_d.setItem((TObject*)NULL);
    
  // clear the tree nodes list
  //
  DoubleLinkedList< TreeNode<TObject> >::setAllocationMode(DstrBase::SYSTEM);
  DoubleLinkedList< TreeNode<TObject> >::clear(Integral::RESET);
  DoubleLinkedList< TreeNode<TObject> >::setAllocationMode(DstrBase::USER);
  
  // exit gracefully
  //
  return true;
}

//------------------------------------------------------------------------
//
// class-specific public methods:
//  i/o methods
//
//------------------------------------------------------------------------

// method: read
//
// arguments:
//  Sof& sof: (input) sof file object
//  long tag: (input) sof object instance tag
//  const String& name: (input) sof object instance name
//
// return: a boolean value indicating status
//
// this method has the object read itself from an Sof file according
// to the specified name and tag
//
template <class TObject>
boolean Tree<TObject>::read(Sof& sof_a, long tag_a, const String& name_a) {

  // exit gracefully
  //
  return true;
}

// method: readData
//
// arguments:
//  Sof& sof: (input) sof file object
//  const String& pname: (input) parameter name
//  long size: (input) size in bytes of object (or FULL_OBJECT)
//  boolean param: (input) is the parameter name in the file?
//  boolean nested: (input) are we nested?
//
// return: a boolean value indicating status
//
// this method has the object read itself from an Sof file. it assumes
// that the Sof file is already positioned correctly
//
template <class TObject>
boolean Tree<TObject>::readData(Sof& sof_a, const String& pname_a,
			      long size_a, boolean param_a, boolean nested_a) {

  // exit gracefully
  //
  return true;
}

// method: sofSize
//
// arguments: none
//
// return: size of object
//
// this method returns the size of the object in the Sof file and is
// used for binary write
//
template <class TObject>
long Tree<TObject>::sofSize() const {

  // return the size
  //
  return bytes;
}

// method: write
//
// arguments:
//  Sof& sof: (input) sof file object
//  long tag: (input) sof object instance tag
//  const String& name: (input) sof object instance name
//
// return: a boolean value indicating status
//
// this method has the object write itself to an Sof file
//
template <class TObject>
boolean Tree<TObject>::write(Sof& sof_a, long tag_a,
			     const String& name_a) const {

  // exit gracefully
  //
  return true;
}

//------------------------------------------------------------------------
//
// class-specific public methods:
//  tree manipulation methods
//
//------------------------------------------------------------------------

// method: setRootItem
//
// arguments:
//  TObject* obj: (input) object to be inserted in the tree
//
// return: a boolean value indicating status
//
// this method inserts the input object as the root item
//
template<class TObject>
boolean Tree<TObject>::setRootItem(TObject* obj_a) {

  // perform error checking
  //
  if (obj_a == (TObject*)NULL) {
    Error::handle(name(), L"insert", Error::ARG, __FILE__, __LINE__);
    return (TreeNode<TObject>*)NULL;
  }
  
  // declare local variables and allocate a new TreeNode object
  //
  TObject* new_obj = (TObject*)NULL;

  // when the tree is in SYSTEM mode make a copy of the object
  //
  if (alloc_d == SYSTEM) {
    new_obj = new TObject(*obj_a);
  }

  // assign the object pointer when in USER mode
  //
  else {
    new_obj = obj_a;
  }

  // set the object on the tree node
  //
  root_d.setItem(new_obj);

  // exit gracefully
  //
  return true;
}
  
// method: insert
//
// arguments:
//  TObject* obj: (input) object to be inserted in the tree
//
// return: a boolean value indicating status
//
// this method inserts the input object into the tree structure
//
template<class TObject>
TreeNode<TObject>* Tree<TObject>::insert(TObject* obj_a) {

  // perform error checking
  //
  if (obj_a == (TObject*)NULL) {
    Error::handle(name(), L"insert", Error::ARG, __FILE__, __LINE__);
    return (TreeNode<TObject>*)NULL;
  }
  
  // declare local variables and allocate a new TreeNode object
  //
  TObject* new_obj = (TObject*)NULL;
  TreeNode<TObject>* node = new TreeNode<TObject>();

  // when the tree is in SYSTEM mode make a copy of the object
  //
  if (alloc_d == SYSTEM) {
    new_obj = new TObject(*obj_a);
  }

  // assign the object pointer when in USER mode
  //
  else {
    new_obj = obj_a;
  }

  // set the object on the tree node
  //
  node->setItem(new_obj);

  // add vertex on the graph
  //
  DoubleLinkedList< TreeNode<TObject> >::insert(node);

  // exit gracefully
  //
  return node;  
}

// method: insertChild
//
// arguments:
//  TreeNode<TObject>* pnone: (input) parent tree node
//  TreeNode<TObject>* cnone: (input) child tree node
//
// return: a boolean value indicating status
//
// this method sets the child node as one of the children of the parent node
//
template<class TObject>
boolean Tree<TObject>::insertChild(TreeNode<TObject>* pnode_a,
				    TreeNode<TObject>* cnode_a) {

  // declare local variables
  //
  TreeNode<TObject>* node = (TreeNode<TObject>*)NULL;
  
  // verify that the input is valid
  //
  if ((pnode_a == (TreeNode<TObject>*)NULL) ||
      (cnode_a == (TreeNode<TObject>*)NULL)) {
    return Error::handle(name(), L"insertChild", Error::ARG, __FILE__, __LINE__);
  }

  // child cannot have multiple children
  //
  if (cnode_a->getParent() != (TreeNode<TObject>*)NULL) {
    return Error::handle(name(), L"insertChild", Error::ARG, __FILE__, __LINE__);
  }
  
  // if the left child is null set the child node as the left child
  //
  if (pnode_a->getLeftChild() == (TreeNode<TObject>*)NULL) {
    pnode_a->setLeftChild(cnode_a);
  }

  // else set the child node as a right sibling
  //  
  else {

    // if the right sibling is null set the child node as the right sibling
    //
    if ((node = pnode_a->getLeftChild()->getRightSibling())
	== (TreeNode<TObject>*)NULL) {
      pnode_a->getLeftChild()->setRightSibling(cnode_a);
    }

    // insert the child node as one of the right siblings of the left child
    //    
    else {

      while (node->getRightSibling() != (TreeNode<TObject>*)NULL) {
	node = node->getRightSibling();
      }
      node->setRightSibling(cnode_a);
    }
  }

  // set the parent of the child node
  //
  cnode_a->setParent(pnode_a);
  
  // increment the degree of the parent node
  //  
  pnode_a->increment();
  
  // exit gracefully
  //
  return true;
}

// method: remove
//
// arguments: none
//
// return: a boolean value indicating status