Go to the previous, next section.
#include <nihcl/Set.h>
A
Set
is an unordered collection of objects. The objects cannot be accessed by a key as can the objects in a
Dictionary
, for example. Unlike a
Bag
, in which equal objects may occur more than once, a
Set
ignores attempts to add any object that duplicates one already in the
Set
. A
Set
considers two objects to be duplicates if they are
isEqual()
to one another.
Class
Set
is implemented using a hash table with open addressing.
Set::add()
calls the virtual member function
hash()
and uses the number returned to compute an index to the hash table at which to begin searching, and
isEqual()
is called to check for equality.
Set(unsigned
capacity
=DEFAULT_CAPACITY)
Set
that can hold up to
capacity
objects. An
NIHCL_ALLOCSIZE
error is raised if
capacity
is not greater than 0. If an attempt is made to add more than
capacity
objects to a
Set
,
reSize()
is called to increase its capacity. Since this is an expensive operation, it is wise to supply a reasonable estimate for
capacity.
virtual Object* add(Object&
ob)
Set
and returns a pointer to either a duplicate (i.e.,
isEqual()
) object already in this
Set
, or a pointer to
ob
if there was not already a duplicate object in this
Set
.
virtual Object* remove(const Object&
ob)
isEqual()
to
ob
from this
Set
and returns a pointer to the object removed. If an object equal to
ob
does not occur in the
Set
, an
NIHCL_REMOVEERR
is raised.
virtual void removeAll()
Set
.
virtual Object* findObjectWithKey(const Object&
ob) const
Set
to find an object that is
isEqual()
to
ob. Returns a pointer to the
Nil
object if an equal object is not found.
virtual unsigned hash() const
Set
can use as a hash table probe. Class
Set
implements
hash()
by exclusive ORing the results of applying
hash()
to all objects in the
Set
.
virtual unsigned occurrencesOf(const Object&
ob) const
isEqual()
to
ob
occurs in this
Set
; otherwise,
occurrencesOf()
returns 0.
bool operator==(const Set&) const
bool operator!=(const Set&) const
YES
if the right
Set
operand is equal to (or not equal to) the left
Set
operand. Two
Set
s
a
and
b
are equal if they contain the same number of objects and if, for each object in
a, there is an
isEqual()
object in
b.
Set operator&(const Set&) const
Set
containing all objects that are in both the left and right operand
Set
s. For example:
Set s,t; Integer i(0),j(1),k(2); s.add(i); s.add(j); // s contains 0,1 t.add(j); t.add(k); // t contains 1,2 cout << (s&t); // prints 1
Set operator|(const Set&) const
Set
containing all objects that are in either the left or right operand
Set
s. For example:
Set s,t; Integer i(0),j(1),k(2); s.add(i); s.add(j); // s contains 0,1 t.add(j); t.add(k); // t contains 1,2 cout << (s|t); // prints 0 1 2
Set operator-(const Set&) const
Set
that contains all objects that are in the left operand
Set
and not in the right operand
Set
. For example:
Set s,t; Integer i(0),j(1),k(2); s.add(i); s.add(j); // s contains 0,1 t.add(j); t.add(k); // t contains 1,2 cout << (s-t); // prints 0
virtual bool isEqual(const Object&
a) const
YES
if this
Set
and the argument object are comparable and they have equal values. The argument object
a
is comparable if it returns the address of class
Set
's class descriptor for its
species()
. Class
Set
implements
isEqual()
by applying
isEqual()
to all objects in a
Set
.
virtual void deepenShallowCopy()
deepCopy()
to all the object pointers, replacing each pointer with a pointer to its copy.
virtual Object*& at(int
i)
virtual const Object *const& at(int
i) const
Set
. This will be a pointer to either the
Nil
object (if the
ith hash table position is unoccupied), or a pointer to the object that hashes to the
ith slot. This is an implementation dependent function not recommended for general use.
virtual unsigned capacity() const
Set
can hold before it will need to be expanded.
virtual unsigned size() const
Set
.
virtual void reSize(unsigned
newSize)
Set
to
newSize. If
newSize
is less than or equal to
capacity()
, then the capacity is not changed.
virtual Object* doNext(Iterator&
pos) const
Set
, or 0 if no more objects remain. The
Iterator
argument
pos
maintains the current position in the
Set
.
virtual const Class* species() const
Set
.
unsigned mask
Set
, which must be a power of 2, minus 1.
ArrayOb contents
ArrayOb
used as a hash table by this
Set
.
virtual void storer(OIOofd&
fd) const
virtual void storer(OIOout&
strm) const
Set
to
fd
or
strm
by applying
storeOn()
to each of them.
virtual int findIndexOf(const Object&
ob) const
Set
for an object that is
isEqual()
to
ob
and returns the index of this object, if found, or the index of an empty slot in the hash table where
ob
should be inserted. Derived classes such as
IdentDict
and
IdentSet
redefine
findIndexOf()
to implement searching and comparison based on other criteria, such as an object's address.
int h(unsigned long
k) const
hash()
, into a hash table index.
virtual unsigned hashOf(const Object&
ob) const
hash()
to
ob. Derived classes such as
IdentDict
and
IdentSet
redefine
hashOf()
to implement hashing based on other criteria, such as an object's address.
unsigned setCapacity(unsigned
capacity)
Set
. Rounds
capacity
up to the next higher power of two, if necessary.
virtual int compare(const Object&) const
shouldNotImplement()
.
NIHCL_ALLOCSIZE
,
NIHCL_REMOVEERR
Go to the previous, next section.