ezdsl.doc

Eazy Data Structures library for Delphi.

======================================================================
                                EZDSL
                             version 3.03

    Easy classical data structures for Delphi 1, 2, 3, 4, 5, and 6

              Copyright (c) 1993,2002 Julian M. Bucknall
======================================================================


Introduction
----------------------------------------------------------------------
The EZDSL units provide an OOP interface for classical data structures
for Delphi: stacks, queues, priority queues, lists, binary trees, hash
tables and so forth.

My objective in writing these units was to provide myself with a set
of well-encapsulated classes that would manage the tedium of using
these types of data structures, leaving me to concentrate on coding my
latest application. Furthermore, since I was able to concentrate on
the structures one at a time, without the hazard of an application
awaiting my endeavors, I could research and use the latest and best
algorithms.

This library was rewritten from my EZSTRUCS library that I first
released in August 1994. EZSTRUCS was written for Borland Pascal 7 and
hence it was not a simple port to Delphi. I was determined to use some
of the whiz new syntax of Delphi: exceptions, virtual constructors,
properties and so on. The first version of EZDSL appeared in 1995,
version 2 was ported to 32 bits for the Delphi 2.0 compiler (of course
making sure that it could still be compiled with Delphi 1.0 in 16
bits) and now, support for Delphi 3, 4, 5, 6 and packages.

For programmers migrating from BP7 a TCollection replacement is also
provided, although I would like to deprecate it a little. Originally,
the main purpose of the replacement TCollection was familiarity.
Having used Borland's TCollection from Turbo Vision and OWL a great
deal, I wanted to mimic as far as I could a container that had the
functionality and naming conventions contained within that object,
without necessarily restricting myself by doing so. However, what has
happened since the original TEZCollection was written is that I've
become well used to Delphi's TList; so much so in fact, that
TEZCollection seems archaic and outmoded. I warn old EZDSL aficionados
that TEZCollection probably won't make it into version 4.

Within this document I shall not spend too much time describing how
the data structures work and what they're for; any data structures
book will be able to provide that kind of information easily, and in
more depth than I could hope to do. The three books I have made a
great deal of use of (and that I recommend heartily) are

Algorithms, by Robert Sedgewick; Addison-Wesley
Data Structures, Algorithms and Performance, by Derek Wood; 
    Addison-Wesley
Practical Data Structures in C++, by Bryan Flamig; Wiley

Also, the three volumes of The Art of Computer Programming by Donald
Knuth belong on every serious programmer's shelf.

Also, a small word of warning. Using these units require that you have
a fairly good grounding in using pointers, objects and classes in
Delphi, including typecasting. If you need to, please review your
Delphi documentation on how to use them.

Note: this used to be a help file (originally converted from a text
document like this), but this was proving problematic when I wanted to
port EZDSL to Kylix. So, it's now a text file, again...



What's new in version 3?
----------------------------------------------------------------------
To all the previous users of EZDSL, welcome to version 3.

What is new about this version 3? Without further ado:

  Delphi 3, 4, 5 and 6 support, including EZDSL packages for each
  (Delphi 6 support is NEW FOR 3.03);

  A hash table class, using linear probing for collision detection,
  automatic table expansion/shrinking, support for different hash
  functions;

  NEW FOR 3.01 A boolean array class (also known as a bitset, a bit
  array or a bitmap); enabling several million booleans in an array
  like structure to be set true, false, toggled, ANDed, ORed, XORed
  with other boolean arrays, navigation though all true or false
  booleans, backwards and forwards.

  Simplification of the use of Compare with sorted containers, now you
  can alter Compare with a non-empty container and the container will
  sort its data objects according to the new Compare function.

  Separate thread-safe containers for 32-bit programming, thread-safe
  node allocation.

  The pseudo random number generator has been revamped and documented.

  There's been a lot of code clean-up behind the scenes as well. For
  example, I've changed my coding style and I've used different naming
  conventions for the protected/private fields inside the containers.

  Also, a warning is due: the TEZCollection will become deprecated in
  the next major version. I no longer use it--I've moved over to TList
  pretty well completely instead--and it doesn't really fit in any
  more. After all it was originally written to help BP7 programmers
  migrate to Delphi 1 and we're now at Delphi 6, with
  Kylix 2 on the Linux platform.

Note that there's no official Kylix support yet, I'm afraid. It should
be easy to do--I just claim a lack of spare time.



Container classes and Data objects
----------------------------------------------------------------------
The EZDSLxxx units define a set of data object containers. These are
containers into which you throw a bunch of data 'things' and retrieve
them at a later stage. The data 'things' can be anything:  integers,
strings, records, object instances, or whatever; we'll just use the
generic term data object. The different kinds of containers each have
different characteristics, some will keep the data objects sorted in
some order, some will give you fast serial access times, some will
just give you them back in the same order you put them in.  Some will
allow you to navigate through the structure (and will provide a
classic iterator method), some do not.

The containers can be separated into two types: those that own their
data objects, and those that do not. Being a data owner means that a
container will destroy its data objects when it is emptied or itself
destroyed. This distinction means that you could create two skip lists
for example, one a data owner and the other not, each with a different
sort sequence. You could then insert the same set of data objects into
both and know that, when you call the Empty method for both lists, the
data objects will get destroyed only once.

As you look at the code for the containers and at this documentation,
you'll see that the hierarchy tree is fairly flat (or narrow if you
look at it vertically): 

TAbstractContainer                 (EZDSLBSE.PAS)
  +--TStack                        (EZDSLSTK.PAS)
  +--TQueue                        (EZDSLQUE.PAS)
  |    +--TDeque                   (EZDSLQUE.PAS)
  +--TPriorityQueue                (EZDSLPQU.PAS)
  +--TLinkList                     (EZDSLLST.PAS) - single linked list
  +--TDList                        (EZDSLDBL.PAS) - doubly linked list
  +--TSkipList                     (EZDSLSKL.PAS)
  +--TBinTree                      (EZDSLBTR.PAS)
  |    +--TBinSearchTree           (EZDSLBTR.PAS)
  |         +--TrbSearchTree       (EZDSLBTR.PAS)
  +--THashTable                    (EZDSLHSH.PAS)
  +--TEZCollection                 (EZDSLCOL.PAS)
       +--TEZSortedCollection      (EZDSLCOL.PAS)
            +--TEZStringCollection (EZDSLCOL.PAS)
            +--TEZStrZCollection   (EZDSLCOL.PAS)
TBooleanArray                      (EZDSLBAR.PAS)

There is a single ancestor class that provides the important common
methods and fields (allocating/freeing a node, whether a container is
empty) and the base of the virtual methods hierarchy (Compare,
DisposeData, et al). Most of the other classes are descended directly
from this, with only a few further descendants. This is contrary to
lots of other container hierarchies where the author has endeavored to
arrange things so that everything descends from one another all the
way back to a doubly linked list or something. I felt that this type
of scheme was too restricting: if I found a better implementation of a
list I don't have to worry too much about breaking up my hierarchy (so
long as I interface the same methods). The other thing is that
deriving a stack from a linked list for example means that not only do
you get the Push and Pop methods but you also get a whole slew of
linked list methods appearing as well (Prev, Next, Insert, Delete or
whatever).

However I have tried to be consistent in my naming convention so that
for example, there is a method called Next for a TLinkList, TDList and
TSkipList but it works in different ways for each (and has a different
calling interface) - the Next method is not virtual.

There is one container that stands out from the crowd and from much of
the above: the boolean array. This data structure just provides an
array of boolean values, true or false, and no data objects are stored
inside. Remember that all of the information in this help file
relating to data objects (including ownership, disposal, duplication,
and so on) do not apply to the boolean array. It is a container truly
"on its own," since it doesn't descend from TAbstractContainer either.

The EZDSL library has been written assuming that the data objects are
pointers to something. This scheme makes it easy to have the
containers have lots of different kinds of objects and to be able to
deal with them properly.  However, there is nothing to stop you using
pointers to strings or even plain longints instead; just typecast to a
pointer when required (and typecast back again when the object is
retrieved from the container!). For example when using a stack you
could use integers as follows:

  var
    MyStack : TStack;
  begin
    MyStack := TStack.Create(False);
    try
      with MyStack do begin
        Push(pointer(19));
        Push(pointer(57));
        writeln(longint(Pop)); {outputs: 57}
        writeln(longint(Pop)); {outputs: 19}
      end;
    finally
      MyStack.Free;
    end;
  end;

Or you could write a container that would wrap up this slight
awkwardness and hide it from you. See the example programs EXINTQUE
and EXSTRSTK.



Data Objects and Polymorphism
----------------------------------------------------------------------
The first version of the EZSTRUCS unit (on which this EZDSL library
was originally based) had virtual methods called Compare, DisposeData
and DupData. However, I found that often the ONLY methods I was
overriding were... Compare, DisposeData and DupData! The data
container worked fine 'out of the box', it was such a pain to override
yet another class just to alter one of these methods.

I had two solutions to my perceived problem: make the data objects
derive from an ancestor object class or make the methods function
pointers. The first was out (I find it awkward), but the second was
just what I wanted. In fact Delphi itself is rife with this kind of
delegation model.

So, the data object related methods in the containers are in fact
procedure and function pointers held as properties in the container.
You set them when you initialize a new container, and they will be
used whenever two data objects need to be compared, or a data object
needs to be disposed of or you need to duplicate a data object.

To set them you first create your new container object by calling the
Create constructor. This sets the internal procedure and function
pointers of the object to 'do nothing' abstract routines. Then you set
the actual routines you want to use by modifying the required
properties: Compare, DisposeData and DupData.  EZDSL provides some
popular ones in EZDSLSUP.PAS:  comparison between two longints,
between two strings (short strings in Delphi 2/3), disposing and
duplicating the same.  

Although you can alter the DisposeData and DupData properties when the
container is not empty, it doesn't make much sense to do so. Altering
the Compare property has an interesting side effect: if the container
maintains its data objects in a sorted order, changing the Compare
method will cause the data objects to be resorted in the container
(note: this does not apply to the TEZSortedCollection).

The Compare, DisposeData and DupData routines that you write *must* be
global, declared 'far' in Delphi 1.0 and declared using the normal
Pascal fastcall calling convention (viz 'register') in Delphi 2/3. In
other words 

    (a) they cannot be nested routines;
    (b) in Delphi 1.0 they cannot be declared implicitly or 
        explicitly as near routines; and
    (c) in 32-bit Delphi they cannot be declared 'cdecl' or 'stdcall'.

They must also follow the routine prototypes TCompareFunc,
TDisposeDataProc and TDupDataFunc respectively.

To facilitate cloning containers with the most flexibility, you can
clone a container and use a different Compare function than the
container you are cloning from (useful for maintaining trees or lists
with their data objects in two different orders).

To facilitate cloning containers with the most flexibility, you can
clone a container and use a different Compare function than the
container you are cloning from (useful for maintaining trees or lists
with their data objects in two different orders).



Sorted Containers, Compare and Duplicate Data Objects
----------------------------------------------------------------------
A number of the containers in EZDSL maintain their data objects in
some kind of ordered sequence. The sequence that they are maintained
in is generally defined by the container's Compare property. Some
containers are automatically and always 'sorted': skip lists and
binary search trees are two examples. Some are never sorted: stacks
and queues for example. Some containers can be used sorted or
unsorted: examples are linked lists or double linked lists. One
container is kept in an ordered sequence, yet that sequence has
nothing to do with Compare : the hash table. The boolean array doesn't
support storing data objects at all, so this topic doesn't even apply.

The Compare property is a function that you write (or is one of the
supplied functions). The routine must compare two data objects and
return a negative number (e.g. -1) if the first data object is 'less'
than the second, zero if they are equal, and a positive number (e.g.