11.12 DYNAMIC ARRAY, STACK, BINARY HEAP, SORTED COLLECTION

Purpose:

The prime purpose of this class is to provide an array that automatically reallocates itself when a larger size is required. A BINARY HEAP is only a special case of the ARRAY organization. Note that an ARRAY (or a HEAP) can contain either whole objects or pointers to objects.

In OrgC, an array always exists as an attribute of a holder object. This allows you, for example, to have a ring of objects with an array on each object, or an array of arrays. If you need just an array as such, declare a dummy "holder" object for it.

Memory considerations:

Internally, the holder object contains a pointer to a transparent header, which then points to the array itself. This represents an overhead of 32 bytes under UNIX or 16 bytes for medium/small model under DOS, for each array used. When an array is declared but not used, only one pointer is used.

Note that increment>0 represents an arithmetic increment, increment<0 represents a multiplicative increment. For example, increment=-3 will triple the size of the array any time the array size overflows. Increment= -1 is interpreted as an array of fixed size. Index overflow for such an array generates an error message.

Warning:

When an array reallocates itself, the old array becomes free but may not be very useful. For example, when doubling the array size several times, almost 1/2 of the memory may essentially be wasted. Intuitively, an array looks like a simple and practical data arrangement but, in many practical situations, a ring is better; it requires less memory and is faster to operate upon.

Warning:

Array of (void *) pointers is not permitted in the current version. Use (char *) pointers instead.

Index access (in-line function):

Other objects must refer to the elements of the array by index, never by pointer. However, when indexing an array, a pointer may be used temporarily. For example, ind() checks the index range, and returns a pointer to the array. If the index overflows the size, the array automatically resets its size.

p=id.ind(hp,i); *p=k; is equivalent to a[i]=k;

Inside algorithms, where high speed is required, and the size of the array does not change, you must first establish the base of the array by calling: a=id.ind(hp,0). Then you can access the array as if no special management were in force: a[i]=k; a[12]=a[1]+a[3] and so on.

Note that id.head(hp); is equivalent to id.ind(hp.0); but faster.

Sorting:

An array can be sorted. The user must provide a function that compares two objects. Internally, the sort is based on qsort().

Stack:

An array may be used as a stack. After forming the initial array, each push() adds one object to the top of the array, and each pop() returns the top object of the stack. If the size of the stack overflows the size of the array, the array increases its size by the given increment.

Sorted Collection:

In addition to function sort() which sorts the array, there is aset of functions which keep the array sorted even after adding or removing its elements. Such sorted array can be used as an ordered collection. This applies not only to arrays of full objects, but also to arrays of pointers.

Operations on sorted arrays are relatively fast: sort() uses the system function qsort(), binary search is used to find objects in the array, and a fast system function moves blocks of memory when a inserting or removing an element of the array.

If you want to keep the array sorted, restrict yourself to using the following commands: addOrd(), delOrd(), getOrd(), ins(), and ind().

For an example of using a sorted array, see test53.c.

Binary Heap:

A partially sorted binary heap can be efficiently implemented as an array. The heap requires a function which compares two array entries, just like the function required for qsort(). The heap is always ordered so that the minimum array entry is at the top of the heap (index=0).

All HEAP operations require that a callback function is given. Any time an object changes its position within the heap, this function is called with the new index location. This permits you, for objects outside of the queue, to monitor permanently the position of the objects within the queue. This can be best seen from the following example.

Example:

class Head { 
    ZZ_EXT_Head 
}; 
class Employee { 
    ZZ_EXT_Employee 
public: 
    int heapIndex; /* everything public just for demonstration */ 
    int salary; 
    ... 
}; 
class PtrEmpl { 
    ZZ_EXT_PtrEmpl 
}; 
ZZ_HYPER_ARRAY(heap,Head,PtrEmpl); 
ZZ_HYPER_SINGLE_LINK(link,PtrEmpl,Employee); 
void bck(void *p,int i){ /* call-back function to record position */ 
    Employee *e; 
    e=link.fwd((PtrEmpl *)p); 
    e->heapIndex=i; 
} 
int sortFun(const void *v1,const void *v2){ 
    Employee *e1,*e2; 
    e1=link.fwd((PrtEmpl *)v1);
    e2=link.fwd((PtrEmpl *)v2); 
    return(e2->salary - e1>>salary); 
} 

Head *h; 
PtrEmpl *p; 
Employee *e; 
int i; 
... 
/* assume Employee e is given and should enter the heap */ 
p=new PtrEmpl; 
link.add(p,e); 
heap.inHeap(sortFun,h,p,bck); /* automatically updates heapIndex */ 
... 
/* now we can update any Employee object */ 
e->salary=4600; /* new value */ 
i=e->heapIndex; 
if(i>=0)heap.updHeap(sortFun,h,i,bck); 

The parameters of the callback function are:
void *p; ... pointer to the object in the queue, cast as (void*);
int i; ... index in the queue.

If the object in the queue provides a pointer to the outside object, this is enough to reach the outside object. When using only inHeap() and outHeap(), this function is not really needed, and can be replace by a dummy function

void bck(void *p,int i){}.

Using a heap of pointers is usually better than working with a heap of whole objects.

Arrays and pointers:

Generally, it is not good practice to access elements of an array via pointers. An array is a sequential arrangement of objects, and should be accessed by index. If you decide to violate this rule (the reason may be the performance of some special algorithm), make sure that the array has a fixed size (form the array with increment= -1). If the array may reallocate itself, pointers leading into the array may suddenly become invalid.

There are three typical situations when pointers leading into an array may cause trouble:

1. Temporary object linked to the array:

struct tempObj {
    ....
    Blob *b;
};
ZZ_HYPER_ARRAY(ar,Head,Blob);
Head *hp; tempObj t;
    ...
t.b=ar.ind(hp,42);

2. Remembering a pointer for too long

typedef struct Blob Blob;
class Blob {
ZZ_EXT_Blob
public:
    int i;
};

ZZ_HYPER_ARRAY(ar,Head,Blob);
Head *hp; Blob *b;
    ...
b=ar.ind(hp,42);
b->i=31; /* perfectly fine */
    ... /* lot of array manipulation */
b->i=32; /* may crash the run */

3. Transparent pointers

ZZ_HYPER_ARRAY(ar,Head,Blob);
ZZ_HYPER_SINGLE_RING(myRing,Blob);

The array must be fixed, otherwise reallocation of the array may destroy the ring.

Sometimes, a change of organization can improve the robustness of the data. In the following organization, the AGGREGATE parent pointer leads from Employee to Department:

class Header {...};
class Department {..};
class Employee {... };
ZZ_HYPER_ARRAY(myArray,Header,Department);
ZZ_HYPER_SINGLE_AGGREGATE(inDept,Department, Employee);
...
// potential problem with the parent pointer in 'inDept'
a=myArray.form(hp,2000,500); 
...
// no problem but what do you do if the array is not big enough
a=myArray.form(hp,2000,-1);

Better organization is to store an integer index directly inside the Employee class, and update it manually:

When no pointers lead into an array, there is no potential danger or restrictions:

class Header {...};
class Department {..};
class Employee {int parent; ... };
ZZ_HYPER_ARRAY(myArray,Header,Department);
ZZ_HYPER_SINGLE_COLLECT(inDept,,Department,Employee);

Saving to disk:

save() and open() treat an ARRAY as a part of the holding object, and they save/restore the array automatically with it. In the SWEEP operation, the expansion process passes through the array and its elements as if they were normal single objects.

Whether you use a plain C++ array, or the dynamic ARRAY from the OrgC++ library, make sure that #define ZZ_INHERIT is included in your environ.h file.

If you have an array of (char *) pointers, the pointers will be properly updated after save() and open(). However, the expansion algorithm will not expand through these pointers. The situation is similar to the use of GENERAL_LINK (see p.11.6.2).

Syntax:

Explanation:

High_water_mark is the highest index used. It is -1 before the array has been used, and equal to size-1 when it is full. For example, if you formed an array of 10 elements with increment=30, and you called the ind() function for index=13,22,58,16, and 0, then the size() function will return: size=80, increment=30, and high_water_mark=58.

Examples:

1. A comprehensive test of all ARRAY features is in test9a.c. Note that both an array of objects and an array of pointers to these objects are used. Binary heap operations are also tested.
2. test16c.c shows how to save an array of objects to disk, and how to work with an array of integers. For the purpose of testing, the data is first saved in ASCII, restored, saved in binary, restored, and only then the third copy is printed.
3. test32a.c and test32b.c show some examples of advanced handling of arrays.

Previous Section 11.11 Time Stamp

Next Section 11.13 Hash Tables