
DIRECTORY
IO USING [STREAM],
Rope USING [ROPE];

BitTableLookup: CEDAR DEFINITIONS =
BEGIN
ROPE: TYPE = Rope.ROPE;
STREAM: TYPE = IO.STREAM;


Create: PROC [size: INT] RETURNS [table: Table];

NumberHashFunctions: PROC [] RETURNS [numberHashFunctions: INT];
Read: PROC [in: STREAM] RETURNS [table: Table];

Write: PROC [table: Table, out: STREAM];

Insert: PROC [table: Table, word: REF TEXT];


Lookup: PROC [table: Table, word: REF TEXT] RETURNS [member: BOOLEAN];
RowContents: TYPE = PACKED ARRAY [0..4096) OF BOOL;
RowPointer: TYPE = REF RowContents;
RowPrime: CARDINAL = 4093; -- Prime less than 4096.

Table: TYPE = REF TableContents;
TableContents: TYPE = MACHINE DEPENDENT RECORD[
bits: SEQUENCE rowSize: CARDINAL OF RowPointer];


FailureTypes: TYPE = {TooLarge, BadTable};

Failed: ERROR[ why: FailureTypes ];

END.

CHANGE LOG

Created by Nix on September 15, 1983 10:36 am

   ‚  
BitTableLookup.mesa - interface for space efficient set membership test, useful for implementing sleazy spelling checkers.
Copyright Ó 1987, 1992 by Xerox Corporation.  All rights reserved.
Beach, February 13, 1985 10:15:07 pm PST
Tim Diebert: January 26, 1987 4:48:19 pm PST
Kenneth A. Pier, March 7, 1990 6:02 pm PST
Creates a table with the given number of bits of capacity.   The number of bits should be a prime number that is approximately 20 times the number of words in the given table.
ERRORS: Raises Failed[TableTooLarge] if the table size is greater than 1,048,576 bits; tables of this size suffice to hold 50,000 items while maintaining a probability of ~0.001 that non-members will erroneously be called members.
Returns the number of hash functions used by the lookup/insertion procedure.

Reads in a Table from the given stream.  
ERRORS: Raises Failed[BadTable] if it detects that the stream does not contain a valid bit table.
Writes out a Table to the given stream.
Inserts the word into the given Table.
Looks up the word in the Table and returns TRUE iff it thinks that the word is in there.  If the word actually was in the Table, then this will always return TRUE.  However if the word actually was not in the table then it may erroneously return TRUE, although this won't happen very often.


The representation of the bit table.

Errors

There are currently two kinds of errors:
TooLarge: raised by Create when asked to create a bit table that is larger than implementation restrictions currently allow (currently raised at about 1,000,000 bits).
BadTable: raised by Read when it finds that the stream does not contain a valid table.
 Ê™  •NewlineDelimiter
–(cedarcode) style™ šœz™zIcodešœ
Ïeœ7™BJ™(K™,K™*—K˜ šÏk	˜	Kšžœžœžœ˜Kšœžœžœ˜—K˜ KšÏbœžœžœ˜#Kšž˜Kšžœžœžœ˜Kšžœžœžœžœ˜K˜ K˜ šÏnœžœžœžœ˜0Jšœ¯™¯Jšœæ™æ—K˜ š œžœžœžœ˜@JšœL™LJ™ —š œžœžœžœ˜/Jšœ)™)Jšœa™aK˜ —š œžœžœ˜(Jšœ'™'K˜ —š œžœžœžœ˜,Jšœ&™&—K˜ K˜ š œžœžœžœžœ
žœ˜FJšœ¢™¢J™ J™ —J™$J™ Kšœžœžœžœžœžœ˜3Kšœžœžœ˜#Kšœ
žœ	Ïc˜3K˜ Kšœžœžœ˜ š	œžœžœž	œžœ˜/Kšœžœ
žœžœ˜0—K˜ K˜ K˜ K˜ Jšœ™J™ Kšœžœ˜*K˜ šœžœ˜#šœ(™(Jšœ§™§JšœV™V——K˜ Kšžœ˜K˜ Kšžœž˜
K˜ K˜.— …—    z  •  