ezdsl.doc

Delphi数据结构分析源码

  (beyond the end of the list).

Declaration
  function IsBeforeFirst : boolean;
Description
  Returns true if the cursor is before all data objects in the list.

Declaration
  procedure Join(List : TLinkList);
Description
  Adds all the data objects in List to the current list, placing them
  after the cursor. List is then destroyed. To add the data objects
  before all the current ones, call SetBeforeFirst first; to add them
  after all the current ones, call SetAfterLast and Prev first. Note
  that if the destination list is sorted, the nodes from List are
  added in sorted order. In DEBUG mode, an assertion error will occur
  if the cursor is at AfterLast.  Please note that both lists
  concerned must either be data owners or not.  You cannot Join a
  list that is a data owner to one that is not.

Declaration
  procedure Next;
Description
  Moves the cursor to the next data object in the list. In DEBUG
  mode, an assertion error will occur if the cursor is at AfterLast.

Declaration
  procedure Prev;
Description
  Moves the cursor to the previous data object in the list. In DEBUG
  mode, an assertion error will occur if the cursor is at
  BeforeFirst.

Declaration
  function Replace(aData : pointer) : pointer;
Description
  Replaces the data object at the cursor with aData and returns the
  replaced data object. Note that for sorted lists, the cursor might
  be moved. In DEBUG mode an assertion error will occur if the cursor
  is currently at BeforeFirst or AfterLast.

Declaration
  function Search(aData : pointer) : boolean;
Description
  Returns true if the data object aData is found in the list (Compare
  must return 0 between it and one of the data objects in the list),
  if not (and the list is sorted) it leaves the cursor just past
  where the data object could be inserted.

Declaration
  procedure SetAfterLast;
Description
  Moves the cursor after all the data objects in the list. Calling
  Prev from this position gives you the last object on the list.

Declaration
  procedure SetBeforeFirst;
Description
  Moves the cursor before all the data objects in the list. Calling
  Next from this position gives you the first object on the list.

Declaration
  function Split : TLinkList;
Description
  Splits the linked list into two at the cursor by creating a new
  list, and moving all the data objects from the cursor onwards to
  the new list. In DEBUG mode, an assertion error will occur if the
  cursor is at BeforeFirst or AfterLast (ie at least ONE data object
  must be moved; you cannot call Split for an empty list).

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

TDList
======

This is a linked list of data objects. Compared with TLinkList, this
implementation uses external 'cursors' which point to the various
data objects, you move these cursors along the list by means of the
list's methods. You can examine the data object that a cursor is
pointing to, or insert a new one before or after a given cursor, or
delete the data object at a cursor (unlink it). Again, there are two
special cursor positions: before the first data object (BeforeFirst)
and after the last data object (AfterLast). Even in an empty list
these are different.

The difference between this object and TList is in the use of
external cursors, and also in the internal implementation. This
object uses nodes with two links (hence 'doubly linked') rather than
one.

Notice that it is up to you to make sure that your external cursors
are valid. The following code is deemed a programming error:

  begin
    {...}
    with MyDList do
      begin
        Cursor := Next(SetBeforeFirst);
        NextCursor := Delete(Cursor);
        if (Next(Cursor) = NextCursor) then   {<=== CRASH}
          {...}

Here, the value of Cursor is undefined after the call to Delete. This
is much the same as using pointers: you may have several copies of a
pointer to a heap memory block, but as soon as you free that memory
block all those pointer variables are invalid.

As a convenience to the programmer, this implementation of a doubly
linked list allows the data objects to be maintained in a sorted
order, much as for TLinkList. Please see the discussion of sorted
lists above in that section.

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 12.  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 exact copy of the Source list. If the original list was
  sorted then the cloned list is also sorted.

Declaration
  function Delete(Cursor : TListCursor) : TListCursor;
Description
  Unlinks the passed cursor but does not dispose of its data object.
  The cursor of the next data object in the list is returned. Please
  note that the parameter Cursor is invalid after this routine is
  called. In DEBUG mode, an assertion error will occur if Cursor is
  at BeforeFirst or AfterLast.

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

Declaration
  function Erase(Cursor : TListCursor) : TListCursor;
Description
  Works like Delete, but also disposes the data object by calling
  DisposeData, providing the list owns its data objects.

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

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

Description
  procedure InsertAfter(Cursor : TListCursor; aData : pointer);
Description
  Inserts the data object aData after 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(Cursor : TListCursor; aData : pointer);
Description
  Inserts the data object aData after 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 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 the data object is inserted at the front
  of the list. Requires Compare to be overridden. *Not* efficient for
  long lists, you should use a skip list or binary search tree
  instead.

Declaration
  function IsAfterLast(Cursor : TListCursor) : boolean;
Description
  Returns true if Cursor is after all data objects in the list.

Declaration
  function IsBeforeFirst(Cursor : TListCursor) : boolean;
Description
  Returns true if Cursor is before all data objects in the list.

Declaration
  procedure Join(Cursor : TListCursor; List : TDList);
Description
  Adds all the data objects in List to the current list, placing them
  after Cursor. List is then destroyed. To add the data objects
  before all the current ones, use SetBeforeFirst as cursor; to add
  them after all the current ones, use SetAfterLast and Prev as
  cursor.  Note that if the destination list is sorted, the nodes
  from List are added in sorted order. In DEBUG mode, an assertion
  error will occur if the cursor is at AfterLast.  Please note that
  both lists concerned must either be data owners or not.  You cannot
  Join a list that is a data owner to one that is not.

Declaration
  function Next(Cursor : TListCursor) : TListCursor;
Description
  Given a Cursor into the list, returns a cursor to the next data
  object. In DEBUG mode, an assertion error will occur if Cursor is
  at AfterLast.

Declaration
  function Prev(Cursor : TListCursor) : TListCursor;
Description
  Given a Cursor into the list, returns a cursor to the previous data
  object. In DEBUG mode, an assertion error will occur if Cursor is
  at BeforeFirst.

Declaration
  function Replace(Cursor : TListCursor; aData : pointer) :  pointer;
Description
  Replaces the data object at Cursor with aData and returns the
  replaced data object. In DEBUG mode an assertion error will occur if
  the cursor is currently at BeforeFirst or AfterLast.

Declaration
  function Search(var Cursor : TListCursor;
                      aData  : pointer) : boolean;
Description
  Returns true if the data object aData is found in the list (Compare
  must return 0 between it and an object in the list), and returns
  the cursor. If the data object was not found in a sorted list,
  Search returns the cursor just past where the data object should be
  inserted.

Declaration
  function SetAfterLast : TListCursor;
Description
  Returns the cursor that is after all the data objects in the list.

Declaration
  function SetBeforeFirst : TListCursor;
Description
  Returns the cursor that is before all the data objects in the list.

Declaration
  function Split(Cursor : TListCursor) : TDList;
Description
  Splits the linked list into two at Cursor by creating a new list,
  and moving all the data objects from Cursor onwards to the new list.
  In DEBUG mode, an assertion error will occur if Cursor is at
  BeforeFirst or AfterLast (ie at least ONE data object must be moved;
  you cannot call Split for an empty list).

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

TSkipList
=========

A skip list is a special type of linked list of data objects. The
list is sorted and therefore requires the Compare method to be
overridden.  Compared with TList and TDList, this implementation uses
nodes of varying sizes. The nodes have between 1 and 16 (skMaxLevels)
of forward pointers, the higher ones skipping over nodes with less
forward pointers. This means much faster search times, but slightly
slower list update times (ie insert and delete). Can cope with
searching long lists without too much degradation. Compared with a
red-black binary search tree, this type of data structure will
consume more memory, will have equivalent insert times and delete
times, and will have comparable (amortised) search times.

Like TList and TDList, the skip list has two special positions:
before all the data objects and after all the data objects.

To grasp how it works, start with a classic doubly linked list where
each node has a pointer to the next and previous nodes. Now imagine
that about one in four of these nodes has a pointer to the node 4
nodes ahead as well. Furthermore suppose that about one in sixteen of
the nodes has a pointer to the node 16 nodes ahead. And so on. As you
can see, you can navigate through the list pretty quickly, jumping
over lesser nodes and 'homing in' o