User's Guide to the GNU C++ Class Library - Plex

Plex classes

A ``Plex'' is a kind of array with the following properties:

• Plexes may have arbitrary upper and lower index bounds. For example a Plex may be declared to run from indices -10 .. 10.

• Plexes may be dynamically expanded at both the lower and upper bounds of the array in steps of one element.

• Only elements that have been specifically initialized or added may be accessed.

• Elements may be accessed via indices. Indices are always checked for validity at run time. Plexes may be traversed via simple variations of standard array indexing loops.

• Plex elements may be accessed and traversed via Pixes.

• Plex-to-Plex assignment and related operations on entire Plexes are supported.

• Plex classes contain methods to help programmers check the validity of indexing and pointer operations.

• Plexes form ``natural'' base classes for many restricted-access data structures relying on logically contiguous indices, such as array-based stacks and queues.

• Plexes are implemented as pseudo-generic classes, and must be generated via the genclass utility.

Four subclasses of Plexes are supported: A FPlex is a Plex that may only grow or shrink within declared bounds; an XPlex may dynamically grow or shrink without bounds; an RPlex is the same as an XPlex but better supports indexing with poor locality of reference; a MPlex may grow or shrink, and additionally allows the logical deletion and restoration of elements. Because these classes are virtual subclasses of the ``abstract'' class Plex , it is possible to write user code such as void f(Plex& a) ... that operates on any kind of Plex. However, as with nearly any virtual class, specifying the particular Plex class being used results in more efficient code.

Plexes are implemented as a linked list of IChunks . Each chunk contains a part of the array. Chunk sizes may be specified within Plex constructors. Default versions also exist, that use a #define'd default. Plexes grow by filling unused space in existing chunks, if possible, else, except for FPlexes, by adding another chunk. Whenever Plexes grow by a new chunk, the default element constructors (i.e., those which take no arguments) for all chunk elements are called at once. When Plexes shrink, destructors for the elements are not called until an entire chunk is freed. For this reason, Plexes (like C++ arrays) should only be used for elements with default constructors and destructors that have no side effects.

Plexes may be indexed and used like arrays, although traversal syntax is slightly different. Even though Plexes maintain elements in lists of chunks, they are implemented so that iteration and other constructs that maintain locality of reference require very little overhead over that for simple array traversal Pix-based traversal is also supported. For example, for a plex, p, of ints, the following traversal methods could be used.

	for (int i = p.low(); i < p.fence(); p.next(i)) use(p[i]);
	for (int i = p.high(); i > p.ecnef(); p.prev(i)) use(p[i]);
	for (Pix t = p.first(); t != 0; p.next(t)) use(p(i));
	for (Pix t = p.last(); t != 0; p.prev(t)) use(p(i));

Except for MPlexes, simply using ++i and --i works just as well as p.next(i) and p.prev(i) when traversing by index. Index-based traversal is generally a bit faster than Pix-based traversal.

XPlexes and MPlexes are less than optimal for applications in which widely scattered elements are indexed, as might occur when using Plexes as hash tables or ``manually'' allocated linked lists. In such applications, RPlexes are often preferable. RPlexes use a secondary chunk index table that requires slightly greater, but entirely uniform overhead per index operation.

Even though they may grow in either direction, Plexes are normally constructed so that their ``natural'' growth direction is upwards, in that default chunk construction leaves free space, if present, at the end of the plex. However, if the chunksize arguments to constructors are negative, they leave space at the beginning.

All versions of Plexes support the following basic capabilities. (letting Plex stand for the type name constructed via the genclass utility (e.g., intPlex , doublePlex )). Assume declarations of Plex p, q , int i, j , base element x , and Pix pix .

Plex p;

Declares p to be an initially zero-sized Plex with low index of zero, and the default chunk size. For FPlexes, chunk sizes represent maximum sizes.

Plex p(int size);

Declares p to be an initially zero-sized Plex with low index of zero, and the indicated chunk size. If size is negative, then the Plex is created with free space at the beginning of the Plex, allowing more efficient add_low() operations. Otherwise, it leaves space at the end.

Plex p(int low, int size);

Declares p to be an initially zero-sized Plex with low index of low, and the indicated chunk size.

Plex p(int low, int high, Base initval, int size = 0);

Declares p to be a Plex with indices from low to high, initially filled with initval, and the indicated chunk size if specified, else the default or (high - low + 1), whichever is greater.

Plex q(p);

Declares q to be a copy of p.

p = q;

Copies Plex q into p, deleting its previous contents.

p.length()

Returns the number of elements in the Plex.

p.empty()

Returns true if Plex p contains no elements.

p.full()

Returns true if Plex p cannot be expanded. This always returns false for XPlexes and MPlexes.

p[i]

Returns a reference to the i'th element of p. An exception (error) occurs if i is not a valid index.

p.valid(i)

Returns true if i is a valid index into Plex p.

p.low(); p.high();

Return the minimum (maximum) valid index of the Plex, or the high (low) fence if the plex is empty.

p.ecnef(); p.fence();

Return the index one position past the minimum (maximum) valid index.

p.next(i); i = p.prev(i);

Set i to the next (previous) index. This index may not be within bounds.

p(pix)

returns a reference to the item at Pix pix.

pix = p.first(); pix = p.last();

Return the minimum (maximum) valid Pix of the Plex, or 0 if the plex is empty.

p.next(pix); p.prev(pix);

set pix to the next (previous) Pix, or 0 if there is none.

p.owns(pix)

Returns true if the Plex contains the element associated with pix.

p.Pix_to_index(pix)

If pix is a valid Pix to an element of the Plex, returns its corresponding index, else raises an exception.

ptr = p.index_to_Pix(i)

if i is a valid index, returns a the corresponding Pix.

p.low_element(); p.high_element();

Return a reference to the element at the minimum (maximum) valid index. An exception occurs if the Plex is empty.

p.can_add_low(); p.can_add_high();

Returns true if the plex can be extended one element downward (upward). These always return true for XPlex and MPlex.

j = p.add_low(x); j = p.add_high(x);

Extend the Plex by one element downward (upward). The new minimum (maximum) index is returned.

j = p.del_low(); j = p.del_high()

Shrink the Plex by one element on the low (high) end. The new minimum (maximum) element is returned. An exception occurs if the Plex is empty.

p.append(q);

Append all of Plex q to the high side of p.

p.prepend(q);

Prepend all of q to the low side of p.

p.clear()

Delete all elements, resetting p to a zero-sized Plex.

p.reset_low(i);

Resets p to be indexed starting at low() = i. For example. if p were initially declared via Plex p(0, 10, 0) , and then re-indexed via p.reset_low(5) , it could then be indexed from indices 5 .. 14.

p.fill(x)

sets all p[i] to x.

p.fill(x, lo, hi)

sets all of p[i] from lo to hi, inclusive, to x.

p.reverse()

reverses p in-place.

p.chunk_size()

returns the chunk size used for the plex.

p.error(const char * msg)

calls the resettable error handler.

MPlexes are plexes with bitmaps that allow items to be logically deleted and restored. They behave like other plexes, but also support the following additional and modified capabilities:

p.del_index(i); p.del_Pix(pix)

logically deletes p[i] (p(pix)). After deletion, attempts to access p[i] generate a error. Indexing via low(), high(), prev(), and next() skip the element. Deleting an element never changes the logical bounds of the plex.

p.undel_index(i); p.undel_Pix(pix)

logically undeletes p[i] (p(pix)).

p.del_low(); p.del_high()

Delete the lowest (highest) undeleted element, resetting the logical bounds of the plex to the next lowest (highest) undeleted index. Thus, MPlex del_low() and del_high() may shrink the bounds of the plex by more than one index.

p.adjust_bounds()

Resets the low and high bounds of the Plex to the indexes of the lowest and highest actual undeleted elements.

int i = p.add(x)

Adds x in an unused index, if possible, else performs add_high.

p.count()

returns the number of valid (undeleted) elements.

p.available()

returns the number of available (deleted) indices.

int i = p.unused_index()

returns the index of some deleted element, if one exists, else triggers an error. An unused element may be reused via undel.

pix = p.unused_Pix()

returns the pix of some deleted element, if one exists, else 0. An unused element may be reused via undel.