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; RowPrime: CARDINAL = 4093; -- Prime less than 4096. TableContents: TYPE = RECORD[ bits: SEQUENCE rowSize: CARDINAL OF REF RowContents ]; Table: TYPE = REF TableContents; FailureTypes: TYPE = {TooLarge, BadTable}; Failed: ERROR[ why: FailureTypes ]; END. CHANGE LOG Created by Nix on September 15, 1983 10:36 am xBitTableLookup.mesa - interface for space efficient set membership test, useful for implementing sleazy spelling checkers. -- Last Edited by -- Nix on October 27, 1983 1:15 pm 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. A vector of bits, so declared because there is a restriction on the maximum number of bits in a straightforward packed array of bool. 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. ÊS˜Jšœ¯™¯J˜šÏk ˜ Jšœœœ˜Jšœœœ˜—J˜JšÏbœœ œ˜#Jš˜Jšœœœ˜Jšœœœœ˜J˜J˜šÏnœœœœ˜0Jšœ¯™¯Jšœæ™æ—J˜šŸœœœœ˜@JšœL™LJ™—šŸœœœœ˜/Jšœ)™)Jšœa™aJ˜—šŸœœœ˜(Jšœ'™'J˜—šŸœœœœ˜,Jšœ&™&—J˜J˜š Ÿœœœœœ œ˜FJšœ¢™¢J™J™—J™$J™Jš œ œœœ œœ˜3Jšœ œ Ïc˜3šœœœ˜š œœ œœœ ˜3Jšœ…™…—J˜—Jšœœœ˜ J˜J˜J˜J˜Jšœ™J™Jšœœ˜*J˜šœœ˜#šœ(™(Jšœ§™§JšœV™V——J˜Jšœ˜J˜Jšœ˜ J˜Jšœ.˜.—…—J