DIRECTORY
Basics USING [bytesPerWord, CompareCard, Comparison, LongDiv, LongMult],
BcdDefs USING [VersionStamp],
FS USING [StreamOpen],
IO USING [Close, EndOfStream, GetChar, GetIndex, SetLength, STREAM, UnsafeGetBlock, UnsafePutBlock, PutRope],
Rope,
RopeFile USING [SubstrCreate],
VersionMap;

VersionMapImpl: CEDAR PROGRAM
IMPORTS Basics, FS, IO, Rope, RopeFile
EXPORTS VersionMap
SHARES VersionMap
= BEGIN OPEN VersionMap;

bytesPerWord: INT = Basics.bytesPerWord;
Comparison: TYPE = Basics.Comparison;
ROPE: TYPE = Rope.ROPE;
VersionStamp: TYPE = BcdDefs.VersionStamp;

NullStamp: MyStamp _ [0, 0, 0];
MyStampAsHex: TYPE = PACKED ARRAY [0..12) OF [0..16);

EntryIndex: TYPE = CARDINAL;
NullEntryIndex: EntryIndex = LAST[CARDINAL];

EntryRef: TYPE = REF EntryRep;
EntryRep: TYPE = RECORD [next: EntryRef, name: ROPE, version: MyStamp];


VersionToName: PUBLIC PROC
[list: MapList, stamp: VersionStamp] RETURNS [result: MapAndName] = {
result _ [NIL, NIL];
FOR each: MapList _ list, each.rest WHILE each # NIL DO
map: Map _ each.first;
nx: EntryIndex _ FindIndex[map, stamp];
IF nx # NullEntryIndex THEN {
result.name _ IndexToFullName[map, map[nx].index];
result.map _ map;
RETURN};
ENDLOOP;
};

VersionToAllNames: PUBLIC PROC
[list: MapList, stamp: VersionStamp] RETURNS [result: MapAndNameList] = {
tail: MapAndNameList _ NIL;
result _ NIL;
FOR each: MapList _ list, each.rest WHILE each # NIL DO
map: Map _ each.first;
lo,hi: EntryIndex;
[lo,hi] _ FindIndexRange[map, stamp];
FOR x: EntryIndex IN [lo..hi] DO
name: ROPE _  IndexToFullName[map, map[x].index];
new: MapAndNameList _ LIST[[map, name]];
IF tail = NIL THEN result _ new ELSE tail.rest _ new;
tail _ new;
ENDLOOP;
ENDLOOP;
};

ShortName: PUBLIC PROC [longName: ROPE] RETURNS [ROPE] = {
lim: INT _ Rope.Length[longName];
pos: INT _ lim;
WHILE pos > 0 DO
c: CHAR _ Rope.Fetch[longName, pos _ pos - 1];
SELECT c FROM
'! => lim _ pos;
'], '>, '/ => {pos _ pos + 1; EXIT};
ENDCASE;
ENDLOOP;
RETURN [Rope.Flatten[longName, pos, lim-pos]];
};

ShortNameToNames: PUBLIC PROC
[list: MapList, shortName: ROPE] RETURNS [MapAndNameList] = {
rangeList: RangeList _ ShortNameToRanges[list, shortName _ ShortName[shortName]];
head,tail: MapAndNameList _ NIL;
WHILE rangeList # NIL DO
range: Range _ rangeList.first;
map: Map _ range.map;
rangeList _ rangeList.rest;
FOR index: CARDINAL IN [range.first..range.first+range.len) DO
name: ROPE _ FetchName[map, map.shortNameSeq[index]];
new: MapAndNameList _ LIST[[map, name]];
IF tail = NIL THEN head _ new ELSE tail.rest _ new;
tail _ new;
ENDLOOP;
ENDLOOP;
RETURN [head];
};

ShortNameToRanges: PUBLIC PROC
[list: MapList, shortName: ROPE] RETURNS [RangeList] = {
head,tail: RangeList _ NIL;
shortName _ ShortName[shortName];
WHILE list # NIL DO
map: Map _ list.first;
shorts: ShortNameSeq _ map.shortNameSeq;
list _ list.rest;
IF map # NIL THEN {
found: BOOL;
index: CARDINAL;
range: Range _ [map: map, first: 0, len: 0];
new: RangeList;
[index, found] _ ShortNameFind[map, shortName];
IF found
THEN {
x,y: CARDINAL _ index;
WHILE x > 0 DO
IF ShortNameFindPred[shortName, shorts[x-1], map] # equal THEN EXIT;
x _ x - 1;
ENDLOOP;
WHILE y+1 < map.len DO
IF ShortNameFindPred[shortName, shorts[y+1], map] # equal THEN EXIT;
y _ y + 1;
ENDLOOP;
range.first _ x;
range.len _ y+1 - x;
}
ELSE {
range.first _ index;
WHILE range.first < map.len DO
SELECT ShortNameFindPred[shortName, shorts[range.first], map] FROM
less => EXIT;
equal => ERROR;  -- the shortNameSeq was not properly sorted!
greater => range.first _ range.first + 1;
ENDCASE;
ENDLOOP;
};
new _ LIST [range];
IF tail = NIL THEN head _ new ELSE tail.rest _ new;
tail _ new;
};
ENDLOOP;
RETURN [head];
};

GetPrefix: PUBLIC PROC [map: Map] RETURNS [ROPE] = {
RETURN [IndexToShortName[map, 0]];
};

StampToHex: PUBLIC PROC [stamp: BcdDefs.VersionStamp] RETURNS [ROPE] = {
RETURN [MyStampToHex[LOOPHOLE[stamp, MyStamp]]];
};

SaveMapToFile: PUBLIC PROC [map: Map, name: ROPE] = TRUSTED {
st: IO.STREAM _ FS.StreamOpen[name, $create];
names: ROPE _ map.names;
namesChars: INT _ names.Size[];
len: NAT _ map.len;
IO.UnsafePutBlock[st,
[LOOPHOLE[LONG[@len]], 0, SIZE[NAT]*bytesPerWord]];
IO.UnsafePutBlock[st,
[LOOPHOLE[@map.entries[0]], 0, len*(SIZE[MapEntry]*bytesPerWord)]];
IO.UnsafePutBlock[st,
[LOOPHOLE[@map.shortNameSeq[0]], 0, len*(SIZE[CARDINAL]*bytesPerWord)]];
IO.UnsafePutBlock[st,
[LOOPHOLE[LONG[@namesChars]], 0, (SIZE[INT]*bytesPerWord)]];
IO.PutRope[st, names];
IO.PutRope[st, "\000\000\000"];
IO.SetLength[st, IO.GetIndex[st]]; -- force goddamm truncation already!!!
IO.Close[st];
};

RestoreMapFromFile: PUBLIC PROC
[name: ROPE, assumeImmutable: BOOL _ TRUE] RETURNS [map: Map] = TRUSTED {
st: IO.STREAM _ FS.StreamOpen[name, $read];
namesChars: INT _ 0;
bytes: INT _ 0;
len: NAT _ 0;
pos: INT _ 0;
names: ROPE _ NIL;
eachChar: PROC RETURNS [c: CHAR] = TRUSTED {
c _ IO.GetChar[st]};
{ENABLE
IO.EndOfStream => {map _ NIL; GO TO noGot};
[] _ IO.UnsafeGetBlock[st, [LOOPHOLE[LONG[@len]], 0, SIZE[NAT]*bytesPerWord]];
map _ NEW[MapRep[len]];
map.shortNameSeq _ NEW[ShortNameSeqRep[len]];
[] _ IO.UnsafeGetBlock[st,
[LOOPHOLE[@map.entries[0]], 0, len*(SIZE[MapEntry]*bytesPerWord)]];
[] _ IO.UnsafeGetBlock[st,
[LOOPHOLE[@map.shortNameSeq[0]], 0, len*(SIZE[CARDINAL]*bytesPerWord)]];
[] _ IO.UnsafeGetBlock[st,
[LOOPHOLE[LONG[@namesChars]], 0, (SIZE[INT]*bytesPerWord)]];
pos _ IO.GetIndex[st];
IF assumeImmutable
THEN {
map.names _ RopeFile.SubstrCreate[name, pos, namesChars];
}
ELSE {
map.names _ names _ Rope.FromProc[namesChars, eachChar];
};
EXITS noGot => {};
};
IO.Close[st];
};

Length: PUBLIC PROC [map: Map] RETURNS [INT] = {
RETURN [IF map = NIL THEN 0 ELSE map.len];
};

Fetch: PUBLIC PROC
[map: Map, index: CARDINAL] RETURNS [stamp: VersionStamp, name: ROPE] = {
stamp _ LOOPHOLE[NullStamp];
name _ NIL;
IF map # NIL AND index IN [0..map.len) THEN {
entry: MapEntry _ map[index];
stamp _ LOOPHOLE[entry.stamp];
name _ IndexToFullName[map, entry.index]};
};

FetchStamp: PUBLIC PROC [map: Map, index: CARDINAL] RETURNS [stamp: VersionStamp] = {
stamp _ LOOPHOLE[NullStamp];
IF map # NIL AND index IN [0..map.len) THEN {
entry: MapEntry _ map[index];
stamp _ LOOPHOLE[entry.stamp]};
};

FetchName: PUBLIC PROC [map: Map, index: CARDINAL] RETURNS [name: ROPE] = {
name _ NIL;
IF map # NIL AND index IN [0..map.len) THEN {
entry: MapEntry _ map[index];
name _ IndexToFullName[map, entry.index]};
};

RangeToEntry: PUBLIC PROC
[range: Range] RETURNS [name: ROPE, stamp: VersionStamp, next: Range] = {
IF range.len = 0
THEN {name _ NIL; next _ [range.map, 0, 0]}
ELSE {
index: CARDINAL _ range.map.shortNameSeq[range.first];
next _ [range.map, range.first+1, range.len-1];
name _ FetchName[range.map, index];
stamp _ LOOPHOLE[range.map[index].stamp];
};
};


MyStampToHex: PROC [stamp: MyStamp] RETURNS [ROPE] = {
index: NAT _ 0;
each: PROC RETURNS [c: CHAR] = {
x: CARDINAL [0..15] _ hex[index];
IF x IN [0..9] THEN c _ 'a + hex[index];
index _ index + 1;
};
hex: MyStampAsHex _ LOOPHOLE[stamp];
RETURN [Rope.FromProc[12, each]];
};

IndexToShortName: PROC [map: Map, index: INT] RETURNS [ROPE] = {
names: ROPE _ map.names;
pos: INT _ names.SkipTo[index, "!\n"];
RETURN [names.Substr[index, pos-index]];
};

IndexToMidName: PROC [map: Map, index: INT] RETURNS [ROPE] = {
names: ROPE _ map.names;
pos: INT _ names.Index[index, "\n"];
RETURN [names.Substr[index, pos-index]];
};

IndexToFullName: PROC [map: Map, index: INT] RETURNS [ROPE] = {
names: ROPE _ map.names;
pos: INT _ names.Index[index, "\n"];
name: ROPE _ names.Substr[index, pos-index];
IF NOT Rope.Match["[*", name] THEN {
prepos: INT _ names.Index[0, "\n"];
prefix: ROPE _ names.Substr[0, prepos];
name _ prefix.Concat[name]};
RETURN [name];
};

FindIndex: PUBLIC PROC
[vmap: Map, t: BcdDefs.VersionStamp]
RETURNS [index: EntryIndex] = {
mt: MyStamp _ LOOPHOLE[t];
mn: CARDINAL _ mt.num;
i,k: CARDINAL _ 0;
j: CARDINAL _ vmap.len-1;
lo,mid: CARDINAL _ vmap[i].stamp.num;
hi: CARDINAL _ vmap[j].stamp.num;
probes: NAT _ 0;
DO
SELECT mn FROM
< lo, > hi => EXIT; -- can never find it!
= lo => k _ i; -- found it at the low point!
= hi => k _ j; -- found it at the high point!
ENDCASE =>
{-- use interpolation for speed!
dh: CARDINAL = hi-lo;
dt: CARDINAL = mn-lo;
TRUSTED
{k _ Basics.LongDiv[Basics.LongMult[j-i, dt], dh] + i};
mid _ vmap[k].stamp.num;
probes _ probes + 1;
SELECT mid FROM
< mn => {lo _ vmap[i _ k + 1].stamp.num; LOOP};
> mn => {hi _ vmap[j _ k - 1].stamp.num; LOOP};
ENDCASE};
{-- at this point, we are in a range of stamps that have equal mid-values; also, vmap[k].stamp.num = mt; a sequential search will do just fine
km: CARDINAL _ k;
m: MyStamp _ vmap[k].stamp;
IF m = mt THEN GO TO found;
WHILE km > i DO
km _ km-1;
m _ vmap[km].stamp;
IF m = mt THEN {k _ km; GO TO found};
IF m.num # mn THEN EXIT;
ENDLOOP;
WHILE k < j DO
k _ k+1;
m _ vmap[k].stamp;
IF m = mt THEN GO TO found;
IF m.num # mn THEN EXIT;
ENDLOOP;
EXIT; -- not found
EXITS
found =>  {
RETURN [k]}};
ENDLOOP;
RETURN [NullEntryIndex];
};

FindIndexRange: PUBLIC PROC
[vmap: Map, t: BcdDefs.VersionStamp]
RETURNS [lo,hi: EntryIndex] = {
stamp: MyStamp _ LOOPHOLE[t];
lim: EntryIndex _ vmap.len - 1;
hi _ 0;
lo _ FindIndex[vmap, t];
IF lo = NullEntryIndex THEN RETURN;
hi _ lo;
WHILE lo > 0 DO
IF vmap[lo-1].stamp # stamp THEN EXIT;
lo _ lo-1;
ENDLOOP;
WHILE hi < lim DO
IF vmap[hi+1].stamp # stamp THEN EXIT;
hi _ hi + 1;
ENDLOOP;
};

GetFirstShortNameIndex: PROC [map: Map, index: CARDINAL] RETURNS [INT] = {
len: CARDINAL = map.len;
names: ROPE = map.names;
pos: INT _ (IF index+1 >= len THEN Rope.Length[names] ELSE map[index+1].index)-1;
DO
c: CHAR = Rope.Fetch[names, pos _ pos - 1];
SELECT c FROM
'\n, '/, '>, '] => RETURN [pos+1];
ENDCASE;
ENDLOOP;
};
ShortNameFind: PROC
[map: Map, name: ROPE] RETURNS [index: CARDINAL, found: BOOL _ TRUE] = {
mapIndex: ShortNameSeq = map.shortNameSeq;
lo: CARDINAL _ 0;
hi: CARDINAL _ mapIndex.len-1;
name _ Rope.Flatten[name];  -- to speed comparisons
WHILE lo <= hi DO
index _ (lo+hi)/2;
SELECT ShortNameFindPred[name, mapIndex[index], map] FROM
less => {
IF lo = index THEN EXIT;
hi _ index - 1;
};
greater => {
IF hi = index THEN EXIT;
lo _ index + 1;
};
equal => RETURN;
ENDCASE => ERROR;
ENDLOOP;
found _ FALSE;
};

ShortNameFindPred: PROC
[name: ROPE, index: CARDINAL, map: Map] RETURNS [Comparison] = {
len: CARDINAL = map.len;
names: ROPE = map.names;
pos1: INT _ 0;
lim1: INT = Rope.Length[name];
pos2: INT _ GetFirstShortNameIndex[map, index];
DO
c1: CHAR _ IF pos1 = lim1 THEN '\n ELSE Rope.Fetch[name, pos1];
c2: CHAR _ Rope.Fetch[names, pos2];
IF LOOPHOLE[c1-'A, CARDINAL] <= ('Z-'A) THEN c1 _ c1 + ('a-'A);
SELECT TRUE FROM
c2 = '! => c2 _ '\n;
LOOPHOLE[c2-'A, CARDINAL] <= ('Z-'A) => c2 _ c2 + ('a-'A);
ENDCASE;
IF c1 # c2 THEN RETURN [
Basics.CompareCard[LOOPHOLE[c1, CARDINAL], LOOPHOLE[c2, CARDINAL]]];
IF c1 = '\n THEN RETURN [equal];
pos1 _ pos1 + 1;
pos2 _ pos2 + 1;
ENDLOOP;
};


GoodChars: TYPE = CHAR[40C..'z];
ArrayOfQueue: TYPE = ARRAY CHAR OF Cvt;

FillInShortNames: PUBLIC PROC [map: Map] = {
names: ROPE = map.names;
len: CARDINAL = map.len;
subLen: CARDINAL = len/32;
pqa: REF ArrayOfQueue _ NEW[ArrayOfQueue _ ALL[NIL]];
dstx: CARDINAL _ 0;
new: ShortNameSeq _ NEW[ShortNameSeqRep[len]];
map.shortNameSeq _ new;
FOR i: CARDINAL IN [0..len) DO
c: CHAR _ Rope.Fetch[names, GetFirstShortNameIndex[map, i]];
pq: Cvt _ NIL;
SELECT TRUE FROM
LOOPHOLE[c-'A, CARDINAL] <= ('Z-'A) => c _ c + ('a-'A);
c NOT IN GoodChars => c _ FIRST[GoodChars];
ENDCASE;
pq _ pqa[c];
IF pq = NIL THEN pqa[c] _ pq _ CreatePQ[map, subLen];
Insert[pq, i];
ENDLOOP;
FOR c: CHAR IN GoodChars DO
pq: Cvt = pqa[c];
IF pq # NIL THEN {
FOR i: CARDINAL IN [0..pq.size) DO
new[dstx] _ Remove[pq];
dstx _ dstx + 1;
ENDLOOP;
};
ENDLOOP;
pqa^ _ ALL[NIL];  -- I deserve a good citizenship award for this!
};

ShortNameSortPred: PROC [x1,x2: CARDINAL, map: Map] RETURNS [Comparison] = {
len: CARDINAL = map.len;
names: ROPE = map.names;
pos1: INT _ GetFirstShortNameIndex[map, x1];
pos2: INT _ GetFirstShortNameIndex[map, x2];
DO
c1: CHAR _ Rope.Fetch[names, pos1];
c2: CHAR _ Rope.Fetch[names, pos2];
IF LOOPHOLE[c1-'A, CARDINAL] <= ('Z-'A) THEN c1 _ c1 + ('a-'A);
IF LOOPHOLE[c2-'A, CARDINAL] <= ('Z-'A) THEN c2 _ c2 + ('a-'A);
IF c1 # c2 THEN RETURN [
Basics.CompareCard[LOOPHOLE[c1, CARDINAL], LOOPHOLE[c2, CARDINAL]]];
SELECT c1 FROM '!, '\n => RETURN [equal]; ENDCASE;
pos1 _ pos1 + 1;
pos2 _ pos2 + 1;
ENDLOOP;
};


PQempty: PUBLIC ERROR = CODE;
PQover: PUBLIC ERROR = CODE;

MaxSize: INT = LAST[CARDINAL];
Seq: TYPE = REF SeqRep;
SeqRep: TYPE = RECORD [elements: SEQUENCE space: CARDINAL OF CARDINAL];
Cvt: TYPE = REF Rep;
Rep: TYPE = RECORD [
map: Map,
size: CARDINAL,
seq: Seq];

CreatePQ: PROC [map: Map, size: INT _ 0] RETURNS [pq: Cvt] = {
IF size > MaxSize THEN ERROR PQover;
IF size <= 0 THEN size _ 4 ELSE size _ size + 1;
pq _ NEW[Rep _ [map, 0, NEW[SeqRep[size]]]];
};

Insert: PROC [pq: Cvt, item: CARDINAL] = {
size: CARDINAL _ pq.size;  -- figure out new size
a: Seq _ pq.seq;             -- grab the descriptor
space: CARDINAL _ IF a = NIL THEN 0 ELSE a.space;
maxCard: CARDINAL = MaxSize;  -- to aid the poor little compiler

IF size = MaxSize THEN RETURN WITH ERROR PQover;
size _ size + 1;

IF size >= space THEN {
seq: Seq _ NIL;
IF space = 0 THEN space _ 1;
SELECT space FROM
< 2048 => space _ space + space;
< maxCard-1024 => space _ space + 1024;
ENDCASE => space _ MaxSize; 
seq _ NEW[SeqRep[space]];
FOR i: CARDINAL IN [1..size) DO
seq[i] _ a[i];
ENDLOOP;
pq.seq _ a _ seq;
};

IF size = 1
THEN a[1] _ item
ELSE {
son: CARDINAL _ size;
dad: CARDINAL _ son/2;
map: Map = pq.map;
dadItem: CARDINAL;
WHILE dad > 0 AND ShortNameSortPred[item, dadItem _ a[dad], map] = less DO
a[son] _ dadItem;
son _ dad;
dad _ son/2;
ENDLOOP;
a[son] _ item;    -- finally insert the new item
};
pq.size _ size;  -- also update the size
};

Remove: PROC [pq: Cvt] RETURNS [CARDINAL] = {
size: CARDINAL _ pq.size;    -- current size of pq
a: Seq _ pq.seq;           -- desc to real stuff
best: CARDINAL;            -- holder for best item
item: CARDINAL;            -- holder for moving item
IF size = 0 THEN ERROR PQempty;

best _ a[1];           -- remember best item
item _ a[size];        -- get moving item
size _ size - 1;       -- new size of pq
pq.size _ size;        -- also update size in pq
IF size # 0 THEN {
dad: CARDINAL _ 1;             -- current index for moving item
maxdad: CARDINAL _ size / 2;   -- highest index for father item
map: Map = pq.map;
WHILE dad <= maxdad DO
son: CARDINAL _ dad + dad;
sonItem: CARDINAL _ a[son];
IF son < size THEN {
nson: CARDINAL _ son + 1;
nsonItem: CARDINAL _ a[nson];
IF ShortNameSortPred[nsonItem, sonItem, map] = less THEN {
son _ nson;
sonItem _ nsonItem;
};
};
IF ShortNameSortPred[item, sonItem, map] = less THEN EXIT;
a[dad] _ sonItem;
dad _ son;
ENDLOOP;
a[dad] _ item;
};

RETURN [best];
};


TestFindIndexFailed: ERROR = CODE;
SingleTestFindIndex: PROC [map: Map, i: NAT] RETURNS [index: INT] = {
lo,hi: EntryIndex;
entry: MapEntry _ map[i];
[lo,hi] _ FindIndexRange[map, LOOPHOLE[map[i].stamp]];
IF i NOT IN [lo..hi] THEN ERROR TestFindIndexFailed;
};

TestFindIndex: PROC [map: Map] RETURNS [allProbes: INT, len: NAT] = {
allProbes _ 0;
len _ map.len;
FOR i: NAT IN [0..len) DO
[] _ SingleTestFindIndex[map, i];
ENDLOOP;
};

END.


ώVersionMapImpl.mesa
Copyright c 1984 by Xerox Corporation.  All rights reserved.
Russ Atkinson, November 15, 1983 1:40 am
Paul Rovner, August 19, 1983 1:16 pm
**** BEGIN EXPORTED PROCEDURES **** --
... returns a full path name (FS format) for the given version stamp.  The list of maps is searched in order.  For convenience on a match, the containing map is also returned.  If the stamp is not found, [NIL, NIL] is returned.
... returns all of the full path names (FS format) for the given version stamp.  The list of maps is searched in order.  For convenience on a match, the containing map is also returned.  If the stamp is not found, [NIL, NIL] is returned.
... returns the short name for the given long name.  This simply involves stripping off the directory and version information.
... returns all of the full path names (FS format) for the given short name.  The list of maps is searched in order.  For convenience on a match, the containing map is also returned.  If the stamp is not found, [NIL, NIL] is returned.
... returns all of the ranges that correspond to the given short name (see the comments for Range).
Extend the range to encompass ALL of the matching short names.
Scan forward until we have gone beyond the short name.  This allows us to find long names using simple prefixes of short names.
returns the creating prefix for the map
useful little utility to turn a stamp into hex (Satterthwaite convention)
first, output the # of entries
next, the entries themselves
next, the shortNameSeq
next, the number of characters we are about to write (not counting the end marker)
then the names rope
marker at end to make Tioga happy
restores a map from a file written by SaveMapToFile
if assumeImmutable, then the named file is assumed to not change
(this avoids copying the file names from the save file) 
next, read the entries themselves
next, read the shortNameSeq
next, read the number of characters we are about to read
make a rope that reads from the IO
we assume that the file will not change
copy the chars from the file into storage
after all, the file could change!
returns the # of entries in the map 
returns the stamp and name at the given index
index must be in [0..Length[map])
returns the stamp at the given index
index must be in [0..Length[map])
returns the name at the given index
index must be in [0..Length[map])
... returns the name and stamp for the first entry in the range, also returning the next range.  If an empty range is given, the name returned will be NIL, and the range returned will be empty.

**** END EXPORTED PROCEDURES **** --
return the name without the prefix or version
return the name without the prefix
return the full path name
assert: 0 < dt < dh, i < j
try for the quick kill first (most likely)
otherwise, first search lower in the map
sigh, must search higher in the map
Scan backwards until a character before a short name is found.

... finds the given short name in the index, using the given predicate, which must be consistent with the predicate sued to build the index.
In this module we take advantage of the fact that all names of entries completely contain the short names of interest, and that all names of entries are bound by CRs ('\n).  The given name is already presumed to be short.
Scan through the two names comparing characters (case ignored).
Routines to fill in the shortNameSeq
In this module we take advantage of the fact that all names of entries completely contain the short names of interest, and that all names of entries are bound by CRs ('\n).
Scan through the two names comparing characters (case ignored).
Special clone of PriorityQueue intended for shuffling indexes.
create a priority queue object, initially empty
insert a new item into the queue
overflow check - unfortunately, we can't get more than LAST[CARDINAL] words!    
Must first check for room in array.  If there is not enough room, then allocate new storage, copy, and free the old storage.
Insert item by shuffling items down until invariant holds (assuming that a[son] will hold item).
item is better than a[dad], so shuffle a[dad] down
remove the "best" item in the queue
Remove top item from the array and prepare to move bottom item
Restore the invariant by moving the item down
(better items move up)
must find better of the two sons
Return the saved best item
Test routines
ΚE˜š
œ™Jšœ
Οm
œ1™<Jš
œ(™(Jš
œ$™$—J˜š
Οk	˜	Icodešœžœ<˜HKšœžœ˜Kšžœ
žœ˜Kšžœ
žœ4žœ+˜mKš
œ˜Kšœ	žœ˜š
œ˜J˜——šœžœ
ž˜Jšžœ	žœžœ˜&Jšžœ˜Jšžœ˜Jšœžœ
žœ˜J˜Jšœžœ˜(Jšœžœ˜%Jšžœžœžœ
˜Jšœžœ˜*J˜Jš
œ˜Jš	œžœžœ
žœ	žœ	˜5J˜Jšœžœžœ
˜Jšœžœ
žœ˜,J˜Jšœ
žœžœ
˜Jšœ
žœžœžœ˜GJ˜Jš
œ&™&J˜šΟn
œžœ
ž˜Jšœ$žœ˜EJšœžœ­
žœžœ™γ
Jšœ
žœžœ˜šžœ!žœžœ
ž˜7J˜J˜'šžœžœ˜Jš
œ2˜2J˜Jšžœ˜—Jšžœ
˜—J˜J˜—šŸœžœ
ž˜Jšœ$žœ˜IJšœ(žœ­
žœžœ™ν
Jšœžœ
˜Jšœ	žœ
˜
šžœ!žœžœ
ž˜7J˜J˜J˜%šžœžœ
ž˜ Jšœžœ'˜1Jšœžœ˜(Jšžœžœ
žœžœ˜5J˜Jšžœ
˜—Jšžœ
˜—J˜J˜—šŸ	œžœ
žœžœžœžœ˜:Jš
œ~™~Jšœžœ˜!Jšœžœ˜šžœ	ž˜Jšœžœ'˜.šžœž˜
J˜Jšœžœ˜$Jšžœ
˜—Jšžœ
˜—Jšžœ(˜.J˜J˜—šŸœžœ
ž˜Jšœžœžœ˜=Jšœ(žœͺ
žœžœ™κ
Jš
œQ˜QJšœžœ
˜ šžœ
žœ
ž˜Jš
œ˜J˜Jš
œ˜šžœžœ
žœ&ž˜>Jšœžœ+˜5Jšœžœ˜(Jšžœžœ
žœžœ˜3J˜Jšžœ
˜—Jšžœ
˜—Jšžœ˜Jš
œ˜J˜—šŸœžœ
ž˜Jšœžœžœ˜8Jš
œc™cJšœžœ
˜Jš
œ!˜!šžœžœ
ž˜Jš
œ˜Jš
œ(˜(Jš
œ˜šžœžœ
žœ˜Jšœžœ
˜Jšœžœ
˜J˜,J˜Jš
œ/˜/šžœ˜šžœ˜Jšœžœ™>Jšœžœ	˜šžœž˜Jšžœ8žœ
žœ
˜DJ˜
Jšžœ
˜—šžœž˜Jšžœ8žœ
žœ
˜DJ˜
Jšžœ
˜—J˜J˜J˜
—šžœ˜Jš
œ™J˜šžœž˜šžœ8ž˜BJšœžœ
˜
Jšœ	žœΟc,˜=Jš
œ)˜)Jšžœ
˜—Jšžœ
˜—J˜——Jšœžœ	˜Jšžœžœ
žœžœ˜3J˜J˜—Jšžœ
˜—Jšžœ˜J˜J˜—š
Ÿ	œžœ
žœžœžœ˜4Jš
œ'™'Jšžœ˜"J˜J˜—š
Ÿ
œžœ
žœžœžœ˜HJš
œI™IJšžœžœ˜0Jš
œ˜J˜—š
Ÿ
œžœ
žœžœžœ˜=Jšœžœ
žœžœ˜-Jšœžœ
˜Jšœžœ˜Jšœžœ˜šžœ˜Jš	œ
žœ
žœžœ
žœ˜3Jš
œ™—šžœ˜Jšœ
žœžœ˜CJš
œ™—šžœ˜Jšœ
žœ žœ
žœ˜HJš
œ™—šžœ˜Jš	œ
žœ
žœžœ
žœ˜<Jš
œR™R—šžœ˜Jš
œ™—šžœ˜Jš
œ!™!—Jšžœžœ &˜IJšžœ˜
J˜J˜—šŸœžœ
ž˜Jšœžœžœžœžœžœ˜IJš
œ3™3Jš
œ@™@Jš
œ8™8Jšœžœ
žœžœ˜+Jšœžœ˜Jšœžœ˜Jšœžœ˜
Jšœžœ˜
Jšœžœžœ
˜š	œ
žœ
žœžœžœ˜,Jšœžœ˜—šœ
ž˜Jšžœžœžœ
žœ˜+Jšœžœžœ
žœžœ
žœ˜NJšœžœ˜Jšœžœ˜-šœžœ˜Jšœ
žœžœ˜CJš
œ!™!—šœžœ˜Jšœ
žœ žœ
žœ˜HJš
œ™—šœžœ˜Jš	œ
žœ
žœžœ
žœ˜<Jš
œ8™8—Jšœžœ˜šžœ˜šžœ˜Jš
œ"™"Jš
œ'™'Jš
œ9˜9J˜
—šžœ˜Jš
œ)™)Jš
œ!™!J˜8Jš
œ˜——Jšžœ
˜J˜—Jšžœ˜
J˜J˜—š
Ÿœžœ
žœžœžœ˜0Jš
œ$™$Jš
žœžœžœ
žœžœ
˜*J˜J˜—šŸœžœ
ž˜Jšœžœžœžœ˜IJš
œ-™-Jš
œ!™!Jšœžœ˜Jšœžœ
˜š
žœžœ
žœžœžœ˜-Jš
œ˜Jšœžœ˜J˜*—J˜J˜—š
Ÿ
œžœ
žœžœžœ˜UJš
œ$™$Jš
œ!™!Jšœžœ˜š
žœžœ
žœžœžœ˜-Jš
œ˜Jšœžœ˜—J˜J˜—šŸ	œžœ
žœžœžœžœ˜KJš
œ#™#Jš
œ!™!Jšœžœ
˜š
žœžœ
žœžœžœ˜-Jš
œ˜J˜*—J˜J˜—šŸœžœ
ž˜Jšœžœžœ'˜IJš
œΑ
™Α
šžœ˜Jšžœ	žœ˜+šžœ˜Jšœžœ'˜6J˜/Jš
œ#˜#Jšœžœ˜)J˜——Jš
œ˜J™J˜—Jš
œ$™$J˜šŸœžœžœžœ˜6Jšœžœ˜šœžœ
žœžœ˜ Jšœžœ˜!Jšžœžœžœ˜(J˜J˜—Jšœžœ˜$Jšžœ˜!J˜J˜—š
Ÿœžœžœžœžœ˜@Jš
œ-™-Jšœžœ
˜Jšœžœ˜&Jšžœ"˜(J˜J˜—š
Ÿœžœžœžœžœ˜>Jš
œ"™"Jšœžœ
˜Jšœžœ˜$Jšžœ"˜(J˜J˜—š
Ÿœžœžœžœžœ˜?Jš
œ™Jšœžœ
˜Jšœžœ˜$Jšœžœ"˜,šžœ
žœžœ˜$Jšœžœ˜#Jšœžœ˜'J˜—Jšžœ˜J˜J˜—šŸ	œžœ
ž˜J˜$Jšžœ˜Jšœžœ˜Jšœžœ
˜Jšœžœ˜Jšœžœ˜Jšœžœ˜%Jšœžœ˜!Jšœžœ˜š
ž˜šžœž˜Jšœžœ ˜)Jšœ ˜,Jšœ ˜-šžœ˜
šœ
 ˜ Jšœžœ	˜Jšœžœ	˜Jš
œ™š
ž˜J˜7—J˜J˜šžœž˜Jšœ)žœ˜/šœ)žœ˜/Jšžœ˜	—————šœ
 
˜Ž
Jšœžœ˜J˜Jš
œ*™*Jšžœžœ
žœ
žœ˜Jš
œ(™(šžœž˜J˜
J˜Jšžœžœ
žœ
žœ˜%Jšžœžœ
žœ
˜Jšžœ
˜—Jš
œ#™#šžœž˜J˜J˜Jšžœžœ
žœ
žœ˜Jšžœžœ
žœ
˜Jšžœ
˜—Jšžœ ˜—š
ž˜˜Jšžœ˜
——Jšžœ
˜—Jšžœ˜J˜J˜—šŸœžœ
ž˜J˜$Jšžœ˜Jšœžœ˜J˜J˜J˜Jšžœžœ
žœ
˜#J˜šžœž˜Jšžœžœ
žœ
˜&J˜
Jšžœ
˜—šžœ
ž˜Jšžœžœ
žœ
˜&J˜Jšžœ
˜—J˜J˜—š
Ÿœžœžœžœžœ˜JJšœžœ˜Jšœžœ
˜Jš	œžœžœžœžœ˜Qš
ž˜Jš
œ>™>Jšœžœ$˜+šžœž˜
Jšœžœ	˜"Jšžœ
˜—Jšžœ
˜—J˜J™—šŸ
œž˜Jšœžœ
žœ	žœ	žœžœ˜HJš
œŒ
™Œ
Jš
œ*˜*Jšœžœ˜Jšœžœ˜Jšœ ˜3šžœ
ž˜Jš
œ˜šžœ/ž˜9š
œ	˜	Jšžœžœ
žœ
˜Jš
œ˜J˜—˜Jšžœžœ
žœ
˜Jš
œ˜J˜—Jšœ	žœ
˜Jšžœžœ
˜—Jšžœ
˜—Jšœžœ
˜J˜J˜—šŸœž˜Jšœžœ	žœžœ˜@J™έ
Jšœžœ˜Jšœžœ
˜Jšœžœ˜Jšœžœ˜Jšœžœ&˜/š
ž˜Jš
œ?™?Jš	œžœžœ
žœžœ˜?Jšœžœ˜#Jšžœ
žœžœ
žœ˜?šžœ
žœ
ž˜J˜Jšžœžœ"˜:Jšžœ
˜—šžœ	žœ
žœ˜Jš	œžœžœžœžœ˜D—Jšžœ
žœ
žœ	˜ Jš
œ˜Jš
œ˜Jšžœ
˜—J˜J˜——š
œ$™$J˜Jšœžœžœ
˜ Jš	œžœžœ
žœ
žœ˜'J˜šŸœžœ
žœ˜,Jšœžœ
˜Jšœžœ˜Jšœžœ
˜Jš	œžœžœžœ
žœ˜5Jšœžœ˜Jšœžœ˜.Jš
œ˜šžœžœ
žœ
ž˜Jšœžœ5˜<Jšœ
žœ
˜šžœ
žœ
ž˜Jšžœžœ ˜7Jšœžœ
žœžœ˜+Jšžœ
˜—Jš
œ˜Jšžœžœ
žœ%˜5Jš
œ˜Jšžœ
˜—šžœžœ
žœž˜J˜šžœžœ
žœ˜šžœžœ
žœž˜"Jš
œ˜Jš
œ˜Jšžœ
˜—J˜—Jšžœ
˜—Jšœžœ
žœ /˜AJ˜J˜—šŸœžœ	žœžœ˜LJ™¬
Jšœžœ˜Jšœžœ
˜Jšœžœ#˜,Jšœžœ#˜,š
ž˜Jš
œ?™?Jšœžœ˜#Jšœžœ˜#Jšžœ
žœžœ
žœ˜?Jšžœ
žœžœ
žœ˜?šžœ	žœ
žœ˜Jš	œžœžœžœžœ˜D—Jšžœžœžœ
žœ
˜2Jš
œ˜Jš
œ˜Jšžœ
˜—J˜——J˜š
œ>™>J˜Jšœ	žœ
žœžœ
˜Jšœžœ
žœžœ
˜J˜Jšœ	žœžœ
žœ˜Jšœžœžœ˜Jš
œžœžœžœžœ
žœ
žœ˜GJšœžœžœ˜šœžœžœ˜Jš
œ	˜	Jšœžœ
˜J˜
—J˜šŸœžœžœžœ˜>Jš
œ/™/Jšžœžœ
žœ˜$Jšžœžœ
žœ˜0Jšœžœžœ˜,J˜J˜—šŸœžœžœ˜*Jš
œ ™ Jšœžœ
 ˜1Jšœ ˜3Jšœžœžœžœ
žœžœ	˜1Jšœ	žœ
 "˜@J˜Jš
œP™PJš
žœžœ
žœ
žœ
žœ˜0J˜J˜Jš
œ|™|šžœžœ˜Jšœžœ
˜Jšžœžœ˜šžœž˜J˜ J˜'Jšžœ˜—Jšœžœ˜šžœžœ
žœž˜J˜Jšžœ
˜—J˜J˜J˜—šžœ	˜Jšžœ˜šžœ˜Jš
œ`™`Jšœžœ˜Jšœžœ	˜J˜Jšœ	žœ
˜šžœ	žœ7ž˜JJš
œ2™2Jš
œ˜J˜
J˜Jšžœ
˜—Jšœ ˜0J˜——Jšœ ˜(J˜J˜—šŸœžœžœžœ˜-Jš
œ#™#Jšœžœ ˜2Jšœ ˜0Jšœžœ
 ˜2Jšœžœ
 ˜4Jšžœ
žœ
žœ	˜J˜Jš
œ>™>Jšœ ˜,Jšœ ˜)Jšœ ˜(Jšœ ˜0šžœ
žœ˜Jš
œ-™-Jš
œ™Jšœžœ  ˜?Jšœžœ  ˜?J˜šžœž˜Jšœžœ
˜Jšœ	žœ
˜šžœžœ˜Jš
œ ™ Jšœžœ˜Jšœ
žœ˜šžœ2žœ˜:J˜J˜J˜—J˜—Jšžœ.žœ
žœ
˜:J˜J˜
Jšžœ
˜—J˜J˜J˜—Jš
œ™Jšžœ˜˜J˜———š
œ
™
J˜Jšœžœžœ
˜"š
Ÿœžœžœžœ	žœ˜EJ˜J˜Jšœžœ˜6Jš
žœžœ
žœ
žœ
žœ˜4J˜J˜—š
Ÿ
œžœžœ
žœžœ˜EJ˜J˜šžœžœ
žœ
ž˜J˜!Jšžœ
˜—J˜J˜——šžœ
˜J˜J˜——…—;’eε