Keyed sets

In keyed-set.diesel:

Keyed sets are a space-saving cross between a table and a set. A keyed set is a table where the keys are stored as part of the elements of the table; if the key was already part of the value, then this is more efficient than extracting the key from the value, then storing it separately in a table.

extend module Stdlib;

module KeyedSet;

Keyed set elements must be subtypes of keyed_comparable:

abstract class keyed_comparable[Key <= comparable[Key]];
  fun key(:keyed_comparable[`Key]):Key;
  fun has_key(k1:keyed_comparable[`Key], k2:Key):bool;
  fun is_same_key(k1:keyed_comparable[`Key],
                         k2:keyed_comparable[`Key]):bool;

Keyed sets also support removable_ and extensible_collection operations such as remove, add, add_all, add_nonmember. Keyed sets also support table behavior, plus an associative lookup operation, match, which returns the element of the set that has the same key (using =) as the second argument (invoking the if_absent closure if no such matching element is found).

abstract class keyed_set[Key <= comparable[Key],
                                Value <= keyed_comparable[Key]]
                isa table[Key,Value],
                    unordered_collection[Value],
                    - Value type parameter is covariant:
                    keyed_set[Key, `Value1 >= Value];
abstract class keyed_set_exactly[Key <= comparable[Key],
                                        Value <= keyed_comparable[Key]]
                isa table_exactly[Key,Value],
                    unordered_collection_exactly[Value],
                    keyed_set[Key, Value];
  fun match(t:keyed_set_exactly[`Key,`Value], v:Value,
                   if_absent:&():`T):Value|T;
  fun match(t:keyed_set_exactly[`Key,`Value], v:Value):Value;

If values are comparable or hashable, then so is the collection. Two keyed sets are equal when they include the same elements (regular set equality operations).

  extend class keyed_set_exactly[`Key, `Value <= comparable[Value]]
                                isa comparable[keyed_set_exactly[Key,Value]];
  extend class keyed_set_exactly[`Key, `Value <= hashable[Value]]
                                isa hashable[keyed_set_exactly[Key,Value]];

As usual, immutable and mutable varieties are defined. Mutable keyed sets also support the adding and removing operations of extensible_collection, thereby acting a lot like sets (hence their name), and the storing and removing operations of m_removable_table. The store operation for keyed sets is restricted, however, in that the key of the value being stored must match the key where it's being stored, i.e., store(k, v) must be identical in effect to add(v).

abstract class i_keyed_set[Key <= comparable[Key],
                                  Value <= keyed_comparable[Key]]
                isa keyed_set[Key,Value],
                    i_table[Key,Value],
                    i_unordered_collection[Value],
                    - Value type parameter is covariant:
                    i_keyed_set[Key, `Value1 >= Value];
abstract class i_keyed_set_exactly[Key <= comparable[Key],
                                          Value <= keyed_comparable[Key]]
                isa keyed_set_exactly[Key,Value],
                    i_table_exactly[Key,Value],
                    i_unordered_collection_exactly[Value],
                    i_keyed_set[Key, Value];
abstract class m_keyed_set[Key <= comparable[Key],
                                  Value <= keyed_comparable[Key]]
                isa keyed_set_exactly[Key,Value],
                    m_removable_table[Key,Value],
                    extensible_collection[Value],
                    m_unordered_collection[Value];
  extend class m_keyed_set[`Key, `Value <= comparable[Value]]
                isa removable_collection[Value];

Mutable keyed sets also support a remove_match operation that removes the element of the table whose key matches that of the argument element.

  fun remove_match(:m_keyed_set[`Key,`Value], value:Value,
                          if_absent:&():`Else):Value|Else;
  fun remove_match(t:m_keyed_set[`Key,`Value], value:Value):Value;

A linked-list based implementation of m_keyed_sets.

class list_keyed_set[Key <= comparable[Key],
                            Value <= keyed_comparable[Key]]
                                                isa m_keyed_set[Key,Value];
  fun new_list_keyed_set[Key <= comparable[Key],
                                Value <= keyed_comparable[Key]](
                                      ):list_keyed_set[Key,Value];

end module KeyedSet;

In hash-keyed-set.diesel:

The hashing-based keyed sets require the keys to be hashable, implying that the elements of the keyed set must be subtypes of keyed_hashable, not just keyed_comparable. hash_keyed_set is an implementation of mutable keyed sets using open hashing; chained_hash_keyed_set is an implementation of mutable keyed sets based on closed hashing. The hashing-based keyed set implementations allow a guess at a maximum size to be provided when the collection is created. As with all hashing-based implementations, however, the keyed set will automatically resize itself if it grows too large or small.

extend module Stdlib;

module HashKeyedSet;
abstract class keyed_hashable[Key <= hashable[Key]]
                                                isa keyed_comparable[Key];
  fun hash_key(k:keyed_hashable[`Key], range:int):int;
class hash_keyed_set[Key <= hashable[Key],
                            Value <= keyed_hashable[Key]]
                    isa m_keyed_set[Key,Value];
fun new_hash_keyed_set[Key <= hashable[Key],
                              Value <= keyed_hashable[Key]](
      ):hash_keyed_set[Key,Value];
fun new_hash_keyed_set[Key <= hashable[Key],
                              Value <= keyed_hashable[Key]](
      size:int):hash_keyed_set[Key,Value];

end module HashKeyedSet;

In chained-hash-keyed-set.diesel:

extend module Stdlib;

module ChainedHashKeyedSet;
class chained_hash_keyed_set[Key <= hashable[Key],
                                    Value <= keyed_hashable[Key]]
                                            isa m_keyed_set[Key,Value];
  fun new_chained_hash_keyed_set[Key <= hashable[Key],
                                        Value <= keyed_hashable[Key]](
        ):chained_hash_keyed_set[Key,Value];
  fun new_chained_hash_keyed_set[Key <= hashable[Key],
                                        Value <= keyed_hashable[Key]](
        size:int):chained_hash_keyed_set[Key,Value];

end module ChainedHashKeyedSet;

In small-keyed-set.diesel:

An implementation of m_keyed_set that is space efficient when there are only a few elements, but scales well when there are a large number of elements. Keys of small keyed sets are required to be hashable, as in hash_keyed_sets.

extend module Stdlib;

module SmallKeyedSet;
class small_keyed_set[K <= hashable[K], V <= keyed_hashable[K]]
                                                        isa m_keyed_set[K,V];
fun shrink_small_set(t:small_keyed_set[`K,`V]):void;
fun new_small_keyed_set[K <= hashable[K],
                               V <= keyed_hashable[K]]():small_keyed_set[K,V];
module AbsentKeyedSet;
synonym big_keyed_set[`K,`V] = m_keyed_set[K,V]|absent_keyed_set[K,V];
object absent_keyed_set[K <= hashable[K], V <= keyed_hashable[K]];

end module AbsentKeyedSet;

end module SmallKeyedSet;