Keyed sets

In keyed-set.cecil:

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.

abstract object keyed_comparable[Key <= comparable[Key]];
  signature key(keyed_comparable[`Key]):Key;
  method has_key(k1@:keyed_comparable[`Key], k2:Key):bool;
  method is_same_key(k1@:keyed_comparable[`Key],
                     k2@:keyed_comparable[`Key]):bool;

Keyed set elements must be subtypes of keyed_comparable:

abstract object keyed_set[Key <= comparable[Key],
                          Value <= keyed_comparable[Key]]
                isa table[Key,Value],
                    unordered_collection[Value]
           subtypes keyed_set[Key, `Value1 >= Value];
  method do_associations(t@:keyed_set[`Key,`Value], c:&(Key,Value):void):void;
  method do_associations_allowing_updates(t@:keyed_set[`Key,`Value],
                                          c:&(Key,Value):void):void;
  method fetch(t@:keyed_set[`Key,`Value], key:Key, if_absent:&():Value):Value;
  method match(t@:keyed_set[`Key,`Value], v:Value, if_absent:&():Value):Value;
  method match(t@:keyed_set[`Key,`Value], v:Value):Value;
  method find_key(t@:keyed_set[`Key,`Value <= comparable[Value]], value:Value,
                  if_absent:&():Key):Key;
  method elems_print_string(t@:keyed_set[`Key,`Value]):string;
  method elems_print(t@:keyed_set[`Key,`Value]):void;

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).

  extend keyed_set[`Key, `Value]
        isa comparable[keyed_set[Key,`Value <= comparable[Value]]],
            hashable[keyed_set[Key, `Value <= hashable[Value]]];
  method =(t1@:keyed_set[`Key, `Value <= comparable[Value]],
           t2@:keyed_set[Key, Value]):bool;
  method hash(t@:keyed_set[`Key,`Value <= hashable[Value]], range:int):int;

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).

abstract object i_keyed_set[Key <= comparable[Key],
                            Value <= keyed_comparable[Key]]
                isa keyed_set[Key,Value],
                    i_table[Key,Value],
                    i_unordered_collection[Value]
           subtypes i_keyed_set[Key, `Value1 >= Value];
  method copy(t@:i_keyed_set[`Key,`Value]):i_keyed_set[Key,Value];
abstract object m_keyed_set[Key <= comparable[Key],
                            Value <= keyed_comparable[Key]]
                isa keyed_set[Key,Value],
                    m_removable_table[Key,Value],
                    extensible_collection[Value],
                    m_unordered_collection[Value],
                    removable_collection[`Value <= comparable[Value]];
  method fetch_or_init(t@:m_keyed_set[`Key,`Value], key:Key,
                       if_init:&():Value):Value;
  method store(t@:m_keyed_set[`Key,`Value], key:Key, value:Value,
               if_absent:&():void):void;
  method store_no_dup(t@:m_keyed_set[`Key,`Value], key:Key, value:Value):void;

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).

  signature remove_match(m_keyed_set[`Key,`Value], value:Value,
                         if_absent:&():`Else):Value|Else;
  method remove_match(t@:m_keyed_set[`Key,`Value], value:Value):Value;
  signature copy_empty(m_keyed_set[`Key,`Value]):m_keyed_set[Key,Value];
  method copy(t@:m_keyed_set[`Key,`Value]):m_keyed_set[Key,Value];
  signature add_nonmember(m_keyed_set[`Key,`Value], Value):void;

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

template object list_keyed_set[Key <= comparable[Key],
                               Value <= keyed_comparable[Key]]
                                                isa m_keyed_set[Key,Value];
  method collection_name(@:list_keyed_set[`Key,`Value]):string;
  method length(t@:list_keyed_set[`Key,`Value]):int;
  method is_empty(t@:list_keyed_set[`Key,`Value]):bool;
  method do(t@:list_keyed_set[`Key,`Value], c:&(Value):void):void;
  method add(m@:list_keyed_set[`Key,`Value], x:Value):void;
  method add_nonmember(m@:list_keyed_set[`Key,`Value], x:Value):void;
  method remove_key(t@:list_keyed_set[`Key,`Value], key:Key,
                    if_absent:&():`Else):Value|Else;
  method remove_match(t@:list_keyed_set[`Key,`Value], x:Value,
                         if_absent:&():`Else):Value|Else;
  method remove(t@:list_keyed_set[`Key,`Value <= comparable[Value]], x:Value,
                if_absent:&():void):void;
  method remove_any(t@:list_keyed_set[`Key,`Value],
                    if_empty:&():`Else):Value|Else;
  method remove_all(t@:list_keyed_set[`Key,`Value]):void;
  method remove_if(t@:list_keyed_set[`Key,`Value],
                   pred:&(Value):bool):int;
  method remove_keys_if(t@:list_keyed_set[`Key,`Value],
                        pred:&(Key):bool):int;
  method new_list_keyed_set[Key <= comparable[Key],
                            Value <= keyed_comparable[Key]](
                                  ):list_keyed_set[Key,Value];
  method copy_empty(c@:list_keyed_set[`Key,`Value]):list_keyed_set[Key,Value];

A linked-list based implementation of m_keyed_sets.

abstract object keyed_hashable[Key <= hashable[Key]] isa keyed_comparable[Key];
  method hash_key(k@:keyed_hashable[`Key], range:int):int;
template object chained_hash_keyed_set[Key <= hashable[Key],
                                       Value <= keyed_hashable[Key]]
                                            isa m_keyed_set[Key,Value];
  method collection_name(@:chained_hash_keyed_set[`Key,`Value]):string;
  method do(t@:chained_hash_keyed_set[`Key,`Value], c:&(Value):void):void;
  method do_allowing_updates(t@:chained_hash_keyed_set[`Key,`Value],
                             c:&(Value):void):void;
  method includes(t@:chained_hash_keyed_set[`Key,`Value <= comparable[Value]],
                  x:Value):bool;
  method fetch(t@:chained_hash_keyed_set[`Key,`Value], key:Key,
               if_absent:&():Value):Value;
  method match(t@:chained_hash_keyed_set[`Key,`Value], v:Value,
               if_absent:&():Value):Value;
  method add(t@:chained_hash_keyed_set[`Key,`Value], x:Value):void;
  method add_nonmember(t@:chained_hash_keyed_set[`Key,`Value], x:Value):void;
  method remove_key(t@:chained_hash_keyed_set[`Key,`Value], key:Key,
                    if_absent:&():`Else):Value|Else;
  method remove_match(t@:chained_hash_keyed_set[`Key,`Value], x:Value,
                      if_absent:&():`Else):Value|Else;
  method remove(t@:chained_hash_keyed_set[`Key,`Value <= comparable[Value]],
                x:Value, if_absent:&():void):void;
  method remove_any(t@:chained_hash_keyed_set[`Key,`Value],
                    if_empty:&():`Else):Value|Else;
  method remove_all(t@:chained_hash_keyed_set[`Key,`Value]):void;
  method remove_if(t@:chained_hash_keyed_set[`Key,`Value],
                   pred:&(Value):bool):int;
  method remove_keys_if(t@:chained_hash_keyed_set[`Key,`Value],
                        pred:&(Key):bool):int;
  method new_chained_hash_keyed_set[Key <= hashable[Key],
                                    Value <= keyed_hashable[Key]](
        ):chained_hash_keyed_set[Key,Value];
  method new_chained_hash_keyed_set[Key <= hashable[Key],
                                    Value <= keyed_hashable[Key]](
        size:int):chained_hash_keyed_set[Key,Value];
  method copy_empty(c@:chained_hash_keyed_set[`Key,`Value])
     :chained_hash_keyed_set[Key,Value];

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. chained_hash_keyed_set is an implementation of mutable keyed sets using closed hashing; hash_keyed_set is an implementation of mutable keyed sets based on open 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. In hash-keyed-set.cecil:

template object hash_keyed_set[Key <= hashable[Key],
                               Value <= keyed_hashable[Key]]
                    isa m_keyed_set[Key,Value], open_table[Value];
method collection_name(@:hash_keyed_set[`Key,`Value]):string;
method do(t@:hash_keyed_set[`Key,`Value], c:&(Value):void):void;
method do_allowing_updates(t@:hash_keyed_set[`Key,`Value],
                           c:&(Value):void):void;
method includes(t@:hash_keyed_set[`Key,`Value <= comparable[Value]],
                val:Value):bool;
method fetch(t@:hash_keyed_set[`Key,`Value], key:Key,
             if_absent:&():Value):Value;
method match(t@:hash_keyed_set[`Key,`Value], val:Value,
             if_absent:&():Value):Value;
method add(t@:hash_keyed_set[`Key,`Value], val:Value):void;
method remove_key(t@:hash_keyed_set[`Key,`Value], key:Key,
                  if_absent:&():`Else):Value|Else;
method remove_match(t@:hash_keyed_set[`Key,`Value], val:Value,
                       if_absent:&():`Else):Value|Else;
method remove(t@:hash_keyed_set[`Key,`Value <= comparable[Value]], val:Value,
              if_absent:&():void):void;
method remove_any(t@:hash_keyed_set[`Key,`Value],
                  if_empty:&():`Else):Value|Else;
method remove_all(t@:hash_keyed_set[`Key,`Value]):void;
method remove_if(t@:hash_keyed_set[`Key,`Value], pred:&(Value):bool):int;
method remove_keys_if(t@:hash_keyed_set[`Key,`Value],
                       pred:&(Key):bool):int;
let var default_hash_keyed_set_size:int;
method new_hash_keyed_set[Key <= hashable[Key], Value <= keyed_hashable[Key]](
      ):hash_keyed_set[Key,Value];
method new_hash_keyed_set[Key <= hashable[Key], Value <= keyed_hashable[Key]](
      size:int):hash_keyed_set[Key,Value];
method copy_empty(c@:hash_keyed_set[`Key,`Value]):hash_keyed_set[Key,Value];
method copy(t@:hash_keyed_set[`Key,`Value]):hash_keyed_set[Key,Value];

In small-keyed-set.cecil:

template object small_keyed_set[K <= hashable[K], V <= keyed_hashable[K]]
                                                        isa m_keyed_set[K,V];
method collection_name(@:small_keyed_set[`K,`V]):string;
method do(t@:small_keyed_set[`K,`V], c:&(V):void):void;
method do_allowing_updates(t@:small_keyed_set[`K,`V], c:&(V):void):void;
method length(t@:small_keyed_set[`K,`V]):int;
method is_empty(t@:small_keyed_set[`K,`V]):bool;
method fetch(t@:small_keyed_set[`K,`V], k:K, if_absent:&():V):V;
method add(t@:small_keyed_set[`K,`V], v:V):void;
method add_nonmember(t@:small_keyed_set[`K,`V], v:V):void;
method includes(t@:small_keyed_set[`K,`V <= comparable[V]], x:V):bool;
method includes_key(t@:small_keyed_set[`K,`V], k:K):bool;
method remove(t@:small_keyed_set[`K,`V <= comparable[V]], x:V,
              if_absent:&():void):void;
method remove_key(t@:small_keyed_set[`K,`V], k:K, if_absent:&():`T):V|T;
method remove_any(t@:small_keyed_set[`K,`V], if_empty:&():`T):V|T;
method remove_all(t@:small_keyed_set[`K,`V]):void;
method remove_if(t@:small_keyed_set[`K,`V], pred:&(V):bool):int;
method remove_keys_if(t@:small_keyed_set[`K,`V], pred:&(K):bool):int;
method copy_empty(t@:small_keyed_set[`K,`V]):small_keyed_set[K,V];
method copy(t@:small_keyed_set[`K,`V]):small_keyed_set[K,V];
method shrink_small_set(t@:small_keyed_set[`K,`V]):void;
method new_small_keyed_set[K <= hashable[K],
                           V <= keyed_hashable[K]]():small_keyed_set[K,V];
type synonym big_keyed_set[`K,`V] = m_keyed_set[K,V]|absent_keyed_set[K,V];
signature do(t:big_keyed_set[`K,`V], c:&(V):void):void;
signature do_allowing_updates(t:big_keyed_set[`K,`V], c:&(V):void):void;
signature length(t:big_keyed_set[`K,`V]):int;
signature is_empty(t:big_keyed_set[`K,`V]):bool;
signature fetch(t:big_keyed_set[`K,`V], k:K, if_absent:&():V):V;
signature add_nonmember(t:big_keyed_set[`K,`V], x:V):void;
signature includes(t:big_keyed_set[`K,`V <= comparable[V]], x:V):bool;
signature includes_key(t:big_keyed_set[`K,`V], k:K):bool;
signature remove(t:big_keyed_set[`K,`V <= comparable[V]], x:V,
                 if_absent:&():void):void;
signature remove_key(t:big_keyed_set[`K,`V], k:K, if_absent:&():`T):V|T;
signature remove_if(t:big_keyed_set[`K,`V], pred:&(V):bool):int;
signature remove_keys_if(t:big_keyed_set[`K,`V], pred:&(K):bool):int;
signature remove_any(t:big_keyed_set[`K,`V], if_empty:&():`T):V|T;
signature remove_all(t:big_keyed_set[`K,`V]):void;
signature copy(t:big_keyed_set[`K,`V]):big_keyed_set[K,V];
concrete object absent_keyed_set[K <= hashable[K], V <= keyed_hashable[K]];
implementation do(t@:absent_keyed_set[`K,`V], c:&(V):void):void;
implementation do_allowing_updates(t@:absent_keyed_set[`K,`V],
                                   c:&(V):void):void;
implementation length(t@:absent_keyed_set[`K,`V]):int;
implementation is_empty(t@:absent_keyed_set[`K,`V]):bool;
implementation fetch(t@:absent_keyed_set[`K,`V], k:K, if_absent:&():V):V;
implementation add_nonmember(t@:absent_keyed_set[`K,`V], x:V):void;
implementation includes(t@:absent_keyed_set[`K,`V <= comparable[V]],
                        x:V):bool;
implementation includes_key(t@:absent_keyed_set[`K,`V], k:K):bool;
implementation remove(t@:absent_keyed_set[`K,`V <= comparable[V]], x:V,
                      if_absent:&():void):void;
implementation remove_key(t@:absent_keyed_set[`K,`V], k:K,
                          if_absent:&():`T):V|T;
implementation remove_if(t@:absent_keyed_set[`K,`V], pred:&(V):bool):int;
implementation remove_keys_if(t@:absent_keyed_set[`K,`V], pred:&(K):bool):int;
implementation remove_any(t@:absent_keyed_set[`K,`V], if_empty:&():`T):V|T;
implementation remove_all(t@:absent_keyed_set[`K,`V]):void;
implementation copy(t@:absent_keyed_set[`K,`V]):big_keyed_set[K,V];

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.