## hashtable.pkg
#
# Typeagnostic hashtables.
#
# See also:
#
# src/lib/src/int-hashtable.pkg# src/lib/src/unt-hashtable.pkg# src/lib/src/quickstring-hashtable.pkg# src/lib/src/typelocked-hashtable-g.pkg# src/lib/src/typelocked-double-keyed-hashtable-g.pkg# Compiled by:
# src/lib/std/standard.lib### "The sciences do not try to explain, they hardly
### even try to interpret, they mainly make models.
###
### By a model is meant a mathematical construct which,
### with the addition of certain verbal interpretations,
### describes observed phenomena.
###
### The justification of such a mathematical construct
### is solely and precisely that it is expected to work."
###
### -- Johnny von Neuman
stipulate
package hr = hashtable_representation; # hashtable_representation is from src/lib/src/hashtable-rep.pkg package rwv = rw_vector; # rw_vector is from src/lib/std/src/rw-vector.pkgherein
package hashtable
: (weak) Hashtable # Hashtable is from src/lib/src/hashtable.api {
Hashtable (X, Y)
=
HASHTABLE
{
hash_g: X -> Unt,
eq_pred: (X, X) -> Bool,
#
not_found_exception: Exception,
#
table: Ref( hr::Table( X, Y ) ),
n_items: Ref( Int )
};
fun index (i, size)
=
unt::to_int_x (unt::bitwise_and (i, unt::from_int size - 0u1));
# Find smallest power of 2 (>= 32) that is >= n
#
fun round_up n
=
f 32
where
fun f i
=
if (i >= n) i;
else f (i * 2); fi;
end;
# Create a new table; the
# int is a size hint and the
# exception is to be raised by find.
#
fun make_hashtable (hash, eq) { size_hint, not_found_exception }
=
HASHTABLE {
hash_g => hash,
eq_pred => eq,
not_found_exception,
table => REF (hr::allot size_hint),
n_items => REF 0
};
# Remove all elements from the table
#
fun clear (HASHTABLE { table, n_items, ... } )
=
{ hr::clear *table;
n_items := 0;
};
# Insert an item. If the key already has an item associated with it,
# then the old item is discarded.
#
fun set (my_table as HASHTABLE { hash_g, eq_pred, table, n_items, ... } ) (key, item)
=
{ vector = *table;
size = rwv::length vector;
hash = hash_g key;
index = index (hash, size);
fun get hr::NIL
=>
{ rwv::set (vector, index, hr::BUCKET (hash, key, item, rwv::get (vector, index)));
n_items := *n_items + 1;
hr::grow_table_if_needed (table, *n_items);
hr::NIL;
};
get (hr::BUCKET (h, k, v, r))
=>
if (hash == h and eq_pred (key, k))
#
hr::BUCKET (hash, key, item, r);
else
case (get r)
#
hr::NIL => hr::NIL;
rest => hr::BUCKET (h, k, v, rest);
esac;
fi;
end;
case (get (rwv::get (vector, index)))
#
hr::NIL => ();
b => rwv::set (vector, index, b);
esac;
};
# Return TRUE iff the key is in the domain of the table:
#
fun contains_key (HASHTABLE { hash_g, eq_pred, table, ... } ) key
=
get (rwv::get (vector, index))
where
vector = *table;
hash = hash_g key;
index = index (hash, rwv::length vector);
fun get (hr::BUCKET (h, k, v, r))
=>
(hash == h and eq_pred (key, k)) or
get r;
get hr::NIL
=>
FALSE;
end;
end;
# Find an item; if it is missing raise the table's not-found exception.
#
fun look_up (HASHTABLE { hash_g, eq_pred, table, not_found_exception, ... } ) key
=
get (rwv::get (vector, index))
where
vector = *table;
size = rwv::length vector;
hash = hash_g key;
index = index (hash, size);
fun get (hr::BUCKET (h, k, v, r))
=>
if (hash == h and eq_pred (key, k)) v;
else get r;
fi;
get hr::NIL
=>
raise exception not_found_exception;
end;
end;
# Find an item; if it is missing return NULL.
#
fun find (HASHTABLE { hash_g, eq_pred, table, ... } ) key
=
get (rwv::get (vector, index))
where
vector = *table;
size = rwv::length vector;
hash = hash_g key;
index = index (hash, size);
fun get (hr::BUCKET (h, k, v, r))
=>
if (hash == h and eq_pred (key, k)) THE v;
else get r;
fi;
#
get hr::NIL
=>
NULL;
end;
end;
# Remove an item; if is it missing raise the table's not-found exception.
#
fun remove (HASHTABLE { hash_g, eq_pred, not_found_exception, table, n_items } ) key
=
item
where
vector = *table;
size = rwv::length vector;
hash = hash_g key;
index = index (hash, size);
fun get (hr::BUCKET (h, k, v, r))
=>
if (hash == h and eq_pred (key, k))
#
(v, r);
else
(get r) -> (item, r');
#
(item, hr::BUCKET (h, k, v, r'));
fi;
#
get hr::NIL
=>
raise exception not_found_exception;
end;
(get (rwv::get (vector, index)))
->
(item, bucket);
rwv::set (vector, index, bucket);
n_items := *n_items - 1;
end;
# Return the number of items in the table:
#
fun vals_count (HASHTABLE { n_items, ... } )
=
*n_items;
# Return a list of the items in the table.
#
fun vals_list (HASHTABLE { table => REF vector, n_items, ... } )
=
hr::vals_list (vector, n_items);
fun keyvals_list (HASHTABLE { table => REF vector, n_items, ... } )
=
hr::keyvals_list (vector, n_items);
# Apply a function to the entries of the table:
#
fun keyed_apply f (HASHTABLE { table, ... } ) = hr::keyed_apply f *table;
fun apply f (HASHTABLE { table, ... } ) = hr::apply f *table;
# Map a table to a new table that has the same keys and exception:
#
fun keyed_map f (HASHTABLE { hash_g, eq_pred, table, n_items, not_found_exception } )
=
HASHTABLE
{
hash_g,
eq_pred,
table => REF (hr::keyed_map f *table),
n_items => REF *n_items,
not_found_exception
};
# Map a table to a new table that has the same keys and exception:
#
fun map f (HASHTABLE { hash_g, eq_pred, table, n_items, not_found_exception } )
=
HASHTABLE
{
hash_g,
eq_pred,
table => REF (hr::map f *table),
n_items => REF *n_items,
not_found_exception
};
# Fold a function over the entries of the table:
#
fun foldi f init (HASHTABLE { table, ... } ) = hr::foldi f init *table;
fun fold f init (HASHTABLE { table, ... } ) = hr::fold f init *table;
# Modify the hashtable items in place:
#
fun keyed_map_in_place f (HASHTABLE { table, ... } ) = hr::keyed_map_in_place f *table;
fun map_in_place f (HASHTABLE { table, ... } ) = hr::map_in_place f *table;
# Remove any hashtable items that do
# not satisfy the given predicate.
#
fun keyed_filter prior (HASHTABLE { table, n_items, ... } )
=
n_items := hr::keyed_filter prior *table;
fun filter prior (HASHTABLE { table, n_items, ... } )
=
n_items := hr::filter prior *table;
# Create a copy of a hashtable
#
fun copy (HASHTABLE { hash_g, eq_pred, table, n_items, not_found_exception } )
=
HASHTABLE
{
hash_g,
eq_pred,
table => REF (hr::copy *table),
n_items => REF *n_items,
not_found_exception
};
# Return a list of the sizes of the various buckets.
# This is to allow users to gauge the quality of
# their hashing function:
#
fun bucket_sizes (HASHTABLE { table, ... } )
=
hr::bucket_sizes *table;
}; # package hashtable
end;