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

include "ilist.cecil";

(--
`table_assoc' is an implementation of tables based on a linked list of
key/value associations.  The keys must be `comparable'; here is what we
assume about type `comparable':

	type comparable[`T] where T <= comparable[T];
	signature =(`T,`T):bool where T <= comparable[T];

This type (and object) is declared in the stdlib file `comparable.cecil'.
In the same file is also the definition of object `ordered[T]' which
you may want to use for your homework.  The implementation of association
tables used by the stdandard library is in file `assoc-table.cecil'.
--)

----------------------
-- associations

(--
The declaration of the `association' object has a constraint on its type
parameter.  This constraint will be checked every time this object is
referred to (for example, as in `association[int,string]' or in the
`new_association' method below).

For convenience, the typechecker inserts this constraint automatically
when `association' is referred to under the following condition:
`association' is parameterized by type variables and they have
preceeding backquotes.  (The type variables mentioned in each
particular case will be the ones on which the condition is inserted,
not necessarily `Key' and `Value'.)

For example, this constraint is automatically added by the typechecker
to the field declarations below, but not in the `new_association' method.
(The constraint is checked no matter if it has been added automatically
 or not.)

Instead of the F-bounded subtyping constraint `Key <= comparable[Key]'
one could use the signature constraint `signature =(Key,Key):bool',
for example, as in

	template object association[`Key, `Value]
	  where signature =(Key,Key):bool;
--)

template object association[`Key, `Value] where Key <= comparable[Key];
      field key(@:association[`Key,`Value]):Key;
  var field value(@:association[`Key,`Value]):Value;

  method print_string(a@:association[`Key,`Value]):string {
      a.key.print_string || " -> " || a.value.print_string }

  method new_association[`Key, `Value](k:Key, v:Value):association[Key,Value]
      where Key <= comparable[Key]
 { concrete object isa association[Key,Value] { key := k, value := v } }


----------------------
-- table_assoc
--
template object table_assoc[`Key, `Value] where Key <= comparable[Key];
extend table_assoc[`Key, `Value] isa m_table[Key,Value];

  private var field assocs(@:table_assoc[`Key,`Value]
			   ):i_list[association[Key,Value]] := i_nil;

  method new_table_assoc[Key, Value]():table_assoc[Key,Value]
      where Key <= comparable[Key]
  { concrete object isa table_assoc[Key,Value] }

  method length(t@:table_assoc[`Key,`Value]):int { t.assocs.length }

  method do(t@:table_assoc[`Key,`Value], closure:&(elm:Value):void):void {
      do_associations(t, &(k:Key,v:Value){ eval(closure, v) });
  }

  method do_associations(t@:table_assoc[`Key,`Value],
			 c:&(Key,Value):void):void
  {
      do(t.assocs, &(a:association[Key,Value]){ eval(c, a.key, a.value); });
  }

  method store(t@:table_assoc[`Key,`Value], key:Key, value:Value,
	       if_absent:&():void):void
  {
      -- if the key is already in the table, update the corresponding value
      do(t.assocs, &(a:association[Key,Value]){
	  if(key = a.key, { a.value := value; ^ });
      });
      -- if the key is not in the table, add a new association
      t.assocs := i_cons(new_association[Key,Value](key,value), t.assocs);
  }

  method fetch(t@:table_assoc[`Key,`Value], key:Key):Value {
    fetch(t, key, { error("key not found in table") }) }

  method fetch(t@:table_assoc[`Key,`Value], key:Key, if_absent:&():`Else
	       ):Value|Else {
      do_associations(t, &(k:Key, v:Value){ if(key = k, { ^ v }); });
      eval(if_absent) }