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 copy(m@:mapped_table[`Key1, `Key2, `Value]
            ):mapped_table[`Key1, `Key2, `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 copy(m@:m_mapped_table[`Key1, `Key2, `Value]
            ):m_mapped_table[`Key1, `Key2, `Value];
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];
method view_mapped(t@:m_mapped_table[`Key2, `Key3, `Value],
                   map@:table[`Key1, Key2]):m_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):indexed[T];
method view_subrange(t@:m_indexed[`T], from:int):m_indexed[T];
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(t@:string, from:int):string;
method view_subrange(t@:m_string, from: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.''