62:268 System Design

Tutorial: vector storage for the set hierarchy

The object hierarchy explored so far includes two set implementations with different behaviours implemented with an underlying storage model based on the primitive array type of C++. The goal of this tutorial is to augment the object hierarchy by encapsulating the primitive array and promoting it to a class of its own, Vector,  within the hierarchy.

The following basic interface is defined for SetObject and classes derived from it. 

class SetObject  
{
public:
	virtual void printOn(ostream &os) = 0;
	virtual unsigned int hashValue() = 0;
	SetObject();
	virtual ~SetObject();
	virtual SetObject * cloneForContainment() = 0;
	virtual int operator == (SetObject &s) = 0;
	virtual isClonedForContainment() = 0;
};

Vector is derived from SetObject and implements, at minimum, the methods shown above.

From inspecting the use of the array storage in Set and its derivatives, the minimum requirement for Vector is an array of pointer-to SetObject with retrieval and update operations called, say, get() and put().

class Vector : public SetObject
{
public:
	Vector(int initialCapacity);
	virtual ~Vector();
	// ... pure virtual functions from SetObject
	SetObject &get(int index);
	void put(int index, SetObject &s);
	int GetCapacity();
	void Grow(int newcapacity);
protected:
	int capacity;
	SetObject *storage;
};

However, the implementations of Set and its derivatives are littered with expressions like storage[i] = ... and  = ... storage[i] ...; i.e., assignments to and extractions from the i^th element of storage. The following operator definition for class Vector permits these expressions to remain unchanged.

SetObject *& Vector::operator [] (int index) {
	return storage[index];
}

That is, operator[ ] returns a pointer to SetObject by reference and is thus useable on either side of an assignment operator. With this operator definition, get() and put() become unnecessary.

Vector is a container like Set and should follow the same regime for comparison and copying. Methods cloneForContainment(), isClonedForContainment() and operator == have similar implementations in Vector and Set. So much so, in fact, that consideration should be given to adding SetReferenceObject and SetValueObject to the hierarchy and deriving Set and Vector from the former, String from the latter.

The output method Vector::printOn is not used directly in the Set implementations, although it is useful for instances of Vector outside the Set implementations.

Vector::grow() is similar to that in SmallSet and can be used directly in the implementation of SmallSet::grow(), but cannot be used directly in the implementation of FastSet::grow() .  The latter requires a new fresh Vector to receive values at re-randomized index locations. The ordering of post-grow contents bears no relation to the ordering of pre-grow contents. 

Vector::grow() can actually shrink the storage, depending on the value of newCapacity. But if grow extends, It is useful to implement Vector so that the new element locations are set to zero. It is also useful to set new elements locations to zero in the constructor.

With this considerations in mind, the implementation of FastSet::grow() becomes:

void FastSet::grow()
{
	Vector oldstorage(storage.getCapacity());
	for (int i = 0; i < storage.getCapacity(); i++)
		oldstorage[i] = storage[i];
	storage.grow(storage.getCapacity() * 4 / 3);
	for (i = 0; i < storage.getCapacity(); i++)
		storage[i] = NULL;
	for (i = 0; i < oldstorage.getCapacity(); i++)
		if (oldstorage[i])
			add(*oldstorage[i]);
}

Vector does not contain a data member count. The index operator, operator[ ], is valid for the entire range 0 to capacity-1. count is part of Set's state, and its value is maintained in the implementations of Set methods.

With Vector properly implemented, it should be possible to simply remove the member capacity from Set and replace the definition of storage from PSetObject *storage to Vector storage. Note that this instance of Vector is contained within Set by value.

In the implementation of Set and its derivatives, some minor changes are required.

• in the constructor for Set, the constructor for storage must be explicitly called with an initialCapacity value.

Set::Set(): storage(4)
{
	count = 0;
}

• all references to capacity must be changed to storage.getCapacity()
• the implementations of grow() has to be reviewed, as per the notes above.

Now it is possible to have a Vector of Set or Set of Vector. Being truly polymorphic, the hierarchy supports different items in the same container, such as a Vector that contains a Set and a String, or a Set that contains a Vector, a String, and another Set.