Abstract Data Types

The utilib/src/adt directory contains definitions for the following abstract datatypes:

These data types are defined as templates.

Arrays

The array classes provide a nice level of encapsulation for array data types. The main distinction between the Basic, Simple and Num array types is that the Basic array types do not include I/O operations, the Simple arrays add I/O operations, and the Num arrays add numerical vector operations. The following is a brief tutorial on how to use array-type classes in utilib. This is just what you need to get up and running. I'll touch on implementation where necessary to explain behavior and where useful for debugging. The primary advantage of using these classes is extra safety features such as runtime bounds checking and reference counting. Also bit arrays can save a lot of space.

One-Dimensional Arrays

The most commonly used 1D arrays are BitArray's, IntVector's and RealVector's. The syntax for doubles and ints is the same, so we only include examples for IntVector's, indicating where BitArray syntax differs. To use these arrays, you need to include the appropriate header files: 

   #include "BitArray.H"
   #include "DoubleVector.H"
   #include "IntVector.H"
You can then declare variables as usual: 
   IntVector IntTester;
   BitArray BitTester;
All of these ArrayData classes have a pointer to the data in the field Data . You can get this pointer using the data() function. 
   int *intarray = IntTester.data();
Ordinarily, you will not need to do this, but it can be useful for debugging. Inside a debugger like dbx, typing 
   print *IntTester
will return useful information like the data location, size, etc, and 
   print IntTester.Data[i]
allows you to view the ith entry in the IntVector.

The declarations above (no arguments) construct an object with a NULL data pointer. One can also specify the initial content of the IntVector: 

   int array-of-ints[20];
   IntVector IntTester(20, array-of-ints);
The first argument is the length of the array and the second is a pointer to an array of the appropriate type. The data field in the IntVector will point to this array. One can also construct a copy of an existing IntVector: 
   IntVector CopiedVector(IntTester);
This will allocate a new integer vector and initialize it with the contents of IntTester. The Data field in CopiedVector points to the new copy.

Frequently, one will need to use an empty constructor (i.e. start with a size-zero vector) and then put in the true data. More generally, you may want to grow and shrink the vector dynamically: 

   IntTester.resize(100);
This will allocate a new array of 100 integers and copy the old data (if any) into the beginning of the array. For example, if a 30-element array is resized to 70, the first 30 elements of the new array will be the values from the old array. For BasicArray and SimpleArray objects, you cannot assume anything about the next 40 values (initialize or set them yourself), but for NumArray objects these array elements will be initialized to zero. If an array of size 70 is resized to 30, then the last 40 elements are truncated. 
   IntTester.size()
returns the length of IntTester (in integers [more generally, array elements], not bytes).

The equals (=) operator allocates new space. Thus 

   CopiedVector = IntTester;
creates a new integer array and copies the contents of IntTester into that array. The Data field of CopiedVector points to the new space. If the vector already exists and you want to reuse the already-allocated space, use the << operator: 
   ExistingIntVector << IntTester;
This copies the contents of the Data array from IntTester into the array for ExistingIntVector. The allocated arrays must be of the same size or you will get an error. To copy by reference, use the &= operator. Thus 
   Intvector SharedVector &= IntTester;
will have the data of SharedVector point to the same array that the data of IntTester points to (reference counts are properly updated).

The equals (=) operator is overloaded to allow(re)initialization of a vector that has already been created. 

   intTester = 15;
This sets every element of IntTester to 15 (or obviously some other integer).

Getting array elements works looks like normal array references (at least for 1D arrays): 

   int index, newvalue;
   IntTester[index] = newvalue;
   newvalue = IntTester[index];
Here's where BitArray syntax varies slightly. Instead of typing 
   BitTester[index] = 1;  // wrong
you should use 
   BitTester.set(index);  // turns the (index)th bit on
   BitTester.reset(index); // turns the (index)th bit off
There are ways to manipulate consecutive subvectors. I haven't needed them, so I'm omitting them for now.

Finally, note that the BitArray class is derived from BitArrayBase. This class can be used to define compact representations for user-defined enumeration types. For example, see the TwoBitArray and EnumBitArray classes.

Dynamic Abstract Data Types

Two different classes of templates have been defined for hash tables, heaps and splay trees. The first is a simple template, which uses a simple data type to define the key used by these data structures. The second is a generic template, which uses a generic class to define the key. These two classes are derived from from an abstract datatype class that defines the basic operations of the class using abstract operations on the keys.

Splay Trees

Splay trees, or self-adjusting search trees, are a simple and efficient data structure for storing an ordered set. The data structure consists of a binary tree, with no additional fields. It allows searching, insertion, deletion, deletemin, deletemax, splitting, joining, and many other operations, all with amortized logarithmic performance. Since the trees adapt to the sequence of requests, their performance on real access patterns is typically even better. Splay trees are described in a number of texts and papers [LewDen91, SleTar85, Wei92, Woo93].

Heaps

See [CorLeiRiv96] for more details about heaps. The design of the UTILIB heap classes is similar to the heap classes developed for the PICO software library.

Hash Tables

See Cormen, Leiserson and Rivest [CorLeiRiv96] for more details about hash tables. UTILIB provides several default hash functions.