digraph.h

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

// file: $isip/class/dstr/DiGraph/DiGraph.h
// version: $Id: DiGraph.h,v 1.26 2003/03/28 19:21:26 alphonso Exp $
//

// make sure definitions are only made once
//
#ifndef ISIP_DI_GRAPH
#define ISIP_DI_GRAPH

// isip include files
//
#ifndef ISIP_DOUBLE_LINKED_LIST
#include <DoubleLinkedList.h>
#endif

#ifndef ISIP_SINGLE_LINKED_LIST
#include <SingleLinkedList.h>
#endif

#ifndef ISIP_COLOR_HASH
#include <ColorHash.h>
#endif

#ifndef ISIP_BOOLEAN
#include <Boolean.h>
#endif

#ifndef ISIP_TRIPLE
#include <Triple.h>
#endif

#ifndef ISIP_PAIR
#include <Pair.h>
#endif

#ifndef ISIP_LONG
#include <Long.h>
#endif

#ifndef ISIP_GRAPH_VERTEX
#include <GraphVertex.h>
#endif

#ifndef ISIP_BIGRAPH_VERTEX
#include <BiGraphVertex.h>
#endif

#ifndef ISIP_BI_GRAPH
#include <BiGraph.h>
#endif

// forward class definitions:
//  we must define the GraphVertex class here first because the header files
//  might be short-circuited by the ifndef.
//
template<class TObject> class ColorHash;
template<class TObject> class GraphVertex;

// DiGraph: a generic directed-graph template class. it is implemented
//  with something close to an adjacency list, with data held on the
//  vertices. each vertex holds both a TObject* and a list of all
//  emanating arcs. a graph can be in either USER or SYSTEM allocated
//  mode, for a USER-allocated list the TObject data is never copied.
//
template<class TObject>
class DiGraph : private DoubleLinkedList< GraphVertex<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_VERTICES;
  static const String PARAM_ARCS;
  static const String PARAM_WEIGHTED;
  static const String START_NAME;
  static const String TERM_NAME;
  
  //----------------------------------------
  //
  // dummy objects for start and end vertices
  //
  //----------------------------------------  

  static const TObject START_OBJ;
  static const TObject TERM_OBJ;

  //----------------------------------------
  //
  // indeces for start and end vertices
  //
  //----------------------------------------

  static const long START_INDEX = -1;
  static const long TERM_INDEX = -2;  
  
  //----------------------------------------
  //
  // default values and arguments
  //
  //----------------------------------------

  // default values
  //
  static const boolean DEF_IS_WEIGHTED = true;

  // default arguments to methods
  //
  
  //----------------------------------------
  //
  // error codes
  //
  //----------------------------------------  
  
  static const long ERR = 41200;
  static const long ERR_EPSCYC = 41201;
  static const long ERR_MULPAR = 41202;
  
  //---------------------------------------------------------------------------
  //
  // protected data
  //
  //---------------------------------------------------------------------------
protected:

  // define the object used to hold graph topology in read and write
  //
  typedef Triple< Pair<Long, Long>, Float, Boolean> TopoTriple;
  typedef HashTable< String, GraphVertex<TObject> > ReadHash;
  
  // each graph has a dummy start vertex
  //
  GraphVertex<TObject>* start_vertex_d;

  // each graph has a dummy terminal vertex
  //
  GraphVertex<TObject>* term_vertex_d;

  // each graph has a hash table that associates a color with the
  // graph vertices that tell us if the vertex has been
  // visited. unless explicitely allocated via the makeColorHash
  // method this will be a null pointer and all color methods will
  // fail.
  //
  ColorHash<TObject>* chash_d;
  
  // is the graph weighted?
  //
  Boolean is_weighted_d;

  // the allocation mode
  //
  DstrBase::ALLOCATION alloc_d;  
  
  // debugging parameters
  //
  static Integral::DEBUG debug_level_d;
  
  // define the memory manager
  //
  static MemoryManager mgr_d;
  
  //---------------------------------------------------------------------------
  //
  // required public methods
  //
  //---------------------------------------------------------------------------
public:

  // static methods
  //  diagnose method is moved outside the class header file and
  //  defined in the DiGraphDiagnose.h in order to avoid issues
  //  related to 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* message) const;

  // destructor
  //
  ~DiGraph();

  // default constructor
  //
  DiGraph(DstrBase::ALLOCATION alloc = DEF_ALLOCATION);

  // copy constructor
  //
  DiGraph(const DiGraph<TObject>& copy_graph);
  
  // assign methods:
  //  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!
  //
  boolean assign(const DiGraph<TObject>& copy_graph);
  boolean assign(SingleLinkedList<TObject>& data,
		 SingleLinkedList<TopoTriple>& arcs);

  boolean assign(const BiGraph<TObject>& copy_graph);
  
  // method: operator=
  //
  DiGraph<TObject>& operator=(const DiGraph<TObject>& arg) {
    assign(arg);
    return *this;
  }

  // equality method
  //
  boolean eq(const DiGraph<TObject>& compare_graph) const;
  
  // i/o methods
  //
  long sofSize() const;
  
  // method: read
  //
  boolean read(Sof& sof, long tag) {
    return read(sof, tag, name());
  }
  boolean read(Sof& sof, long tag, const String& name);

  // method: write
  //
  boolean write(Sof& sof, long tag) const {
    return write(sof, tag, name());
  }
  boolean write(Sof& sof, long tag, const String& name) const;

  boolean readData(Sof& sof, const String& pname = DEF_PARAM,
		   long size = SofParser::FULL_OBJECT, boolean param = true,
                   boolean nested = false);
  boolean writeData(Sof& sof, const String& pname = DEF_PARAM) const;

  boolean readDataText(Sof& sof, const String& pname = DEF_PARAM,
		       long size = SofParser::FULL_OBJECT,
		       boolean param = true,
		       boolean nested = false);
  boolean readDataBinary(Sof& sof);
  
  boolean writeDataText(Sof& sof, const String& pname,
			SingleLinkedList<TObject>& dlist,
			SingleLinkedList<TopoTriple>& alist) const;
  boolean writeDataBinary(Sof& sof, const String& pname,
			  SingleLinkedList<TObject>& dlist,
			  SingleLinkedList<TopoTriple>& alist) const;    

  // method: new
  //
  void* operator new(size_t size) {
    return mgr_d.get();
  }

  // method: new[]
  // 
  void* operator new[](size_t size) {
    return mgr_d.getBlock(size);
  }

  // method: delete
  //  
  void operator delete(void* ptr) {
    mgr_d.release(ptr);
  }

  // method: delete[]
  //  
  void operator delete[](void* ptr) {
    mgr_d.releaseBlock(ptr);
  }

  // method: setGrowSize
  //  
  static boolean setGrowSize(long grow_size) {
    return mgr_d.setGrow(grow_size);
  }

  // other memory management methods
  //  
  boolean clear(Integral::CMODE cmode = Integral::DEF_CMODE);

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

  // method: insertArc
  //
  boolean insertArc(long start_index, long end_index,
		    boolean is_epsilon = GraphArc<TObject>::DEF_EPSILON,
		    float weight = GraphArc<TObject>::DEF_WEIGHT) {
    gotoPosition(start_index);
    GraphVertex<TObject> * start_vertex = getCurr();
    gotoPosition(end_index);
    GraphVertex<TObject>* end_vertex = getCurr();
    return insertArc(start_vertex, end_vertex,
		     is_epsilon, weight);
  }

  // other arc insertion methods
  //
  boolean insertArc(GraphVertex<TObject>* start_vertex,
		    GraphVertex<TObject>* end_vertex,
		    boolean is_epsilon = GraphArc<TObject>::DEF_EPSILON,
		    float weight = GraphArc<TObject>::DEF_WEIGHT);
  
  // method: removeArc
  //
  boolean removeArc(long start_index, long end_index) {
    return removeArc(getPosition(start_index), getPosition(end_vertex));
  }

  // other arc removal methods
  //  
  boolean removeArc(GraphVertex<TObject>* start_vertex,
		    GraphVertex<TObject>* end_vertex);

  // insert vertex methods
  //
  GraphVertex<TObject>* insertVertex(TObject* arg);

  // remove vertex methods
  //
  boolean removeVertex();  
  boolean removeVertex(TObject*& arg);
  
  // item containment methods:
  //
  boolean find(const TObject* obj);
  boolean find(const GraphVertex<TObject>* vertex);
  boolean contains(const TObject* obj) const;
  boolean contains(const GraphVertex<TObject>* vertex) const;  
  
  //---------------------------------------------------------------------------
  //
  // class-specific public methods:
  //  graph property methods
  //
  //---------------------------------------------------------------------------
    
  // method: getStart
  //
  GraphVertex<TObject>* getStart() const {
    return start_vertex_d;
  }

  // method: getTerm
  //
  GraphVertex<TObject>* getTerm() const {
    return term_vertex_d;
  }

  // this method extracts the structure of the graph and places them
  // in two lists. the first list contains the vertices and the second
  // list contains the arcs between the vertices.
  //
  boolean get(SingleLinkedList<TObject>& data,
	      SingleLinkedList<TopoTriple>& arcs) const;
  
  // method: isWeighted
  //
  boolean isWeighted() const {
    return is_weighted_d;
  }

  // method: setWeighted
  //
  boolean setWeighted(boolean is_weighted = true) {
    is_weighted_d = is_weighted;
    return true;
  }
  
  //---------------------------------------------------------------------------
  //
  // class-specific public methods:
  //  graph ordering methods
  //
  //---------------------------------------------------------------------------
  
  // topological sort methods
  //
  boolean topologicalSort(SingleLinkedList<TObject>& sorted_data,
			  boolean partial = false);

  // method: getColor
  //
  Integral::COLOR getColor(const GraphVertex<TObject>* v) const {
    return chash_d->get(v);
  }

  // method: setColor
  //
  boolean setColor(const GraphVertex<TObject>* v, Integral::COLOR col) {
    return chash_d->set(v, col);
  }
  
  // method: releaseColorHash
  //
  boolean releaseColorHash() {
    chash_d->clear(Integral::RESET);    
    if (chash_d != (ColorHash<TObject>*)NULL) {
      delete chash_d;
      chash_d = (ColorHash<TObject>*)NULL;
    }
    return true;
  }
  
  // other color methods
  //
  boolean invertColor();
  boolean makeColorHash(Integral::COLOR col = Integral::DEF_COLOR);
  boolean setColor(Integral::COLOR col);
  boolean isColor(Integral::COLOR col);
  boolean replaceColor(Integral::COLOR old_col,
		       Integral::COLOR new_col);

  // methods to do simple depth first search
  //
  boolean dfsVisit(GraphVertex<TObject>& vertex);

  //---------------------------------------------------------------------------
  //
  // class-specific public methods:
  //  graph 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:
  //  double linked list methods
  //
  //---------------------------------------------------------------------------  
  // the DiGraph class derives the DoubleLinkedList bases class which
  // is used as the primary underlying container class. to prevent the
  // user from circumventing the DiGraph'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< GraphVertex<TObject> >::length;
  using DoubleLinkedList< GraphVertex<TObject> >::gotoFirst;
  using DoubleLinkedList< GraphVertex<TObject> >::gotoNext;
  using DoubleLinkedList< GraphVertex<TObject> >::gotoPrev;
  using DoubleLinkedList< GraphVertex<TObject> >::getCurr;
  using DoubleLinkedList< GraphVertex<TObject> >::getFirst;
  using DoubleLinkedList< GraphVertex<TObject> >::getLast;
  using DoubleLinkedList< GraphVertex<TObject> >::gotoMark;
  using DoubleLinkedList< GraphVertex<TObject> >::setMark;
  using DoubleLinkedList< GraphVertex<TObject> >::gotoPosition;
  using DoubleLinkedList< GraphVertex<TObject> >::getPosition;

  using DoubleLinkedList< GraphVertex<TObject> >::isLast;
  using DoubleLinkedList< GraphVertex<TObject> >::isEmpty;
  using DoubleLinkedList< GraphVertex<TObject> >::isMarkedElement;

  //---------------------------------------------------------------------------
  //
  // private methods
  //
  //---------------------------------------------------------------------------
private:

  // methods to split writeData:
  //  the readData needed to be broken up
  //
  boolean readVertexDataText(Sof& sof_a, SofParser& parser,
			     ReadHash& hash) const;
  boolean readArcDataText(Sof& sof_a, SofParser& parser,