(*
8.1 Sequential Search Utilities - Interface
In this section are provided several utility routines implementing
search algorithms on singly-linked unbounded lists.
The reader should find it trivial to generate equivalent modules
for the other list structures.
*)
DEFINITION MODULE ListSUMSearch;
(*==========================================================
Version : 1.00 18 May 1989 C. Lins
Compiler : TopSpeed Modula-2 Compiler
Component: Tools - Structure Utility - Single List Search
Revision History
v1.00 18 May 1989 C. Lins
Initial implementation.
(C) Copyright 1989 Charles A. Lins
=============================================================*)
FROM Items IMPORT
(*--Type*) Item, CompareProc;
FROM ListSUM IMPORT
(*--Type*) List;
(*--------------------*)
TYPE SuccessProc = PROCEDURE (Item);
TYPE FailureProc = PROCEDURE (Item);
(*--------------------*)
(*
8.1.1 PrimarySearch
Searches theList for the first occurance of theItem with the required
key. This is called the primary key search. It is assumed that the
item comparison routine knows how to extract the key from the items
if necessary. If the search succeeds then the found procedure parameter
is invoked, otherwise the notfound routine is called. The list is
assumed to be unordered.
*)
PROCEDURE PrimarySearch ( theItem : Item (*-- in *);
theList : List (*-- in *);
keysEqual : CompareProc (*-- in *);
found : SuccessProc (*-- in *);
notFound : FailureProc (*-- in *));
(*
8.1.2 SecondarySearch
Searches theList for every occurance of theItem with the required
key. This is called the secondary key search. It is assumed that the
item comparison routine knows how to extract the key from the items
if necessary. Each time the search succeeds the found procedure parameter
is invoked. The list is assumed to be unordered.
*)
PROCEDURE SecondarySearch ( theItem : Item (*-- in *);
theList : List (*-- in *);
keysEqual : CompareProc (*-- in *);
found : SuccessProc (*-- in *));
(*
8.1.3 Self-organizing Sequential Search - MoveToFront
This routine is essentially the primary key search modified to apply
a heuristic for improving the list ordering. When a key is found,
theItem is moved to the front of the list. The idea is that the
access distribution of items in the list is unequal, and therefore,
the most frequently accessed items should be closer to the front.
For a sophisticated analysis comparing self-organizing heuristics
see reference [1].
*)
PROCEDURE MoveToFront ( theItem : Item (*-- in *);
VAR theList : List (*-- inout *);
keysEqual : CompareProc (*-- in *);
found : SuccessProc (*-- in *);
notFound : FailureProc (*-- in *));
(*
8.1.4 Self-organizing Sequential Search - Transpose
Instead of moving the found item to the front of the list, the Transpose
heuristic moves the item one position closer to the front by swapping
positions with its predecessor.
*)
PROCEDURE Transpose ( theItem : Item (*-- in *);
VAR theList : List (*-- inout *);
keysEqual : CompareProc (*-- in *);
found : SuccessProc (*-- in *);
notFound : FailureProc (*-- in *));
END ListSUMSearch.
(*
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.
*)