Keyed sets

The remainder of this section describes advanced collections and can be skipped upon first reading.

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];
extend type keyed_set[`Key,`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;

Keyed sets also support removable_ and extensible_collection operations such as remove, add, add_all, add_no_dup. 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 <= comparable[Value]] 
isa unordered_collection[Value], comparable[keyed_set[Key,Value]];
method =(t1@:keyed_set[`Key, `Value <= comparable[Value]], 
t2@:keyed_set[Key, Value]):bool;
extend keyed_set[`Key, `Value <= hashable[Value]] 
isa hashable[keyed_set[Key,Value]];
method hash(t@:keyed_set[`Key,`Value <= hashable[Value]], range:int):int; 
method elems_print_string(t@:keyed_set[`Key,`Value]):string; 
method elems_print(t@:keyed_set[`Key,`Value]):void; 

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];
extend i_keyed_set[`Key, `Value <= comparable[Value]] 
isa i_unordered_collection[Value];
extend type i_keyed_set[`Key,`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];
extend m_keyed_set[`Key, `Value <= comparable[Value]] 
isa m_unordered_collection[Value], removable_collection[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;

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 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];