hashtable.h

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

  // print out the load factor
  //
  value.assign((float)load_factor_d);
  output.debugStr(name(), message_a, L"load_factor_d", value);
  Console::put(output);
  
  // print out the capacity
  //
  value.assign((long)getCapacity());
  output.debugStr(name(), message_a, L"capacity_d", value);
  Console::put(output);
  
  // print out the memory allocation mode
  //
  output.debugStr(name(), message_a, L"alloc_d",
		  NameMap::ALLOCATION_MAP((long)alloc_d));
  Console::put(output);

  // get the list
  //
  SingleLinkedList<HashNode> temp_list(USER);
  const_cast< HashTable<THashable, TObject>* >(this)->getList(temp_list);
  
  Console::increaseIndention();
  
  // loop over each element and print its value
  //
  for (boolean more = temp_list.gotoFirst(); more;
       more = temp_list.gotoNext()) {
    value.assign(temp_list.getCurr()->first().hash(getCapacity()));
    temp_list.getCurr()->first().debug((unichar*)value);
    Console::increaseIndention();
    temp_list.getCurr()->second().getItem()->debug((unichar*)value);
    Console::decreaseIndention();
  }

  Console::decreaseIndention();
  
  // exit gracefully
  // 
  return true;
}

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

// method: default constructor
//
// arguments:
//  ALLOCATION alloc: (input) the flag to specify whether or not the item
//                    memory is allocated by the node
//  long init_capacity: (input) the initial capacity of the hash table
//  float load_factor: (input) the load factor of the hash table
//
// return: none
//
// this is the default constructor for the HashTable class
//
template<class THashable, class TObject>
HashTable<THashable, TObject>::HashTable(ALLOCATION alloc_a,
					 long init_capacity_a,
					 float load_factor_a) {
  
  // initialize the number of elements
  //
  num_items_d = (long)0;

  // initialize the load factor
  //
  setLoadFactor(load_factor_a);
  
  // initialize memory allocation flag
  //
  alloc_d = alloc_a;
  
  // initialize the capacity
  //
  setCapacity(init_capacity_a);
}

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

// method: assign
//
// arguments:
//  const HashTable<THashable, TObject>& arg: (input) table to copy
//
// return: a boolean value indicating status
//
// this method copies the contents of the input to this hash table
//
template<class THashable, class TObject>
boolean HashTable<THashable, TObject>::assign(const HashTable<THashable,
					      TObject>& arg_a) {

  // clear this table
  //
  clear(Integral::RESET);

  // copy the allocation mode and the load factor
  //
  alloc_d = arg_a.alloc_d;
  load_factor_d = arg_a.load_factor_d;
  
  Vector<THashable> keys;
  arg_a.keys(keys);

  long len = keys.length();

  for (long i = 0; i < len; i++) {
    insert(keys(i), const_cast<Type*>(&arg_a)->get(keys(i)));
  }

  // exit gracefully
  //
  return true;
}

//------------------------------------------------------------------------
//
// required i/o methods
//
//------------------------------------------------------------------------

// method: sofSize
//
// arguments: none
//
// return: size of object as written to disk via the i/o methods
//
// this method determines the size of the object on disk
//
template<class THashable, class TObject>
long HashTable<THashable, TObject>::sofSize() const{

  // declare temporary variables
  //
  long tmp_size = 0;
  
  // count the size of the load_factor_d
  //
  tmp_size = load_factor_d.sofSize();
  
  // get the capacity of the hash table
  //
  long capacity = getCapacity();
  
  // loop over each element and add the size of that element. this is the
  // total size of the hash table
  // 
  for (long i = 0; i < capacity; i++) {
    
    // add the size of this element
    //
    tmp_size += table_d(i).sofSize();
  }
  
  // return the size
  //
  return tmp_size;
}

// method: read
//
// arguments:
//  Sof& sof: (input) sof file object
//  long tag: (input) sof object instance tag
//  const String& name: (input) sof object instance name
//
// return: a boolean value indicating status
//
// this method has the object read itself from an Sof file
//
template<class THashable, class TObject>
boolean HashTable<THashable, TObject>::read(Sof& sof_a, long tag_a,
					    const String& name_a) {
  
  // get the instance of the object from the Sof file
  //
  if (!sof_a.find(name_a, tag_a)) {
    return false;
  }

  // read the actual data from the sof file
  //
  if (!readData(sof_a)) {
    return false;
  }

  // exit gracefully
  //
  return true;
}

// method: write
//
// arguments:
//  Sof& sof: (input) sof file object
//  long tag: (input) sof object instance tag
//  const String& name: (input) sof object instance name
//
// return: a boolean value indicating status
//
// this method has the object write itself to an Sof file
//
template<class THashable, class TObject>
boolean HashTable<THashable, TObject>::write(Sof& sof_a, long tag_a,
					     const String& name_a) const {
  
  // declare a temporary size variable
  //
  long obj_size = 0;

  // switch on ascii or binary mode
  //
  if (sof_a.isText()) {
    
    // set the size to be dynamic
    //
    obj_size = Sof::ANY_SIZE;
  }
  else {

    // the size of the binary data to write
    //
    obj_size = sofSize();
  }
  
  // put the object into the sof file's index
  //
  if (!sof_a.put(name_a, tag_a, obj_size)) {
    return false;
  }
  
  // exit gracefully
  //
  return writeData(sof_a);
}

// method: readData
//
// arguments:
//  Sof& sof: (input) sof file object
//  const String& pname: (input) parameter name
//  long size: (input) size of the object
//  boolean param: (input) is the parameter specified?
//  boolean nested: (input) is this nested?
//
// return: a boolean value indicating status
//
// this method has the object read itself from an Sof file. it assumes
// that the Sof file is already positioned correctly.
//
template<class THashable, class TObject>
boolean
HashTable<THashable, TObject>::readData(Sof& sof_a, const String& pname_a,
					long size_a, boolean param_a,
					boolean nested_a) {
  
  // first cleanup the hash table
  //
  if (!clear(Integral::RESET)) {
    return Error::handle(name(), L"readData", Error::READ,
			 __FILE__, __LINE__, Error::WARNING);
  }
  
  // implicit parameter is impossible with composite objects,  but
  // nesting can be used
  //
  SofParser parser;

  parser.setDebug(debug_level_d);
  
  if (nested_a) {
    parser.setNest();
  }
  
  // load the parser
  //  
  parser.load(sof_a, size_a);
    
  // read and set the load factor
  //
  Float factor;
  if (!factor.readData(sof_a, PARAM_LOAD_FACTOR,
		       parser.getEntry(sof_a, PARAM_LOAD_FACTOR))) {
    return Error::handle(name(), L"readData", Error::READ,
			 __FILE__, __LINE__, Error::WARNING);
  }
  setLoadFactor(factor);
  
  // read the hash nodes into a temporary list
  //
  SingleLinkedList< HashNode > temp_list(SYSTEM);
  temp_list.setDebug(debug_level_d);
  if (!temp_list.readData(sof_a, PARAM_NODES,
			  parser.getEntry(sof_a, PARAM_NODES), 
			  false)) {
    return Error::handle(name(), L"readData", Error::READ,
			 __FILE__, __LINE__, Error::WARNING);
  }
  
  // according to the number of num_items and the load factor, compute
  // a suitable capacity
  //
  long num_items = temp_list.length();
  Double cap;
  cap = (double)num_items / (((double)load_factor_d) * 100);
  cap.ceil();
  long capacity = ((long)(double)cap) * 100; 
  
  // set the capacity
  //
  table_d.setLength((long)capacity);

  // place the objects from the list onto the table
  //
  temp_list.setAllocationMode(USER);
  assignFromList(temp_list);
  
  // clean up the list
  //
  temp_list.clear(Integral::RESET);

  // exit gracefully 
  //
  return true;
}

// method: writeData
//
// arguments:
//  Sof& sof: (input) sof file object
//  const String& pname: (input) parameter name
//
// return: a boolean value indicating status
//
// this method writes the object to the Sof file. it assumes that the
// Sof file is already positioned correctly.
//
template<class THashable, class TObject>
boolean
HashTable<THashable, TObject>::writeData(Sof& sof_a,
					 const String& pname_a) const {
  
  // local variables
  //
  SingleLinkedList<HashNode> temp_list(USER);
  
  // extract the list of nodes
  //
  const_cast<HashTable<THashable,TObject>*>(this)->getList(temp_list);

  // write the label prefix
  //
  sof_a.writeLabelPrefix(pname_a);
  
  // write the load factor
  //
  if (!load_factor_d.writeData(sof_a, PARAM_LOAD_FACTOR)) {
    return Error::handle(name(), L"write load factor", HashTable::ERR,
			 __FILE__, __LINE__);
  }
  
  // write the nodes list
  //
  if (!temp_list.writeData(sof_a, PARAM_NODES)) {
    return Error::handle(name(), L"write the nodes", HashTable::ERR,
			 __FILE__, __LINE__);
  };
  
  // write the label suffix
  //
  sof_a.writeLabelSuffix(pname_a);

  // exit gracefully
  //
  return true;
}

//-----------------------------------------------------------------------
//
// required equality methods
//
//------------------------------------------------------------------------

// method: eq
//
// arguments:
//  const HashTable<THashable, TObject>& compare_table: (input) the hash table to compare
//
// return: a boolean value indicating status
//
// this method compares two hash tables for equivalence. two hash tables are
// equivalent if all corresponding elements are equivalent
//
template<class THashable, class TObject>
boolean
HashTable<THashable, TObject>::eq(const HashTable<THashable, TObject>&
				  compare_table_a) const {

  // two hash table can't be equal if they have different number of items
  //
  if (num_items_d != compare_table_a.num_items_d) {
    return false;
  } 
  
  // compare if the two hash tables contain the same hash nodes
  //
  for (long i = 0; i < getCapacity(); i++) {
    
    for (boolean more = const_cast<Type*>(this)->table_d(i).gotoFirst();
	 more; more = const_cast<Type*>(this)->table_d(i).gotoNext()) {
      
      if (!compare_table_a.containsValue(getCurrObject(i))) {
	return false;
      }
    }
  }

  // exit gracefully: the two hash tables are the same
  // 
  return true;
}

//-------------------------------------------------------------------------
//
//  required clear method
//
//-------------------------------------------------------------------------

// method: clear
//
// arguments:
//  Integral::CMODE cmode: (input) clear mode
//  
// return: a boolean value indicating status
//
// this method clears the contents of the hash table. for RETAIN mode,
// all keys remain but the objects are cleared. for RESET and RELEASE
// mode, the table is emptied. for FREE mode the table is emptied and
// all memory is deleted regardless of allocation mode.
//
template<class THashable, class TObject>
boolean HashTable<THashable, TObject>::clear(Integral::CMODE cmode_a) {

  // initialize local varaibles
  //
  long capacity = getCapacity();

  // loop over all elements in the table
  //
  for (long i = 0; i < capacity; i++) {    

    // for RETAIN or FREE propogate clear to all objects
    //
    if ((cmode_a == Integral::RETAIN) || (cmode_a == Integral::FREE)) {
      for (boolean more = table_d(i).gotoFirst(); more;
	   more = table_d(i).gotoNext()) {
	getCurrObject(i)->clear(cmode_a);
      }
    }

    // in system mode or clear::FREE delete memory
    //
    if ((alloc_d == SYSTEM) || (cmode_a == Integral::FREE)) {
      for (boolean more = table_d(i).gotoFirst(); more;
	   more = table_d(i).gotoNext()) {
	delete getCurrObject(i);
	setCurrObject(i, (TObject*)NULL);
      }
    }
    
    // remove references to these objects if not in RETAIN mode, i.e.,
    // empty the table.
    //
    if (cmode_a != Integral::RETAIN) {
      table_d(i).clear(cmode_a);
    }
  }

  // if cmode_a is called with the RESET, set the length of the table
  // to be 0
  //  
  if (cmode_a == Integral::RESET) {
    table_d.setLength(DEF_CAPACITY);
  }

  // for RELEASE and FREE also set the capacity to be DEF_CAPACITY
  //
  else if ((cmode_a == Integral::RELEASE) || (cmode_a == Integral::FREE))  {
    table_d.setLength(DEF_CAPACITY);
    table_d.setCapacity(DEF_CAPACITY);
  }

  // reset the number of items if not in retain mode
  //
  if (cmode_a != Integral::RETAIN) {
    num_items_d = 0;
  }

  // exit gracefully
  //
  return true;
}

//------------------------------------------------------------------------
//
// class-specific public methods:
//  hash table manipulation methods
//
//------------------------------------------------------------------------

// method: get
//
// arguments:
//  const THashable& key: (input) the key used to find the item
//  
// return: the item corresponding to a given key
//
// this method gets the item corresponding to a key
//
template<class THashable, class TObject>
TObject* HashTable<THashable, TObject>::get(const THashable& key_a) {

  // declare local variables
  //
  long index = 0;

  // find if there is such a key is in the hash table
  //
  if (findKey(index, key_a)) {
    
    // the linked list is positioned correctly now  
    //
    return getCurrObject(index);
  }
    
  // nothing in the hash table, return null