9.3. Evolution of the system's design

Designing the class interfaces

Once the basic principles for building the system's architecture have been worked out, the remaining work is simple, but often rather boring and tedious. The next stage will consist of implementing three or four families of classes (such as queue, set, and tree) in accordance with the chosen architecture, and then testing them in several applications [Wirfs-Brock believes that a development environment must be tested on at least three applications in order to verify the correctness of the strategic and tactical decisions [15]].

The hardest part of this stage is creating a suitable interface for each base class. And here, while developing individual classes in isolation (see Chapter 6), one must not forget the task of ensuring that all parts of the system fit one another globally. In particular, for the class Set the following protocol may be defined:

In a similar way, the protocol of the class BinaryTree:

For similar operations we use similar names. In developing the interface we also check the resulting solution against the criteria of sufficiency, completeness, and primitiveness (see Chapter 3).

Support classes

In implementing the class responsible for manipulating text strings, we found that the capabilities provided by the support classes Bounded and Unbounded were clearly insufficient. The bounded form, in particular, turns out to be inefficient for working with strings from the standpoint of memory, since we have to instantiate this form to accommodate the largest possible string, and consequently waste memory on shorter strings. The unbounded form, in turn, is inefficient from the standpoint of speed: searching for an element in a string may require sequentially scanning all the elements of the linked list. For these reasons we had to develop a third, "dynamic" variant:

The structure is stored on the heap as an array whose length may shrink or grow.

The corresponding support class Dynamic represents an intermediate variant with respect to the bounded and unbounded classes, providing the speed of the bounded form (direct indexing of elements is possible) and the storage efficiency inherent in the unbounded form (memory is allocated only for the elements that actually exist).

Since the protocol of this class is identical to the protocol of the classes Bounded and Unbounded, adding a new mechanism to the library will not be very difficult. We must create three new classes for each family (for example, DynamicString, GuardedDynamicString and SynchronizedDynamicString). Thus, we introduce the following support class:

template<class Item, class StorageManager>
class Dynamic {
public:

Dynamic(unsigned int chunkSize);

protected:

Item* rep;
unsigned int size;
unsigned int totalChunks;
unsigned int chunkSize;
unsigned int start;
unsigned int stop;
void resize(unsigned int currentLength,
unsigned int newLength, int preserve - 1);
unsigned int expandLeft(unsigned int from);
unsigned int expandRight(unsigned int from);
void shrinkLeft(unsigned int from);
void shrinkRight(unsigned int from);

};

Sequences are divided into chunks in accordance with the constructor argument chunkSize. Thus, the client can regulate the size of the future object.

It is clear from the interface that the class Dynamic has much in common with the classes Bounded and Unbounded. The differences in the implementation of the three types of classes in each family will be minimal.

Let us now turn to the class of associative arrays. Its implementation will require a further reworking of the bounded, dynamic, and unbounded forms. In particular, searching for an element in an associative array takes far too much time if it has to be done by scanning all the elements. But performance can be increased significantly by using open hash tables.

The abstraction of an open hash table is simple. The table is an array of sequences that are called buckets. When placing a new element into the table, we first generate a hash code from that element, and then use the code to select the bucket into which the element will be placed. Thus, an open hash table divides a long sequence into several shorter ones, which significantly speeds up searching.

The corresponding abstraction can be defined as follows:

template<class Item, class Value, unsigned int Buckets, class Container>
class Table {
public:

Table(unsigned int (*hash)(const Item&));
void setHashFunction(unsigned int (*hash)(const Item&));
void clear();
int bind(const Item&, const Value&);
int rebind(const Item&, const Value&);
int unbind(const Item&);
Container* bucket(unsigned int bucket);
unsigned int extent() const;
int isBound(const Item&) const;
const Value* valueOf(const Item&) const;
const Container *const bucket(unsigned int bucket) const;

protected:

Container rep[Buckets];

};

Using the class Container as a template argument makes it possible to apply the hash table abstraction independently of the type of the particular sequence. Consider as an example the (greatly simplified) declaration of an unbounded associative array built on the basis of the classes Table and Unbounded:

template<class Item, class Value, unsigned int Buckets,
class StorageManager>
class UnboundedMap : public Map<Item, Value> {
public:

UnboundedMap();
virtual int bind(const Item&, const Value&);
virtual int rebind(const Item&, const Value&);
virtual int unbind(const Item&);

protected:

Table<Item, Value, Buckets, Unbounded<Pair<Item, Value>, StorageManager>> rep;

};

In this case we instantiate the class Table with the container unbounded. Figure 9-12 illustrates how these classes collaborate.

As evidence of the general applicability of this abstraction, we can use the class Table in implementing the classes for sets and bags.

Figure 9-12. Support classes.

Tools

For our library the main role of templates is to parameterize structures by the types of the elements they will contain; this is why such structures are called container classes. But, as can be seen from the definition of the class Table, templates can also be used to pass a class certain information about the implementation.

An even more complicated situation arises when creating tools that operate upon other structures. As has already been noted, algorithms too can be represented as classes whose objects act as the agents responsible for carrying out the algorithm. This approach corresponds to Jacobson's idea of a control object, which serves as the connecting link that brings about the interaction of ordinary objects [16]. The advantage of this approach lies in the possibility of creating families of algorithms united by inheritance. This not only simplifies their use, but also makes it possible to unite conceptually similar algorithms.

Consider as an example algorithms for searching for a pattern within a sequence. There are a whole range of such algorithms:

All these algorithms have at least three features in common: they all perform operations on sequences (and hence work with objects having a similar protocol), they require the existence of a comparison operation for the type of the elements among which the search is conducted (the standard comparison operator may prove insufficient), and they have the same call signature (the target string, the search pattern, and the index of the element at which the search will begin).

The comparison operation deserves special discussion. Suppose, for example, that there is an ordered list of a firm's employees. We want to search it by a particular criterion, say, to find groups of three records with employees working in one and the same department. Using the operator operator== defined for the class PersonnelRecord will not give the desired result, since this operator most likely performs the check according to a different criterion, for example, the employee's payroll number. Therefore we will have to develop specially for this purpose a new comparison operator that would query (by calling the appropriate selector) the name of the department in which the employee works. Since each agent that performs pattern matching requires its own equality-testing function, we can develop a general protocol for introducing such a function as part of some abstract base class. Consider as an example the following declaration:

template<class Item, class Sequence>
class PatternMatch {
public:

PatternMatch();
PatternMatch(int (*isEqual)(const Item& x, const Item& y));
virtual ~PatternMatch();
virtual void setIsEqualFunction(int (*)(const Item& x, const Item& y));
virtual int match(const Sequence& target, const Sequences; pattern, unsigned int start = 0) = 0;
virtual int match(const Sequence&; target, unsigned int start = 0) = 0;

protected:

Sequence rep;
int (*isEqual)(const Item& x, const Item& y);

private:

void operator=(coust PattemMatcb&) {}
void operator==(const PatternMatch&) {}
void operator!=(const PatternMatch&) {}

};

Assignment and equality-comparison operations for objects of this class and its subclasses are impossible, since we have used the corresponding idioms. We did this because assignment and comparison operations make no sense for agent abstractions.

Now let us describe a concrete subclass that defines the Boyer-Moore algorithm:

template<class Item, class Sequence>
class BMPatternMatch : public PatternMatch<Item, Sequence> {
public:

BMPatternMatch();
BMPattemMatch(int (*isEqual) (const Item& x, const Item& y));
virtual ~BMPattemMatch();
virtual int match(const Sequence& target, const Seque unsigned int start = 0);
virtual int match(const Sequence& target, unsigned in

protected:

unsigned int length;
unsigned int* skipTable;
void preprogress(const Sequence& pattern);
unsigned int itemsSkip(const Sequence& pattern, const Item& item);

};

Figure 9-13. Pattern matching classes.

The public protocol of this class copies exactly the corresponding protocol of its superclass. In addition, its declaration further includes two data members and two helper functions. One of the features of this class consists in the creation of a temporary table that is used to skip long non-matching sequences. These additional members are needed to implement the algorithm.

Figure 9-13 shows the hierarchy of the pattern matching classes. A hierarchy of this kind is applicable to most of the library's tools. This forms families of classes that are similar in structure, which allows users to find their way among them easily and to choose those that best suit their applications.