hashtable.h

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

// file: $isip/class/dstr/HashTable/HashTable.h
// version: $Id: HashTable.h,v 1.58 2001/12/28 15:22:06 alphonso Exp $
//

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

// isip include files
//
#ifndef ISIP_VECTOR
#include <Vector.h>
#endif

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

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

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

#ifndef ISIP_STRING
#include <String.h>
#endif

#ifndef ISIP_FLOAT
#include <Float.h>
#endif

#ifndef ISIP_CONSOLE
#include <Console.h>
#endif

// forward class definitions
//
template<class THashable, class TObject> class HashTableDiagnose;

// HashTable: this class implements a hash table using a vector
// of single linked lists.
//
// note that internally the List objects will always be in SYSTEM
// mode. The only difference for USER and SYSTEM mode will be
// controlled manually via the Node class inside the HashNode.
//
template <class THashable, class TObject>
class HashTable : public DstrBase {
  
  //---------------------------------------------------------------------------
  //
  // 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_NODES;
  static const String PARAM_LOAD_FACTOR;
  
  //----------------------------------------
  //
  // default values and arguments
  //
  //----------------------------------------

  // default values
  //
  static const float DEF_LOAD_FACTOR = 0.75;
  static const long DEF_CAPACITY = 128;
  
  // default arguments to methods
  //

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

  // when to compress the capacity
  //
  static const float LOAD_LOWER_BOUND = 0.10;

  //----------------------------------------
  //
  // error codes
  //
  //----------------------------------------  
  
  static const long ERR = 40800;
  
  //---------------------------------------------------------------------------
  //
  // protected data
  //
  //---------------------------------------------------------------------------
protected:

  // define the hash node object
  //
  typedef Pair< THashable, Node<TObject> > HashNode;
  typedef HashTable<THashable, TObject> Type;
  
  // define the storage element for the hash entries:
  //  the internal structure of the HashTable is a Vector where each entry in
  //  the vector is a linked list. The list elements will hold the (key, value)
  //  pairs for the hash lookup.
  //
  Vector< SingleLinkedList<HashNode> > table_d;

  // define the load factor:
  //  the load factor determines how full the hash table is allowed to
  //  get before its capacity is increased. if the number of elements
  //  grows larger than the load factor multiplied by the current capacity
  //  then the capacity is increased and the table rehashed.
  //
  Float load_factor_d;

  // define the total number of items in the hash table
  //
  Long num_items_d;

  // the allocation mode
  //
  ALLOCATION alloc_d;

  // declare the debugging parameters
  //
  static Integral::DEBUG debug_level_d;

  // define the memory manager
  //
  static MemoryManager mgr_d;  
  
  //---------------------------------------------------------------------------
  //
  // required public methods
  //
  //---------------------------------------------------------------------------
public:
  
  // static methods
  //  the diagnose method is moved outside the class header file and
  //  defined in the HashTableDiagnose.h in order to avoid issues
  //  with 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;

  // method: destructor
  // 
  ~HashTable() {
    clear(Integral::RESET);
  }

  // default constructor
  //
  HashTable(ALLOCATION alloc = DEF_ALLOCATION,
	    long initial_capacity = DEF_CAPACITY,
	    float load_factor = DEF_LOAD_FACTOR);

  // method: copy constructor
  //
  HashTable(const HashTable<THashable, TObject>& arg) {
    assign(arg);
  }
  
  // assign methods
  //
  boolean assign(const HashTable<THashable, TObject>& arg);

  // method: operator=
  //
  HashTable<THashable, TObject>&
  operator=(const HashTable<THashable, TObject>& arg) {
    assign(arg);
    return *this;
  }

  // equality methods:
  //
  boolean eq(const HashTable<THashable, TObject>& compare_htable) const;

  // other i/o methods
  //
  long sofSize() const;
  
  // method: read
  //
  boolean read(Sof& sof, long tag) {
    return read(sof, tag, name());
  }

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

  // other i/o methods
  //
  boolean read(Sof& sof, long tag, const String& 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;
   
  // 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:
  //  extension to required methods
  //
  //---------------------------------------------------------------------------

  // method: ne
  //
  boolean ne(const HashTable<THashable, TObject>& compare_htable) const {
    return (!eq(compare_htable));
  }

  //---------------------------------------------------------------------------
  //
  // class-specific public methods:
  //  hash table manipulation methods
  //
  //---------------------------------------------------------------------------
  
  // data access methods
  //
  TObject* get(const THashable& key);
  const TObject* get(const THashable& key) const;
  
  // insert methods
  //
  boolean insert(const THashable& key, TObject* value);

  // remove methods
  //
  boolean remove(const THashable& key, TObject*& value);
  boolean remove(const THashable& key);

  //---------------------------------------------------------------------------
  //
  // class-specific public methods:
  //  hash table data access methods
  //
  //---------------------------------------------------------------------------
    
  // methods to get all keys/values
  //
  boolean keys(Vector<THashable>& keys_list) const;
  boolean values(Vector<TObject>& items_list) const;

  //---------------------------------------------------------------------------
  //
  // class-specific public methods:
  //  hash table property methods
  //
  //---------------------------------------------------------------------------
  
  // method: getCapacity
  //
  long getCapacity() const {
    return table_d.length();
  }

  // method: setCapacity
  //
  boolean setCapacity(long capacity) {
    return rehash(capacity);
  }

  // method: setLoadFactor
  //
  boolean setLoadFactor(float factor) {
    if (factor < (2 * LOAD_LOWER_BOUND)) {
      return Error::handle(name(), L"setLoadFactor", Error::ARG,
			   __FILE__, __LINE__);
    }
    load_factor_d = factor;

    // possibly rehash the table
    //
    if ((long)num_items_d > (((float)load_factor_d) * getCapacity())) {
      return rehash((long)(load_factor_d / (float)num_items_d * (float)2));
    }
    return true;
  }

  // method: getNumItems
  //
  long getNumItems() const {
    return num_items_d;
  }

  // method: isEmpty
  //
  boolean isEmpty() const {
    return ((long)num_items_d == 0);
  }

  // method: containsKey
  //
  boolean containsKey(const THashable& key) const {
    long index = 0;
    return const_cast<Type*>(this)->findKey(index, key);
  }

  // other methods to determine the occupancy of the HashTable
  //
  boolean containsValue(const TObject* item) const;

  //---------------------------------------------------------------------------
  //
  // class-specific public methods:
  //  hash table memory allocation methods
  //
  //---------------------------------------------------------------------------
  
  // method: getAllocationMode
  //
  ALLOCATION getAllocationMode() const {
    return alloc_d;
  }

  // method: setAllocationMode
  //  
  boolean setAllocationMode(ALLOCATION alloc) {
    alloc_d = alloc;
    return true;
  }
  
  //---------------------------------------------------------------------------
  //
  // private methods
  //
  //---------------------------------------------------------------------------
private:

  // methods to determine if the specified object is contained in the HashTable
  // it outputs the vector index and positions the SingleLinkedList accordingly
  //
  boolean findKey(long& index, const THashable& key);

  // rehashing method
  //
  boolean rehash(long new_capacity);

  // method: getCurrKey
  //
  const THashable& getCurrKey(long index) const {
    return table_d(index).getCurr()->first();
  }

  // method: getCurrKey
  //
  THashable& getCurrKey(long index) {
    return table_d(index).getCurr()->first();
  }

  // method: getCurrObject
  //
  const TObject* getCurrObject(long index) const {
    return table_d(index).getCurr()->second().getItem();
  }

  // method: getCurrObject
  //
  TObject* getCurrObject(long index) {
    return table_d(index).getCurr()->second().getItem();
  }

  // method: setCurrObject
  //
  boolean setCurrObject(long index, TObject* arg) {
    return table_d(index).getCurr()->second().setItem(arg);
  }

  // methods to transorm to and from a single list
  //
  boolean getList(SingleLinkedList<HashNode>& arg);
  boolean assignFromList(SingleLinkedList<HashNode>& arg);

  // friend class
  //
  template <class THashable_diagnose, class TObject_diagnose> 
  friend class HashTableDiagnose;
};

//-----------------------------------------------------------------------------
//
// 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 THashable, class TObject>
const String HashTable<THashable, TObject>::CLASS_NAME(L"HashTable");

template <class THashable, class TObject>
const String HashTable<THashable, TObject>::DEF_PARAM(L"");

template <class THashable, class TObject>
const String HashTable<THashable, TObject>::PARAM_NODES(L"table");

template <class THashable, class TObject>
const String HashTable<THashable, TObject>::PARAM_LOAD_FACTOR(L"load_factor");

// static instantiations: debug level
//
template <class THashable, class TObject>
Integral::DEBUG HashTable<THashable, TObject>::debug_level_d = Integral::NONE;

// static instantiations: the memory manager
//
template <class THashable, class TObject>
MemoryManager HashTable<THashable, TObject>::mgr_d(sizeof(HashTable<THashable, TObject>), CLASS_NAME);

// below are all the methods for the HashTable 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 THashable, class TObject>
const String& HashTable<THashable, 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(THashable::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 THashable, class TObject>
boolean HashTable<THashable, TObject>::debug(const unichar* message_a) const {
  
  // declare local variables
  //
  String output;
  String value;

  // print out the number of items
  //
  value.assign((long)num_items_d);
  output.debugStr(name(), message_a, L"num_items_d", value);
  Console::put(output);