-- Copyright 1993-1998, by the Cecil Project
-- Department of Computer Science and Engineering, University of Washington
-- See the LICENSE file for license information.

(--DOC
  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: 
  <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);
  <ENDEXAMPLE>
--)

-- a view of a table, mapping one set of keys to another.
-- things will break if viewed table changes its set of legal keys
--   and then the view is consulted again.

template representation mapped_table[Key1, Key2, Value]
			isa table[Key1, Value];
private field 
    key_map(@:mapped_table[`Key1,`Key2,`Value]):table[Key1,Key2];
private field 
    table(@:mapped_table[`Key1,`Key2,`Value]):table[Key2,Value];

method length(v@:mapped_table[`Key1, `Key2, `Value]):int { v.key_map.length }
method is_empty(v@:mapped_table[`Key1, `Key2, `Value]):bool {
    v.key_map.is_empty }

method fetch(v@:mapped_table[`Key1, `Key2, `Value], key:Key1,
	     if_absent:&():Value):Value {
    fetch(v.table, fetch(v.key_map, key, { ^ eval(if_absent) }),
	  { error("viewed collection has changed keys") }) }


method collection_name(@:mapped_table[`Key1, `Key2, `Value]):string { 
    "mapped_table" }


-- mutable views.
-- can change bindings of keys, but don't support adding new keys to viewee

template representation m_mapped_table[Key1, Key2, Value] 
	        isa mapped_table[Key1,Key2,Value], m_table[Key1, Value];
private field signature table(m_mapped_table[`Key1,`Key2,`Value]
			      ):m_table[Key2,Value];

method store(v@:m_mapped_table[`Key1, `Key2, `Value], key:Key1, value:Value,
	     if_absent:&():void):void {
    store(v.table, fetch(v.key_map, key, { ^ eval(if_absent) }), value,
	  { error("viewed collection has changed keys") }) }


-- constructors for mapped views and special cases.

-- all operations are replicated to distinguish read-only views from
--   mutable views, mainly in the result type.  is there a better way?
--   maybe predicate types or dependent types?
--   e.g. result mutable iff viewee mutable?

method view_mapped(t@:table[`Key2, `Value], map@:table[`Key1, Key2])
		  :table[Key1, Value] {
    concrete object isa 
        mapped_table[Key1, Key2, Value] { table := t, key_map := map } }
method view_mapped(t@:m_table[`Key2, `Value], map@:table[`Key1, Key2])
		  :m_table[Key1, Value] {
    concrete object isa
	m_mapped_table[Key1, Key2, Value] { table := t, key_map := map } }


-- optimizations for viewing a view
method view_mapped(t@:mapped_table[`Key2, `Key3, `Value],
		   map@:table[`Key1, Key2]):table[Key1, Value] {
    view_mapped(t.table, compose(t.key_map, map)) }

-- signatures to refine the result type
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];



-- indexed view of a table

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] {
    concrete object isa 
        indexed_table[Key, Value] { table := t, key_map := map } }
method view_index_mapped(t@:m_table[`Key, `Value], map@:indexed[Key])
		  	:m_indexed[Value] {
    concrete object isa
	m_indexed_table[Key, Value] { table := t, key_map := map } }


-- optimizations for viewing a view
method view_index_mapped(t@:indexed_table[`Key, `Value], map@:indexed[int])
		  	:indexed[Value] {
    view_index_mapped(t.table, compose(t.key_map, map)) }
method view_index_mapped(t@:m_indexed_table[`Key, `Value], map@:indexed[int])
		  	:m_indexed[Value] {
    view_index_mapped(t.table, compose(t.key_map, map)) }


-- views of indexed collections
method view_subrange(t@:indexed[`T], from:int):indexed[T] {
    view_subrange(t, from, t.length.pred) }
method view_subrange(t@:m_indexed[`T], from:int):m_indexed[T] {
    view_subrange(t, from, t.length.pred) }
method view_subrange(t@:indexed[`T], from:int, to:int):indexed[T] {
    view_index_mapped(t, new_interval(from, to)) }
method view_subrange(t@:m_indexed[`T], from:int, to:int):m_indexed[T] {
    view_index_mapped(t, new_interval(from, to)) }
method view_subrange(t@:indexed[`T], from:int, to:int, step:int):indexed[T] {
    view_index_mapped(t, new_interval(from, to, step)) }
method view_subrange(t@:m_indexed[`T], from:int, to:int, step:int)
		    :m_indexed[T] {
    view_index_mapped(t, new_interval(from, to, step)) }


-- views of strings

--DOC Views of strings preserve "stringness."

template representation string_view isa indexed_table[int,char], string;
  private field signature table(string_view):string;
template representation m_string_view
			isa string_view, m_string, m_indexed_table[int,char];
  private field signature table(m_string_view):m_string;

method view_string_index_mapped(s@:string, map@:indexed[int]):string {
    concrete object isa string_view { table := s, key_map := map } }
method view_string_index_mapped(s@:m_string, map@:indexed[int]):m_string {
    concrete object isa m_string_view { table := s, key_map := map } }

-- optimizations for viewing a string view
method view_string_index_mapped(s@:string_view, map@:indexed[int]):string {
    view_string_index_mapped(s.table, compose(s.key_map, map)) }
method view_string_index_mapped(s@:m_string_view, map@:indexed[int]):m_string {
    view_string_index_mapped(s.table, compose(s.key_map, map)) }

-- convenient interface for substrings
method view_subrange(t@:string, from:int):string {
    view_subrange(t, from, t.length.pred) }
method view_subrange(t@:m_string, from:int):m_string {
    view_subrange(t, from, t.length.pred) }
method view_subrange(s@:string, from:int, to:int):string {
    view_string_index_mapped(s, new_interval(from, to)) }
method view_subrange(s@:m_string, from:int, to:int):m_string {
    view_string_index_mapped(s, new_interval(from, to)) }
method view_subrange(s@:string, from:int, to:int, step:int):string {
    view_string_index_mapped(s, new_interval(from, to, step)) }
method view_subrange(s@:m_string, from:int, to:int, step:int):m_string {
    view_string_index_mapped(s, new_interval(from, to, step)) }


-- composing tables:
-- first map keys using t2, then map using t1, i.e. map using (t1 o t2)
method compose(t1@:table[`Key2,`Value], t2@:table[`Key1,Key2])
     	      :table[Key1,Value] {
    view_mapped(t1, t2) }
method compose(t1@:table[`Key2,`Value], t2@:indexed[Key2])
     	      :indexed[Value] {
    view_mapped(t1, t2) }

method compose(t1@:interval, t2@:interval):interval {
    -- can combine intervals; good for optimizing subranges of subranges
    if(t2.is_empty, { ^ t2 });
    new_interval(t1!t2.start, t1!t2.stop, t1.step * t2.step) }