(*
Doubly-linked List Sequential Search Utilities - Implementation
Presented below are the implementation details of our sequential search
algorithms for the doubly-linked bounded list.
*)
IMPLEMENTATION MODULE ListDBMSearch;
(*==========================================================
Version : 1.00 18 May 1989 C. Lins
Compiler : TopSpeed Modula-2
Component: Tools - Structure Utility - Doubly-linked List Search
Revision History
v1.00 18 May 1989 C. Lins
Initial implementation.
(C) Copyright 1989 Charles A. Lins
==========================================================*)
FROM Relations IMPORT
(*--Type*) Relation;
FROM Items IMPORT
(*--Type*) Item, CompareProc;
FROM ListDBM IMPORT
(*--Type*) List, Pool, NullList,
(*--Proc*) GetNext, GetItem, IsEmpty, SetNext, SetItem,
GetPrev, SetPrev;
(*--------------------*)
(*
PrimarySearch
Our primary key search routine has been optimized using the LOOP construct
instead of a WHILE statement to avoid multiple calls to IsEmpty,
GetItem, and keysEqual at the end of the routine when determining
success or failure. (See reference [2]).
*)
PROCEDURE PrimarySearch ( theItem : Item (*-- in *);
theList : List (*-- in *);
thePool : Pool (*-- in *);
keysEqual : CompareProc (*-- in *);
found : SuccessProc (*-- in *);
notFound : FailureProc (*-- in *));
BEGIN
LOOP
IF IsEmpty(thePool, theList) THEN
notFound(theItem);
EXIT (*--loop*);
ELSIF (keysEqual(GetItem(thePool, theList), theItem) = equal) THEN
found(theItem);
EXIT (*--loop*);
END (*--if*);
theList := GetNext(thePool, theList);
END (*--loop*);
END PrimarySearch;
(*-------------------------*)
(*
SecondarySearch
Where the primary key search stops after the finding the first occurance
of theItem, the secondary key search continues to the end of the list
in order to find all occurances of theItem. Therefore, the complexity
is O(n).
*)
PROCEDURE SecondarySearch ( theItem : Item (*-- in *);
theList : List (*-- in *);
thePool : Pool (*-- in *);
keysEqual : CompareProc (*-- in *);
found : SuccessProc (*-- in *));
BEGIN
WHILE ~IsEmpty(thePool, theList) DO
IF keysEqual(GetItem(thePool, theList), theItem) = equal THEN
found(theItem);
END (*--if*);
theList := GetNext(thePool, theList);
END (*--while*);
END SecondarySearch;
(*-------------------------*)
(*
Self-organizing Sequential Search - MoveToFront
The algorithm first takes care of the special cases where the list is
empty or when the item is already at the front of the list. Then if it
is necessary to scan the list, the routine does so remembering the last
node examined in case theItem is found it can be easily moved to the
front without searching for the node's predecessor.
*)
PROCEDURE MoveToFront ( theItem : Item (*-- in *);
VAR theList : List (*-- inout *);
thePool : Pool (*-- in *);
keysEqual : CompareProc (*-- in *);
found : SuccessProc (*-- in *);
notFound : FailureProc (*-- in *));
VAR index : List; (*-- loop index over the nodes of the list *)
next : List; (*-- link to next node from the last node *)
succ : List; (*-- successor to indexes' successor *)
BEGIN
IF IsEmpty(thePool, theList) THEN
notFound(theItem);
ELSIF keysEqual(theItem, GetItem(thePool, theList)) = equal THEN
found(theItem);
ELSE
index := theList;
LOOP
next := GetNext(thePool, index);
IF IsEmpty(thePool, next) THEN
notFound(theItem);
EXIT (*--loop*);
ELSIF keysEqual(theItem, GetItem(thePool, next)) = equal THEN
(*-- unlink found node from the list *)
succ := GetNext(thePool, next);
SetNext(thePool, index, succ);
IF ~IsEmpty(thePool, succ) THEN
SetPrev(thePool, succ, index);
END (*--if*);
(*-- relink found node at front of the list *)
SetPrev(thePool, next, NullList);
SetNext(thePool, next, theList);
SetPrev(thePool, theList, next);
(*-- return found node as the new front *)
theList := next;
found(theItem);
EXIT (*--loop*);
END (*--if*);
index := next;
END (*--loop*);
END (*--if*);
END MoveToFront;
(*-------------------------*)
(*
Self-organizing Sequential Search - Transpose
The transpose hueristic is similar to the Move-To-Front method, above,
except when theItem is found it is moved only one position forward in
the list. Here, theItem is used as a temporary when moving the value
forward in the list. For a Pascal version of this algorithm using arrays
see Gonnet [2].
*)
PROCEDURE Transpose ( theItem : Item (*-- in *);
VAR theList : List (*-- inout *);
thePool : Pool (*-- in *);
keysEqual : CompareProc (*-- in *);
found : SuccessProc (*-- in *);
notFound : FailureProc (*-- in *));
VAR index : List; (*-- node being examined *)
prev : List; (*-- previous node *)
data : Item;
BEGIN
IF IsEmpty(thePool, theList) THEN
notFound(theItem);
ELSIF keysEqual(theItem, GetItem(thePool, theList)) = equal THEN
found(theItem);
ELSE
index := theList;
LOOP
index := GetNext(thePool, index);
IF IsEmpty(thePool, index) THEN
notFound(theItem);
EXIT (*--loop*);
ELSIF keysEqual(theItem, GetItem(thePool, index)) = equal THEN
data := GetItem(thePool, index);
prev := GetPrev(thePool, index);
SetItem(thePool, index, GetItem(thePool, prev));
SetItem(thePool, prev, data);
found(theItem);
EXIT (*--loop*);
END (*--if*);
END (*--loop*);
END (*--if*);
END Transpose;
(*-------------------------*)
END ListDBMSearch.
(*
References
[1] J.L. Bentley and C.C. McGeoch, Worst-Case Analyses of
Self-Organizing Sequential Search Heuristics,
Carnegie-Mellon University, 1983.
[2] G.H. Gonnet, Handbook of Algorithms and Data Structures,
Searching Algorithms, Addison-Wesley, London 1984,
pp. 23-30.
*)