home *** CD-ROM | disk | FTP | other *** search
/ PC World 1998 October / PCWorld_1998-10_cd.bin / software / prehled / komix / DATA.Z / HashTbl.hxx < prev    next >
Text File  |  1996-05-31  |  15KB  |  484 lines
  1. /*---------------------------------------------------------------------------
  2.  *
  3.  *    (c)    Westmount Technology    1991
  4.  *
  5.  *    File:         @(#)HashTbl.hxx    1.2    (1.7) (1.1)
  6.  *    Author:        sipi (original by K.E. Gorlen)
  7.  *    Description:    implementation of hash tables
  8.  *        A hash table is an unordered collection of objects in which
  9.  *          no object is duplicated. Duplicate objects are defined by
  10.  *          the function Hashable::isEqual.
  11.  *        The capacity() function returns 1/2 the capacity of the
  12.  *          hash table and the size() function returns the number of
  13.  *          objects currently in the hash table.
  14.  *        For efficiency, the capacity is always a power of two and
  15.  *        is doubled whenever the table becomes half full.
  16.  *
  17.  *---------------------------------------------------------------------------
  18.  SccsId = @(#)HashTbl.hxx    1.2    (1.7) (1.1)\t11 Nov 1993 Copyright 1992 Westmount Technology */
  19.  
  20. #ifndef HASHTBL_HXX
  21. #define HASHTBL_HXX
  22.  
  23. #ifndef TEMPLCONF_HXX
  24. #include "TemplConf.hxx"
  25. #endif
  26.  
  27. #if HAS_TEMPLATES
  28.  
  29. #ifndef FLEXARRAY_HXX
  30. #include <FlexArray.hxx>
  31. #endif
  32.  
  33. class Hashable {
  34.     public:
  35.     Hashable() {}
  36.     virtual ~Hashable();
  37.  
  38.     // Calculate a hash value for this object
  39.     //
  40.     virtual unsigned    hash() const = 0;
  41.  
  42.     // Compare the given key with the key from this Hashable
  43.     // If both are equal then return 1 else return 0
  44.     //
  45.     virtual int        isEqual(const Hashable& key) const = 0;
  46. };
  47.  
  48. class hash_iter;
  49. typedef Hashable *hashptr;
  50.  
  51. typedef FlexArray<hashptr> hashList;
  52.  
  53. class HashTbl {
  54.     friend class hash_iter;
  55.     private:
  56.     unsigned     count;        // number of objects in set 
  57.     unsigned     nbits;        // log base 2 of contents.capacity() 
  58.     unsigned     mask;        // contents.capacity()-1 
  59.     hashList    contents;    // array of pointers to Hashables
  60.     int        current;    // current in array for first/next
  61.  
  62.     private:
  63.     // Compute set allocation size.
  64.     // Round size up to the next highest power of two, if necessary
  65.     //
  66.     unsigned     setCapacity(unsigned);
  67.  
  68.     // Convert hash key into contents index
  69.     //
  70.     int         getIndex(unsigned long) const;
  71.  
  72.     // Search this set for the specified Hashable
  73.     // and return index of object if found or nil slot if not found
  74.     //
  75.     int         findIndexOf(const Hashable&) const;
  76.  
  77.     // Change the capacity of this HashTbl to new size
  78.     //
  79.     void         reSize(unsigned new_size);
  80.  
  81.     public:
  82.     static unsigned DEFAULT_SIZE;        // HashTbl size
  83.     static unsigned EXPANSION_FACTOR;    // HashTbl grow factor
  84.  
  85.     public:
  86.     HashTbl(unsigned size = HashTbl::DEFAULT_SIZE);
  87.     HashTbl(const HashTbl&);
  88.     ~HashTbl();
  89.     HashTbl& operator=(const HashTbl&);
  90.  
  91.     // Add an object to this HashTbl,
  92.     // making the HashTbl larger if it becomes half full.
  93.     // Return pointer to given object if it does not yet exist
  94.     // else return pointer to existing object in HashTbl.
  95.     //
  96.     Hashable    *add(Hashable&);
  97.  
  98.     // Add all objects from given HashTbl to this HashTbl
  99.     //
  100.     void        addAll(const HashTbl&);
  101.  
  102.     // Remove object from HashTbl
  103.     // Return pointer to given object of it is removed
  104.     // else return 0 if it does not exist in this HashTbl.
  105.     //
  106.     Hashable    *remove(const Hashable&);
  107.  
  108.     // Remove all objects from HashTbl
  109.     //
  110.     void         removeAll();
  111.  
  112.     // Remove all objects present in given HashTbl from HashTbl
  113.     //
  114.     void         removeAll(const HashTbl&);
  115.  
  116.     // Remove all objects from HashTbl and destruct each individual object
  117.     //
  118.     void        destructAll();
  119.  
  120.     // Find object in HashTbl using given key
  121.     // Returns 0 if not found else pointer to object
  122.     //
  123.     Hashable    *find(const Hashable& key) const
  124.                     {return contents.at(findIndexOf(key));}
  125.     Hashable    *operator[](const Hashable& key) const
  126.                     {return contents.at(findIndexOf(key));}
  127.  
  128.     // Return 1 if the specified HashTbl equals this HashTbl
  129.     // Else return 0
  130.     //
  131.     int operator==(const HashTbl&) const;
  132.  
  133.     // Return 1 if the specified HashTbl does not equal this HashTbl
  134.     // Else return 0
  135.     //
  136.     int operator!=(const HashTbl& tbl) const    {return !(*this==tbl);}
  137.  
  138.     // Walk through HashTbl using index
  139.     // Either 0 or a pointer to a Hashable is returned
  140.     //
  141.     Hashable     *at(int index) const    {return contents[index];}
  142.  
  143.     // Walk through HashTbl using first/next (no order is defined)
  144.     // Returns 0 if the HashTbl is empty or no next element.
  145.     //
  146.     Hashable    *first();
  147.     Hashable    *next();
  148.  
  149.     // The capacity() function returns 1/2 the capacity of the
  150.     // hash table and the size() function returns the number of
  151.     // objects currently in the hash table.
  152.     //
  153.     unsigned capacity() const    {return contents.capacity()>>1;}
  154.     unsigned size() const        {return count;}
  155. };
  156.  
  157. class hash_iter {
  158.     const HashTbl& tbl;
  159.     int curr_idx;
  160. public:
  161.         hash_iter(const HashTbl& tbl); 
  162.         ~hash_iter();   
  163.  
  164.     // Start iterating again
  165.     //
  166.     void rewind(void);
  167.  
  168.     // Go to next element if there is one
  169.     // Sets the iterator in the end-of-iteration state if positioned
  170.     // at the last element
  171.     //
  172.     void advance(void);
  173.  
  174.     // get current entry if there is one
  175.     // Effect is undefined if iterator is in end-of-iteration state
  176.     //
  177.     Hashable* get(void) const    { return tbl.at(curr_idx); }
  178.  
  179.     // testing: return non-0 if advanced over the last element
  180.     //
  181.     int end_of_iteration(void) const { return curr_idx == -1; }
  182.  
  183.     // Shorthands:
  184.     operator const void* (void) const
  185.             { return end_of_iteration()? 0: this; }
  186.     int operator ! (void) const    { return !end_of_iteration(); }
  187.     void operator++ (void)        { advance(); }
  188.     Hashable* operator() (void) const { return get(); }
  189. };
  190.  
  191. template<class Key, class Value> class hashTbl;
  192.  
  193. template<class Key, class Value>
  194. class hashIter : private hash_iter {
  195. public:
  196.     hash_iter::rewind;
  197.     hash_iter::advance;
  198.     hash_iter::end_of_iteration;
  199.     hash_iter::operator !;
  200.     hash_iter::operator++;
  201.  
  202.     hashIter(const hashTbl<Key,Value>& x): hash_iter(x) {}
  203.     Value* operator()()    { return (Value*) hash_iter::operator()();}
  204.     Value* get()        { return (Value*) hash_iter::get();}
  205.     operator const void* () const
  206.         { return hash_iter::operator const void*(); }
  207. };
  208.  
  209. template<class Key, class Value>
  210. class hashTbl : private HashTbl {
  211.     friend class hashIter<Key, Value>;
  212.     public:
  213.     hashTbl<Key,Value>& operator=(const hashTbl<Key,Value>& tbl)
  214.          {return (hashTbl<Key,Value> &) HashTbl::operator=(tbl);}
  215.     hashTbl(unsigned size = HashTbl::DEFAULT_SIZE)
  216.          : HashTbl(size) {}
  217.     hashTbl(const hashTbl<Key,Value> & tbl)
  218.          : HashTbl(tbl) {}
  219.     Value        *add(Key & x)
  220.          {return (Value*)HashTbl::add(x);}
  221.     void        addAll(const hashTbl<Key,Value> & tbl)
  222.          {HashTbl::addAll(tbl);}
  223.     Value        *remove(const Key & x )
  224.          {return (Value*) HashTbl::remove(x);}
  225.     Value        *find(const Key & x) const
  226.          {return (Value*) HashTbl::find(x);}
  227.     Value        *operator[](const Key & x) const
  228.          {return (Value*) HashTbl::operator[](x);}
  229.     int         operator==(const hashTbl<Key,Value> & tbl) const
  230.          {return HashTbl::operator==(tbl);}
  231.     int         operator!=(const hashTbl<Key,Value> & tbl) const
  232.          {return HashTbl::operator!=(tbl);}
  233.     Value         *at(int index) const
  234.          {return (Value*) HashTbl::at(index);}
  235.     Value        *first()
  236.          {return (Value*) HashTbl::first();}
  237.     Value        *next()
  238.          {return (Value*) HashTbl::next();}
  239.     void         removeAll()
  240.          {HashTbl::removeAll();}
  241.     void         removeAll(const hashTbl<Key,Value> & tbl)
  242.          {HashTbl::removeAll(tbl);}
  243.     void        destructAll()
  244.          {HashTbl::destructAll();}
  245.     unsigned     capacity() const
  246.          {return HashTbl::capacity();}
  247.     unsigned     size() const
  248.          {return HashTbl::size();}
  249. };
  250.  
  251. #else
  252.  
  253. #ifndef GENERICH
  254. #include <generic.h>
  255. #endif
  256.  
  257. #ifndef FLEXARRAY_HXX
  258. #include <FlexArray.hxx>
  259. #endif
  260.  
  261. class Hashable {
  262.     public:
  263.     Hashable() {}
  264.     virtual ~Hashable();
  265.  
  266.     // Calculate a hash value for this object
  267.     //
  268.     virtual unsigned    hash() const = 0;
  269.  
  270.     // Compare the given key with the key from this Hashable
  271.     // If both are equal then return 1 else return 0
  272.     //
  273.     virtual int        isEqual(const Hashable& key) const = 0;
  274. };
  275.  
  276. class hash_iter;
  277. typedef Hashable *hashptr;
  278. declare(FlexArray,hashptr);
  279. typedef hashptr_FlexArray hashList;
  280.  
  281. class HashTbl {
  282.     friend class hash_iter;
  283.     private:
  284.     unsigned     count;        // number of objects in set 
  285.     unsigned     nbits;        // log base 2 of contents.capacity() 
  286.     unsigned     mask;        // contents.capacity()-1 
  287.     hashList    contents;    // array of pointers to Hashables
  288.     int        current;    // current in array for first/next
  289.  
  290.     private:
  291.     // Compute set allocation size.
  292.     // Round size up to the next highest power of two, if necessary
  293.     //
  294.     unsigned     setCapacity(unsigned);
  295.  
  296.     // Convert hash key into contents index
  297.     //
  298.     int         getIndex(unsigned long) const;
  299.  
  300.     // Search this set for the specified Hashable
  301.     // and return index of object if found or nil slot if not found
  302.     //
  303.     int         findIndexOf(const Hashable&) const;
  304.  
  305.     // Change the capacity of this HashTbl to new size
  306.     //
  307.     void         reSize(unsigned new_size);
  308.  
  309.     public:
  310.     static unsigned DEFAULT_SIZE;        // HashTbl size
  311.     static unsigned EXPANSION_FACTOR;    // HashTbl grow factor
  312.  
  313.     public:
  314.     HashTbl(unsigned size = HashTbl::DEFAULT_SIZE);
  315.     HashTbl(const HashTbl&);
  316.     ~HashTbl();
  317.     HashTbl& operator=(const HashTbl&);
  318.  
  319.     // Add an object to this HashTbl,
  320.     // making the HashTbl larger if it becomes half full.
  321.     // Return pointer to given object if it does not yet exist
  322.     // else return pointer to existing object in HashTbl.
  323.     //
  324.     Hashable    *add(Hashable&);
  325.  
  326.     // Add all objects from given HashTbl to this HashTbl
  327.     //
  328.     void        addAll(const HashTbl&);
  329.  
  330.     // Remove object from HashTbl
  331.     // Return pointer to given object of it is removed
  332.     // else return 0 if it does not exist in this HashTbl.
  333.     //
  334.     Hashable    *remove(const Hashable&);
  335.  
  336.     // Remove all objects from HashTbl
  337.     //
  338.     void         removeAll();
  339.  
  340.     // Remove all objects present in given HashTbl from HashTbl
  341.     //
  342.     void         removeAll(const HashTbl&);
  343.  
  344.     // Remove all objects from HashTbl and destruct each individual object
  345.     //
  346.     void        destructAll();
  347.  
  348.     // Find object in HashTbl using given key
  349.     // Returns 0 if not found else pointer to object
  350.     //
  351.     Hashable    *find(const Hashable& key) const
  352.                     {return contents.at(findIndexOf(key));}
  353.     Hashable    *operator[](const Hashable& key) const
  354.                     {return contents.at(findIndexOf(key));}
  355.  
  356.     // Return 1 if the specified HashTbl equals this HashTbl
  357.     // Else return 0
  358.     //
  359.     int operator==(const HashTbl&) const;
  360.  
  361.     // Return 1 if the specified HashTbl does not equal this HashTbl
  362.     // Else return 0
  363.     //
  364.     int operator!=(const HashTbl& tbl) const    {return !(*this==tbl);}
  365.  
  366.     // Walk through HashTbl using index
  367.     // Either 0 or a pointer to a Hashable is returned
  368.     //
  369.     Hashable     *at(int index) const    {return contents[index];}
  370.  
  371.     // Walk through HashTbl using first/next (no order is defined)
  372.     // Returns 0 if the HashTbl is empty or no next element.
  373.     //
  374.     Hashable    *first();
  375.     Hashable    *next();
  376.  
  377.     // The capacity() function returns 1/2 the capacity of the
  378.     // hash table and the size() function returns the number of
  379.     // objects currently in the hash table.
  380.     //
  381.     unsigned capacity() const    {return contents.capacity()>>1;}
  382.     unsigned size() const        {return count;}
  383. };
  384.  
  385. class hash_iter {
  386.     const HashTbl& tbl;
  387.     int curr_idx;
  388. public:
  389.         hash_iter(const HashTbl& tbl); 
  390.         ~hash_iter();   
  391.  
  392.     // Start iterating again
  393.     //
  394.     void rewind(void);
  395.  
  396.     // Go to next element if there is one
  397.     // Sets the iterator in the end-of-iteration state if positioned
  398.     // at the last element
  399.     //
  400.     void advance(void);
  401.  
  402.     // get current entry if there is one
  403.     // Effect is undefined if iterator is in end-of-iteration state
  404.     //
  405.     Hashable* get(void) const    { return tbl.at(curr_idx); }
  406.  
  407.     // testing: return non-0 if advanced over the last element
  408.     //
  409.     int end_of_iteration(void) const { return curr_idx == -1; }
  410.  
  411.     // Shorthands:
  412.     operator const void* (void) const
  413.             { return end_of_iteration()? 0: this; }
  414.     int operator ! (void) const    { return !end_of_iteration(); }
  415.     void operator++ (void)        { advance(); }
  416.     Hashable* operator() (void) const { return get(); }
  417. };
  418.  
  419. #define hashTbl(key,keyval) name3(key,keyval,_HashTbl)
  420. #define hashIter(key,keyval) name3(key,keyval,_hash_iter)
  421.  
  422. #define hashIterdeclare2(key,keyval)                    \
  423. class hashIter(key,keyval) : private hash_iter {            \
  424. public:                                    \
  425.     hash_iter::rewind;                        \
  426.     hash_iter::advance;                        \
  427.     hash_iter::end_of_iteration;                    \
  428.     hash_iter::operator !;                        \
  429.     hash_iter::operator++;                        \
  430.                                     \
  431.     hashIter(key,keyval)(const hashTbl(key,keyval)& x): hash_iter(x){}\
  432.     keyval* operator()()    { return (keyval*) hash_iter::operator()();}\
  433.     keyval* get()        { return (keyval*) hash_iter::get();}    \
  434.     operator const void* () const                    \
  435.         { return hash_iter::operator const void*(); }        \
  436. }
  437.  
  438. #define HashTbldeclare2(key,keyval)                    \
  439. class hashTbl(key,keyval) : private HashTbl {                \
  440.     friend class hashIter(key,keyval);                \
  441.     public:                                \
  442.     hashTbl(key,keyval) & operator=(const hashTbl(key,keyval) & tbl)\
  443.          {return (hashTbl(key,keyval) &) HashTbl::operator=(tbl);}    \
  444.     hashTbl(key,keyval) (unsigned size = HashTbl::DEFAULT_SIZE)    \
  445.          : HashTbl(size) {}                        \
  446.     hashTbl(key,keyval) (const hashTbl(key,keyval) & tbl)        \
  447.          : HashTbl(tbl) {}                        \
  448.     keyval        *add(key & x)                    \
  449.          {return (keyval*)HashTbl::add(x);}                \
  450.     void        addAll(const hashTbl(key,keyval) & tbl)        \
  451.          {HashTbl::addAll(tbl);}                    \
  452.     keyval        *remove(const key & x )                \
  453.          {return (keyval*) HashTbl::remove(x);}            \
  454.     keyval        *find(const key & x) const            \
  455.          {return (keyval*) HashTbl::find(x);}            \
  456.     keyval        *operator[](const key & x) const        \
  457.          {return (keyval*) HashTbl::operator[](x);}            \
  458.     int         operator==(const hashTbl(key,keyval) & tbl) const\
  459.          {return HashTbl::operator==(tbl);}                \
  460.     int         operator!=(const hashTbl(key,keyval) & tbl) const\
  461.          {return HashTbl::operator!=(tbl);}                \
  462.     keyval         *at(int index) const                \
  463.          {return (keyval*) HashTbl::at(index);}            \
  464.     keyval        *first()                    \
  465.          {return (keyval*) HashTbl::first();}            \
  466.     keyval        *next()                        \
  467.          {return (keyval*) HashTbl::next();}            \
  468.     void         removeAll()                    \
  469.          {HashTbl::removeAll();}                    \
  470.     void         removeAll(const hashTbl(key,keyval) & tbl)    \
  471.          {HashTbl::removeAll(tbl);}                    \
  472.     void        destructAll()                    \
  473.          {HashTbl::destructAll();}                    \
  474.     unsigned     capacity() const                \
  475.          {return HashTbl::capacity();}                \
  476.     unsigned     size() const                    \
  477.          {return HashTbl::size();}                    \
  478. };                                    \
  479.      hashIterdeclare2(key,keyval)
  480.  
  481. #endif /* HAS_TEMPLATES */
  482.  
  483. #endif /* HASHTBL_HXX */
  484.