bigraph.h

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

  // methods for topological sort:
  //  topological sort needs some customized DFS routines
  //
  boolean dfsVisitTS(DoubleLinkedList<TObject>& output,
		     BiGraphVertex<TObject>& vertex);
};

//-----------------------------------------------------------------------------
//
// 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 BiGraph<TObject>::CLASS_NAME(L"BiGraph");

// constants: i/o related constants
//
template <class TObject>
const String BiGraph<TObject>::DEF_PARAM(L"");

template <class TObject>
const String BiGraph<TObject>::PARAM_VERTICES(L"vertices");

template <class TObject>
const String BiGraph<TObject>::PARAM_ARCS(L"arcs");

template <class TObject>
const String BiGraph<TObject>::PARAM_WEIGHTED(L"weighted");

// constants: define non-integral constants in the default constructor
//
template <class TObject>
const String BiGraph<TObject>::START_NAME(L"S");

template <class TObject>
const String BiGraph<TObject>::TERM_NAME(L"T");

template <class TObject>
const TObject BiGraph<TObject>::START_OBJ;

template <class TObject>
const TObject BiGraph<TObject>::TERM_OBJ;

// static instantiations: debug level and memory manager
//
template <class TObject>
Integral::DEBUG BiGraph<TObject>::debug_level_d = Integral::NONE;

template <class TObject>
MemoryManager BiGraph<TObject>::mgr_d(sizeof(BiGraph<TObject>),
				    CLASS_NAME);

// below are all the methods for the BiGraph 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& BiGraph<TObject>::name() {

  // create the static name string for this class and return it
  //
  static String cname(CLASS_NAME);
  cname.clear(Integral::RESET);
  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:
//  const unichar* message: (input) information message
//
// return: a boolean value indicating status
//
// this method dumps the contents of an object to the console
// 
template<class TObject>
boolean BiGraph<TObject>::debug(const unichar* message_a) const {

  // build a debug string
  //
  String val;
  String output;
  output.debugStr(name(), message_a, L"");
  Console::put(output);
  
  Console::increaseIndention();

  // dump the this pointer
  //
  val.assign(this);
  output.debugStr(name(), message_a, L"this", val);
  Console::put(output);
  
  // dump allocation mode
  //
  output.debugStr(name(), message_a, L"alloc_d",
		  NameMap::ALLOCATION_MAP((long)alloc_d));
  Console::put(output);
  
  // dump is_weighted
  //
  val.assign(is_weighted_d);
  output.debugStr(name(), message_a, L"is_weighted_d", val);
  Console::put(output);
  
  // dump a pointer to the start vertex
  //
  val.assign(start_vertex_d);
  output.debugStr(name(), message_a, L"start_vertex_d", val);
  Console::put(output);

  // print the start vertex information
  //
  start_vertex_d->debug(L"start_vertex_d");  

  // call the parent debug method to debug the list of vertices itself
  //
  DoubleLinkedList< BiGraphVertex<TObject> >::debug(L"vertices");

  // dump a pointer to the terminal vertex
  //
  val.assign(term_vertex_d);
  output.debugStr(name(), message_a, L"term_vertex_d", val);
  Console::put(output);
  
  // print the terminal vertex information
  //
  term_vertex_d->debug(L"term_vertex_d");
  
  // that's it for sub-items, decrease indentation
  //
  Console::decreaseIndention();

  // exit gracefully
  // 
  return true;
}

//------------------------------------------------------------------------
//
// required destructor/constructor(s)
//
//-----------------------------------------------------------------------

// method: destructor
//
// arguments: none
//
// return: none
//
// this is the default destructor for the BiGraph class
//
template<class TObject>
BiGraph<TObject>::~BiGraph() {

  // clear the BiGraph
  //
  BiGraph<TObject>::clear(Integral::RESET);

  // delete the start and terminal vertices
  //
  delete start_vertex_d;
  start_vertex_d = (BiGraphVertex<TObject>*)NULL;
  delete term_vertex_d;
  term_vertex_d = (BiGraphVertex<TObject>*)NULL;

  // delete the color hash table
  //
  if (chash_d != (BiColorHash<TObject>*)NULL) {
    delete chash_d;
    chash_d = (BiColorHash<TObject>*)NULL;
  }
}

// method: default constructor
//
// arguments:
//  ALLOCATION alloc: (input) allocation mode for nodes
//
// return: none
//
// this is the default constructor for the BiGraph class
//
template<class TObject>
BiGraph<TObject>::BiGraph(DstrBase::ALLOCATION alloc_a) {

  // initialize internal data
  //
  is_weighted_d = DEF_IS_WEIGHTED;

  // set the allocation flag
  //
  alloc_d = alloc_a;
  
  // create and initialize the start and terminal vertices
  //
  start_vertex_d = new BiGraphVertex<TObject>();
  term_vertex_d = new BiGraphVertex<TObject>();

  start_vertex_d->setItem((TObject*)&START_OBJ);
  term_vertex_d->setItem((TObject*)&TERM_OBJ);

  start_vertex_d->setParentGraph(this);
  term_vertex_d->setParentGraph(this);

  // initialize the color hash table
  //
  chash_d = (BiColorHash<TObject>*)NULL;
  
  // set the allocation mode of the parent class
  //
  DoubleLinkedList< BiGraphVertex<TObject> >::setAllocationMode(USER);
}

// method: copy constructor
//
// arguments:
//  BiGraph<TObject>& arg: (input) the graph to copy
//
// return: none
//
// this is the copy constructor for the BiGraph class. note that having the
// same vertex appear in two different graphs is not allowed. thus, memory is
// created for copied vertices even if the graph is in user-allocating
// mode!
//
template<class TObject>
BiGraph<TObject>::BiGraph(const BiGraph<TObject>& copy_graph_a) {

  // create and initialize the start and terminal vertices
  //
  start_vertex_d = new BiGraphVertex<TObject>();
  term_vertex_d = new BiGraphVertex<TObject>();

  start_vertex_d->setItem((TObject*)&START_OBJ);
  term_vertex_d->setItem((TObject*)&TERM_OBJ);

  start_vertex_d->setParentGraph(this);
  term_vertex_d->setParentGraph(this);

  // initialize the color hash table
  //
  chash_d = (BiColorHash<TObject>*)NULL;
  
  // set the allocation mode of the parent class
  //
  DoubleLinkedList< BiGraphVertex<TObject> >::setAllocationMode(USER);

  // intialize the allocation flag to default
  //
  alloc_d = DEF_ALLOCATION;
  
  // call the copy assign method
  //
  assign(copy_graph_a);
}

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

// method: assign
//
// arguments:
//  BiGraph<TObject>& copy_graph: (input) the graph to copy
//
// return: a boolean value indicating status
//
// this is the assign method for the BiGraph class. we can't just copy
// the data over since the arcs make connections by pointer (and we
// can't share vertices across two graphs), hence we must manually
// insert every vertex and every arc. new vertices are created, but if
// the graph is in USER mode the tobject is not copied.
//
template<class TObject>
boolean BiGraph<TObject>::assign(const BiGraph<TObject>& arg_a) {

  // first cleanup the list
  //
  if (!clear(Integral::RESET)) {
    return Error::handle(name(), L"assign", Error::ARG, __FILE__, __LINE__);
  }
  
  // copy the weighting flag.
  //
  is_weighted_d = arg_a.is_weighted_d;

  // copy the allocation flag
  //
  alloc_d = arg_a.alloc_d;
  
  // save the state of the input graph
  //
  const_cast<BiGraph<TObject>& >(arg_a).setMark();
  
  // we need to build a cross-referencing scheme to make sure we cover
  // all arcs and all nodes. the (+2) is for the start and terminal
  // vertices since they are NOT included in the list
  //
  long num_vertices = arg_a.length() + 2;
  
  BiGraphVertex<TObject>* copy_sym_ptrs[num_vertices];
  BiGraphVertex<TObject>* this_sym_ptrs[num_vertices];

  // set the start and terminal vertices
  //
  copy_sym_ptrs[0] = arg_a.getStart();
  copy_sym_ptrs[num_vertices - 1] = arg_a.getTerm();
  
  // loop through the list of vertices, and number them
  //
  const_cast<BiGraph<TObject>& >(arg_a).gotoFirst();

  for (long i = 1; i < num_vertices - 1; i++) {

    // get the current node in the graph and assign it to the array
    //
    copy_sym_ptrs[i] = const_cast<BiGraphVertex<TObject>* >
      (arg_a.getCurr());

    // move to the next node in the graph
    //
    const_cast<BiGraph<TObject>& >(arg_a).gotoNext();
  }

  // before we assign the input graph we need to clear the current graph
  //
  this->clear(Integral::RESET);
  
  // set the start and terminal vertices
  //
  this_sym_ptrs[0] = getStart();
  this_sym_ptrs[num_vertices - 1] = getTerm();  

  for (long i = 1; i < num_vertices - 1; i++) {

    // create a new graph vertex
    //
    this_sym_ptrs[i] = this->insertVertex(copy_sym_ptrs[i]->getItem());
  }

  // now build the arclists for each node
  //
  for (long i = 0; i < num_vertices; i++) {

    // get the vertex in question
    //
    BiGraphVertex<TObject>* tmp_copy_vert = copy_sym_ptrs[i];

    // loop over the copy graph's arclist
    //
    boolean arcs_remain = tmp_copy_vert->gotoFirstChild();

    while (arcs_remain) {

      // setup temporary variables
      //
      long dest_index = -1;
      BiGraphArc<TObject>* tmp_arc = tmp_copy_vert->getCurrChild();
      BiGraphVertex<TObject>* dest_vertex = tmp_arc->getVertex();

      // find the destination vertex index
      //
      for (long j = 0; j < num_vertices; j++) {
	if (dest_vertex == copy_sym_ptrs[j]) {
	  dest_index = j;
	  break;
	}
      }

      if (dest_index == -1) {
	return Error::handle(name(), L"assign", Error::ARG,
			     __FILE__, __LINE__);
      }

      // link the vertices in the new graph
      //
      insertArc(this_sym_ptrs[i], this_sym_ptrs[dest_index],
		tmp_arc->getEpsilon(), tmp_arc->getWeight());

      // goto the next arc
      //
      arcs_remain = tmp_copy_vert->gotoNextChild();
    }
  }

  // put the copy graph back in its original state
  //
  const_cast<BiGraph<TObject>& >(arg_a).gotoMark();

  // exit gracefully
  //
  return true;
}

// method: assign
//
// arguments:
//  DiGraph<TObject>& copy_graph: (input) the graph to copy
//
// return: a boolean value indicating status
//
// this is the assign method for the BiGraph class. we can't just copy
// the data over since the arcs make connections by pointer (and we
// can't share vertices across two graphs), hence we must manually
// insert every vertex and every arc. new vertices are created, but if
// the graph is in USER mode the tobject is not copied.
//
template<class TObject>
boolean BiGraph<TObject>::assign(const DiGraph<TObject>& arg_a) {

  // first cleanup the list
  //
  if (!clear(Integral::RESET)) {
    return Error::handle(name(), L"assign", Error::ARG, __FILE__, __LINE__);
  }
  
  // copy the weighting flag.
  //
  is_weighted_d = arg_a.isWeighted();

  // copy the allocation flag
  //
  alloc_d = arg_a.getAllocationMode();
  
  // save the state of the input graph
  //
  const_cast<DiGraph<TObject>& >(arg_a).setMark();
  
  // we need to build a cross-referencing scheme to make sure we cover
  // all arcs and all nodes. the (+2) is for the start and terminal
  // vertices since they are NOT included in the list
  //
  long num_vertices = arg_a.length() + 2;
  
  GraphVertex<TObject>* copy_sym_ptrs[num_vertices];
  BiGraphVertex<TObject>* this_sym_ptrs[num_vertices];

  // set the start and terminal vertices
  //
  copy_sym_ptrs[0] = arg_a.getStart();
  copy_sym_ptrs[num_vertices - 1] = arg_a.getTerm();
  
  // loop through the list of vertices, and number them
  //
  const_cast<DiGraph<TObject>& >(arg_a).gotoFirst();

  for (long i = 1; i < num_vertices - 1; i++) {

    // get the current node in the graph and assign it to the array
    //
    copy_sym_ptrs[i] = const_cast<GraphVertex<TObject>* >
      (arg_a.getCurr());

    // move to the next node in the graph
    //
    const_cast<DiGraph<TObject>& >(arg_a).gotoNext();
  }

  // before we assign the input graph we need to clear the current graph
  //
  this->clear(Integral::RESET);
  
  // set the start and terminal vertices
  //
  this_sym_ptrs[0] = getStart();
  this_sym_ptrs[num_vertices - 1] = getTerm();