Expandable

Expandable.h may be found in the Library. It provides a feature that I've implemented several times although this one is better that the past versions.

Templates are a fairly recent C++ invention (considering that programming languages started around the late 50s). The idea is simple: Write a description of an algorithm or group of algorithms that may be applied to any class of objects. An example might be a sorting algorithm. This is a single algorithm but it is complicated to get right. It would be nice to be able to do a qsort on an array of say, integers and strings and class objects. Sorting requires some sort of selection mechanism like "greater than" and an assignment operator like "=". But each of the objects suggested above have really different selection and assignment operators. So, the template allows the objects do define their own operations while the basic sorting algorithm does its work deciding how the items should be sorted.

In the C language arrays are statically defined. They are fixed in length. So the programmer is left with very little option but to make really large arrays to avoid overflow. Not a good choice. Expandable at a run time cost avoids that dilemma. The declaration for an expandable array is:

Expandable<String, 2> data;

String& s = ex[0];
  ex[3] = _T("Nonsense");
  s = ex[3];

The reference s is to the first element of the array ex. So far the array ex doesn't look too interesting. The fourth element of the array (i.e. ex[3]) is set to "Nonsense" (the _T("") creates an Unicode string). Then the last assignment to s will copy the string in the first element of the array. Note that during the assignement to the fourth element the array had to be expanded as only 2 elements were originally assigned to the array.

Where it becomes interesting is when I try to put 100 strings into it. Behind the scene ex expands to accomodate the 100 strings. It does this by quietly increasing the size of the array as new elements are added to the array that exceed the current size of the array. It is still an array, one can qsort it, one can index into it, one can loop over all the elements forward, backward and randomly.

Well that solves the overflow problem of C style arrays. What is the cost of this? The cost includes the requirement that any entity (class or typedef) must have four specific operations. A class Data, e.g. class Data {...}, must have the following "methods" or functions:

• Constructor with no argument, e.g. Data(), which initializes all components of the class
• Copy Constructor, e.g. Data(const Data& d), which copies all components of object d to object *this
• Assignment operator, e.g. Data& operator= (Data& d), which copies all components of object d to object *this and returns *this
• Destructor, e.g. ~Data() that releases objects obtained from the heap and zeros all data components

Furthermore, the Expandable Template requires a "method" to compute the index each and every time so that overflow is detected and avoided. It avoids overflow by creating a new array block double in size of the current array block and copying all the data from the current block to the new block. Expensive, you say, yep. But bloody convenient to know that there can never be overflow! And it can be sorted too. Loops are easy, it is just an indexed array.

Is there any way to cut the overhead down? Yes, just make the expandable array contain pointers to the data. Then the only copying required is a pointer. For big complicated data structures that makes the cost quite reasonable. However, for simpler structures with better guesses about size, one can just put the structure in the array and be done with it.

ExpandableP

The idea of an array of pointers to cut the overhead of copying the data when expanding the array was enough incentive to create a template to do just that. But it turns out that having an array of pointers made the destructor a bit clumsy. So another template is required to manage the pointers:

class Datum {
private:
int      value;
String   name;
public:

  Datum() : value(0) { }
 ~Datum() { }
   o o o
  };


typedef RcdPtrT<Datum> DatumP;


class MyClass {
ExpandableP<Datum, DatumP, 2> data;
public:

  MyClass() { }
 ~MyClass() { }
   o o o
  }

The Record Pointer (i.e. DatumP) defined by the RcdPtr Template (i.e. RcdPtrT) does all the right things when the expandable array needs to be expanded. The actual data node (i.e. Datum) is just moved from one array to another during the expansion.

Iterators

One day I got tired of creating for loops for an expandable array. First one needs to find the current number of elements in the array. Then a loop is created with an index that ranges from zero to just less than the the number of elements. This two step process still left one with the job of indexing into the array to accomplish any task. By the way, I came on this idea by using one of the MFC facilities for accessing the Microsoft ACCESS database.

Anyway, this is certainly a simpler version of an iterator over a database. I created a template to iterate over an expandable array provided there was one such array in the class. The implementation can be found in the Library, but for now I'll just show how to use it:

Datum* find(String name) {
MyDataIter iter(myObject);     // where my Object is an object of MyClass
Datum*     datum;

  for (datum = iter(); datum; datum = iter++) {
    if (datum->name == name) return datum;
    }

  return 0;
  }

MyDataIter is either a class or a typedef and requires the name of the object to iterate over. Both iter() and iter++ return a pointer to a datum or return zero (i.e. null, NULL, 0). Zero is interpreted as the end of the array in the loop, i.e. false in the for conditional segment. So the body of the loop is assured of having a real "datum" pointed to by the datum variable.

The iterator is useful because the mechanism for controlling the point in the array to reference is contained in the iterator not in the object holding the data. So having two iterations over the same data are possible and they do not interfere with each other (unless there is a lot of adding and deleting happening).

The idea worked so well that for an array I added a reverse iteration (i.e. iter--)and deleting an object in the array and collapsing the array to fill in the hole.

Then I noticed that other data structures could be managed this same way. So I added an iterator with identical use (though not identical implementation) for the linked list in the library. When I come across other data structures that lend themselves to this approach I generally create a class that will contain the iteration mechanisms. Be aware though that adding and deleting may cause problems with iteration (even with just one iterator, think hard about those operations).