The Simons     Component Library

           

---

Set Class Reference

#include <Set.h>

Inheritance diagram for Set:

List of all members.

---

Detailed Description

Set: an unordered collection of uniquely-occurring objects.

The Set class is one of the Unordered collections. In a Set, elements occur uniquely, such that no element is EQUAL to any other. The inserted order of elements is not significant. Adding new elements includes them in the Set, replacing any EQUAL elements. Adding, removing and retaining collections of elements is equivalent to mutating set union, set difference and set intersection, respectively. Comparing two Sets may determine that one is included by (LESS), equal to (EQUAL) or includes (MORE) the other, or that they are disjoint (NONE) or intersect (SOME). Sets are the most efficient Collection to search for the presence or absence of elements.

A Set is implemented as an open hash-table. It locates its elements by hashing on the elements, with an average seek time of 1.3 lookups. In the rare event of a collision, elements are relocated. When elements are removed, the table is compacted in an average time of 2.3 lookups. The hash table is never more than 2/3 full for optimum performance.

Public Member Functions
	Set ()
	Construct an empty Set.
virtual	~Set ()
	Release an unused Set.
	Set (CollectionID)
	Construct a Set from another Collection.
virtual ObjectID	clone () const
	Clone a shallow copy of this Set.
virtual Natural	size () const
	The cardinality of this Set.
virtual Boolean	has (ObjectID) const
	Test if this Set contains a particular Object.
virtual Natural	count (ObjectID) const
	Count the occurrences of an Object in this Set.
virtual ObjectID	find (ObjectID) const
	Find an Object equal to another in this Set.
virtual ObjectID	item (Integer) const
	Select an Object contained in this Set.
virtual Void	add (ObjectID)
	Add an Object to this Set.
virtual Void	remove (ObjectID)
	Remove an Object from this Set.
Protected Member Functions
	Set (const Set &)
	Copy another Set.
Void	deepRemove (EntryID)
	Remove an Entry from this Set, which is a Map.

---

Constructor & Destructor Documentation

Set::Set (  const Set &  set  )  [protected]

Copy another Set. Required by C++ to ensure that copying a Set faithfully copies an Unordered collection. Takes a shallow copy of the other Set by allocating a hash table with the same capacity, then copying all the other Set's elements to the same hashed locations. Used by clone(), this method is more efficient than the constructor to build a Set from a Collection. Parameters: set  - the other Set to copy. Returns: a Set, a shallow copy.

Set::Set (   )

Construct an empty Set. The size() of the Set is zero, but a hash table of the default capacity is constructed and every entry is initialised to null. Returns: an empty Set.

Set::~Set (   )  [virtual]

Release an unused Set. Deletes the hash table used to store the Set's elements.

Set::Set (  CollectionID  other  )

Construct a Set from another Collection. This is the main method for converting an arbitrary Collection into a Set, especially if it is desired to search for the presence or absence of particular elements. The other Collection is unchanged, but this Set will share (typically a subset of) its elements. Allocates a hash table with enough capacity to hold all the elements of the other Collection. Inserts them into this Set using addAll(), which eliminates duplicate elements and disregards their order. Parameters: other  - the other Collection to copy. Returns: a Set containing the elements of the Collection uniquely.

---

Member Function Documentation

Void Set::add (  ObjectID  object  )  [virtual]

Add an Object to this Set. Inserts the Object uniquely into this Set, replacing any Object judged EQUAL, under compare(). Increments the size of this Set if the Object was not previously present. The order of inserted objects is essentially arbitrary. Rarely, two non-EQUAL Objects may hash to the same location (a collision) and one of these will be displaced. The size of the underlying hash table will expand when it reaches 2/3 full. Parameters: object  - an Object to be inserted. Reimplemented from Collection. Reimplemented in Map.

ObjectID Set::clone (   )  const [virtual]

Clone a shallow copy of this Set. Returns: a shallow copy of this Set. Reimplemented from Object. Reimplemented in Map.

Natural Set::count (  ObjectID  object  )  const [virtual]

Count the occurrences of an Object in this Set. Parameters: object  - an Object to search for. Returns: 1 if this Set contains the Object, otherwise 0. Reimplemented from Unordered.

Void Set::deepRemove (  EntryID  entry  )  [protected]

Remove an Entry from this Set, which is a Map. Removes an Entry from this Set that is judged deep EQUAL, under deepCompare(), to the requested Entry. Has no effect if no such Entry is present in this Set. This Set is a Map, containing Entries with unique domain keys, which are judged EQUAL under compare() if the keys are EQUAL. This secret method is needed to remove only an Entry that is deep EQUAL to the requested Entry, that is, whose key and value are both EQUAL to those of the requested Entry. The underlying hash table may be compacted if the last Entry in a collision-set is removed. Parameters: entry  - the Entry to be removed.

ObjectID Set::find (  ObjectID  object  )  const [virtual]

Find an Object equal to another in this Set. Parameters: object  - the Object to search for. Returns: the Object found in this Set, or null. Reimplemented from Unordered.

Boolean Set::has (  ObjectID  object  )  const [virtual]

Test if this Set contains a particular Object. Parameters: object  - an Object to search for. Returns: true, if this Set contains the Object, otherwise false. Reimplemented from Collection.

ObjectID Set::item (  Integer  index  )  const [virtual]

Select an Object contained in this Set. Selects an arbitrary element from this Set; however, each distinct index is guaranteed to access a distinct element from the Set. Iterating over the Set visits each element exactly once. Repeated access to the same element at the same index is in constant time. Sequential access to all elements using an incrementing index is in near-constant time. Random access is in linear time. Parameters: index  - an index into this Set. Returns: an Object from this Set. Reimplemented from Collection.

Void Set::remove (  ObjectID  object  )  [virtual]

Remove an Object from this Set. Removes a single Object, judged EQUAL under compare(), to the requested Object, if such an Object is found. Has no effect if no such Object is present in this Set. The underlying hash table may be compacted if the removed Object was in a collision-set. Parameters: object  - the Object to be removed. Reimplemented from Unordered. Reimplemented in Map.

Natural Set::size (   )  const [virtual]

The cardinality of this Set. Returns: the number of elements in this Set. Reimplemented from Collection.

---

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

• Set.h
• Set.cc

---