Go to the previous, next section.
A "Plex" is a kind of array with the following properties:
Four subclasses of Plexes are supported: A
FPlex is a Plex that
may only grow or shrink within declared bounds; an
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
Plex, it is possible to write user code
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
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 works just as
p.prev(i) when traversing by index.
Index-based traversal is generally a bit faster than Pix-based
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.
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.
Plex stand for the type name constructed via the
genclass utility (e.g.,
Plex p, q,
int i, j, base element
x, and Pix
Plex p(int size);
Plex p(int low, int size);
Plex p(int low, int high, Base initval, int size = 0);
p = q;
p.next(i); i = p.prev(i);
pix = p.first(); pix = p.last();
ptr = p.index_to_Pix(i)
j = p.add_low(x); j = p.add_high(x);
j = p.del_low(); j = p.del_high()
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, lo, hi)
p.error(const char * msg)
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:
int i = p.add(x)
int i = p.unused_index()
pix = p.unused_Pix()
Go to the previous, next section.