/////////////////////////////////////////////////////////////////////////////////////////
// PROGRAMER: Chad Langston, clangsto@vt.edu
// NAME: HashT.h
// LASTCOMPILED: 8/5/2000
// OS: Windows 95 SE
// COMPILER: MSVC++ 6.0(service pack4)
//
// SUMMARY:
// This templated hash takes one parameter, an ItemType. ItemType is the type of data
// that is to be inserted in the hash table. It does not provide a hash function. The
// user of this template must implement their own hashing function. NOTE: the users
// hash indexing function has a huge impact on the efficiency of this hash. This hash
// template stores pointers to ItemTypes. So, if the user is storing different types
// of derived class, they can instantiate the hash using their base class and
// effectively store any of the derived classes. Also, the user does not need to
// specify an empty marker or a tomb marker. The status of a slot is taken care of
// internally.
//
// ASSUMTIONS:
// For this hash to work properly the user needs to overload the == and != operators
// for their ItemType. These operators should compare one field only, the field they
// used as their key value. They also need to overload the output stream insertion
// operator, "ostream& operator << (ostream& out, ItemType item)". And, if their
// ItemType contains dynamic data they also need to overload the assignment operator
// and provide a copy constructor.
/////////////////////////////////////////////////////////////////////////////////////////
#ifndef HASHT_H
#define HASHT_H
#include <iostream> //used by the print function
#include <iomanip>
using namespace std;
namespace hashEnum {
//enumerated type used by the probe function
enum SlotStatus { EMPTY, ITEM_LOCATED, FULL };
}
template <class ItemType> class HashT
{
public:
//CONSTRUCTORS, DESTRUCTORS AND OVERLOADED OPERATORS
HashT(int size = 1);
//-----------------------------------------------------------------------------------
// FUNCTION: HashT
// PURPOSE: to initialize the member variables of a HashT object
// PARAMETERS: int variable, size - the size of the hash table
// CALLED BY: anyone who instantiates a HashT object with the given parameters
// CALLS: none
// PRE: none
// POST: tableSize is set to size or 1 if size is not passed to the function
// a new array of ItemType pointers of size size is allocated
// a new array of bool variables of size size is allocated
// each element of the array of ItemType pointers is NULL
// each element of the array of bool variables is false
//-----------------------------------------------------------------------------------
~HashT();
//-----------------------------------------------------------------------------------
// FUNCTION: ~HashT
// PURPOSE: to dealocate dynamically allocated memory
// PARAMETERS: none
// CALLED BY: the system when a HashT object goes out of scope
// CALLS: none
// PRE: none
// POST: dynamically allocated memory has been dealocated
//-----------------------------------------------------------------------------------
HashT(const HashT<ItemType>& source);
//-----------------------------------------------------------------------------------
// FUNCTION: HashT
// PURPOSE: to make deep copies of a HashT<ItemType> object when the object has
// been initialized with a default value when it is declared or has been
// passed to a function.
// PARAMETERS: HashT<ItemType> object by constant reference
// CALLED BY: anyone who instantiates a HashT object with the given parameter
// CALLS: none
// PRE: none
// POST: the HashT<ItemType> object is now a deep copy of the parameter
//-----------------------------------------------------------------------------------
HashT<ItemType>& operator = (const HashT<ItemType>& source);
//-----------------------------------------------------------------------------------
// FUNCTION: =
// PURPOSE: to make deep copies of a HashT<ItemType> object when one object of
// type HashT<ItemType> has been assigned to another object of type
// HashT<ItemType>.
// PARAMETERS: HashT<ItemType> object by constant reference
// CALLED BY: anyone who assigns one object of type HashT<ItemType> to another
// object of type HashT<ItemType>.
// CALLS: none
// PRE: none
// POST: the left hand operand of type, HashT<ItemType>, is now a deep copy
// of the right hand operand of type HashT<ItemType>.
//-----------------------------------------------------------------------------------
//METHODS AND BEHAVIORS
bool find(int& idx, const ItemType& toFind);
//-----------------------------------------------------------------------------------
// FUNCTION: find
// PURPOSE: to find an object of type ItemType in the array of dynamically
// created ItemType objects.
// PARAMETERS: the hashed location of the item to find, idx
// the item the user wishes to find, toFind
// CALLED BY: the class user
// CALLS: probe(idx, toFind)
// PRE: ItemType can compare for == and !=
// POST: if toFind is in the hash table, returns true and the location of toFind
// is copied to idx.
// if toFind is not in the hash, returns false and the last location
// probed is copied to idx.
//-----------------------------------------------------------------------------------
bool get(int& idx, ItemType& itemToGet);
//-----------------------------------------------------------------------------------
// FUNCTION: get
// PURPOSE: to retrieve an object of type ItemType from the array of dynamically
// created ItemType objects.
// PARAMETERS: the hashed location of the item to get, idx
// the item that the user wishes to get, itemToGet
// CALLED BY: the class user
// CALLS: probe(idx, itemToGet)
// PRE: ItemType can compare for == and !=, and ItemType supports assignment.
// itemToGet has allready been declared.
// POST: If itemToGet is in the hash table, returns true, the location of
// itemToGet is copied to idx, and the sends the item from the hash table
// to itemToGet.
// If toFind is not in the hash, returns false and the last location
// probed is copied to idx.
//-----------------------------------------------------------------------------------
int insert(int& idx, const ItemType& newItem);
//-----------------------------------------------------------------------------------
// FUNCTION: insert
// PURPOSE: to insert an object of type ItemType into the hash table.
// PARAMETERS: the hashed location of the item to insert, idx
// the item that the user wishes to insert, newItem
// CALLED BY: the class user
// CALLS: probe(idx, newItem)
// PRE: ItemType can compare for == and !=, and ItemType supports assignment.
// POST: If newItem does not exist, returns 1, and newItem is inserted into
// the hash table.
// If newItem allready exists, returns 0.
// If the hash table is full, returns -1.
//-----------------------------------------------------------------------------------
bool save(int& idx, const ItemType& toSave);
//-----------------------------------------------------------------------------------
// FUNCTION: save
// PURPOSE: to overwrite an object of type ItemType that is stored in the hash
// table.
// PARAMETERS: the hashed location of the item to save, idx
// the item that the user wishes to save, toSave
// CALLED BY: the class user
// CALLS: probe(idx, toSave)
// PRE: ItemType can compare for == and !=, and ItemType supports assignment.
// POST: If toSave is in the hash table, returns true and overwrites the item
// in the hash table == toSave with toSave.
// If toSave is not in the hash, returns false.
//-----------------------------------------------------------------------------------
bool remove(int& idx, const ItemType& toRemove);
//-----------------------------------------------------------------------------------
// FUNCTION: remove
// PURPOSE: to remove an object of type ItemType that is stored in the hash
// table.
// PARAMETERS: the hashed location of the item to remove, idx
// the item that the user wishes to remove, toRemove
// CALLED BY: the class user
// CALLS: probe(idx, toRemove)
// PRE: ItemType can compare for == and !=, and ItemType supports assignment.
// POST: If toRemove is in the hash table, returns true and sets the isTomb
// boolean variable = true at the idx returned by the probe function.
// If toRemove is not in the hash, returns false.
//-----------------------------------------------------------------------------------
void print(ostream& out, int width = 0);
//-----------------------------------------------------------------------------------
// FUNCTION: print
// PURPOSE: output the contents of the hash table.
// PARAMETERS: an ostream object by reference
// an integer, width - offsets the output width characters
// CALLED BY: the class user
// CALLS: none
// PRE: the ostream object has allready been declared.
// POST: the contents of the hash table are printed to out
//-----------------------------------------------------------------------------------
void clear();
//-----------------------------------------------------------------------------------
// FUNCTION: clear
// PURPOSE: clear the hash table.
// PARAMETERS: none
// CALLED BY: the class user
// CALLS: none
// PRE: none
// POST: all dynamically allocated items of type ItemType have been dealocated
// each element of the array of ItemType pointers is NULL
// each element of the array of bool variables is false
//-----------------------------------------------------------------------------------
int size();
//-----------------------------------------------------------------------------------
// FUNCTION: size
// PURPOSE: return the size of the hash table
// PARAMETERS: none
// CALLED BY: the class user
// CALLS: none
// PRE: none
// POST: none
//-----------------------------------------------------------------------------------
private:
int tableSize;
bool* isTomb; //points to a dynamically created array of bools
ItemType** items; //points to a dynamically created array of item pointers
hashEnum::SlotStatus probe(int& idx, const ItemType& item);
//-----------------------------------------------------------------------------------
// FUNCTION: probe
// PURPOSE: return an enumerated type describing the status of the hash table
// and sends the appropriate index to the parameter idx.
// PARAMETERS: an int variable by reference, idx.
// an ItemType object by constant reference, item
// CALLED BY: the class user
// CALLS: none
// PRE: idx has allready been declared.
// POST: If Item exists, returns ITEM_LOCATED and sets idx = location of Item
// If item does not exist, returns EMPTY and sets idx = the empty location
// or the first dead slot.
// If hash is full, returns FULL. idx does not change
//-----------------------------------------------------------------------------------
};//end of templated class HashT
|