Public Types | Public Member Functions | Public Attributes | Private Member Functions | Static Private Member Functions | Private Attributes | Static Private Attributes

chomp::homology::hashedset< element > Class Template Reference

This is a template for a set of objects of the given type. More...

#include <hashsets.h>

List of all members.

Public Types

typedef element value_type
 The type of elements stored in the set.

Public Member Functions

 hashedset (int_t initialsize=0, int bequiet=1)
 The default constructor for creating an empty set of objects.
 hashedset (const hashedset< element > &s)
 The copy constructor.
hashedset & operator= (const hashedset< element > &s)
 The assignment operator.
 ~hashedset (void)
 The destructor.
int_t getnumber (const element &e) const
 Finds the given element and returns its number.
bool checknum (int_t n) const
 Checks if the given number is an index of some element in the set, that is, if the number is non-negative and strictly smaller than the number of elements in the set.
bool check (const element &e) const
 Checks if the given element is in the set.
const element & operator[] (int_t n) const
 Returns the element with the given number from the set.
const element & get (int_t n) const
 Returns the element with the given number from the set.
const element & front () const
 Returns the last element in the set.
const element & top () const
 Returns the last element in the set.
int_t add (const element &e)
 Adds the given element to the set and returns its number.
int_t push (const element &e)
 Adds an element to the set (this is an equivalent of 'add').
int_t push_back (const element &e)
 Adds an element to the set (this is an equivalent of 'add').
int remove (const element &e)
 Removes the given element from the set.
int removenum (int_t n)
 Returns an element with the given number from the set.
int_t pop ()
 Removes the last element from the set.
hashedset< element > & add (const hashedset< element > &s)
 Adds an entire set of elements to the set.
hashedset< element > & remove (const hashedset< element > &s)
 Removes an entire set of elements from the set.
int_t size () const
 Returns the number of elements in the set.
bool empty () const
 Returns true if the set is empty. Otherwise returns false.
void swap (hashedset< element > &other)
 Swaps two hashed sets by swapping their internal data.
bool operator== (const hashedset< element > &other) const
 Verifies whether two hashed sets have the same elements.
void intersection (const hashedset< element > &s1, const hashedset< element > &s2)
 Computes the intersection of two hashed sets and adds the result to the current set.

Public Attributes

hashstat * stat
 Hashed set statistics.

Private Member Functions

int_t hashfind (const element &e, int_t *addpos=NULL) const
 Finds the position in the hashing table at which the number of the given element should be.
void rehash (int_t newsize=0)
 Replace the old hashing table with a new one.

Static Private Member Functions

static bool numberisprime (const int_t &n)
 Verifies whether the given number is prime or not.
static int_t rounduptoprime (int_t n)
 Rounds up the given number to a prime number.

Private Attributes

int_t nelem
 The number of elements stored in the set.
multitable< element > tab
 The table of these elements.
int hashing
 Is the hashing table in use?
int_t hashsize
 The size of the hashing table.
int_t hashcleared
 The number of cleared entries in the hashing table.
multitable< int_t > hashtable
 The hashing table.

Static Private Attributes

static const int_t InitHashSize
 The default initial size of a hashing table.
static const int_t InitTabSize
 The initial size of a table in a hashed set.
static const int_t StartHashingSize
 The minimal number of elements above which hashing table is actually used.

Detailed Description

template<class element>
class chomp::homology::hashedset< element >

This is a template for a set of objects of the given type.

Each of the objects should have two functions for generating hashing keys: "int_t hashkey1 (const object &x)" and "int_t hashkey2 (x)". Note: If you remove elements which are not at the end of the set, then the numbers of other elements can change! In the current solution, the last element is put in place of the removed one, but this behavior may be changed in the future versions of this template.

Definition at line 130 of file hashsets.h.

Member Typedef Documentation

template<class element>
typedef element chomp::homology::hashedset< element >::value_type

The type of elements stored in the set.

Definition at line 134 of file hashsets.h.

Constructor & Destructor Documentation

template<class element >
chomp::homology::hashedset< element >::hashedset ( int_t  initialsize = 0,
int  bequiet = 1 
) [explicit]

The default constructor for creating an empty set of objects.

If you expect the set to keep a lot of elements, you may want to set the initial size to something large.

Definition at line 296 of file hashsets.h.

References chomp::homology::hashedset< element >::hashsize, chomp::homology::hashedset< element >::rounduptoprime(), and chomp::homology::hashedset< element >::stat.

                                                            :
        nelem (0), tab ((initialsize > 0) ? initialsize :
                int_t (InitTabSize)),
        hashing (0),
        hashsize (initialsize + (initialsize >> 2) + InitHashSize),
        hashcleared (0), hashtable (hashsize)
{
        hashedset<element>::rounduptoprime (hashsize);
        if (bequiet)
                stat = NULL;
        else
                stat = new hashstat;
        return;
} /* hashedset<element>::hashedset */

template<class element>
chomp::homology::hashedset< element >::hashedset ( const hashedset< element > &  s  ) 

The copy constructor.

Definition at line 312 of file hashsets.h.

References chomp::homology::hashedset< element >::stat.

                                                         :
        nelem (s. nelem), tab (s. tab),
        hashing (s. hashing), hashsize (s. hashsize),
        hashcleared (s. hashcleared), hashtable (s. hashtable)
{
        if (s. stat)
                stat = new hashstat;
        else
                stat = NULL;
        return;
} /* hashedset<element>::hashedset */

template<class element >
chomp::homology::hashedset< element >::~hashedset ( void   ) 

The destructor.

Definition at line 344 of file hashsets.h.

References chomp::homology::sout, and chomp::homology::hashedset< element >::stat.

{
        if (!stat)
                return;
        sout << "  " << *stat << '\n';
        delete stat;
        stat = NULL;
        return;
} /* hashedset<element>::~hashedset */

Member Function Documentation

template<class element>
int_t chomp::homology::hashedset< element >::add ( const element &  e  ) 

Adds the given element to the set and returns its number.

If the element was already in the set, it is not added the second time, only its number is returned.

Definition at line 413 of file hashsets.h.

References chomp::homology::hashedset< element >::hashcleared, chomp::homology::hashedset< element >::hashfind(), chomp::homology::hashedset< element >::hashing, chomp::homology::hashedset< element >::hashsize, chomp::homology::hashedset< element >::hashtable, chomp::homology::hashedset< element >::nelem, chomp::homology::hashedset< element >::rehash(), chomp::homology::hashedset< element >::StartHashingSize, and chomp::homology::hashedset< element >::tab.

Referenced by chomp::homology::hashedset< element >::add(), chomp::homology::hashedset< element >::hashfind(), chomp::homology::hashedset< element >::intersection(), chomp::homology::hashedset< element >::push(), and chomp::homology::hashedset< element >::push_back().

{
        if (!hashing)
        {
                for (int_t i = 0; i < nelem; ++ i)
                {
                        if (tab (i) == e)
                                return i;
                }
                tab [nelem ++] = e;
                if (nelem >= StartHashingSize)
                {
                        hashing = 1;
                        rehash ();
                }
                return (nelem - 1);
        }

        // rehash if there is very little free space in the hashing table
        if (hashsize - hashcleared < nelem + (nelem >> 1) + 19)
                rehash ();

        // find the position of the element's number in the hashing table
        int_t addpos = -1;
        int_t pos = hashfind (e, &addpos);

        // if it alread was in the set, then just return its number
        if (hashtable (pos) >= 0)
                return hashtable (pos);

        // add this element to the set and return its new number
        if (addpos >= 0)
                pos = addpos;
        hashtable [pos] = nelem;
        tab [nelem] = e;
        return nelem ++;
} /* hashedset<element>::add */

template<class element>
hashedset< element > & chomp::homology::hashedset< element >::add ( const hashedset< element > &  s  ) 

Adds an entire set of elements to the set.

Definition at line 538 of file hashsets.h.

References chomp::homology::hashedset< element >::add(), and chomp::homology::hashedset< element >::size().

{
        int_t n = s. size ();
        for (int_t i = 0; i < n; ++ i)
                add (s [i]);
        return *this;
} /* hashedset<element>::add */

template<class element>
bool chomp::homology::hashedset< element >::check ( const element &  e  )  const [inline]

Checks if the given element is in the set.

Returns true if yes, false if no.

Definition at line 380 of file hashsets.h.

References chomp::homology::hashedset< element >::getnumber().

Referenced by chomp::homology::hashedset< element >::intersection(), and chomp::homology::hashedset< element >::remove().

{
        return (getnumber (e) >= 0);
} /* hashedset<element>::check */

template<class element >
bool chomp::homology::hashedset< element >::checknum ( int_t  n  )  const [inline]

Checks if the given number is an index of some element in the set, that is, if the number is non-negative and strictly smaller than the number of elements in the set.

Returns true if yes, false if no.

Definition at line 374 of file hashsets.h.

References chomp::homology::hashedset< element >::nelem.

{
        return ((n >= 0) && (n < nelem));
} /* hashedset<element>::checknum */

template<class element >
bool chomp::homology::hashedset< element >::empty (  )  const [inline]

Returns true if the set is empty. Otherwise returns false.

Definition at line 567 of file hashsets.h.

References chomp::homology::hashedset< element >::nelem.

{
        return !nelem;
} /* hashedset<element>::empty */

template<class element >
const element & chomp::homology::hashedset< element >::front (  )  const [inline]

Returns the last element in the set.

Definition at line 401 of file hashsets.h.

References chomp::homology::hashedset< element >::nelem.

{
        return get (nelem - 1);
} /* hashedset<element>::front */

template<class element >
const element & chomp::homology::hashedset< element >::get ( int_t  n  )  const [inline]

Returns the element with the given number from the set.

Definition at line 387 of file hashsets.h.

References chomp::homology::hashedset< element >::nelem, and chomp::homology::hashedset< element >::tab.

{
        if ((n < 0) || (n >= nelem))
                throw "Trying to get an element out of range.";
        return tab (n);
} /* hashedset<element>::get */

template<class element>
int_t chomp::homology::hashedset< element >::getnumber ( const element &  e  )  const

Finds the given element and returns its number.

Returns -1 if the element is not in the set.

Definition at line 355 of file hashsets.h.

References chomp::homology::hashedset< element >::hashfind(), chomp::homology::hashedset< element >::hashing, chomp::homology::hashedset< element >::hashtable, chomp::homology::hashedset< element >::nelem, and chomp::homology::hashedset< element >::tab.

Referenced by chomp::homology::hashedset< element >::check().

{
        if (hashing)
        {
                int_t pos = hashfind (e);
                return (hashtable (pos));
        }
        else
        {
                for (int_t i = 0; i < nelem; ++ i)
                {
                        if (tab (i) == e)
                                return i;
                }
                return -1;
        }
} /* hashedset<element>::getnumber */

template<class element>
int_t chomp::homology::hashedset< element >::hashfind ( const element &  e,
int_t *  addpos = NULL 
) const [private]

Finds the position in the hashing table at which the number of the given element should be.

If there is -1 there, then the number's element should be written there if adding. Saves to 'addposition' the first cleared position in the hashing table if found or sets it to -1 otherwise.

Definition at line 634 of file hashsets.h.

References chomp::homology::hashedset< element >::add(), chomp::homology::hashedset< element >::hashing, chomp::homology::hashkey1(), chomp::homology::hashkey2(), chomp::homology::hashedset< element >::hashsize, chomp::homology::hashedset< element >::hashtable, chomp::homology::hashedset< element >::stat, and chomp::homology::hashedset< element >::tab.

Referenced by chomp::homology::hashedset< element >::add(), chomp::homology::hashedset< element >::getnumber(), chomp::homology::hashedset< element >::rehash(), and chomp::homology::hashedset< element >::remove().

{
        if (!hashing)
                throw "Hashing is turned off.";

        int_t key = hashkey1 (e);
        if (key < 0)
                key = -(key + 1);
        int_t pos = key % hashsize;
        if (addpos)
                *addpos = -1;

        // start updating hashing statistics
        if (stat)
                ++ (stat -> hashhits);

        // find the position of the element in the hashing table
        int_t number;
        int_t add = 0;
        while ((number = hashtable (pos)) != -1)
        {
                if ((number >= 0) && (e == tab (number)))
                        return (pos);
                if (addpos && (*addpos < 0) && (number == -2))
                        *addpos = pos;
                if (!add)
                {
                        int_t key = hashkey2 (e);
                        if (key < 0)
                                key = -(key + 1);
                        add = key % (hashsize - 1) + 1;
                }
                pos += add;
                if (pos >= hashsize)
                        pos -= hashsize;
                if (stat)
                        ++ (stat -> hashmisses);
        }

        // return the position located in the hashing table
        return (pos);

} /* hashedset<element>::hashfind */

template<class element>
void chomp::homology::hashedset< element >::intersection ( const hashedset< element > &  s1,
const hashedset< element > &  s2 
) [inline]

Computes the intersection of two hashed sets and adds the result to the current set.

Definition at line 606 of file hashsets.h.

References chomp::homology::hashedset< element >::add(), chomp::homology::hashedset< element >::check(), chomp::homology::hashedset< element >::size(), and chomp::homology::hashedset< element >::tab.

{
        int_t size1 = s1. size ();
        int_t size2 = s2. size ();

        if (size1 <= size2)
        {
                for (int_t i = 0; i < size1; ++ i)
                {
                        const element &elem = s1. tab [i];
                        if (s2. check (elem))
                                this -> add (elem);
                }
        }
        else
        {
                for (int_t i = 0; i < size2; ++ i)
                {
                        const element &elem = s2. tab [i];
                        if (s1. check (elem))
                                this -> add (elem);
                }
        }
        return;
} /* hashedset<element>::intersection */

template<class element >
bool chomp::homology::hashedset< element >::numberisprime ( const int_t &  n  )  [inline, static, private]

Verifies whether the given number is prime or not.

Note: This procedure is quite inefficient for large numbers.

Definition at line 723 of file hashsets.h.

{
        if (n < 2)
                return 0;

        int_t i = 2;
        while (i * i <= n)
        {
                if (!(n % i))
                        return false;
                ++ i;
        }

        return true;
} /* hashedset<element>::numberisprime */

template<class element>
hashedset< element > & chomp::homology::hashedset< element >::operator= ( const hashedset< element > &  s  ) 

The assignment operator.

Definition at line 326 of file hashsets.h.

{
        if (this == &s)
                return *this;

        if (s. stat)
                stat = new hashstat (*stat);
        nelem = s. nelem;
        tab = s. tab;
        hashing = s. hashing;
        hashsize = s. hashsize;
        hashcleared = s. hashcleared;
        hashtable = s. hashtable;

        return *this;
} /* multitable<element>::operator = */

template<class element>
bool chomp::homology::hashedset< element >::operator== ( const hashedset< element > &  other  )  const [inline]

Verifies whether two hashed sets have the same elements.

Uses the standard comparison operator for the elements.

Definition at line 593 of file hashsets.h.

{
        if (this -> nelem != other. nelem)
                return false;
        for (int_t i = 0; i < nelem; ++ i)
        {
                if (!other. check (this -> tab [i]))
                        return false;
        }
        return true;
} /* hashedset<element>::swap */

template<class element >
const element & chomp::homology::hashedset< element >::operator[] ( int_t  n  )  const [inline]

Returns the element with the given number from the set.

Definition at line 395 of file hashsets.h.

{
        return get (n);
} /* hashedset<element>::operator [] */

template<class element >
int_t chomp::homology::hashedset< element >::pop (  )  [inline]

Removes the last element from the set.

Throws an exception if the set is empty.

Definition at line 530 of file hashsets.h.

References chomp::homology::hashedset< element >::nelem, and chomp::homology::hashedset< element >::removenum().

{
        if (!nelem)
                throw "Trying to remove an element from an empty set.";
        return removenum (nelem - 1);
} /* hashedset<element>::pop */

template<class element>
int_t chomp::homology::hashedset< element >::push ( const element &  e  )  [inline]

Adds an element to the set (this is an equivalent of 'add').

Definition at line 452 of file hashsets.h.

References chomp::homology::hashedset< element >::add().

{
        return add (e);
} /* hashedset<element>::push */

template<class element>
int_t chomp::homology::hashedset< element >::push_back ( const element &  e  )  [inline]

Adds an element to the set (this is an equivalent of 'add').

Definition at line 458 of file hashsets.h.

References chomp::homology::hashedset< element >::add().

{
        return add (e);
} /* hashedset<element>::push_back */

template<class element >
void chomp::homology::hashedset< element >::rehash ( int_t  newsize = 0  )  [private]

Replace the old hashing table with a new one.

The desired size may be given, otherwise an optimal size is determined and the table is made larger or smaller.

Definition at line 679 of file hashsets.h.

References chomp::homology::hashedset< element >::hashcleared, chomp::homology::hashedset< element >::hashfind(), chomp::homology::hashedset< element >::hashsize, chomp::homology::hashedset< element >::hashtable, chomp::homology::hashedset< element >::InitHashSize, chomp::homology::hashedset< element >::nelem, chomp::homology::hashedset< element >::rounduptoprime(), chomp::homology::hashedset< element >::stat, and chomp::homology::hashedset< element >::tab.

Referenced by chomp::homology::hashedset< element >::add(), and chomp::homology::hashedset< element >::remove().

{
        if (stat)
                ++ (stat -> rehashcount);

        // adjust the new size of the hashing table
        if ((newsize < (nelem << 1) + InitHashSize) ||
                (newsize > (nelem << 2) + InitHashSize))
                newsize = (nelem << 1) + nelem + InitHashSize;

        // DEBUG
//      sbug << "(rehash: nelem=" << nelem <<
//              ", hashsize=" << hashsize << ", newsize=" << newsize << ")\n";

        // check if it is not too large for 16-bit programs
        int_t x = 0xFFFF;
        if ((x < 0) && (newsize >= 16384))
                throw "Set too large for this 16-bit program.";

        // free unused memory if desired
        if (newsize < hashsize)
        {
                multitable<int_t> empty;
                hashtable = empty;
        }
        
        // set the new value of the hashing table and re-buid it
        hashsize = hashedset<element>::rounduptoprime (newsize);
        hashcleared = 0;

        // build the entire hash table from the beginning
        hashtable. fill (-1, hashsize);
        for (int_t i = 0; i < nelem; ++ i)
        {
                int_t pos = hashfind (tab (i));
                if (hashtable (pos) != -1)
                        throw "A repeated element in a set!";
                hashtable [pos] = i;
        }

        return;
} /* hashedset<element>::rehash */

template<class element>
hashedset< element > & chomp::homology::hashedset< element >::remove ( const hashedset< element > &  s  ) 

Removes an entire set of elements from the set.

Definition at line 547 of file hashsets.h.

References chomp::homology::hashedset< element >::check(), chomp::homology::hashedset< element >::removenum(), and chomp::homology::hashedset< element >::size().

{
        if (this -> size () < s. size ())
        {
                for (int_t i = 0; i < this -> size (); ++ i)
                {
                        if (s. check ((*this) [i]))
                                this -> removenum (i --);
                }
        }
        else
        {
                int_t n = s. size ();
                for (int_t i = 0; i < n; ++ i)
                        remove (s [i]);
        }
        return *this;
} /* hashedset<element>::remove */

template<class element>
int chomp::homology::hashedset< element >::remove ( const element &  e  ) 

Removes the given element from the set.

Returns 0 if successful, -1 if the element was not in the set.

Definition at line 464 of file hashsets.h.

References chomp::homology::hashedset< element >::hashcleared, chomp::homology::hashedset< element >::hashfind(), chomp::homology::hashedset< element >::hashing, chomp::homology::hashedset< element >::hashtable, chomp::homology::hashedset< element >::nelem, chomp::homology::hashedset< element >::rehash(), chomp::homology::hashedset< element >::StartHashingSize, and chomp::homology::hashedset< element >::tab.

{
        if (!hashing)
        {
                for (int_t i = 0; i < nelem; ++ i)
                {
                        if (tab (i) == e)
                        {
                                tab [i] = tab (-- nelem);
                                return 0;
                        }
                }
                return -1;
        }

        // find the position in the hashing table with this element's number
        int_t pos = hashfind (e);

        // if it was not there, then finish
        if (hashtable (pos) < 0)
                return -1;
        int_t n = hashtable (pos);

        // update the hashing table and the number of elements in the set
        hashtable [pos] = -2;
        -- nelem;
        ++ hashcleared;

        // if it was not the last element in the set, move the last one
        // to the vacated place
        if (n != nelem)
        {
                pos = hashfind (tab (nelem));
                hashtable [pos] = n;
                tab [n] = tab (nelem);
        }

        // if there are very few elements in the table, turn off hashing
        if (nelem < StartHashingSize / 2)
        {
                hashing = 0;
        }

        // if there are very many cleared entries, then rehash
        else if (hashcleared > nelem + 19)
                rehash ();

        return 0;
} /* hashedset<element>::remove */

template<class element >
int chomp::homology::hashedset< element >::removenum ( int_t  n  )  [inline]

Returns an element with the given number from the set.

Returns 0 if successful, -1 if the number is out of range.

Definition at line 515 of file hashsets.h.

References chomp::homology::hashedset< element >::hashing, chomp::homology::hashedset< element >::nelem, and chomp::homology::hashedset< element >::tab.

Referenced by chomp::homology::hashedset< element >::pop(), and chomp::homology::hashedset< element >::remove().

{
        if ((n < 0) || (n >= nelem))
                return -1;
        if (!hashing)
        {
                -- nelem;
                if (n != nelem)
                        tab [n] = tab (nelem);
                return 0;
        }
        return remove (tab (n));
} /* hashedset<element>::removenum */

template<class element >
int_t chomp::homology::hashedset< element >::rounduptoprime ( int_t  n  )  [static, private]

Rounds up the given number to a prime number.

Definition at line 740 of file hashsets.h.

Referenced by chomp::homology::hashedset< element >::hashedset(), and chomp::homology::hashedset< element >::rehash().

{
        while (!hashedset<element>::numberisprime (n))
                ++ n;

        return n;
} /* hashedset<element>::rounduptoprime */

template<class element >
int_t chomp::homology::hashedset< element >::size (  )  const [inline]

Returns the number of elements in the set.

Definition at line 573 of file hashsets.h.

References chomp::homology::hashedset< element >::nelem.

Referenced by chomp::homology::hashedset< element >::add(), chomp::homology::hashedset< element >::intersection(), and chomp::homology::hashedset< element >::remove().

{
        return nelem;
} /* hashedset<element>::size */

template<class element>
void chomp::homology::hashedset< element >::swap ( hashedset< element > &  other  )  [inline]

Swaps two hashed sets by swapping their internal data.

Definition at line 579 of file hashsets.h.

References chomp::homology::hashedset< element >::hashcleared, chomp::homology::hashedset< element >::hashing, chomp::homology::hashedset< element >::hashsize, chomp::homology::hashedset< element >::hashtable, chomp::homology::my_swap(), chomp::homology::hashedset< element >::nelem, chomp::homology::hashedset< element >::stat, and chomp::homology::hashedset< element >::tab.

{
        my_swap (stat, other. stat);
        my_swap (nelem, other. nelem);
        tab. swap (other. tab);
        my_swap (hashing, other. hashing);
        my_swap (hashsize, other. hashsize);
        my_swap (hashcleared, other. hashcleared);
        hashtable. swap (other. hashtable);
        return;
} /* hashedset<element>::swap */

template<class element >
const element & chomp::homology::hashedset< element >::top (  )  const [inline]

Returns the last element in the set.

Definition at line 407 of file hashsets.h.

References chomp::homology::hashedset< element >::nelem.

{
        return get (nelem - 1);
} /* hashedset<element>::top */

Member Data Documentation

template<class element>
int_t chomp::homology::hashedset< element >::hashcleared [private]

The number of cleared entries in the hashing table.

Definition at line 255 of file hashsets.h.

Referenced by chomp::homology::hashedset< element >::add(), chomp::homology::hashedset< element >::rehash(), chomp::homology::hashedset< element >::remove(), and chomp::homology::hashedset< element >::swap().

template<class element>
int chomp::homology::hashedset< element >::hashing [private]

Is the hashing table in use?

Definition at line 249 of file hashsets.h.

Referenced by chomp::homology::hashedset< element >::add(), chomp::homology::hashedset< element >::getnumber(), chomp::homology::hashedset< element >::hashfind(), chomp::homology::hashedset< element >::remove(), chomp::homology::hashedset< element >::removenum(), and chomp::homology::hashedset< element >::swap().

template<class element>
int_t chomp::homology::hashedset< element >::hashsize [private]

The size of the hashing table.

Definition at line 252 of file hashsets.h.

Referenced by chomp::homology::hashedset< element >::add(), chomp::homology::hashedset< element >::hashedset(), chomp::homology::hashedset< element >::hashfind(), chomp::homology::hashedset< element >::rehash(), and chomp::homology::hashedset< element >::swap().

template<class element>
multitable<int_t> chomp::homology::hashedset< element >::hashtable [private]

The hashing table.

Each entry contains the index of the element in the set, or -1 if the entry is free, or -2 if it was cleared.

Definition at line 259 of file hashsets.h.

Referenced by chomp::homology::hashedset< element >::add(), chomp::homology::hashedset< element >::getnumber(), chomp::homology::hashedset< element >::hashfind(), chomp::homology::hashedset< element >::rehash(), chomp::homology::hashedset< element >::remove(), and chomp::homology::hashedset< element >::swap().

template<class element>
const int_t chomp::homology::hashedset< element >::InitHashSize [static, private]

The default initial size of a hashing table.

Definition at line 230 of file hashsets.h.

Referenced by chomp::homology::hashedset< element >::rehash().

template<class element>
const int_t chomp::homology::hashedset< element >::InitTabSize [static, private]

The initial size of a table in a hashed set.

Definition at line 233 of file hashsets.h.

template<class element>
int_t chomp::homology::hashedset< element >::nelem [private]

The number of elements stored in the set.

Definition at line 243 of file hashsets.h.

Referenced by chomp::homology::hashedset< element >::add(), chomp::homology::hashedset< element >::checknum(), chomp::homology::hashedset< element >::empty(), chomp::homology::hashedset< element >::front(), chomp::homology::hashedset< element >::get(), chomp::homology::hashedset< element >::getnumber(), chomp::homology::hashedset< element >::pop(), chomp::homology::hashedset< element >::rehash(), chomp::homology::hashedset< element >::remove(), chomp::homology::hashedset< element >::removenum(), chomp::homology::hashedset< element >::size(), chomp::homology::hashedset< element >::swap(), and chomp::homology::hashedset< element >::top().

template<class element>
const int_t chomp::homology::hashedset< element >::StartHashingSize [static, private]

The minimal number of elements above which hashing table is actually used.

If the number of elements is below this threshold, then a simple array is used and elements are searched for by going through all the elements of the array.

Definition at line 240 of file hashsets.h.

Referenced by chomp::homology::hashedset< element >::add(), and chomp::homology::hashedset< element >::remove().

template<class element>
hashstat* chomp::homology::hashedset< element >::stat

Hashed set statistics.

Allocate this structure to make the set gather usage and effectiveness statistics. By default this pointer is set to 0. It is deallocated in the destructor.

Definition at line 226 of file hashsets.h.

Referenced by chomp::homology::hashedset< element >::hashedset(), chomp::homology::hashedset< element >::hashfind(), chomp::homology::hashedset< element >::rehash(), chomp::homology::hashedset< element >::swap(), and chomp::homology::hashedset< element >::~hashedset().

template<class element>
multitable<element> chomp::homology::hashedset< element >::tab [private]

The table of these elements.

Definition at line 246 of file hashsets.h.

Referenced by chomp::homology::hashedset< element >::add(), chomp::homology::hashedset< element >::get(), chomp::homology::hashedset< element >::getnumber(), chomp::homology::hashedset< element >::hashfind(), chomp::homology::hashedset< element >::intersection(), chomp::homology::hashedset< element >::rehash(), chomp::homology::hashedset< element >::remove(), chomp::homology::hashedset< element >::removenum(), and chomp::homology::hashedset< element >::swap().

The documentation for this class was generated from the following file:
Generated on Mon Aug 30 2010 18:00:32 for The CHomP Library by  doxygen 1.7.1