-- filename hashtabl.adb 7:21AM  9/15/95
-- This is the body of package Hashtable.

with text_io, int_io;
package body HashTable is

  MTbucket: constant Bucket := Empty;

  procedure Clear(T: in out Table) is
  begin
     T:= new Tabarray'(others => MTBucket);
  end Clear;

-- Find is a utility to locate a binding (if it exists) in a table, 
-- or find where a binding should go (if it isn't there)
-- if it is there, on return, Current is pointing at its entry.
-- if it is not there, Current is MTBucket. Previous (if not empty)
-- is pointing at the node it should be inserted after, if Previous
-- is MTBucket, then it should be inserted as the first entry in
-- T(B)
  procedure Find(S: in Key; T: in Table;
                 B: in out Positive;
                 Current : in out Bucket;
                 Previous : in out Bucket) is
  begin
     Previous := MTBucket;
     B := (Hash(S) mod NumberOfBuckets) + 1;
     Current := T(B);
     while Current /= MTBucket
       loop
          if first(Current).Index = S
          then return;
          else Previous := Current;
               Current := rest(Current);
          end if;
       end loop;
  end Find;

  procedure AddEntry(S: in Key; V: in Contents; T: in out Table) is
     B : Positive;
     Previous : Bucket;
     Current : Bucket;
  begin
     Find(S, T, B, Current, Previous);
     if Current /= MTBucket
     then raise multiple_binding;
     else T(B) := cons((S,V), T(B)); -- always adds at front
     end if;
  exception
     when Storage_error => raise Table_overflow;
  end AddEntry;

  procedure ChangeEntry(S:in Key; V: in Contents; T:in out Table) is
     B : Positive;
     Previous : Bucket;
     Current : Bucket;
  begin
     Find(S, T, B, Current, Previous);
     if Current /= MTBucket
     then setfirst(Current, (S,V));
     else raise entry_not_found;
     end if;
  end ChangeEntry;

  function Retrieve(S:in Key; T:in Table) return Contents is
     B : Positive;
     Previous : Bucket;
     Current : Bucket;
  begin
     Find(S, T, B, Current, Previous);
     if Current /= MTBucket
     then return first(Current).Value;
     else raise entry_not_found;
     end if;
   end Retrieve;
     

  function IsBound(S: in Key; T:in Table) return Boolean is
     B : Positive;
     Previous : Bucket;
     Current : Bucket;
  begin
     Find(S, T, B, Current, Previous);
     return (Current /= MTBucket);
  end IsBound;

  function IsEmpty(T: in Table) return Boolean is
  begin
     return (T.all = Tabarray'(others=>MTBucket));
  end;

  function Size(T: in Table) return Natural is
     Count:Natural := 0;
     Temp : Bucket;
  begin
     for B in T'Range
       loop
          Temp := T(B);
          while Temp /= MTBucket
            loop
               Count := Count + 1;
               Temp := rest(Temp);
            end loop;
       end loop;
     return Count;
  end Size;

  procedure Put(B: in Binding) is
  begin
     text_io.put("key ");
     putkey(B.index);
     text_io.put(" is bound to ");
     putcontents(B.value);
  end Put;
     
  procedure put(T:in Table) is
     ptr : Bucket;
  begin
     for I in Tabarray'range
       loop
          ptr := T(I);
	  text_io.put("Bucket ");
	  int_io.put(I);
	  text_io.put_line(" has:");
          while ptr /= MTBucket
            loop
	       Put(first(ptr));
               text_io.new_line;
               ptr := rest(ptr);
            end loop;
       end loop;
  end put;


end HashTable;