Filtered and mapped views

Views support a transformation of an existing collection data structure, without requiring a copy operation and while preserving mutability. Filtered tables allow viewing an existing table through an arbitrary predicate filter, such as including only a subset of the keys of the table. Mapped tables support viewing an existing table after first processing the keys through a mapping function.

In filtered.cecil:

template representation filtered_table[Key,Value,Table <= table[Key,Value]] 
isa table[Key,Value];
method length(t@:filtered_table[`Key,`Value,`Table]):int; 
method do_associations(t@:filtered_table[`Key,`Value,`Table], 
c:&(Key,Value):void):void;
method fetch(t@:filtered_table[`Key,`Value,`Table], key:Key, 
if_absent:&():Value):Value;
method collection_name(@:filtered_table[`Key,`Value,`Table]):string; 
template representation m_filtered_table[Key,Value,Table <= m_table[Key,Value]] 
isa filtered_table[Key,Value,Table], m_table[Key,Value];
method store(t@:m_filtered_table[`Key,`Value,`Table], key:Key, value:Value, 
if_absent:&():void):void;
method view_filtered(t@:table[`Key,`Value], filter:&(Key):bool) 
:table[Key,Value];
method view_filtered(t@:m_table[`Key,`Value], filter:&(Key):bool) 
:m_table[Key,Value];
method view_subset(t@:table[`Key <= comparable[Key],`Value], keys@:set[Key]) 
:table[Key,Value];
method view_subset(t@:m_table[`Key <= comparable[Key],`Value], keys@:set[Key]) 
:m_table[Key,Value];

The view_filtered methods take a predicate function to filter the keys. The view_subset function supports the special case where the filtering predicate is that the key is drawn from a particular set. The mutable filtered table implementation doesn't support adding new bindings through the store function, only updating existing bindings.

In mapped.cecil:

template representation mapped_table[Key1, Key2, Value] 
isa table[Key1, Value];
method length(v@:mapped_table[`Key1, `Key2, `Value]):int; 
method is_empty(v@:mapped_table[`Key1, `Key2, `Value]):bool; 
method fetch(v@:mapped_table[`Key1, `Key2, `Value], key:Key1, 
if_absent:&():Value):Value;
method collection_name(@:mapped_table[`Key1, `Key2, `Value]):string; 
template representation m_mapped_table[Key1, Key2, Value]  
isa mapped_table[Key1,Key2,Value], m_table[Key1, Value];
method store(v@:m_mapped_table[`Key1, `Key2, `Value], key:Key1, value:Value, 
if_absent:&():void):void;
method view_mapped(t@:table[`Key2, `Value], map@:table[`Key1, Key2]) 
:table[Key1, Value];
method view_mapped(t@:m_table[`Key2, `Value], map@:table[`Key1, Key2]) 
:m_table[Key1, Value];
method view_mapped(t@:mapped_table[`Key2, `Key3, `Value], 
map@:table[`Key1, Key2]):table[Key1, Value];
signature view_mapped(m_table[`Key2, `Value], 
map:table[`Key1, Key2]):m_table[Key1, Value];
signature view_mapped(table[`Key2, `Value], 
map:indexed[Key2]):indexed[Value];
signature view_mapped(m_table[`Key2, `Value], 
map:indexed[Key2]):m_indexed[Value];
template representation indexed_table[Key, Value] 
isa mapped_table[int,Key,Value], indexed[Value];
template representation m_indexed_table[Key, Value] 
isa indexed_table[Key,Value],
m_mapped_table[int,Key,Value],
m_indexed[Value];
method view_index_mapped(t@:table[`Key, `Value], map@:indexed[Key]) 
:indexed[Value];
method view_index_mapped(t@:m_table[`Key, `Value], map@:indexed[Key]) 
:m_indexed[Value];
method view_index_mapped(t@:indexed_table[`Key, `Value], map@:indexed[int]) 
:indexed[Value];
method view_index_mapped(t@:m_indexed_table[`Key, `Value], map@:indexed[int]) 
:m_indexed[Value];
method view_subrange(t@:indexed[`T], from:int, to:int):indexed[T]; 
method view_subrange(t@:m_indexed[`T], from:int, to:int):m_indexed[T]; 
method view_subrange(t@:indexed[`T], from:int, to:int, step:int):indexed[T]; 
method view_subrange(t@:m_indexed[`T], from:int, to:int, step:int) 
:m_indexed[T];

The view_mapped function takes a table mapping K2 to V and a key mapping table mapping K1 to K2 and returns a new table that maps from K1 to V transparently. The view_index_mapped function takes a table and a mapping from dense integers to the keys of the table (a.k.a. an indexed collection of the keys) and returns a new table mapping from dense integers to the values of the table (a.k.a. an indexed collection of the values). The view_subrange functions support similar functionality if the viewed table is an indexed collection and the key map is an interval. The view_subrange function is particularly useful for constructing (mutable) views of an existing large indexed collection and then applying standard indexed collection operations to the subrange. For example:

let x:array[string] := ...;
let rest:m_indexed[string] := x.view_subrange(1, x.length.pred);
let evens:m_indexed[string] := x.view_subrange(0, x.length.pred, 2);

template representation string_view isa indexed_table[int,char], string; 
template representation m_string_view 
isa string_view, m_string, m_indexed_table[int,char];
method view_string_index_mapped(s@:string, map@:indexed[int]):string; 
method view_string_index_mapped(s@:m_string, map@:indexed[int]):m_string; 
method view_string_index_mapped(s@:string_view, map@:indexed[int]):string; 
method view_string_index_mapped(s@:m_string_view, map@:indexed[int]):m_string; 
method view_subrange(s@:string, from:int, to:int):string; 
method view_subrange(s@:m_string, from:int, to:int):m_string; 
method view_subrange(s@:string, from:int, to:int, step:int):string; 
method view_subrange(s@:m_string, from:int, to:int, step:int):m_string; 
method compose(t1@:table[`Key2,`Value], t2@:table[`Key1,Key2]) 
:table[Key1,Value];
method compose(t1@:table[`Key2,`Value], t2@:indexed[Key2]) 
:indexed[Value];
method compose(t1@:interval, t2@:interval):interval; 

Views of strings preserve ``stringness.''