Class TSkipList (unit EZDSLSkp)

Inherits from

TAbstractContainer

---Place any compiler options you require here----------------------} {--------------------------------------------------------------------} {$I EZDSLOPT.INC

Constructors


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.


Functions

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;

--------

Properties

Events

Variables

skAL : PNode;


skBF : PNode;


skCurLevels : integer;


skNewNodeLevel : integer;


skRandGen : TEZRandomGenerator;



Constructors


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) =====================================================================


Functions


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;

--------


Properties


Events


Variables


skAL : PNode;


skBF : PNode;


skCurLevels : integer;


skNewNodeLevel : integer;


skRandGen : TEZRandomGenerator;