University of Sheffield   

    The Simons
    Component Library
Introduction   Class Hierarchy   Class Listing   Index of Classes   Index of Methods   Header Files  

Bag Class Reference

#include <Bag.h>

Inheritance diagram for Bag:

Unordered Collection Object Relation List of all members.

Detailed Description

Bag: an unordered collection of repeatedly-occurring objects.

The Bag class is one of the Unordered collections. In a Bag, elements may occur multiple times. The inserted order of elements is not significant. Adding new elements always includes them, increasing the size of the Bag. Adding, removing and retaining collections of elements is equivalent to mutating bag union, bag difference and bag intersection, respectively. Comparing two Bags 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). Bags are the most efficient Collection in which to count the quantity of each element.

A Bag is implemented as a chained hash-table. It locates chains of EQUAL elements by hashing on an element with an average seek time of 1.3 lookups. In the rare event of a collision, element chains are relocated. When the last element in a chain is 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

 Bag ()
 Construct an empty Bag.

virtual ~Bag ()
 Release an unused Bag.

 Bag (CollectionID)
 Construct a Bag from another Collection.

virtual ObjectID clone () const
 Clone a shallow copy of this Bag.

virtual Natural size () const
 The cardinality of this Bag.

virtual Boolean has (ObjectID) const
 Test if this Bag contains a particular Object.

virtual Natural count (ObjectID) const
 Count the occurrences of an Object in this Bag.

virtual ObjectID find (ObjectID) const
 Find the Bag of Objects equal to another in this Bag.

virtual ObjectID item (Integer) const
 Select an Object contained in this Bag.

virtual Void add (ObjectID)
 Add an Object to this Bag.

virtual Void remove (ObjectID)
 Remove an Object from this Bag.

Void clear (ObjectID)
 Remove all occurrences of an Object from this Bag.


Protected Member Functions

 Bag (const Bag &)
 Copy another Bag.

Void deepAdd (EntryID)
 Add an Entry to this Bag, which is a Relation.

Void deepRemove (EntryID)
 Remove an Entry from this Bag, which is a Relation.

Constructor & Destructor Documentation

Bag::Bag (  const Bag &  bag  )  [protected]
 

Copy another Bag.

Required by C++ to ensure that copying a Bag faithfully copies an Unordered collection. Takes a shallow copy of the other Bag by allocating a hash table with the same capacity, then copying all the chains of elements to the same hashed locations. Used by clone(), this method is more efficient than the constructor to build a Bag from a Collection.

Parameters:
bag - the other Bag to copy.
Returns:
a Bag, a shallow copy.

Bag::Bag (   ) 
 

Construct an empty Bag.

The size() of the Bag is zero, but a hash table of the default capacity is constructed and every entry is initialised to empty.

Returns:
an empty Bag.

Bag::~Bag (   )  [virtual]
 

Release an unused Bag.

Deletes the hash table used to store the Bag's elements. This is done by deleting the lists of elements stored at each hashed location, then deleting the table itself.

Bag::Bag (  CollectionID  other  ) 
 

Construct a Bag from another Collection.

This is the main method for converting an arbitrary Collection into a Bag, especially if it is desired to count the quantities of particular elements. The other Collection is unchanged, but this Bag will share all of the Collection's elements. Allocates a hash table with enough capacity to hold all the elements of the other Collection. Inserts them into this Bag using addAll(), which preserves duplicate elements but disregards their order.

Parameters:
other - the other Collection to copy.
Returns:
a Bag containing the elements of the Collection.

Member Function Documentation

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

Add an Object to this Bag.

Inserts the Object into this Bag, even if the Object is already present, and increments the size of the Bag. The order of inserted objects is essentially arbitrary, though objects judged EQUAL under compare() will tend to cluster together, since they will hash to the same location and will be chained together in the table. Rarely, two chains of non-EQUAL objects may hash to the same location (a collision) and one of these chains 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 Relation.

Void Bag::clear (  ObjectID  object  ) 
 

Remove all occurrences of an Object from this Bag.

Removes all Objects, judged EQUAL under compare(), to the requested Object, if such Objects are found. Has no effect if no such Object is present in the Bag. The underlying hash table is compacted if the removed Objects were in a collision-set.

Parameters:
object - the Object to be cleared from this Bag.

ObjectID Bag::clone (   )  const [virtual]
 

Clone a shallow copy of this Bag.

Returns:
a shallow copy of this Bag.

Reimplemented from Object.

Reimplemented in Relation.

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

Count the occurrences of an Object in this Bag.

Parameters:
object - an Object to search for.
Returns:
the number of times the Object occurs in this Bag.

Reimplemented from Unordered.

Void Bag::deepAdd (  EntryID  entry  )  [protected]
 

Add an Entry to this Bag, which is a Relation.

Inserts the Entry uniquely into this Bag, replacing any existing Entry that is judged deep EQUAL, under deepCompare(). This Bag is a Relation, containing multiple Entries with the same domain key, which are judged EQUAL under compare(). This secret method is needed to ensure that each Entry is added uniquely. Rarely, two chains of non-EQUAL entries may hash to the same location (a collision) and one of these chains will be displaced. The size of the underlying hash table will expand when it reaches 2/3 full.

Parameters:
entry - an Entry to be inserted.

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

Remove an Entry from this Bag, which is a Relation.

Removes an Entry from this Bag that is judged deep EQUAL, under deepCompare(), to the requested Entry. Has no effect if no such Entry is present in this Bag. This Bag is a Relation, containing multiple Entries with the same domain key, which are all judged EQUAL under compare(). This secret method is needed to remove only the Entry that is deep EQUAL to 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 Bag::find (  ObjectID  object  )  const [virtual]
 

Find the Bag of Objects equal to another in this Bag.

Returns a Bag of Objects, judged EQUAL under compare(), to the argument Object, or null if no such Objects are found.

Parameters:
object - the Object to search for.
Returns:
the Bag of Objects found in this Bag, or null.

Reimplemented from Unordered.

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

Test if this Bag contains a particular Object.

Parameters:
object - an Object to search for.
Returns:
true, if this Bag contains the Object, otherwise false.

Reimplemented from Collection.

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

Select an Object contained in this Bag.

Selects an arbitrary element from this Bag; however, each distinct index is guaranteed to access an element at a distinct location in the Bag. Iterating over the Bag visits every uniquely-added element once, and every multiply-added element as many times as it was added. 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 Bag.
Returns:
an Object from this Bag.

Reimplemented from Collection.

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

Remove an Object from this Bag.

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 Bag. The underlying hash table may be compacted if the last Object in a collision-set is removed.

Parameters:
object - the Object to be removed.

Reimplemented from Unordered.

Reimplemented in Relation.

Natural Bag::size (   )  const [virtual]
 

The cardinality of this Bag.

Returns:
the number of elements in this Bag.

Reimplemented from Collection.

The documentation for this class was generated from the following files:
Generated on Fri May 5 17:17:16 2006 for The Simons Component Library by doxygen1.3