HashTable/HashTableGeneric.h

Go to the documentation of this file.

/*  Last edited: May 29 15:45 2002 (ac2) */

// #######################################################################

// SSAHA : Sequence Search and Alignment by Hashing Algorithm
// Version 3.2, released 1st March 2004
// Copyright (c) Genome Research 2002

// SSAHA is free software; you can redistribute it and/or modify 
// it under the terms of version 2 of the GNU General Public Licence
// as published by the Free Software Foundation.
 
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public Licence for more details.
 
// You should have received a copy of the GNU General Public Licence
// along with this program; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
// or see the on-line version at http://www.gnu.org/copyleft/gpl.txt

// #######################################################################

// Module Name  : HashTableGeneric
// File Name    : HashTableGeneric.h
// Language     : C++
// Module Author: Anthony J. Cox (ac2@sanger.ac.uk)

// Include guard:
#ifndef INCLUDED_HashTableGeneric
#define INCLUDED_HashTableGeneric

// Description:


#include <iosfwd>
#include <string>
#include <utility>
#include <algorithm>
#include <functional>
#include <cassert>
#include "GlobalDefinitions.h"
class SequenceReader;


// ### Class Declarations ###

typedef unsigned int PositionInHitList; 


// Class Name : NameReader
// Description: Sits inside an instance of HashTable giving out
// sequence names. These are either stored locally (NameReaderLocal)
// or grabbed from an instance of SourceReaderIndex (NameReaderIndex) 
class NameReader
{
 public:
  virtual ~NameReader() {}
  virtual const char* getSequenceName
    ( SequenceNumber seqNum ) const {return NULL;} //= 0;
  virtual void getSequenceName
    ( string& seqName, SequenceNumber seqNum ) const {} //= 0;
  virtual void saveSequenceNames( ostream& nameFile ) {}
  virtual void loadSequenceNames( istream& nameFile ) {}
  virtual SequenceNumber size( void ) const { return 0; } //= 0;
};

class NameReaderLocal : public NameReader, private vector<string>
{
 public:
  virtual ~NameReaderLocal() {}
  virtual const char* getSequenceName
  ( SequenceNumber seqNum ) const;
  virtual void getSequenceName
  ( string& seqName, SequenceNumber seqNum ) const;
  string& lastName()
  { 
    string dummy = "";
    push_back(dummy); return back(); 
  }
  virtual void saveSequenceNames( ostream& nameFile );
  virtual void loadSequenceNames
    ( istream& nameFile );
  virtual SequenceNumber size( void ) const
  {
    return vector<string>::size();
  }
  void pop_back( void ) 
  {
    vector<string>::pop_back();
  }
};

class SourceReaderIndex;
class NameReaderIndex : public NameReader
{
 public:
  NameReaderIndex( SourceReaderIndex& reader ) : reader_(reader) {}
  virtual ~NameReaderIndex() {}
  virtual const char* getSequenceName
  ( SequenceNumber seqNum ) const;
  virtual void getSequenceName
  ( string& seqName, SequenceNumber seqNum ) const;
  virtual SequenceNumber size( void ) const;
 private:
  SourceReaderIndex& reader_;
};






class SequenceAdapter
{
public:
  typedef WordSequence::size_type size_type;
  SequenceAdapter() {}
  virtual ~SequenceAdapter () {}

  virtual void link( const WordSequence& seq )
    { pSeq_ = &seq; }
  virtual Word operator[]( size_type j )
    { return (*pSeq_)[j]; }
  virtual size_type size( void ) const
    { return pSeq_->size()-1; }
protected:
  const WordSequence* pSeq_;
};  // ~class SequenceAdapter


class SequenceAdapterWithOverlap : public SequenceAdapter
{
public:  
  SequenceAdapterWithOverlap
  ( int bitsPerSymbol, int wordLength, int stepLength );
  virtual ~SequenceAdapterWithOverlap();

  virtual void link( const WordSequence& seq );
  virtual Word operator[]( size_type j );
  virtual size_type size( void ) const { return size_; }
protected:
  int bitsPerSymbol_;
  int wordLength_;
  int stepLength_;
  size_type size_;
  Word* maskLeft_;
  Word* maskRight_;

}; // ~class SequenceAdapterWithOverlap

class AdapterFactory
{
 public:
  SequenceAdapter* create
  ( int bitsPerSymbol, int wordLength, int stepLength ) 
  { 
    return 
    ( (wordLength==stepLength)
      ? new SequenceAdapter()
      : new SequenceAdapterWithOverlap
      ( bitsPerSymbol, wordLength, stepLength ) );
  } // ~create
        
}; // ~class AdapterFactory

// Class Name : HashTable
// Description: All hash table implementations will inherit their interface
// from this base class
class HashTableGeneric
{

  friend class HashTableFactory;

  // PUBLIC MEMBER FUNCTIONS
  public:

  // Constructors and Destructors

  // Function Name: Constructor
  // Arguments:     ostream&
  // Returns: N/A
  HashTableGeneric
  ( ostream& monitoringStream,
    const string& name,
    Allocator<PositionInHitList>& arrayAllocator );

  // Function Name:
  // Arguments:
  // TYPE  NAME  IN/OUT COMMENT
  // Returns: TYPE COMMENT
  virtual ~HashTableGeneric();
  // (NB destructor should be virtual if class is to be derived from)

  // Manipulator Functions

  // Function Name: createHashTable
  // Arguments: SequenceReader& (in), int (in), int (in)
  // Reads sequence information from an instance of SequenceReader and
  // uses it to create a hash table
  virtual void createHashTable
  ( SequenceReader& sequenceReader, int wordLength, int maxNumHits, 
    int stepLength = 0 );
  virtual int countWordsAndGetNames
    ( SequenceReader& sequenceReader, SequenceAdapter* seq );
  virtual void setupPointerArray( void );
  virtual void computePointerArray( void );
  virtual void setupHitList( void );
  virtual void hashAllWords
    ( SequenceReader& sequenceReader, SequenceAdapter* seq, int numSeqs );
  virtual void cleanupTempData( void );

  Allocator<PositionInHitList>* tempAlloc_;


  //  virtual void hashWords
  //( SequenceAdapter& thisSeq, SequenceNumber seqNum,  
  //  unsigned int* pHitsFoundSoFar_ ) =0;
  virtual void hashWords
    ( SequenceAdapter& thisSeq, SequenceNumber seqNum ) =0;
  virtual void countWords( SequenceAdapter& thisSeq ) =0;

  virtual void matchSequence
  ( WordSequence& seq, HitList& hitListFwd ) =0;

  virtual void setNumRepeats( int nr) =0;
  virtual void setSubstituteThreshold( int ns ) {}

  virtual char* getHitListStart( void ) const=0;
  virtual int getHitTypeSize( void ) const=0;
  virtual void allocateHitList( unsigned long size ) =0;
  virtual void loadHitList( unsigned long size ) =0;
  virtual void saveHitList( void ) =0;
  virtual void loadSequenceNames( void );
  virtual void saveSequenceNames( void );

  // Function Name: loadHashTable
  // Arguments: const string& (in)
  // Reads a pre-computed hash table into memory from a file
  // A hash table is stored as three files:
  //
  // 1. fileNameRoot.head has the following format
  // int stepLength_;
  // PositionInHitList pWordPositionInHitList_[ 2^(2*wordLength) ];
  // This stores an instance of the PositionInHitList type for each possible
  // value of Word (i.e. there are 2^(2*wordLength_) entries in all). Entry
  // number x of *pWordPositionInHitList_ tells you which entry of
  // *pHitListForAllWords_ contains the position of the first occurrence
  // of word x+1 in the subject sequence database.
  // NB wordLength is the length in bases of each hash word and is deduced by
  // loadHashTable from the size of this file.
  //
  // 2. fileNameRoot.body has the following format:
  // PositionInDatabase* pHitListForAllWords_;
  // This stores an instance of the PositionInDatabase type for each
  // occurrence of each Word. Only the first maxNumHits_ occurrences of
  // each Word are stored.
  // 
  // 3. fileNameRoot.name contained the name of each subject sequence, 
  // stored sequentially as strings.
  //  void loadHashTable( HashTableGeneric& ht, const string& fileNameRoot );
  virtual void loadHashTable( SourceReaderIndex* pSourceReader=NULL );

  // Function Name: saveHashTable
  // Arguments: const string& (in)
  // Save hash table into files (for subsequent retrieval by loadHashTable)
  // See description of HashTable::loadHashTable for details of file format 
  // used.
  //  void saveHashTable( HashTableGeneric& ht, const string& fileNameRoot );
  virtual void saveHashTable( void );





  // Accessor Functions
  // (NB all accessor functions should be 'const')

  // Function Name: getSequenceName
  // Arguments: string& (out), SequenceNumber& (in)
  // Places the name of the seqNum'th sequence in the database in seqName
  void getSequenceName
  ( string& seqName, SequenceNumber seqNum ) const;

  // Function Name: getSequenceName
  // Arguments: SequenceNumber& (in)
  // Returns: const char*
  // Returns C style string of the seqNum'th seq in the database
  // NB should be used with caution as the string only lasts as long
  // as the hash table, you have to copy it if you want to keep it
  // after the hash table's destructor is called for any reason.
  const char* getSequenceName
  ( SequenceNumber seqNum ) const;

  // Function Name: getSequenceSize
  // Arguments: SequenceNumber (in)
  // Returns the size of the seqNum'th sequence in the database.
  SequenceOffset getSequenceSize( SequenceNumber seqNum ) const;
  
  // Function Name: printHashStats
  // Prints some stats about the hash table
  virtual void printHashStats( void ); 

  bool isInitialized() const { return isInitialized_; }
  int  getWordLength() const { return wordLength_; }
  int  getStepLength() const { return stepLength_; }
  SequenceNumber getNumSequences() const;
  //  SequenceNumber getNumSequences() const { assert(1==0); }
  virtual int  getMaxNumHits() const { return maxNumHits_; }
  virtual void setMaxNumHits( int mnh ) { maxNumHits_ = mnh; }
  int  getBitsPerSymbol( void ) const { return bitsPerSymbol_; }
  SourceDataType getSourceDataType( void ) const { return sourceData_; }
  HitListFormatType getHitListFormat( void ) const 
    { return hitListFormat_; }
  virtual unsigned long getTotalNumWords( void ) const 
    { return wordsInDatabase_; }
  const NameReader& getNameReader() const { return *pNameReader_; }

  // Function Name:
  // Arguments:
  // TYPE  NAME  IN/OUT COMMENT
  // Returns: TYPE COMMENT
  
  // PROTECTED MEMBER FUNCTIONS 
  // (visible to this class and derived classes only)
  protected:

  // PRIVATE MEMBER FUNCTIONS
  // (visible to instances of this class only)
  private:
  HashTableGeneric( const HashTableGeneric&);             // NOT IMPLEMENTED
  HashTableGeneric& operator=(const HashTableGeneric&);   // NOT IMPLEMENTED

  // PROTECTED MEMBER DATA
  // (visible to this class and derived classes only)
  protected:
  // name_ identifies the hash table & is used as a prefix when 
  // saving/loading to/from files
  string         name_;

  // isInitialized_ is set to true once a hash table has been successfully
  // created, either by loading in from a file or creating from sequence data.
  bool           isInitialized_;

  // wordLength_ is passed in as an argument to HashTable::createHashTable.
  // The subject data is split into words, each containing wordLength_ base 
  // pairs. The hash table stores the positions of each word in the subject
  // data
  int            wordLength_;  

  // stepLength_ is passed in as an argument to HashTable::createHashTable
  // and specifies the interval in base pairs between successive hash words.
  // This must lie between 1 and wordLength_, and its default value is
  // wordLength_.
  int            stepLength_;


  // maxNumHits_ is passed in as an argument to HashTable::createHashTable,
  // and specifies the maximum number of occurrences of each word to be
  // stored in the hash table. If we find more than maxNumHits_ occurrences of
  // a particular hash word, then none of them are stored.
  int            maxNumHits_;

  // bitsPerSymbol_ refers to the number of bit per symbol contained in 
  // a word. In general, either 2 for DNA or 5 for protein, although no
  // reason why code shouldn't work with other values.
  int            bitsPerSymbol_;

  // sourceData_ is the type of data used to create the hash table.
  // Can't just use bitsPerSymbol_ to tell this because 5 bit data
  // can be generated from DNA by translating codons.
  SourceDataType sourceData_;

  // hitListFormat_ is an enum that describes the format used to store
  // the hit list. Set to gNotSpecified in HashTableGeneric and reset
  // to its final `proper' value in its subclass.
  HitListFormatType hitListFormat_;


  // monitoringStream_ specifies where error and progress messages are to be 
  // sent.
  ostream&       monitoringStream_; 

  // wordsInDatabase_ is the number of Words actually found in the subject
  // database
  unsigned long wordsInDatabase_;
  
  // numDifferentWords_ is the number of different possible Words of
  // the chosen word length and symbol size
  unsigned long numDifferentWords_;

  // This is temporary storage for the number of hits found for each word,
  // used during createHashTable.  
  PositionInHitList* pHitsFoundSoFar_;

  // This stores an instance of the PositionInHitList type for each possible
  // value of Word (i.e. there are 2^(2*wordLength_) entries in all). Entry
  // number x of *pWordPositionInHitList_ tells you which entry of
  // *pHitListForAllWords_ contains the position of the first occurrence
  // of word x+1 in the subject sequence database.
  PositionInHitList*  pWordPositionInHitList_; 

  // pArrayAllocator handles dynamic mem alloc for pWordPositionInHitList_
  Allocator<PositionInHitList>* pArrayAllocator_;

 

  // For each sequence in the subject database, this stores a string
  // containing the sequence name.
  //  vector<string*> sequenceNames_;
  NameReader* pNameReader_;

  // For each sequence in the subject database, this stores the number
  // of bases in the sequence.
  SequenceOffset* pSequenceSizes_;


}; // HashTableGeneric


class HashTableFactory
{
 public:
  HashTableFactory( ostream& monStream=cerr ) : monitoringStream_(monStream)
  {}

  // Function Name: createHashTable
  // Arguments: SequenceReader& (in), int (in), int (in)
  // Reads sequence information from an instance of SequenceReader and
  // uses it to create a hash table
  void createHashTable
  ( HashTableGeneric& ht, 
    SequenceReader& sequenceReader, int wordLength, int maxNumHits, 
    int stepLength = 0 )
  {
    ht.createHashTable
      ( sequenceReader, wordLength, maxNumHits, stepLength );
  }

  // Looks at the .name file of a set of saved hash table files, decides
  // what type of hash table it was from, creates the appropriate hash
  // table, loads the data into it and returns a pointer to its handiwork
  HashTableGeneric* loadHashTable
    ( const string& name, SourceReaderIndex* pReader=NULL );

  // Function Name: loadHashTable
  // Arguments: const string& (in)
  // Reads a pre-computed hash table into memory from a file
  // A hash table is stored as three files:
  //
  // 1. fileNameRoot.head has the following format
  // int stepLength_;
  // PositionInHitList pWordPositionInHitList_[ 2^(2*wordLength) ];
  // This stores an instance of the PositionInHitList type for each possible
  // value of Word (i.e. there are 2^(2*wordLength_) entries in all). Entry
  // number x of *pWordPositionInHitList_ tells you which entry of
  // *pHitListForAllWords_ contains the position of the first occurrence
  // of word x+1 in the subject sequence database.
  // NB wordLength is the length in bases of each hash word and is deduced by
  // loadHashTable from the size of this file.
  //
  // 2. fileNameRoot.body has the following format:
  // PositionInDatabase* pHitListForAllWords_;
  // This stores an instance of the PositionInDatabase type for each
  // occurrence of each Word. Only the first maxNumHits_ occurrences of
  // each Word are stored.
  // 
  // 3. fileNameRoot.name contained the name of each subject sequence, 
  // stored sequentially as strings.
  //  void loadHashTable( HashTableGeneric& ht, const string& fileNameRoot );
  void loadHashTable( HashTableGeneric& ht, SourceReaderIndex* pReader=NULL )
  {
    ht.loadHashTable(pReader);
  }



  // Function Name: saveHashTable
  // Arguments: const string& (in)
  // Save hash table into files (for subsequent retrieval by loadHashTable)
  // See description of HashTable::loadHashTable for details of file format 
  // used.
  //  void saveHashTable( HashTableGeneric& ht, const string& fileNameRoot );
  void saveHashTable( HashTableGeneric& ht )
  {
    ht.saveHashTable();
  }


  ostream& monitoringStream_;

};

// Class Name : HashTable
// Description: All hash table implementations will inherit their interface
// from this base class
template<typename T, class SUBCLASS> 
struct HashTableView : public HashTableGeneric // %%%% TBD private??
{

  friend class HashTableFactory;

  // PUBLIC MEMBER FUNCTIONS
  public:
  typedef T HitType; 

  // Constructors and Destructors

  // Function Name: Constructor
  // Arguments:     ostream&
  // Returns: N/A
  HashTableView( ostream& monitoringStream,
                 string name,
                 Allocator<HitType>& hitListAllocator,
                 Allocator<PositionInHitList>& arrayAllocator ) :
  HashTableGeneric
  ( monitoringStream, name, arrayAllocator )
    {
      pHitListAllocator_ =  hitListAllocator.clone
        (&pHitListForAllWords_, name+(string)".body", monitoringStream_ );
      //      pHitListAllocator_->link(&pHitListForAllWords_,name_+(string)".body");
    }

  // Function Name:
  // Arguments:
  // TYPE  NAME  IN/OUT COMMENT
  // Returns: TYPE COMMENT
  virtual ~HashTableView()
  { 
    monitoringStream_ << "destructing HashTableView ...\n";
    if ( isInitialized_ )
    {
      monitoringStream_ << "... deallocating memory\n";
      //      pHitListAllocator_->deallocate();
      delete pHitListAllocator_; // also deallocs hit list
      //      delete [] pHitListForAllWords_; 
    } // ~if 
    else 
    {
      monitoringStream_ 
      << "... never initialized, no memory deallocation required\n";
    } // ~else
  } // destructor

  // (NB destructor should be virtual if class is to be derived from)

  // Manipulator Functions

  virtual void hashWords
  ( SequenceAdapter& thisSeq, SequenceNumber seqNum ) =0;
  virtual void countWords( SequenceAdapter& thisSeq ) =0;

  

  // Accessor Functions
  // (NB all accessor functions should be 'const')



  // The next few lines make HashTable behave like an STL container

  typedef const HitType* iterator;
  typedef const HitType* const_iterator;

  virtual int getHitTypeSize( void ) const 
  {
    return sizeof(HitType);
  }

  virtual char* getHitListStart( void ) const 
  {
    return (char*) pHitListForAllWords_;
  }

  virtual void allocateHitList( unsigned long size )
  {
    //    pHitListForAllWords_=new HitType[size];
    pHitListAllocator_->allocate(size);
  }

  virtual void loadHitList( unsigned long size )
  {
    pHitListAllocator_->load(size);
  }

  virtual void saveHitList( void )
  {
    pHitListAllocator_->save();
  }




  const_iterator begin( Word w ) const
  {
    return pHitListForAllWords_ +
      ( ( w == 0 ) ? 0 : pWordPositionInHitList_[ w - 1 ] );
  } // ~const_iterator begin( Word w ) const

  const_iterator last( Word w ) const
  {  
    return pHitListForAllWords_ + ( pWordPositionInHitList_[ w ] ); 
  } // ~const_iterator last( Word w ) const

  const_iterator end( Word w ) const
  { 
    return( (size(w) > maxNumHits_) ? begin(w) : last(w) ); 
  } // ~const_iterator end( Word w ) const

  const int size( Word w ) const
  { 
    return( last(w) - begin(w) ); 
  } // ~const int size( Word w ) const

  //  inline SequenceNumber getSequence( const_iterator i ) const;
  //  inline SequenceOffset getOffset( const_iterator i ) const;

  template< class HITLIST >
  void matchWord
  ( Word queryWord, HITLIST& hitsFound, int baseOffset=0 ) const
  {
    // About 1/2 the exec time of a matchWord is spent calling end()
    // so bung it in a const variable TC 12.3.2 
    //    for( iterator i( begin( queryWord ) ); 
    // i != end( queryWord ); i++ )
    if ((queryWord&gCursedWord)!=(Word)0) return;
    const_iterator endWord(end(queryWord));
    for( iterator i( begin( queryWord ) ); i != endWord; ++i )
    { 
      hitsFound.addHit
        ( *i, baseOffset );
    } // ~for i

  } // ~template< class HITLIST > void matchWord


  template< class HITLIST >
  void matchWord
  ( const WordSequence& queryWords, 
    HITLIST& hitsFound, 
    int baseOffset=0 ) const
  {
    //    printf("HashTable::matchWord (multiple)\n");
    if (queryWords.size()==0) return;
    
    // WordSequenceIterator last 
    //    = const_cast<WordSequenceIterator>(queryWords.end());
    //   last--; 
    WordSequence::const_iterator last(&queryWords.back());

    for ( WordSequence::const_iterator thisWord(queryWords.begin());
            thisWord != last ; ++thisWord )
    {
      matchWord( *thisWord, hitsFound, baseOffset );
      baseOffset += wordLength_;
    } // ~for

  } // ~  template< class HITLIST > void matchWord



  // Function Name:
  // Arguments:
  // TYPE  NAME  IN/OUT COMMENT
  // Returns: TYPE COMMENT
  
  // PROTECTED MEMBER FUNCTIONS 
  // (visible to this class and derived classes only)
  protected:

  // PRIVATE MEMBER FUNCTIONS
  // (visible to instances of this class only)
  private:
  HashTableView( const HashTableView&);             // NOT IMPLEMENTED
  HashTableView& operator=(const HashTableView&);   // NOT IMPLEMENTED

  // PROTECTED MEMBER DATA
  // (visible to this class and derived classes only)
  protected:
  
  // This stores an instance of the PositionInDatabase type for each
  // occurrence of each Word. Only the first maxNumHits_ occurrences of
  // each Word are stored.
  HitType* pHitListForAllWords_;
  Allocator<HitType>* pHitListAllocator_;
  //  Allocator** ppHitListAllocator_;

}; // HashTableView


// Class Name : TopList
// Description: This class is used by HashTable::printHashStats
// to compute the top 10 words in the data base
class TopList : public vector<pair<int, Word> >
{
public:
  TopList( int size, int wordLength, int bitsPerSymbol=gBaseBits ) : 
    vector<pair<int, Word> >( size, pair<int, Word>(0,0) ),
    wordLength_( wordLength ), bitsPerSymbol_( bitsPerSymbol ) {}
  void push_back( pair<int, Word> p )
  {
    if ( p.first > back().first )
    { 

      vector<pair<int, Word> >::push_back( p );
      sort( begin(), end(), greater<pair<int, Word> >()  );
      pop_back();
    } // ~if                                    
  } // ~push_back

  friend ostream& operator<<
    ( ostream& os, TopList tl )
  {
    if (tl.bitsPerSymbol_==gBaseBits)
    {
     for( vector<pair<int, Word> >::iterator i(tl.begin()); 
          i != tl.end() ; ++i)
       cout << printWord( i->second, tl.wordLength_ ) 
            << ", " << i->first << " occurrences.\n";
    } // ~if 
    else if (tl.bitsPerSymbol_==gResidueBits )
    {
      for( vector<pair<int, Word> >::iterator i(tl.begin()); 
           i != tl.end() ; ++i)
        cout << printResidue( i->second, tl.wordLength_ ) 
             << ", " << i->first << " occurrences.\n";
    }
    else assert(1==0);
    return os;
  } // ~operator<<

 private:
  int wordLength_;
  int bitsPerSymbol_;

  
};

// Class Name : WordSequenceShifted
// Description: Constructed from an instance thisSeq of WordSequence.
// seqs_[i] consists of thisSeq left shifted by i bases, that is, the 1st
// base of seqs_[i] is the (i+1)st base of thisSeq. The purpose of this class
// is to enable the masking out of tandem repeats 
class WordSequenceShifted 
{
  public:
  WordSequenceShifted( const WordSequence& thisSeq, 
                       const HashTableGeneric& hashTable );
  Word& operator[]( unsigned long wordNum )
  {
    return( (seqs_[ wordNum%seqs_.size() ])[ wordNum/seqs_.size() ] );
  }


// NB size_ is not the number of bases in the sequence, it is the number of 
// hash words that may be obtained from the sequence

  //  void screenRepeats( HitList& hitsOut, int numRepeats );

  int size( void ) { return size_; }
 
  protected:
  //  const HashTable& hashTable_;
  vector<WordSequence> seqs_; 
  int size_; 
}; 


// ### Function Declarations ###

// Name:
// Arguments:
// TYPE  NAME  IN/OUT COMMENT
// Returns: TYPE COMMENT

// End of include guard:
#endif

// End of file HashTableGeneric.h

---