hashset_rep< T > Class Template Reference

The hashset_rep class represents an entry in a hash set. More...

#include <hashset.hpp>

Inheritance diagram for hashset_rep< T >:

Collaboration diagram for hashset_rep< T >:

Public Member Functions
	hashset_rep ()
	Construct a new hashset_rep object with default values.
	hashset_rep (int n2, int max2=1)
	Construct a new hashset_rep object with specified values.
	~hashset_rep ()
	Destroy the hashset_rep object.
bool	contains (T x)
void	resize (int n)
void	insert (T x)
void	remove (T x)

Private Attributes
int	size
int	n
int	max
list< T > *	a
Private Attributes inherited from concrete_struct
int	ref_count
	The reference count for the concrete object.

Friends
class	hashset< T >
class	hashset_iterator_rep< T >
int N	LESSGTR (hashset< T > h)
tm_ostream &	operator<<LESSGTR (tm_ostream &out, hashset< T > h)
bool	operator<=LESSGTR (hashset< T > h1, hashset< T > h2)
hashset< T > copy	LESSGTR (hashset< T > h)

Additional Inherited Members
Private Member Functions inherited from concrete_struct
	concrete_struct ()
	Default constructor for the concrete object. Increments the reference count.
virtual	~concrete_struct ()
	Virtual destructor for the concrete object. Decrements the reference count.

Detailed Description

template<class T>
class hashset_rep< T >

The hashset_rep class represents an entry in a hash set.

Template Parameters

T	The type of the data stored in the hash set.

Definition at line 26 of file hashset.hpp.

Constructor & Destructor Documentation

hashset_rep() [1/2]

template<class T >

hashset_rep< T >::hashset_rep ( )

inline

Construct a new hashset_rep object with default values.

Definition at line 37 of file hashset.hpp.

      : size (0), n (1), max (1), a (tm_new_array<list<T>> (1)) {}

hashset_rep() [2/2]

template<class T >

hashset_rep< T >::hashset_rep ( int n2, int max2 = 1 )

inline

Construct a new hashset_rep object with specified values.

Parameters

n2	The number of keys (a power of two).
max2	The mean number of entries per key.

Definition at line 46 of file hashset.hpp.

      : size (0), n (n2), max (max2), a (tm_new_array<list<T>> (n)) {}

~hashset_rep()

template<class T >

hashset_rep< T >::~hashset_rep ( )

inline

Destroy the hashset_rep object.

Definition at line 52 of file hashset.hpp.

{ tm_delete_array (a); }

Member Function Documentation

contains()

template<class T >

bool hashset_rep< T >::contains

(

T

x

)

Definition at line 47 of file hashset.ipp.

                             {
  return (search (a[hash (x) & (n - 1)], x) == NULL ? false : true);
}

resize()

template<class T >

void hashset_rep< T >::resize

(

int

n

)

Definition at line 18 of file hashset.ipp.

                              {
  int      i;
  int      oldn= n;
  list<T>* olda= a;
  n            = n2;
  a            = tm_new_array<list<T>> (n);
  for (i= 0; i < oldn; i++) {
    list<T> l (olda[i]);
    while (!is_nil (l)) {
      list<T>& newl= a[hash (l->item) & (n - 1)];
      newl         = list<T> (l->item, newl);
      l            = l->next;
    }
  }
  tm_delete_array (olda);
}

insert()

template<class T >

void hashset_rep< T >::insert

(

T

x

)

Definition at line 53 of file hashset.ipp.

                           {
  if (size == n * max) resize (n << 1);
  list<T>& l= a[hash (x) & (n - 1)];
  if (search (l, x) != NULL) return;
  l= list<T> (x, l);
  size++;
}

remove()

template<class T >

void hashset_rep< T >::remove

(

T

x

)

Definition at line 63 of file hashset.ipp.

                           {
  list<T>* lptr= &a[hash (x) & (n - 1)];
  while (!is_nil (*lptr)) {
    if ((*lptr)->item == x) {
      *lptr= (*lptr)->next;
      size--;
      return;
    }
    lptr= &((*lptr)->next);
  }
}

Friends And Related Symbol Documentation

hashset< T >

template<class T >

friend class hashset< T >

friend

Definition at line 57 of file hashset.hpp.

hashset_iterator_rep< T >

template<class T >

friend class hashset_iterator_rep< T >

friend

Definition at line 63 of file hashset.hpp.

LESSGTR [1/2]

template<class T >

int N LESSGTR ( hashset< T > h )

friend

operator<<LESSGTR

template<class T >

tm_ostream & operator<<LESSGTR ( tm_ostream & out, hashset< T > h )

friend

operator<=LESSGTR

template<class T >

bool operator<=LESSGTR ( hashset< T > h1, hashset< T > h2 )

friend

LESSGTR [2/2]

template<class T >

hashset< T > copy LESSGTR ( hashset< T > h )

friend

Member Data Documentation

size

template<class T >

int hashset_rep< T >::size

private

The size of the hash set (number of entries).

Definition at line 27 of file hashset.hpp.

n

template<class T >

int hashset_rep< T >::n

private

The number of keys (a power of two).

Definition at line 28 of file hashset.hpp.

max

template<class T >

int hashset_rep< T >::max

private

The mean number of entries per key.

Definition at line 29 of file hashset.hpp.

a

template<class T >

list<T>* hashset_rep< T >::a

private

The array of entries.

Definition at line 30 of file hashset.hpp.

---

The documentation for this class was generated from the following files:

• hashset.hpp
• hashset.ipp