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

--DOC `assoc_table' is an implementation of tables based on a
--DOC linked-list of key/value associations. The keys must be
--DOC `comparable'.

let var warn_for_long_assoc_tables:bool := false;

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

  extend assoc[`Key, `Value <= comparable[Value]]
					isa comparable[assoc[Key,Value]];
  method =(l@:assoc[`Key, `Value <= comparable[Value]],
	   r@:assoc[`Key, `Value <= comparable[Value]]):bool {
      l == r | { l.key = r.key & { l.value = r.value } } }

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

  method new_assoc[Key <= comparable[Key], Value](k:Key, v:Value
						  ):assoc[Key,Value] {
      concrete object isa assoc[Key,Value] { key := k, value := v } }

  method copy(a@:assoc[`Key,`Value]):assoc[Key,Value] {
      new_assoc[Key,Value](a.key, a.value) }


template object assoc_table[Key <= comparable[Key], Value]
					isa m_removable_table[Key,Value];
  private field assocs(@:assoc_table[`Key,`Value]):m_list[assoc[Key,Value]]
  		      := new_m_list[assoc[Key,Value]]();

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

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

  method store(t@:assoc_table[`Key,`Value], key:Key, value:Value,
	       if_absent:&():void):void {
      do(t.assocs, &(a:assoc[Key,Value]){
	  if(key = a.key, { a.value := value; ^ });
      });
      t.store_no_dup(key, value);
  }
  method store_no_dup(t@:assoc_table[`Key,`Value], key:Key, value:Value):void {
      t.add_assoc(new_assoc[Key,Value](key, value));
      if(warn_for_long_assoc_tables & { t.length = 11 }, {
	  print_line("\a** warning: assoc_table " || t.print_string ||
		     " grew to more than 10 entries");
      });
  }
  method add_assoc(t@:assoc_table[`Key,`Value], a:assoc[Key,Value]):void {
      t.assocs.add(a);
  }

  method remove_key(t@:assoc_table[`Key,`Value], key:Key,
		    if_absent:&():`Else):Value|Else {
      t.assocs.remove_and_return_one(&(x:assoc[Key,Value]){ x.key = key },
				     { ^ eval(if_absent) }).value }

  method remove_keys_if(t@:assoc_table[`Key,`Value], pred:&(Key):bool):int {
      t.assocs.remove_if(&(a:assoc[Key,Value]){ eval(pred, a.key); });
  }

  method remove_all(t@:assoc_table[`Key,`Value]):void {
      t.assocs.remove_all;
  }

  method new_assoc_table[Key <= comparable[Key], Value]()
  						:assoc_table[Key,Value] {
      concrete object isa assoc_table[Key,Value] }

  method copy_empty(t@:assoc_table[`Key,`Value]):assoc_table[Key,Value] {
      new_assoc_table[Key,Value]() }
  method copy(t@:assoc_table[`Key,`Value]):assoc_table[Key,Value] {
      let c:assoc_table[Key,Value] := t.copy_empty;
      t.assocs.do(&(a:assoc[Key,Value]){
	  c.add_assoc(a.copy);
      });
      c }



--
-- table data structure with different printing behavior
--
template object assoc_CR_table[Key <= comparable[Key], Value]
			isa assoc_table[Key,Value];
  method elem_separator(t@:assoc_CR_table[`Key,`Value]):string { "\n" }

  method new_assoc_CR_table[Key <= comparable[Key], Value]()
     			   :assoc_CR_table[Key,Value] {
      concrete object isa assoc_CR_table[Key,Value] }

  method copy_empty(c@:assoc_CR_table[`Key,`Value]):assoc_CR_table[Key,Value] {
      new_assoc_CR_table[Key,Value]() }


-- an assoc table that keeps keys *ordered* in the order they were added
-- to the table

template object ordered_assoc_table[Key <= comparable[Key], Value]
					isa assoc_table[Key,Value];
  method add_assoc(t@:ordered_assoc_table[`Key,`Value],
		   a:assoc[Key,Value]):void {
      t.assocs.add_last(a);
  }

  method new_ordered_assoc_table[Key <= comparable[Key], Value]()
     			   :ordered_assoc_table[Key,Value] {
      concrete object isa ordered_assoc_table[Key,Value] }

  method copy_empty(c@:ordered_assoc_table[`Key,`Value]
		    ):ordered_assoc_table[Key,Value] {
      new_ordered_assoc_table[Key,Value]() }


--
-- ordered assoc table data structure with different printing behavior
--
template object ordered_assoc_CR_table[Key <= comparable[Key], Value]
			isa ordered_assoc_table[Key,Value];
  method elem_separator(t@:ordered_assoc_CR_table[`Key,`Value]):string { "\n" }

  method new_ordered_assoc_CR_table[Key <= comparable[Key], Value]()
     			   :ordered_assoc_CR_table[Key,Value] {
      concrete object isa ordered_assoc_CR_table[Key,Value] }

  method copy_empty(c@:ordered_assoc_CR_table[`Key,`Value]
		    ):ordered_assoc_CR_table[Key,Value] {
      new_ordered_assoc_CR_table[Key,Value]() }