hashtable.h

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

  //
  return (TObject*)NULL;
}

// 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>
const TObject*
HashTable<THashable, TObject>::get(const THashable& key_a) const {

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

  // find if there is such a key is in the hash table
  //
  if (const_cast<Type*>(this)->findKey(index, key_a)) {

    // the linked list is positioned correctly now  
    //
    return getCurrObject(index);
  }
    
  // nothing in the hash table, return null
  //
  return (TObject*)NULL;
}

// method: insert
//
// arguments:
//  const THashable& key: (input) the key string of an item
//  TObject* item: (input) the item to put into the hash table
//  
// return: a boolean value indicating status
//
// this method creates a hash node for the given key and value, and inserts it
// into corresponding list in this hash table.
//
template<class THashable, class TObject>
boolean HashTable<THashable, TObject>::insert(const THashable& key_a,
					      TObject* item_a) {

  // make sure the key is unique
  //
  if (containsKey(key_a)) {
    Error::handle(name(), L"this key is already used", ERR,
		  __FILE__, __LINE__);
    return false;
  }

  // start to build the HashNode with the key
  //
  HashNode new_node;
  new_node.first().assign(key_a);

  // when in USER mode we just reference the object
  //
  if (alloc_d == USER) {
    new_node.second().setItem(item_a);
  }

  // when in SYSTEM mode we make a copy of the object
  //
  else {
    new_node.second().setItem(new TObject(*item_a));
  }

  // add this node into the table_d
  //
  long index = key_a.hash(getCapacity());
  table_d(index).insertLast(&new_node);
  
  // increase the number of items
  //
  num_items_d = (long)num_items_d + 1;

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


  
  // exit gracefully
  //
  return true;
}

// method: remove
//
// arguments:
//  const THashable& key: (input) the key string of an item
//  TObject*& item: (output) the item having the given key 
//  
// return: a boolean value indicating status
//
// this method removes the node for the given key and outputs its value.
//
template<class THashable, class TObject>
boolean HashTable<THashable, TObject>::remove(const THashable& key_a,
					      TObject*& item_a) {

  // local variables
  //
  long index = 0;

  // when in SYSTEM mode the item passed in should not be null
  //
  if ((alloc_d == SYSTEM) && (item_a == (TObject*)NULL)) {
    return (Error::handle(name(), L"remove", ERR, __FILE__, __LINE__));
  }

  // when in USER mode the item should be null
  //
  if ((alloc_d == USER) && (item_a != (TObject*)NULL)) {
    return (Error::handle(name(), L"remove", ERR, __FILE__, __LINE__));
  }
  
  // look up the item of the given key
  //
  if (findKey(index, key_a)) {
    
    // if allocation mode is USER, just return the pointer
    //
    if (alloc_d == USER) {
      item_a = getCurrObject(index);
    }

    // for system mode delete the item memory
    //
    else {
      item_a->assign(*getCurrObject(index));
      delete getCurrObject(index);
    }

    // remove the node from the table
    //
    table_d(index).remove();
    
    // decrease the number of items
    //
    num_items_d = (long)num_items_d - 1;

    // decrease the capacity if:
    //   1) the number of items is less than 10% of the capacity, and
    //   2) the current capacity is greater than the default, and
    //   3) the new capacity will still be greater than the default
    //
    // this allows for an intelligent lower bound on the halfing
    //
    long capacity = getCapacity();
    if (((long)num_items_d < (LOAD_LOWER_BOUND * capacity)) &&
	(capacity >= (DEF_CAPACITY * 2))) {
      return rehash(capacity / 2);
    }

    // exit gracefully
    //
    return true;
  }
    
  // exit ungracefully: item not found
  //
  return false;
}

// method: remove
//
// arguments:
//  const THashable& key: (input) the key string of an item
//  
// return: a boolean value indicating status
//
// this method removes the node of the given key.
//
template<class THashable, class TObject>
boolean HashTable<THashable, TObject>::remove(const THashable& key_a) {

  // local variables
  //
  long index = 0;

  // look up the item of the given key
  //
  if (findKey(index, key_a)) {

    // if allocation mode is SYSTEM delete the object
    //
    if (alloc_d == SYSTEM) {
      delete getCurrObject(index);
    }

    // now remove the current linked node
    //
    table_d(index).remove();
    
    // decrease the number of items
    //
    num_items_d = (long)num_items_d - 1;
    
    // decrease the capacity if:
    //   1) the number of items is less than 10% of the capacity, and
    //   2) the current capacity is greater than the default, and
    //   3) the new capacity will still be greater than the default
    //
    // this allows for an intelligent lower bound on the halfing
    //
    long capacity = getCapacity();
    if (((double)num_items_d < (LOAD_LOWER_BOUND * capacity)) &&
	(capacity >= (DEF_CAPACITY * 2))) {
      return rehash(capacity / 2);
    }

    // exit gracefully
    //
    return true;
  }

  // exit ungracefully: item not found
  //
  return false;
}

//------------------------------------------------------------------------
//
// class-specific public methods:
//  hash table data access methods
//
//------------------------------------------------------------------------

// method: keys
//
// arguments:
//  Vector<THashable>& keys_vector: (output) all the key strings
//  
// return: a boolean value indicating status
//
// this method gets all the key strings of this hash table
//
template<class THashable, class TObject>
boolean HashTable<THashable, TObject>::keys(Vector<THashable>& keys_vector_a)
  const {

  // clear the input vector
  //
  keys_vector_a.clear(Integral::RESET);
  keys_vector_a.setLength(num_items_d);
  
  // get the capacity of the hash table
  //
  long capacity = getCapacity();
  
  // loop all the elements of the hash table
  // 
  for (long i = 0, index = 0; i < capacity; i++) {
    
    // loop over each linked list
    //
    for (boolean more = const_cast<Type*>(this)->table_d(i).gotoFirst();
	 more; more = const_cast<Type*>(this)->table_d(i).gotoNext()) {
      
      // get the key of the current hash node, add it into the vector,
      // and increment the index
      //
      keys_vector_a(index++).assign(getCurrKey(i));
    }
  }
  
  // exit gracefully
  //
  return true;
}

// method: values
//
// arguments:
//  Vector<TObject>& values: (output) all the values
//  
// return: a boolean value indicating status
//
// this method gets all the values of this hash table
//
template<class THashable, class TObject>
boolean
HashTable<THashable, TObject>::values(Vector<TObject>& values_a) const {
  
  // clear the input vector and set its length
  //
  values_a.clear(Integral::RESET);
  values_a.setLength(num_items_d);
  
  // get the capacity of the hash table
  //
  long capacity = getCapacity();
  
  // loop all the elements of the hash table
  // 
  for (long i = 0, index = 0; i < capacity; i++) {
    
    // loop each linked list
    //
    for (boolean more = const_cast<Type*>(this)->table_d(i).gotoFirst();
	 more; more = const_cast<Type*>(this)->table_d(i).gotoNext()) {
      
      // get the value of the current hash node, add it into the vector,
      // and increment the index
      //
      values_a(index++).assign(*getCurrObject(i));
    }
  }
  
  // exit gracefully
  //
  return true;
}

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

// method: containsValue
//
// arguments:
//  const TObject* value: (input) the value to be found
//
// return: a boolean value indicating status
//
// this method determines if a value is contained in this hash table
// note the values may be not unique in the hash table
//
template<class THashable, class TObject>
boolean
HashTable<THashable, TObject>::containsValue(const TObject* value_a) const {
  
  // get the length of table_d
  //
  long capacity = getCapacity();
  
  // loop each linked list
  //
  for (long i = 0; i < capacity; i++) {
    
    for (boolean more = const_cast<Type*>(this)->table_d(i).gotoFirst(); more;
	 more = const_cast<Type*>(this)->table_d(i).gotoNext()) {
      
      // if value is found, return true
      //
      if (getCurrObject(i)->eq(*value_a)) {
	return true;
      }
    }
  }  

  // value not found, return false
  //
  return false;
}

// method: getList
//
// arguments:
//  SingleLinkedList<HashNode>& arg: (output) all current hashnodes
//
// return: logical error status
//
// this method obtains a list of all hashnodes by concattenating all
// the lists together.
//
template<class THashable, class TObject>
boolean
HashTable<THashable, TObject>::getList(SingleLinkedList<HashNode>& arg_a) {

  // make sure the argument and the object are in USER mode
  //
  if (arg_a.getAllocationMode() != USER) {
    return Error::handle(name(), L"getList", Error::ARG, __FILE__, __LINE__);
  } 

  // prepare the argument by clearing it
  //
  arg_a.clear(Integral::RESET);
 
  // just copy a reference
  //
  long capacity = table_d.length();
  for (long i = 0; i < capacity; i++) {
    table_d(i).setAllocationMode(USER);
    arg_a.insert(table_d(i));
    table_d(i).setAllocationMode(SYSTEM);
  }

  // exit gracefully
  //
  return true;
}

// method: assignFromList
//
// arguments:
//  SingleLinkedList<HashNode>& arg: (input) all current hashnodes
//
// return: logical error status
//
// this method obtains a list of all hashnodes by concatenating all
// the lists together.
//
template<class THashable, class TObject>
boolean HashTable<THashable, TObject>::assignFromList(SingleLinkedList<HashNode>& arg_a) {

  // make sure the argument and the object are in USER mode
  //
  if (arg_a.getAllocationMode() != USER) {
    return Error::handle(name(), L"assignFromList", Error::ARG, __FILE__,
			 __LINE__);
  }
  
  // loop through the data
  //
  for (boolean more = arg_a.gotoFirst();
       more; more = arg_a.gotoNext()) {

    // determine where to hash the object
    //
    long index = arg_a.getCurr()->first().hash(getCapacity());

    // add the pair onto the given list
    //
    table_d(index).setAllocationMode(USER);
    table_d(index).insert(arg_a.getCurr());
    table_d(index).setAllocationMode(SYSTEM);
  }

  // set the length
  //
  num_items_d = arg_a.length();

  // exit gracefully
  //
  return true;
}

// method: rehash
//
// arguments:
//  long new_capacity: (input) new capacity to rehash to
//
// return: a boolean value indicating status
//
// this method increases the capacity and reorganizes this hash table, in order
// to accommodate and access its items more efficiently.
//
template<class THashable, class TObject>
boolean HashTable<THashable, TObject>::rehash(long new_capacity_a) {

  // local variables
  //
  long capacity = getCapacity();
  SingleLinkedList< HashNode > hashnodes_list(USER);

  // concatenate all lists onto a single list
  //
  getList(hashnodes_list);

  // clear out internal storage (making sure nodes aren't deleted)
  //
  for (long i = 0; i < capacity; i++) {
    table_d(i).setAllocationMode(USER);
    table_d(i).clear(Integral::RESET);
    table_d(i).setAllocationMode(SYSTEM);
  }

  // set the capacity
  //
  table_d.setLength(new_capacity_a);

  // place the objects back on the table
  //
  assignFromList(hashnodes_list);

  // exit gracefully
  //
  return true;
}

//---------------------------------------------------------------------------
//
// class-specific public methods:
//  hash table memory allocation methods
//
//---------------------------------------------------------------------------
  
// method: findKey
//
// arguments:
//  long& index: (output) the list on which the item is found
//  const THashable& key: (input) the key to be found
//
// return: a boolean value indicating status
//
// this method determines if a key is contained in this hash table
// and positions the item with the given key accordingly.
// note this is a private method, the user doesn't need to know the
// index of the linked list in the table_d
//
template<class THashable, class TObject>
boolean HashTable<THashable, TObject>::findKey(long& index_a,
					       const THashable& key_a) {

  // get the key index and loop that linked list
  //
  long index = key_a.hash(getCapacity());
  
  for (boolean more = table_d(index).gotoFirst();
       more; more = table_d(index).gotoNext()) {
    
    if (key_a.eq(getCurrKey(index))) {

      // key is found, exit gracefully
      //
      index_a = index;
      return true;
    }
  }

  // key not found, return false
  //
  return false;
}

// end of include file
//
# endif