p_table=cluster[key_t, value_t: type] is create, lookup, insert, change,

    delete, empty, unparse
    
%  Overview:  Parameterized Table is a mutable structure that associates keys
%             of type key_t, with values of type value_t
%  Requires:  key_t must have an equals procedure and an unparse procedure
%             or be of type string

where key_t has equal: proctype(key_t, key_t) returns(bool)

rep=array[pair]
pair=struct[key: key_t, val: value_t]

create=proc() returns(p_table[key_t, value_t])
    % effects:  Creates and returns
    
    return(up(rep$new()))
  end create

lookup=proc(tbl: p_table[key_t, value_t], key: key_t) returns(value_t) signals(not_found)
    % effects:  If there is an entry in tbl whose key matches key, returns
    %    its associated value.  Signals not_found if there is no entry
    %    whose key matches name.
    
    i: int:= getind(tbl, key)
    if i > array[pair]$high(down(tbl))
      then signal not_found
      else return(pair$get_val(down(tbl)[i]))
      end
  end lookup

insert = proc(tbl: p_table[key_t, value_t], key: key_t, val: value_t) signals(duplicate)
    % modifies:  tbl
    % effects:  Modifies tbl by inserting an entry whose key is labelled
    %    key and whose associated value is val.  Signal duplicate if
    %    a key labelled key already exists
    
    if getind(tbl, key) <= array[pair]$high(down(tbl))
      then signal duplicate
      else array[pair]$addh(down(tbl), pair${key: key, val: val})
      end
  end insert

change=proc(tbl: p_table[key_t, value_t], key: key_t, new_val: value_t) signals(not_found)
    % modifies:  tbl
    % effects:  Modifies tbl by changing the value associated with key to
    %    new_val.  Signals not_found if there is no entry whose key is key.
    
    i: int:=getind(tbl, key)
    if i > array[pair]$high(down(tbl))
      then signal not_found
      else down(tbl)[i]:=pair$replace_val(down(tbl)[i], new_val)
      end
  end change

delete=proc(tbl: p_table[key_t, value_t], key: key_t) signals(not_found)
    % modifies:  tbl
    % effects:  Modifies tbl by removing the entry whose key is key.  Signals
    %    not_found if there is no entry whose key is key.
    
    i: int:=getind(tbl, key)
    if i <= rep$high(down(tbl))
      then down(tbl)[i] := rep$top(down(tbl))
	rep$remh(down(tbl))
      else signal not_found
      end
  end delete

empty=proc(tbl: p_table[key_t, value_t]) returns(bool)
    % effects:  Returns true if there are no entries in tbl, otherwise
    %    returns false.
    
    return(rep$empty(down(tbl)))
  end empty

unparse=proc(tbl: p_table[key_t, value_t])  returns(string) where key_t has

    unparse: proctype(key_t) returns(string), value_t has unparse:

    proctype(value_t) returns(string)
    
    % effects:  Returns a human readable string that describes the current
    %    contents of tbl.
    
    i: int:=array[pair]$low(down(tbl))
    top: int:=array[pair]$high(down(tbl))
    s: string:=("")
    while i <= top do
	s:=string$concat(s, key_t$unparse(pair$get_key(down(tbl)[i])))
	s:=string$concat(s, "     ")
	s:=string$concat(s, value_t$unparse(pair$get_val(down(tbl)[i])))
	s:=string$concat(s, "\n")
	i:=i + 1
      end
    return(string$concat(s, "\n"))
  end unparse

getind=proc(tbl: p_table[key_t, value_t], key: key_t) returns(int)
    % effects:  returns the index of tbl in which the key is key
    
    i: int := array[pair]$low(down(tbl))
    top: int := array[pair]$high(down(tbl))
    while i <= top do
	if pair$get_key(down(tbl)[i]) = key
	  then return (i)
	  end
	i:=i+1
      end
    return(i)
  end getind

end p_table