ezdsl.doc

Delphi数据结构分析源码

  Returns the data object at the top of the stack without popping it.
  If the stack is empty, nil is returned.

Declaration
  function Pop : pointer;
Description
  Pops the data object from the top of the stack and returns it.  In
  DEBUG mode, an assertion error will occur if the stack is empty.

Declaration
  procedure Push(aData : pointer);
Description
  Pushes the data object aData onto the top of the stack.

======================================================================

TQueue (EZDSLQUE.PAS)
======

A queue is a FIFO container (first in first out): the first object put
in the queue will be the first popped, the last object will be the
last to be popped. You can examine (peek at) the next data object to
be popped.  However you cannot navigate through the queue.

Interfaced Methods
------------------

Declaration
  constructor Create(DataOwner : boolean); override;
Description
  Creates the queue by calling the ancestor's Create after setting a
  node size of 8.  If DataOwner is true, the new queue will own its
  data objects.

Declaration
  procedure Append(aData : pointer);
Description
  Adds the data object aData to the end of the queue.

Declaration
  constructor Clone(Source : TAbstractContainer;
                    DataOwner : boolean; NewCompare : TCompareFunc);
                                                            override;
Description
  Creates a copy of the Source queue.

Declaration
  procedure Empty; override;
Description
  Repeatedly calls the Pop method (disposing of the data object
  returned if a data owner) until the queue is empty.

Declaration
  function Examine : pointer;
Description
  Returns the data from the top of the queue without popping it. If
  the stack is empty, nil is returned without causing an error.

Declaration
  function Pop : pointer;
Description
  Pops the data object from the front of the queue and returns it.
  In DEBUG mode, an assertion error will occur if the queue is empty.

======================================================================

TDeque
======

A deque (sometimes pronounced DECK, sometimes DEQUEUE) is a queue
that allows objects to be added to, or removed from the front or back
of the queue. This particular implementation of a deque just allows
queue jumpers, ie data objects can also be pushed into the front of
the queue, giving it stack-like behaviour (Flamig calls this variant
a Staque, see references). It is descended from the basic TQueue and
inherits Pop and Append.

Interfaced Methods
------------------

Declaration
  procedure Push(aData : pointer);
Description
  Pushes the data object aData to the front of the deque.

======================================================================

TPriorityQueue
==============

A priority queue is much like an ordinary queue, except that the
smallest data object in the queue will be popped first (rather than
the 'oldest'). Another name for a priority queue is a heap (not to be
confused with the Pascal heap where memory blocks are allocated and
freed).  As it imposes a sort order on the data objects, you must
override the Compare function.

If the Compare method returns values in the 'normal' sense (ie
Compare returns a negative number if Data1 < Data2, 0 if Data1 =
Data2, and a positive number otherwise), then data objects will be
popped off smallest first, ie in increasing order. However, if
Compare returns values in the 'reverse' sense (ie returning negative
if Data1 > Data2, etc), then elements will be popped off largest
first, ie in decreasing order. Thus by carefully selecting Compare,
this object will provide the classic min-heap and max-heap data
structures.

Notice that the well-known Heap Sort algorithm uses a structure of
this type, and in fact this structure could be used to provide a
generic sort routine. It will be faster than using a skip list for
example (the data objects are not held internally in a fully sorted
manner, they are just sorted in a 'loose' sense).

Interfaced Methods
------------------

Declaration
  constructor Create(DataOwner : boolean);
Description
  Creates the queue by calling the ancestor's Create after setting a
  node size of 16.  If DataOwner is true, the new queue will own its
  data objects.

Declaration
  procedure Append(aData : pointer);
Description
  Adds the data object aData to the priority queue.

Declaration
  constructor Clone(Source : TAbstractContainer;
                    DataOwner : boolean; NewCompare : TCompareFunc);
                                                            override;
Description
  Creates a copy of the Source queue.

Declaration
  procedure Empty; override;
Description
  Repeatedly calls the Pop method (disposing of the data object
  returned if a data owner) until the queue is empty.

Declaration
  function Examine : pointer;
Description
  Returns the data object from the top of the queue without popping
  it. If the queue is empty, nil is returned.

Declaration
  function Pop : pointer;
Description
  Pops the data object from the front of the queue and returns it.
  If Compare works in the 'normal' sense (ie returns a negative value
  for 'less than') then the data object will be the smallest,
  otherwise the data object will be the largest.  In DEBUG mode, an
  assertion error will occur if the queue is empty.

Declaration
  function Replace(aData : pointer) : pointer;
Description
  Equivalent to an Append followed by a Pop, but faster. Note that
  the same data object could be returned (it maybe smaller (larger)
  than all the data objects in the queue).

======================================================================

TLinkList
=========

A linked list is a container which is a chain of data objects. From a
given position in the list you can move forwards or backwards to the
next or previous data object. You cannot directly jump to the Nth
data object, instead you have to walk the list from the beginning
counting as you go. This list implementation has an implied 'cursor'
which points to the current data object, you move this cursor along
the list by means of the list's methods (eg Next and Prev). You can
examine the data object that the cursor is pointing to, or insert a
new one before or after the cursor, or delete the data object at the
cursor (unlink it).

There are two special cursor positions associated with this list:
before the first data object (known as BeforeFirst) and after the
last data object (known as AfterLast). Even in an empty list these
are deemed different. In the diagram of a linked list below the three
data objects are a, b and c, and the internal cursor is pointing at
c:

       BeforeFirst --> a --> b --> c --> AfterLast

                                   |
       Cursor ---------------------+


As a convenience to the programmer, this implementation of a linked
list allows the data objects to be maintained in a sorted order. To
do this there are some practical and some theoretical considerations.
The practical ones first: you must override Compare and you must use
InsertSorted to insert data objects into the list. The theoretical
considerations are to do with the linear sequential nature of a
linked list: to find where to insert a data object the list must
start at the beginning of the list and walk the list calling Compare
for each data object it encounters until it finds the place where the
new data object can be inserted. A time-consuming process as you can
appreciate.  You should only use sorted linked lists if the list is
built only once or if the number of data objects in the list is
likely to be small.

This particular implementation is a singly-linked list (each node has
just a single link to the 'next' node), however it uses a particular
algorithm that enables it to have the performance capabilities of a
doubly-linked list (see below) without the overhead of the extra
links.

Properties
----------

Declaration
  property IsSorted : boolean
Description
  READ ONLY. IsSorted is true if the list is currently sorted. A list
  is deemed sorted if you have provided a Compare routine to the list,
  ie, you have set the CompareData property.
  Note that keeping a linked list in sorted order through many Inserts
  and Deletes is very inefficient, because of the sequential nature of
  the list.

Interfaced Methods
------------------

Declaration
  constructor Create(DataOwner : boolean);
Description
  Creates the object by calling the ancestor's Create after setting a
  node size of 8.  If DataOwner is true, the new list will own its
  data objects.

Declaration
  constructor Clone(Source : TAbstractContainer;
                    DataOwner : boolean; NewCompare : TCompareFunc);
                                                            override;
Description
  Creates a copy of the Source list. If the original list was sorted
  then the cloned list is also sorted.

Declaration
  procedure Delete;
Description
  Unlinks the current data object but does not dispose of it. The
  internal cursor is moved to the next data object in the list, or to
  the AfterLast position if there are no more objects after it.  In
  DEBUG mode, an assertion error will occur if the cursor is at
  BeforeFirst or AfterLast.

Declaration
  procedure Empty; override;
Description
  Walks the list, calling Erase for every data object it finds.

Declaration
  procedure Erase;
Description
  Works like Delete, but also disposes the data object by calling
  DisposeData if the list owns its data objects.

Declaration
  function Examine : pointer;
Description
  Returns the data object the cursor is pointing to.  In DEBUG mode,
  an assertion error will occur if the cursor is at BeforeFirst or
  AfterLast.

Declaration
  function Iterate(Action : TIterator;
                   Backwards : boolean;
                   ExtraData : pointer) : pointer;
Description
  Walks the list from the start (if Backwards is False) or from the
  end (if Backwards is True) and calls Action for each data object
  found.  If Action returns False for a data object, then Iterate
  immediately returns with that data object; if Action always returns
  True then this method will return nil.  ExtraData is a pointer to
  any other data that you may want Action to use.

Declaration
  procedure InsertAfter(aData : pointer);
Description
  Inserts the data object aData after the cursor. If the list is
  currently sorted, calling this method forces it to an unsorted
  state. Use InsertSorted to maintain a sorted list. In DEBUG mode,
  an assertion error will occur if the cursor is at AfterLast.

Declaration
  procedure InsertBefore(aData : pointer);
Description
  Inserts the data object aData before the cursor. If the list is
  currently sorted, calling this method forces it to an unsorted
  state. Use InsertSorted to maintain a sorted list. In DEBUG mode,
  an assertion error will occur if the cursor is at BeforeFirst.

Declaration
  procedure InsertSorted(aData : pointer);
Description
  Inserts the data object aData in the correct place in the list's
  sequence. Only works if ALL data objects are so inserted; if the
  list is currently unsorted InsertBefore or InsertAfter is called
  instead.  Requires Compare to be overridden. *Not* efficient for
  long lists, you should use a skip list or binary search tree
  instead.

Declaration
  function IsAfterLast : boolean;
Description
  Returns true if the cursor is after all data objects in the list