Category : Pascal Source Code
Archive   : GENERICS.ZIP
Filename : GENERICS.DOC

Eric C. Wentz

1-703-860-3807 {evenings before 11 p.m. Eastern}

CompuServe ID: 72070,1015

2374 Antiqua Court
Reston, Va. 22091



General Notes on the Included Archives:

One of the most important ideas behind OOP is that of code
re-useability. One important facet of this concept that seems to
be missing in Turbo's OOP extensions is that of Genericity. To
produce generally useful, re-usable code, it is important to be
able to implement abstract concepts (or datastructures) that are
independent of datatype. For example, consider the simple abstract
concept of a Stack. The operations needed for a Stack are well known
to all programmers. All Stacks implement Push,Pop,Top,Full,Empty and
maybe Depth. Genericity gives us a way to define this abstractly,
and Inheritance gives us the way to implement useable Stacks, such
as IntStacks, RealStacks, RecordStacks etc., with minimal extra coding.
In other words, by defining the abstract concept and utilizing it,
we can forget about the implementation details and achieve yet another
useful layer of abstraction in program design.

As the designer of the Eiffel programming language, Dr. Bertrand Meyer
argues, the true strengths of OOP will be realized by a Bottom-Up approach
to programming design (I can hear the Priests of Top-Down design chanting
evil thoughts even now!). By designing and implementing low-level,
generally useable Objects, we can avoid constantly reinventing that which
has already been adequately designed and implemented elsewhere. The true
power of OOP will not be realized until such time as there exists a large
body of such Objects from which to draw upon when coding specific
applications. The included packages are my (first) contribution to this
idea. I give them to the public domain in the hopes that others will also
undertake to build such low level, generally useable Objects to an ever
growing library of such code.

SPECIFIC NOTES:

FlexArrays.

The FlexArray is a simple analog of the native Array structure. It (as with
the native array) is limited by Turbo to a length of 65521 bytes, but
it is somewhat more flexible in that it is dynamically sized, and may
be dynamically resized as well. A FlexArray can be initialized to any
datatype. In fact, through reinitializing, it is possible to use one
FlexArray variable to contain any number of different datatypes (one at
a time) within the same program, though from a Software Engineering
viewpoint, I don't recommend this practice. If FlexArrays perform
slower then native arrays, it is only marginally so, and due to the
difference between Data Segment access times vs. Heap access times.

FlexStacks.

The FlexStack uses the FlexArray as its base type, and is subject to the
same limitations and capabilities as the FlexArray.

MaxArray.

The MaxArray is (sort of) an extension of the FlexArray. MaxArrays can
be allocated to a maximum size of 655210 bytes (theoretically), as
currently implemented. As this maximum will not be available to any
programs running under DOS, the MaxArray is actually limited only by
available Heap space. The only FlexArray method unsupported by MaxArrays
is that of resizing. MaxArrays are implemented by mapping the virtual
(visible) index onto one of 10 distinct FlexArrays. This makes the resize
operation extremely complex, and in my judgement impractical and unnecessary.
Further, this mapping will also slow the MaxArray's performance, perhaps by
a noticeable margin over that of the FlexArray. The old trade-off again,
Space vs. Speed, but the MaxArray is not really too bad.

GenericHeap.

The GenericHeap uses the MaxArray as its base type, and is subject to the
same limitations and capabilities as the MaxArray. Additionally, when
initializing a GenericHeap, a function must be provided which determines
the sequencing of items in the GenericHeap. This function may be changed
during run-time to provide sorting or prioritization by different keys
when the Heaped items are records -- see unit SortFunc for examples.
In a test program, I used the GenericHeap to sort 250,000 integers on my
humble little 8088 based clone (6.44 mhz of BLAZING "Turbo" speed!). The
sort took just over 9 hours, which I thought was pretty good, all things
considered! The Heap structure itself was built (using the SiftUp operation)
in under an hour, which implies to me that priority queues of such titanic
size would be found to be quite practical. Certainly such queues of only
say, 10,000 records will have very satisfying performance.


A COMMENT ON "PROPRIETARY" CODE INCLUDED WITH THE ABOVE PACKAGES:

I feel that the above packages are complete, with no benefits to be had
by modification. In the spirit of creating a "global" library of generally
useable objects, they SHOULD not EVER be modified, but should remain
"Private". Distributing them only as TPU's guarantees this. You may
cynically note that I have offered the source code for a small sum, but this
is intended only to discourage the distribution. Keeping modifications
out of existence will only serve to enhance the standardization of code
using such a library. I don't want your money, I want you to use my
packages as they were intended to be used!


To seemingly reverse myself immediately, I have included ALL the source code
for the GenDatum,GenList and derivative Objects. This is because I am NOT
so convinced of their completeness as with the others. For example, the
SWAP method in Unit LGenHeap is quite slow, and could no doubt be improved
{I have noted this in the source file}. Additionally, you may have need of
only a singly-linked list, and having the source for the GenDatum object
and the DoubLink derivative, AND the GenList Object should help you design
it. For that matter, what about Generic Trees (Binary and otherwise)? Again,
having the source for these units should provide useful design methods.
The only code here I would like to see remain untampered-with is the GenDatum
itself, but even there somebody wiser than I may be able to truly improve it,
so I have included it as well.

FINAL NOTE:

The truly important aspect of all these packages is that of Genericity. By
utilizing this concept in the design of other Objects, we can (hopefully)
create a foundation of standardized, powerful, reliable Objects upon which
we can build easily maintained and modifiable applications. As the Prophets
of OOP would say, "welcome to the future of Software Engineering"!

FINAL FINAL NOTE:

I am currently working on a derivative of the MaxArray which will allow
N-Dimensional arrays, and on a similar (but not derivative) Object which
will be a Virtual array limited only by disksize (NOT 32 Mbytes!). The
former is almost complete, but the latter is only embryonic. Look for
them sometime around Mid-August. -- ECW