Lolly 1.4.28
Loading...
Searching...
No Matches
Public Member Functions | Private Attributes | Friends | List of all members
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 >:
Inheritance graph
[legend]
Collaboration diagram for hashset_rep< T >:
Collaboration graph
[legend]

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_ostreamoperator<<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
TThe 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.

38 : size (0), n (1), max (1), a (tm_new_array<list<T>> (1)) {}
list< T > * a
Definition hashset.hpp:30
The list class represents a linked list.
Definition list.hpp:48
C * tm_new_array(int n)

◆ 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
n2The number of keys (a power of two).
max2The mean number of entries per key.

Definition at line 46 of file hashset.hpp.

47 : 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.

52{ tm_delete_array (a); }
void tm_delete_array(C *Ptr)

Member Function Documentation

◆ contains()

template<class T >
bool hashset_rep< T >::contains ( T x)

Definition at line 47 of file hashset.ipp.

47 {
48 return (search (a[hash (x) & (n - 1)], x) == NULL ? false : true);
49}
int hash(pointer ptr)
Computes a hash value for a pointer.
Definition basic.cpp:17
static T * search(list< T > l, T x)
Definition hashset.ipp:37

◆ resize()

template<class T >
void hashset_rep< T >::resize ( int n)

Definition at line 18 of file hashset.ipp.

18 {
19 int i;
20 int oldn= n;
21 list<T>* olda= a;
22 n = n2;
24 for (i= 0; i < oldn; i++) {
25 list<T> l (olda[i]);
26 while (!is_nil (l)) {
27 list<T>& newl= a[hash (l->item) & (n - 1)];
28 newl = list<T> (l->item, newl);
29 l = l->next;
30 }
31 }
33}
bool is_nil(blackbox x)
Definition blackbox.hpp:29

◆ insert()

template<class T >
void hashset_rep< T >::insert ( T x)

Definition at line 53 of file hashset.ipp.

53 {
54 if (size == n * max) resize (n << 1);
55 list<T>& l= a[hash (x) & (n - 1)];
56 if (search (l, x) != NULL) return;
57 l= list<T> (x, l);
58 size++;
59}
void resize(int n)
Definition hashset.ipp:18

◆ remove()

template<class T >
void hashset_rep< T >::remove ( T x)

Definition at line 63 of file hashset.ipp.

63 {
64 list<T>* lptr= &a[hash (x) & (n - 1)];
65 while (!is_nil (*lptr)) {
66 if ((*lptr)->item == x) {
67 *lptr= (*lptr)->next;
68 size--;
69 return;
70 }
71 lptr= &((*lptr)->next);
72 }
73}

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: