6.19 Smalltalk-like Collection Classes

The Smalltalk-like collection classes are based on the language Smalltalk-80 and require that their collected objects singly or multiply inherit from the abstract base class RWCollectable.

The following table and figure summarize the Essential Tools Module Smalltalk-like classes. Table 14 lists all 17 classes, along with their typedefs, iterators, and implementations. Following is the class hierarchy.

To orient ourselves, we always like to start with an example. The following example uses a SortedCollection to store and order a set of RWCollectableStrings. SortedCollection is actually a typedef for the Smalltalk-like collection class RWBinaryTree. Objects inserted into it are stored in order according to their relative values as returned by the virtual function compareTo(). (See Section 6.17.4.)

Here is the code:

#define RW_STD_TYPEDEFS 1 //1 #include <rw/bintree.h> #include <rw/collstr.h> //2 #include <rw/rstream.h> using std::cout; using std::endl; int main(){ // Construct an empty SortedCollection SortedCollection sc; //3 // Insert some RWCollectableStrings: sc.insert(new RWCollectableString("George")); //4 sc.insert(new RWCollectableString("Mary")); sc.insert(new RWCollectableString("Bill")); sc.insert(new RWCollectableString("Throkmorton")); // Now iterate through the collection printing all members: RWCollectableString* str; //5 SortedCollectionIterator sci(sc); //6 while( str = (RWCollectableString*)sci() ) //7 cout << *str << endl; //8 sc.clearAndDestroy(); return 0; }

Program Output:

Bill George Mary Throkmorton

The following explains the code line-by-line:

When run, the program prints out the four collected strings in order; for class RWCollectableString, this means lexicographical order.

Class RWHashTable is the easiest Smalltalk-like collection class to understand. It uses a simple hashed lookup to find the bucket where a particular object occurs, then does a linear search of the bucket to find the object. A key concept is that multiple objects that test isEqual to each other can be inserted into a hash table.

Class RWBag is similar to RWHashTable, except that it counts occurrences of multiple objects with the same value; that is, it retains only the first occurrence and merely increments an occurrence count for subsequent ones. RWBag is implemented as a dictionary, where the key is the inserted object and the value is the occurrence count. This is the same way the Smalltalk Bag object is implemented. Note that this implementation differs significantly from many other C++ Bag classes which are closer to the RWHashTable class and not true Bags.

Class RWSet is similar to its base class RWHashTable, except that it doesn't allow duplicates. If you try to insert an object that isEqual to an object already in RWSet, the object will be rejected.

Class RWIdentitySet, which inherits from RWSet, retrieves objects on the basis of identity instead of value. Because RWIdentitySet is a Set, it can take only one instance of a given object.

Classes inheriting from RWSequenceable have an innate ordering. You can speak meaningfully of their first or last object, or of their 6th or ith object.

These classes are implemented generally as either a vector, or a singly-linked or doubly-linked list. Vector-based classes make good stacks and queues, but poor insertions in the middle. If you exceed the capacity of a vector-based collection class, it will automatically resize, but it may exact a significant performance penalty to do so.

The Essential Tools Module provides two dictionary classes: RWHashDictionary, implemented as a hash table, and RWBTreeDictionary, implemented as a B-tree. For these classes, both keys and values must inherit from the abstract base class RWCollectable.

The Smalltalk-like collection classes inherit from the abstract base class RWCollection, which in turn inherits from the abstract base class RWCollectable, described in Section 6.16, Section 6.17, Section 6.18, and Section 6.19.1. (Thus do we produce collections of collections, but that is another story.)

An abstract base class is a class intended to be inherited by some other class, not used as itself per se. If you think of it as a kind of virtual class, you can easily project the meaning of virtual functions. These virtual functions provide a blueprint of functionality for the derived class. As an abstract base class, RWCollection provides a blueprint for collection classes by declaring various virtual functions, such as insert(), remove(), entries(), and so on.

This section describes the virtual functions inherited by the Smalltalk-like collections. Any of these collections can be expected to understand them.

This function inserts in the way most natural for the collection. Faced with a stack, it pushes an item onto the stack. Faced with a queue, it appends the item to the queue. In a sorted collection, it inserts the new item so that items before it compare less than itself, items after it compare greater than itself, and items equal compare equal, if duplicates are allowed. See the example in Section 6.19.2 for an example using insert().

You must always insert pointers to real objects. Since all RWCollection classes need to dereference their contents for some methods such as find(), inserting a zero will cause such methods to crash. If you must store an empty object, we suggest you create and insert a default constructed object of the appropriate type, such as RWCollectable*.

The following example, which builds on the example in Section 6.19.2, uses find() to find occurrences of Mary in the collection, and occurrencesOf() to find the number of times Mary occurs:

#define RW_STD_TYPEDEFS 1 #include <rw/bintree.h> //1 #include <rw/collstr.h> #include <rw/rstream.h> using std::cout; using std::endl; int main(){ // Construct an empty SortedCollection SortedCollection sc; // Insert some RWCollectableStrings: sc.insert(new RWCollectableString("George")); sc.insert(new RWCollectableString("Mary")); sc.insert(new RWCollectableString("Bill")); sc.insert(new RWCollectableString("Throkmorton")); sc.insert(new RWCollectableString("Mary")); //2 cout << sc.entries() << endl; //3 RWCollectableString dummy("Mary"); //4 RWCollectable* t = sc.find( &dummy ); //5 if(t){ //6 if(t->isA() == dummy.isA()) //7 cout << *(RWCollectableString*)t << endl; //8 } else cout << "Object not found.\n"; //9 cout << sc.occurrencesOf(&dummy) << endl; //10 sc.clearAndDestroy(); return 0; }

Program Output:

5 Mary 2

The function removeAndDestroy() is similar except it deletes the item instead of returning it, using the virtual destructor inherited by all RWCollectable items. You must be careful when using this function that the item was actually allocated off the heap, not the stack, and that it is not shared with another collection.

The function clearAndDestroy() not only removes the items, but also calls the virtual destructor for each item. You must use this function with care. The function does check to see if the same item occurs more than once in a collection (by building an RWIdentitySet internally), and thereby deletes each item only once. However, it cannot check whether an item is shared between two different collections. You must also be certain that every member of the collection was allocated off the heap.

There are several other functions that are shared by all classes that inherit from RWCollection. Note that these are not virtual functions.

The following functions allow any collection class to be converted into an RWBag, RWSet, RWOrdered, or a SortedCollection (that is, an RWBinaryTree):

RWBag asBag() const; RWSet asSet() const; RWOrdered asOrderedCollection() const; RWBinaryTree asSortedCollection() const

Collections that inherit from the abstract base class RWSequenceable, which inherits from RWCollectable, have an innate, meaningful ordering. This section describes the virtual functions inherited from RWSequenceable which make use of that ordering. For example, the following virtual functions allow access to the ith item in the collection:

virtual RWCollectable*& at(size_t i); virtual const RWCollectable* at(size_t i) const;

Remember that the first item in any collection is at position i=0. The compiler chooses which function to use on the basis of whether or not your collection has been declared const: the second variant of the function is for const collections, the first for all others. The first variant can also be used as an lvalue, as in the following example:

RWOrdered od; od.insert(new RWCollectableInt(0)); // 0 od.insert(new RWCollectableInt(1)); // 0 1 od.insert(new RWCollectableInt(2)); // 0 1 2 delete od(1); // Use variant available for RWOrdered od.at(1) = new RWCollectableInt(3); // 0 3 2

As you might expect, the operations above are efficient for the class RWOrdered, which is implemented as a vector, but relatively inefficient for a class implemented as a linked-list, because the entire list must be traversed to find a particular index.

The following virtual functions return the first or last item in the collection, respectively, or nil if the collection is empty:

virtual RWCollectable* first() const; virtual RWCollectable* last() const;

The next virtual function returns the index of the first object that is equal to the argument, or the special value RW_NPOS if there is no such object:

virtual size_t index(const RWCollectable*) const;

Here is an example of the index function in use. The output shows that the index of the variable we were searching for was found at position 1.

RWOrdered od; od.insert(new RWCollectableInt(6)); // 6 od.insert(new RWCollectableInt(2)); // 6 2 od.insert(new RWCollectableInt(4)); // 6 2 4 RWCollectableInt dummy(2); size_t inx = od.index(&dummy); if (inx == RW_NPOS) std::cout << "Not found." << std::endl; else std::cout << "Found at index " << inx << std::endl;

Program Output:

Found at index 1

Finally, you can use the following function to insert an item at a particular index:

virtual RWCollectable* insertAt(size_t i, RWCollectable* c);

In the example below, the code uses the function insertAt to insert 4 at position 1.

RWOrdered od; od.insert(new RWCollectableInt(6)); // 6 od.insert(new RWCollectableInt(2)); // 6 2 od.insertAt(1, new RWCollectableInt(4)); // 6 4 2

You may save yourself some difficulty by remembering the following point: the virtual functions of the object within the collection, not those of the target, are called when comparing or testing a target for equality.

In this example, the virtual functions of member within the collection RWCollectableString are called, not the virtual functions of target. In other words:

member.compareTo(&target); //This will get called. target.compareTo(&member); //Not this.

Copyright © Rogue Wave Software, Inc. All Rights Reserved.

The Rogue Wave name and logo, and SourcePro, are registered trademarks of Rogue Wave Software. All other trademarks are the property of their respective owners.
Contact Rogue Wave about documentation or support issues.