/*H+ TTGenericHash.h
*
*    SCCS ID: %Z%%M% %I% %E% SMI
*
*    Copyright (c) 1990-1993 Sun Microsystems, Inc.  All rights reserved.
*    See SUN_LEGAL_NOTICE file for terms of the license.
*
*    PURPOSE:
*
*    Defines the TTGenericHash class.
*
*    AUTHOR: Mark Soloway
*
*    REVISION HISTORY:
*
*    Who       When       Why                   
*    --------- ---------- -----------------------
*    MGS       09/12/90   Original creation.
*
*H-*/

/*C+ TTGenericHash
*
*    DESCRIPTION:
*
*    The TTGenericHash class a provides a way to create hash tables containing
*    any object sub-classed off of the TTGeneric object class.  The hash table
*    can have objects added to it, deleted from it, accessed randomly,
*    traversed in reverse order, and have other hash tables added to it.
*    When the hash table is destructed, delete is called on each of the items
*    in the hash table.  The hash address for an object added to the table
*    is a character string.
*
*    INHERITED CLASSES:
*
*    TTGeneric - Inheriting the TTGeneric class will allow the TTGenericHash
*                class to be treated as a TTGeneric object.  Therefore,
*                a TTGenericHash can contain a TTGenericHash.
*
*    LOCAL CLASSES:
*
*    HashTableEntry - Contains one entry in a hash table and the links to the
*                     previous and next items placed in the hash table as well
*                     as the next item in the current hash table bucket.
*
*    ORDINARY DATA MEMBERS:
*
*    int              numBuckets - Number of hash table buckets
*    HashTableEntry  *position   - Current traversal position
*    HashTableEntry  *start      - Pointer to the first hash table entry
*    HashTableEntry **table      - The actual hash table
*
*    PUBLIC MEMBER FUNCTIONS:
*
*    TTGenericHash (int size=101)            - Creates a hash table.  The first
*                                              prime number >= to the specified
*                                              size is the number of hash table
*                                              buckets.
*    void addItem (const char *address, TTGeneric *)
*                                            - Adds the specified item to the
*                                              hash table.
*    TTGeneric *removeItem (const char *address)
*                                            - Removes and returns the
*                                              item from the hash table.
*    TTGeneric *getItem (const char *address) const
*                                            - Gets the specified item from
*                                              the hash table.
*    TTGeneric *traverse (TTBoolean reset_flag, char* &address)
*                                            - Traverses the hash table in
*                                              reverse order of placement
*                                              in the hash table.  If the
*                                              reset flag is set, traversal
*                                              starts at the beginning of the
*                                              hash table.  The function
*                                              returns both the object pointer
*                                              and the hash address.
*    int getSize () const                    - Returns the number of buckets
*                                              in the hash table.
*    void clear ()                           - Clears the hash table and
*                                              destroys each item in the hash
*                                              table.
*    void dropItems ()                       - Drops the items in the hash
*                                              table without destroying them.
*    TTGenericHash &operator= (const TTGenericHash&)
*                                            - Allows assignment of one hash
*                                              table to another.
*    TTGeneric* &operator[] (const char *address) const
*                                            - Allows access to the specified
*                                              item in the hash table.  The
*                                              hash table entry can be read and
*                                              modified.
*    TTGenericHash &operator+ (const TTGenericHash&)
*                                            - Concatenates two hash tables.
*
*    PROTECTED MEMBER FUNCTIONS:
*
*    void initialize ()			     - Initialize the internals of
*					       the hash table.
*    int getPrime (int)			     - Return the closest prime >=
*					       to the specified integer.
*    int hashString (const char *) const     - Converts the specified string
*					       into a bucket number.
*    TTGeneric *privateTraverse (HashTableEntry*&, char*&) const 
*                                            - Provides a const traverse for
*                                              internal use.
*
*C-*/
#ifndef _TT_GENERIC_HASH_H
#define _TT_GENERIC_HASH_H

// Includes
#include <stddef.h>

#include "TTBoolean.h"
#include "TTGeneric.h"

// Class Definition
class TTGenericHash : public TTGeneric {
public:
  TTGenericHash (int size=101);
  TTGenericHash (const TTGenericHash&);
  ~TTGenericHash ();
  void           addItem (const char *, TTGeneric *);
  TTGeneric     *removeItem (const char *);
  TTGeneric     *getItem (const char *) const;
  TTGeneric     *traverse (TTBoolean, char*&);
  int            getSize () const { return numBuckets; }
  void           clear ();
  void           dropItems ();
  TTGenericHash &operator= (const TTGenericHash&);
  TTGeneric*    &operator[] (const char *) const;
  TTGenericHash &operator+ (const TTGenericHash&);

private:
  class HashTableEntry : public TTGeneric { 
  public: 
    HashTableEntry () 
      { 
        nextEntry = (HashTableEntry *) NULL; 
        rightEntry = (HashTableEntry *) NULL; 
        leftEntry = (HashTableEntry *) NULL; 
        address = (char *) NULL; 
        item = (TTGeneric *) NULL; 
      }  
  
    ~HashTableEntry () 
      { 
        if (address) delete address; 
      }  
  
    HashTableEntry *nextEntry;
    HashTableEntry *rightEntry; 
    HashTableEntry *leftEntry; 
    char           *address; 
    TTGeneric      *item; 
  }; 
  
  int              numBuckets;
  HashTableEntry  *position;
  HashTableEntry  *start;
  HashTableEntry **table;

  void       initialize (); 
  int        getPrime (int) const;
  int        hashString (const char *) const;
  TTGeneric *privateTraverse (HashTableEntry*&, char*&) const;
};

#endif /* _TT_GENERIC_HASH_H */
