tree.h

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

//
// this method removes the current tree node form the tree structure
//
template<class TObject>
boolean Tree<TObject>::remove() {

  // make sure the current tree node is valid
  //
  TreeNode<TObject>* this_node = (TreeNode<TObject>*)this->getCurr();  
  if (this_node == (TreeNode<TObject>*)NULL) {
    return Error::handle(name(), L"remove", Error::ARG, __FILE__, __LINE__);
  }
  
  // unlink the right siblings that reference this node
  //
  TreeNode<TObject>* pnode = this_node->getParent();  
  if (pnode != (TreeNode<TObject>*)NULL) {
    TreeNode<TObject>* tnode = pnode->getLeftChild();
    while (tnode != (TreeNode<TObject>*)NULL) {
      if (tnode->getRightSibling() == this_node) {
	tnode->setRightSibling(this_node->getRightSibling());
	break;
      }
      tnode = tnode->getRightSibling();
    }
  }
      
  // unlink the children that reference this node
  //
  TreeNode<TObject>* lnode = this_node->getLeftChild();
  if (lnode != (TreeNode<TObject>*)NULL) {
    lnode->setParent((TreeNode<TObject>*)NULL);

    TreeNode<TObject>* tnode = lnode->getRightSibling();
    while(tnode != (TreeNode<TObject>*)NULL) {
      tnode->setParent((TreeNode<TObject>*)NULL);
      tnode = tnode->getRightSibling();
    }
  }
      
  // clear the contents of the tree node
  //
  this_node->clear(Integral::FREE);

  // decrement the degree of the parent node
  //
  if (pnode != (TreeNode<TObject>*)NULL) {
    pnode->decrement();
  }
  
  // remove the object from the linked list
  //
  boolean status = false;
  TreeNode<TObject>* tree_node;
  status = DoubleLinkedList< TreeNode<TObject> >::remove(tree_node);
  delete tree_node;

  return status;  
}

// method: remove
//
// arguments:
//  TObject*& obj: (input) object to be removed
//
// return: a boolean value indicating status
//
// this method removes the input tree node form the tree structure
//
template<class TObject>
boolean Tree<TObject>::remove(TObject*& obj_a) {

  // make sure the current tree node is valid
  //
  TreeNode<TObject>* this_node = (TreeNode<TObject>*)this->getCurr();  
  if (this_node == (TreeNode<TObject>*)NULL) {
    return Error::handle(name(), L"remove", Error::ARG, __FILE__, __LINE__);
  }
  
  // make sure memory is allocated if we are SYSTEM-allocated
  //
  if ((alloc_d == SYSTEM) && (obj_a == (TObject*)NULL)) {
    return Error::handle(name(), L"remove", Error::ARG, __FILE__, __LINE__);
  }

  // when in SYSTEM mode make a copy of the object data
  //
  if (alloc_d == SYSTEM) {
    obj_a->assign(*this_node->getItem());
    delete this_node->getItem();
  }

  // when in USER mode assign the object pointer
  //
  else {
    obj_a = this_node->getItem();
  }

  // unlink the right siblings that reference this node
  //
  TreeNode<TObject>* pnode = this_node->getParent();  
  if (pnode != (TreeNode<TObject>*)NULL) {
    TreeNode<TObject>* tnode = pnode->getLeftChild();
    while (tnode != (TreeNode<TObject>*)NULL) {
      if (tnode->getRightSibling() == this_node) {
	tnode->setRightSibling(this_node->getRightSibling());
	break;
      }
      tnode = tnode->getRightSibling();      
    }
  }
      
  // unlink the children that reference this node
  //
  TreeNode<TObject>* lnode = this_node->getLeftChild();
  if (lnode != (TreeNode<TObject>*)NULL) {
    lnode->setParent((TreeNode<TObject>*)NULL);

    TreeNode<TObject>* tnode = lnode->getRightSibling();
    while(tnode != (TreeNode<TObject>*)NULL) {
      tnode->setParent((TreeNode<TObject>*)NULL);
      tnode = tnode->getRightSibling();
    }
  }

  // clear the contents of the tree node
  //
  this_node->clear();

  // decrement the degree of the parent node
  //
  if (pnode != (TreeNode<TObject>*)NULL) {
    pnode->decrement();
  }
  
  // remove the object from the linked list
  //
  boolean status = false;
  TreeNode<TObject>* tree_node;
  status = DoubleLinkedList< TreeNode<TObject> >::remove(tree_node);
  delete tree_node;

  return status;  
}

// method: contains
//
// arguments:
//  TObject* obj: (input) the object to be found
//
// return: a boolean value indicating status
//
// this method determines if the input object is in the list of vertices
//
template<class TObject>
boolean Tree<TObject>::contains(const TObject* obj_a) const {

  // check if the input object is NULL
  //
  if (obj_a == (TObject*)NULL) {
    return Error::handle(name(), L"contains", Error::ARG, __FILE__, __LINE__);
  }

  // save the current position
  //
  long old_pos = const_cast<Tree<TObject>* >(this)->getPosition();

  // temporary variables
  //
  boolean obj_found = false;
  boolean more_nodes = const_cast<Tree<TObject>* >(this)->gotoFirst();
  
  // search from the beginning for the item
  //
  while (!obj_found && more_nodes) {

    // get the current node
    //
    TreeNode<TObject>* this_node =
     (TreeNode<TObject>*) const_cast<Tree<TObject>* >(this)->getCurr();

    // get the object contained in the node
    //
    TObject* this_obj = this_node->getItem();
    
    // compare the objects for equality
    //
    obj_found = obj_a->eq(*this_obj);
    
    if (!obj_found) {
      more_nodes = const_cast<Tree<TObject>* >(this)->gotoNext();
    }
  }

  // restore the previous position
  //
  const_cast<Tree<TObject>* >(this)->gotoPosition(old_pos);
  
  // return whether or not the object was found
  //
  return obj_found;  
}

// method: contains
//
// arguments:
//  TreeNode<TObject>* node: (input) the node to be found
//
// return: a boolean value indicating status
//
// this method determines if the input node is in the list of
// vertices. note that we can't just call list contains since we only
// want to compare pointers, not values.
//
template<class TObject>
boolean
Tree<TObject>::contains(const TreeNode<TObject>* node_a) const {

  // check if the input object is NULL
  //
  if (node_a == (TreeNode<TObject>*)NULL) {
    return Error::handle(name(), L"contains", Error::NULL_ARG,
			 __FILE__, __LINE__);
  }

  // save the current position
  //
  long old_pos = const_cast<Tree<TObject>* >(this)->getPosition();

  // temporary variables
  //
  boolean node_found = false;
  boolean more_nodes = const_cast<Tree<TObject>* >(this)->gotoFirst();
  
  // search from the beginning for the item
  //
  while (!node_found && more_nodes) {

    // get the current node
    //
    TreeNode<TObject>* this_node =
     (TreeNode<TObject>*) const_cast<Tree<TObject>* >(this)->getCurr();

    // compare the pointers for equality
    //
    if (this_node == node_a) {
      node_found = true;
    }
    
    if (!node_found) {
      more_nodes = const_cast<Tree<TObject>* >(this)->gotoNext();
    }
  }

  // restore the previous state
  //
  const_cast<Tree<TObject>* >(this)->gotoPosition(old_pos);
  
  // return whether or not the object was found
  //
  return node_found;
}

// method: find
//
// arguments:
//  TObject* obj: (input) the object to be found
//
// return: a boolean value indicating status
//
// this method determines if the input object is in the list of vertices
// and moves the list current pointer to the first occurance of the object
//
template<class TObject>
boolean Tree<TObject>::find(const TObject* obj_a) {

  // check if the input object is NULL
  //
  if (obj_a == (TObject*)NULL) {
    return Error::handle(name(), L"find", Error::NULL_ARG, __FILE__, __LINE__);
  }

  // save the current position
  //
  this->setMark();

  // temporary variables
  //
  boolean obj_found = false;
  boolean more_nodes = this->gotoFirst();
  
  // search from the beginning for the item
  //
  while (!obj_found && more_nodes) {

    // get the current node
    //
    TreeNode<TObject>* this_node = (TreeNode<TObject>*)this->getCurr();

    // get the object contained in the node
    //
    TObject* this_obj = this_node->getItem();
    
    // compare the objects for equality
    //
    obj_found = obj_a->eq(*this_obj);
    
    if (!obj_found) {
      more_nodes = this->gotoNext();
    }
  }

  if (!obj_found) {
    this->gotoMark();
  }
  
  // return whether or not the object was found
  //
  return obj_found;
}

// method: find
//
// arguments:
//  TreeNode<TObject>* node: (input) the node to be found
//
// return: a boolean value indicating status
//
// this method determines if the input node is in the list of
// vertices. if found the node list is left pointing to the
// node. note that we can't just call list contains since we only
// want to compare pointers, not values.
//
template<class TObject>
boolean Tree<TObject>::find(const TreeNode<TObject>* node_a) {

  // check if the input object is NULL
  //
  if (node_a == (TreeNode<TObject>*)NULL) {
    return Error::handle(name(), L"find", Error::NULL_ARG,
			 __FILE__, __LINE__);
  }

  // save the current position
  //
  long old_pos = const_cast<Tree<TObject>* >(this)->getPosition();

  // temporary variables
  //
  boolean node_found = false;
  boolean more_nodes = const_cast<Tree<TObject>* >(this)->gotoFirst();
  
  // search from the beginning for the item
  //
  while (!node_found && more_nodes) {

    // get the current node
    //
    TreeNode<TObject>* this_node =
      (TreeNode<TObject>*)const_cast<Tree<TObject>* >(this)->getCurr();

    // compare the pointers for equality
    //
    if (this_node == node_a) {
      node_found = true;
    }
    
    if (!node_found) {
      more_nodes = const_cast<Tree<TObject>* >(this)->gotoNext();
    }
  }

  // restore the previous state if the node was not found
  //
  if (!node_found) {
    const_cast<Tree<TObject>* >(this)->gotoPosition(old_pos);
  }
  
  // return whether or not the object was found
  //
  return node_found;
}

// method: set
//
// arguments:
//  Vector<Ulong>& root_adj: (input) adjecent nodes to root node
//  SingleLinkedList<TObject>& node_obj: (input) tree node items
//  SingleLinkedList<Vector<Ulong> >& node_adj: (input) adjacent nodes to tree nodes
//  
// return: a boolean value indicating status
//
// this method uses the extracted structure of the tree in the two
// lists as a blue print to reconstruct the tree structure
//
template<class TObject>
boolean Tree<TObject>::set(Vector<Ulong>& root_adj_a,
			   SingleLinkedList<TObject>& node_obj_a,
			   SingleLinkedList<Vector<Ulong> >& node_adj_a) {

  // declare local variables
  //
  Ulong index = 0;
  Vector<Ulong>* indices = (Vector<Ulong>*)NULL;
  TreeNode<TObject>* node = (TreeNode<TObject>*)NULL;
  HashTable<Ulong, TreeNode<TObject> > khash(DstrBase::USER);
  SingleLinkedList<TreeNode<TObject> > nodes(DstrBase::USER);

  // clear the contents of the tree structure
  //
  clear();

  // loop over each element in the item list
  //    
  for (boolean more = node_obj_a.gotoFirst(); more; more = node_obj_a.gotoNext()) {
    node = insert(node_obj_a.getCurr());
    khash.insert(index, node);
    nodes.insert(node);
    index++;
  }

  // connect the root node to its adjacent nodes
  //
  for (long i=0; i < root_adj_a.length(); i++) {
    insertChild(this->getRoot(), khash.get(root_adj_a(i)));
  }

  // connect the remaining tree nodes to its adjacent nodes
  //
  nodes.gotoFirst();
  for (boolean more = node_adj_a.gotoFirst(); more;
       more = node_adj_a.gotoNext()) {
    indices = node_adj_a.getCurr();
    for (long i=0; i < indices->length(); i++) {
      insertChild(nodes.getCurr(), khash.get((*indices)(i)));
    }
    nodes.gotoNext();    
  }
    
  // exit gracefully
  //
  return true;
}

// method: get
//
// arguments:
//  Vector<Ulong>& root_adj: (output) adjecent nodes to root node
//  SingleLinkedList<TObject>& node_obj: (output) tree node items
//  SingleLinkedList<Vector<Ulong> >& node_adj: (output) adjacent nodes to tree nodes
//  
// return: a boolean value indicating status
//
// 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
//
template<class TObject>
boolean Tree<TObject>::get(Vector<Ulong>& root_adj_a,
			   SingleLinkedList<TObject>& node_obj_a,
			   SingleLinkedList<Vector<Ulong> >& node_adj_a) {

  // declare local variables
  //
  Ulong index = 0;
  Vector<Ulong> indices;
  HashKey<TreeNode<TObject> > hashkey;
  HashTable<HashKey<TreeNode<TObject> >, Ulong> khash;
  TreeNode<TObject>* this_node = (TreeNode<TObject>*)NULL;

  // save the current state of the list
  //
  this->setMark();

  // make sure that the list of node object are in USER mode
  //
  node_obj_a.setAllocationMode(DstrBase::USER);
   
  // add the tree node items to the list
  //
  for (boolean more = this->gotoFirst(); more; more = this->gotoNext()) {

    // add the tree node to the list
    //
    node_obj_a.insert(this->getCurr()->getItem());

    // associate a unique number with the tree node
    //
    hashkey.assign(this->getCurr());
    khash.insert(hashkey, &index);

    // increment the index