Class TSkipList (unit EZDSLSkp) |
Inherits from
TAbstractContainer
---Place any compiler options you require here----------------------} {--------------------------------------------------------------------} {$I EZDSLOPT.INC
constructor Clone(Source : TAbstractContainer;
DataOwner : boolean; NewCompare : TCompareFunc);
- --------
constructor Create(DataOwner : boolean);
- =TSkipList===========================================================
A skip linked list
This is a special type of linked list of data objects.
function Delete(Cursor : TListCursor) : TListCursor;
--------
destructor Destroy;
--------
procedure Empty;
--------
function Erase(Cursor : TListCursor) : TListCursor;
--------
function Examine(Cursor : TListCursor) : pointer;
--------
procedure Insert(var Cursor : TListCursor; aData : pointer);
--------
function IsAfterLast(Cursor : TListCursor) : boolean;
--------
function IsBeforeFirst(Cursor : TListCursor) : boolean;
--------
function Iterate(Action : TIterator; Backwards : boolean;
ExtraData : pointer) : pointer;
--------
procedure Join(List : TSkipList);
--------
function Next(Cursor : TListCursor) : TListCursor;
--------
function Prev(Cursor : TListCursor) : TListCursor;
--------
function Replace(Cursor : TListCursor; aData : pointer) : pointer;
--------
function Search(var Cursor : TListCursor; aData : pointer) : boolean;
--------
function SetAfterLast : TListCursor;
--------
function SetBeforeFirst : TListCursor;
--------
function Split(Cursor : TListCursor) : TSkipList;
--------
procedure acDisposeNode(aNode : PNode);
--------
function acNewNode(aData : pointer) : PNode;
--------
procedure acSort;
--------
function skCloneItem(SL : TAbstractContainer;
aData : pointer;
NSL : pointer) : boolean;
--------
function skMergeLists(aBeforeNode1 : PNode; aCount1 : longint;
aBeforeNode2 : PNode; aCount2 : longint) : PNode;
--------
function skMergeSort(aBeforeNode : PNode; aCount : longint) : PNode;
--------
skAL : PNode;
skBF : PNode;
skCurLevels : integer;
skNewNodeLevel : integer;
skRandGen : TEZRandomGenerator;
constructor Clone(Source : TAbstractContainer;
DataOwner : boolean; NewCompare : TCompareFunc);
--------
constructor Create(DataOwner : boolean);
=TSkipList===========================================================
A skip linked list
This is a special type of linked list of data objects. 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 faster
insert times, slower (?) delete times, and will have comparable
(amortised) search times.
Reference
Scheiner: Skip Lists (DDJ January 1994)
=====================================================================
function Delete(Cursor : TListCursor) : TListCursor;
--------
destructor Destroy;
--------
procedure Empty;
--------
function Erase(Cursor : TListCursor) : TListCursor;
--------
function Examine(Cursor : TListCursor) : pointer;
--------
procedure Insert(var Cursor : TListCursor; aData : pointer);
--------
function IsAfterLast(Cursor : TListCursor) : boolean;
--------
function IsBeforeFirst(Cursor : TListCursor) : boolean;
--------
function Iterate(Action : TIterator; Backwards : boolean;
ExtraData : pointer) : pointer;
--------
procedure Join(List : TSkipList);
--------
function Next(Cursor : TListCursor) : TListCursor;
--------
function Prev(Cursor : TListCursor) : TListCursor;
--------
function Replace(Cursor : TListCursor; aData : pointer) : pointer;
--------
function Search(var Cursor : TListCursor; aData : pointer) : boolean;
--------
function SetAfterLast : TListCursor;
--------
function SetBeforeFirst : TListCursor;
--------
function Split(Cursor : TListCursor) : TSkipList;
--------
procedure acDisposeNode(aNode : PNode);
--------
function acNewNode(aData : pointer) : PNode;
--------
procedure acSort;
--------
function skCloneItem(SL : TAbstractContainer;
aData : pointer;
NSL : pointer) : boolean;
--------
function skMergeLists(aBeforeNode1 : PNode; aCount1 : longint;
aBeforeNode2 : PNode; aCount2 : longint) : PNode;
--------
function skMergeSort(aBeforeNode : PNode; aCount : longint) : PNode;
--------
skAL : PNode;
skBF : PNode;
skCurLevels : integer;
skNewNodeLevel : integer;
skRandGen : TEZRandomGenerator;