soflist.h

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

// file: $isip/class/io/SofList/SofList.h
// version: $Id: SofList.h,v 1.19 2001/02/06 20:39:39 duncan Exp $
//

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

// isip include files
//
#ifndef ISIP_SYS_STRING
#include <SysString.h>
#endif

#define ISIP_INTERNAL_USE_ONLY
#include "SofNode.h"
#undef ISIP_INTERNAL_USE_ONLY

#ifndef ISIP_SOF_SYMBOL_TABLE
#include <SofSymbolTable.h>
#endif

// SofList: a binary search tree used to hold indices for Sof files.
// it is used to keep track of a sorted list of objects.
// 
// a binary search tree is a linked data structure in which each node is
// an object. each node has keys as well as pointers to its left, right
// and parent nodes. let x be a node in a binary search tree:
//   if y is a node in the left subtree of x, then key[y] <= key[x],
//   if y is a node in the right subtree of x, then key[x] <= key[y]
// 
// in this SofList, a name and a tag are used as the keys of a node.
// when comparing two nodes, the names are compared first, if the names
// are the same, the tags are compared. a good tutorial on heaps can be
// found at :
// 
//  T.H. Cormen, C.E. Leiserson and R.L. Rivest, "Introduction to
//  Algorithms," McGraw-Hill, New York, New York, USA, pp. 244-249, 1997.
//
class SofList {
  
  //---------------------------------------------------------------------------
  //
  // public constants
  //
  //---------------------------------------------------------------------------
public:

  // define the class name
  //
  static const SysString CLASS_NAME;

  //----------------------------------------
  //
  // other important constants
  //
  //----------------------------------------  

  // internal stack constants
  //
  static const long STACK_SIZE = 2048;
  static const long GROW_SIZE = 1024;
  
  //----------------------------------------
  //
  // default values and arguments
  //
  //----------------------------------------  

  // default values for stack
  //
  static const long DEF_STACK_SIZE = 0;
  static const long DEF_STACK_PTR = 0;
  static const long DEF_STACK_FRAME = 0;
  
  // a dummy tag for a name not in the soflist
  //
  static const long NO_TAG = -2147483647;
  
  //----------------------------------------
  //
  // error codes
  //
  //----------------------------------------  

  static const long ERR		   = 10100;
  static const long ERR_SYMB	   = 10102;
  static const long ERR_COPY	   = 10104;
  static const long ERR_DELETE	   = 10105;
  static const long ERR_ADD	   = 10106;
  static const long ERR_EXISTS	   = 10107;
  static const long ERR_CURR       = 10108;

  //---------------------------------------------------------------------------
  //
  // protected data
  //
  //---------------------------------------------------------------------------
protected:

  // the root node of the binary tree
  //
  SofNode* root_d;
  
  // the current node
  //
  SofNode* current_d;
  
  // a pointer to the symbol table
  //
  SofSymbolTable* table_d;
  
  // we need an internal stack to avoid recursion in the binary tree search
  //
  SofNode** stack_d;
  long stack_size_d;
  long stack_ptr_d;
  long stack_frame_d;

  // debugging parameters
  //
  Integral::DEBUG debug_level_d;

  // a memory manager
  //
  static MemoryManager mgr_d;
  
  //---------------------------------------------------------------------------
  //
  // required public methods
  //
  //---------------------------------------------------------------------------
public:

  // method: name
  //
  static const SysString& name() {
    return CLASS_NAME;
  }

  // other static methods
  //
  static boolean diagnose(Integral::DEBUG debug_level);
  
  // method: setDebug
  //
  boolean setDebug(Integral::DEBUG level) {
    debug_level_d = level;
    return true;
  }

  // other debug methods
  //
  boolean debug(const unichar* msg) const;
  
  // destructor/constructor(s)
  //
  ~SofList();
  SofList();
  SofList(const SofList& arg);
  
  // assign methods
  //
  boolean assign(const SofList& arg);

  // method: operator=
  //
  SofList& operator= (const SofList& arg) {
    if (!assign(arg)) {
      Error::handle(name(), L"operator=", Error::ARG, __FILE__, __LINE__);
    }      
    return *this;
  }
  
  // i/o methods:
  //  these methods are omitted because SofList can not write itself
  //   to an sof file
  //

  // equality methods:
  //  these methods are omitted because they are not useful for
  //  SofList objects
  //
  
  // memory management methods:
  //  new and delete are omitted because memory for SofList objects is not
  //  managed by the MemoryManager class
  //
  boolean clear(Integral::CMODE ctype = Integral::DEF_CMODE);

  //---------------------------------------------------------------------------
  //
  // class-specific public methods:
  //  extensions to the required public methods
  //
  //---------------------------------------------------------------------------
  
  // memory size methods
  //
  long memSize();
  
  //---------------------------------------------------------------------------
  //
  // class-specific public methods:
  //  soflist manipulation methods
  //
  //---------------------------------------------------------------------------
  
  // add object methods
  //
  boolean add(long name, long tag, long pos, long size);
  boolean addQuick(long name, long tag, long pos, long size);
  
  // remove object methods
  //
  boolean remove();
  
  // search objects methods
  //
  boolean find(long name, long tag);
  long first(long name);
  long last(long name);
  long next(long name, long cur_tag);
  long prev(long name, long cur_tag);
  
  //---------------------------------------------------------------------------
  //
  // class-specific public methods:
  //  set and get methods
  //
  //---------------------------------------------------------------------------

  // note that there is no method for changing name or tag, as this would
  // alter the position of the object in the tree. to do this, delete
  // and re-insert the node with the new information.
  //
  
  // method: setTable
  //  this method sets the symbol table used by the names
  //  this table will only be used by the display methods, not internally
  //
  boolean setTable(SofSymbolTable& table) {
    table_d = &table;
    return true;
  }
  
  // method: setPosition
  //
  boolean setPosition(long pos) {
    if (current_d == (SofNode*)NULL) {
      return Error::handle(name(), L"setPosition", ERR_CURR, __FILE__,
			   __LINE__);
    }
    current_d->pos_d = pos;
    return true;
  }

  // method: setSize
  //
  boolean setSize(long size) {
    if (current_d == (SofNode*)NULL) {
      return Error::handle(name(), L"setSize", ERR_CURR, __FILE__, __LINE__);
    }                  
    current_d->size_d = size;
    return true;
  }
  
  // method: getName
  //
  long getName() const {
    if (current_d == (SofNode*)NULL) {
      Error::handle(name(), L"getName", ERR_CURR, __FILE__, __LINE__);
      return (long)SofSymbolTable::NO_SYMB;
    }                  
    return current_d->name_d;
  }
  
  // method: getTag
  //
  long getTag() const {
    if (current_d == (SofNode*)NULL) {
      Error::handle(name(), L"getTag", ERR_CURR, __FILE__, __LINE__);
      return (long)NO_TAG;
    }                  
    return current_d->tag_d;
  }

  // method: getPosition
  //
  long getPosition() const {
    if (current_d == (SofNode*)NULL) {
      Error::handle(name(), L"getPosition", ERR_CURR, __FILE__, __LINE__);
      return (long)-1;
    }                  
    return current_d->pos_d;
  }
  
  // method: getSize
  //
  long getSize() const {
    if (current_d == (SofNode*)NULL) {
      Error::handle(name(), L"getSize", ERR_CURR, __FILE__, __LINE__);
      return (long)-1;
    }                  
    return current_d->size_d;
  }
  
  // method: getNameCount
  //  this method counts the number of different classes
  //
  long getNameCount() const {    
    if (table_d == (SofSymbolTable*)NULL) {
      return 0;
    }
    return table_d->getCount();
  }
  
  // method: getCount
  //   this method gets the total number of nodes in the tree
  //
  long getCount() {
    return getCount(root_d);
  }
  
  // method: getCount
  //  gets the number of nodes matching name
  //
  long getCount(long name) {
    return getCount(root_d, name);
  }
  
  //---------------------------------------------------------------------------
  //
  // private methods
  //
  //---------------------------------------------------------------------------
private:

  // memory management methods
  //
  SofNode* newNode();		
  boolean deleteNode(SofNode* node);

  // add object methods
  //
  boolean addNode(SofNode* node);
  
  // search objects methods
  //
  SofNode* findNode(long name, long tag);
  SofNode* findNode(long name);

  // methods to compare two SofNodes
  //

  // method: nodeGt
  //
  boolean nodeGt(const SofNode* node, long name, long tag) const {
    return ((node->name_d > name) ||
	    ((node->name_d == name) && (node->tag_d > tag)));
  }
    
  // method: nodeLt
  //
  boolean nodeLt(const SofNode* node, long name, long tag) const {
    return ((node->name_d < name) ||
	    ((node->name_d == name) && (node->tag_d < tag)));
  }

  // method: nodeGt
  //
  boolean nodeGt(const SofNode* node, long name) const {
    return (node->name_d > name);
  }

  // method: nodeLt
  //
  boolean nodeLt(const SofNode* node, long name) const {
    return (node->name_d < name);
  }

  // method: nodeGt
  //
  boolean nodeGt(const SofNode* node_1, const SofNode* node_2) const {
    return nodeGt(node_1, node_2->name_d, node_2->tag_d);
  }

  // method: nodeLt
  //
  boolean nodeLt(const SofNode* node_1, const SofNode* node_2) const {
    return nodeLt(node_1, node_2->name_d, node_2->tag_d);
  }

  // method: nodeEq
  //
  boolean nodeEq(const SofNode* node, long name) const {
    return (node->name_d == name);
  }
  
  // count nodes methods
  //
  long getCount(SofNode* node);
  long getCount(SofNode* node, long name);
  
  // internal stack management methods
  //

  // method: push
  //
  boolean push(SofNode* ptr) {
    if (stack_ptr_d == stack_size_d) {
      mgr_d.reallocateBlock((void***)&stack_d, stack_size_d, STACK_SIZE);
    }
    stack_d[stack_ptr_d++] = ptr;
    return true;
  }

  // method: pop
  //
  boolean pop(SofNode*& ptr) {
    if (stack_ptr_d <= stack_frame_d) {
      ptr = (SofNode*)NULL;
      return false;
    }
    ptr = stack_d[--stack_ptr_d];
    return true;
  }
  
  boolean pushFrame();
  boolean popFrame();
  
  // low-level debugging methods
  //
  boolean display();
  boolean display(SysString& str, SofNode* node);

  // method: displayTree
  //
  boolean displayTree() {
    return displayTree(root_d, 0);
  }
  boolean displayTree(SofNode* node, long level);
};

// end of include file
//
#endif