Next: Collectors
Up: Advanced collection
Previous: Advanced collection
Index
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 <= hashable[K],`V <= keyed_hashable[K]] =
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
.
Next: Collectors
Up: Advanced collection
Previous: Advanced collection
Index
Cecil/Vortex Project