------------------------->  GNU Sather - sourcefile  <-------------------------
-- Copyright (C) 1995 by International Computer Science Institute            --
-- This file is part of the GNU Sather library. It is free software; you may --
-- redistribute  and/or modify it under the terms of the GNU Library General --
-- Public  License (LGPL)  as published  by the  Free  Software  Foundation; --
-- either version 2 of the license, or (at your option) any later version.   --
-- This  library  is distributed  in the  hope that it will  be  useful, but --
-- WITHOUT ANY WARRANTY without even the implied warranty of MERCHANTABILITY --
-- or FITNESS FOR A PARTICULAR PURPOSE. See Doc/LGPL for more details.       --
-- The license text is also available from:  Free Software Foundation, Inc., --
-- 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA                     --
-------------->  Please email comments to <bug-sather@gnu.org>  <--------------

-- h_map.sa: Hash table based map class
-- Author: Benedict A. Gomes <gomes@samosa.ICSI.Berkeley.EDU>

class MAP{ITP,TTP} < $MAP{ITP,TTP} is
   -- Map implementation based on a hash table. 
   -- 
   -- Usage:
   --   m ::= #MAP{INT,STR};
   --   m[3] := "foo";
   --   m[4] := "bar";
   --   loop #OUT+b.elt!; end;     
   --   
   
   include H_MAP_IMPL{ITP,TTP}; 
   include MAP_INCL{ITP,TTP};
   

end; -- MAP{ITP,TTP}
-------------------------------------------------------------------
class VMAP{ITP,TTP} < $VMAP{ITP,TTP} is
   -- Hash table based on data buckets
   include H_MAP_IMPL{ITP,TTP}
	 delete->private delete,
	 aset->private aset;
   include MAP_INCL{ITP,TTP};

   is_eq(a:$OB):BOOL is
      -- Return true if 'self' and 'v' have the same value
      typecase a
      when $RO_BAG{TUP{ITP,TTP}} then 
	 if size /= a.size then return false; end;
	 loop e:TUP{ITP,TTP} := a.unique!;
	    if count(e)/=a.count(e) then return false; end;
	 end;
	 return true;
      else return false end;
   end;

   hash:INT is
      res:INT := 0; loop e ::= elt!; res := res.bxor(elt_hash(e)); end;
      return res;
   end;

end; -- VMAP{ITP,TTP}
-------------------------------------------------------------------
class H_MAP_IMPL{ITP,TTP} is
   -- Hash table based on data buckets
   private include DYNAMIC_DATABUCKET_TABLE{ITP,TTP} 
   -- Make public
	 create->create,
	 map_has_ind->has_ind, 
	 map_copy->copy,
	 map_pair!->elt!, 
	 map_key!->ind!, 
	 map_delete->map_delete,
	 map_aget->aget,
	 map_aset->aset;

   insert(e:TUP{ITP,TTP}):SAME is 
      res ::= copy; res.aset(e.t1,e.t2); return res;
   end;

   target!:TTP is
      loop i ::= ind!; yield aget(i); end;
   end;

   delete(e:TUP{ITP,TTP}) is delete(e.t1) end;
   
   delete(k:ITP) pre ~void(self) is  dummy ::= map_delete(k)  end;

   size: INT is return n_inds end;

   
end; 
-------------------------------------------------------------------
