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.diesel:

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.

extend module Stdlib;

module FilteredTable;
class filtered_table[Key,Value,Table <= table_exactly[Key,Value]]
                                                isa table_exactly[Key,Value];
class m_filtered_table[Key,Value,Table <= m_table[Key,Value]]
                isa filtered_table[Key,Value,Table], m_table[Key,Value];
fun view_filtered(t:table_exactly[`Key,`Value], filter:&(Key):bool
                         ):table_exactly[Key,Value];
fun view_subset(t:table_exactly[`Key <= comparable[Key],`Value],
                       keys:set[Key]
                       ):table_exactly[Key,Value];

end module FilteredTable;

In mapped.diesel:

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

extend module Stdlib;

module MappedCollection;
class mapped_table[Key1, Key2, Value] isa table_exactly[Key1, Value];
class m_mapped_table[Key1, Key2, Value]
                isa mapped_table[Key1,Key2,Value], m_table[Key1, Value];
fun view_mapped(t:table[`Key2, `Value],
                       map:table_exactly[`Key1, Key2]
                       ):table[Key1, Value];
class indexed_table[Key, Value]
    isa mapped_table[int,Key,Value], indexed_exactly[Value];
class m_indexed_table[Key, Value]
    isa indexed_table[Key,Value],
        m_mapped_table[int,Key,Value],
        m_indexed[Value];
fun view_index_mapped(t:table[`Key, `Value],
                             map:indexed_exactly[Key]
                             ):indexed[Value];
fun view_subrange(t:indexed[`T], from:int):indexed[T];
fun view_subrange(t:indexed[`T], from:int, to:int):indexed[T];
fun view_subrange(t:indexed[`T], from:int, to:int, step:int):indexed[T];

Views of strings preserve ``stringness.''

class string_view isa indexed_table[int,char], string;
class m_string_view isa string_view, m_string,
                               m_indexed_table[int,char];
fun view_string_index_mapped(s:string, map:indexed_exactly[int]
                                    ):string;

end module MappedCollection;