h_multimap.sa

 
---------------------------> Sather 1.1 source file <--------------------------
-- h_multimap.sa: Hash table based multimap
-- Author: Benedict A. Gomes <gomes@samosa.ICSI.Berkeley.EDU>
-- Copyright (C) 1995, International Computer Science Institute
-- $Id: h_multimap.sa,v 1.3 1996/04/09 10:05:05 borisv Exp $
--
-- COPYRIGHT NOTICE: This code is provided WITHOUT ANY WARRANTY
-- and is subject to the terms of the SATHER LIBRARY GENERAL PUBLIC
-- LICENSE contained in the file: Sather/Doc/License of the
-- Sather distribution. The license is also available from ICSI,
-- 1947 Center St., Suite 600, Berkeley CA 94704, USA.



class H_MULTIMAP{K,E} < $MULTIMAP{K,E} 
class H_MULTIMAP{K,E} < $MULTIMAP{K,E} is
   -- Multimap based on the DYNAMIC_DATABUCKET_TABLE
   
   private include DYNAMIC_DATABUCKET_TABLE{K,H_BAG{E}} 
	 map_key!->ind!,n_inds->n_inds,create->create;		
   -- make public
   include MULTIMAP_INCL{K,E} elt!->,size->,ind!->,pair!->,
	 n_targets->,n_inds->;
   
   readonly attr total_size: INT;

   size: INT is return total_size end;
   
   copy: SAME
      pre ~void(self)
   is
      res ::= map_copy;
      res.total_size := total_size;
      return res
   end;

   aset(k:K,e:E)
      pre ~void(self)
   is
      h ::= hash(k);
      loop
	 b ::= bucket(h).list!;
	 if elt_key_eq(b.item,k) then
	    ssize ::= b.data.size;
	    b.data.insert(e);
	    if ssize < b.data.size then
	       total_size := total_size + 1
	    end;
	    return
	 end
      end;
      newset ::= #H_BAG{E};
      newset.insert(e);
      set_bucket(h,#DATABUCKET{K,H_BAG{E}}(k,newset,bucket(h)));
      total_size := total_size + 1;
      n_inds := n_inds + 1;
      update_insert
   end;

   n_targets(k:K): INT
      pre ~void(self)
   is 
      loop
	 b ::= bucket(hash(k)).list!;
	 if elt_key_eq(k,b.item) then
	    return b.data.size
	 end
      end;
      return 0
   end;

   has_ind(k:K): BOOL
   -- Return true if the multi-map (dictionary) has the index "k"
      pre ~void(self)
   is
      return n_targets(k) > 0
   end;

   has(k:K,e:E): BOOL
      pre ~void(self)
   is
      loop
	 b ::= bucket(hash(k)).list!;
	 if elt_key_eq(k,b.item) then
	    return b.data.has(e)
	 end
      end;
      return false
   end;

   delete(k:K,e:E)
   -- Delete a single occurence of the key value pair(k,e)
      pre ~void(self)
   is
      h: INT;
      b,prev: DATABUCKET{K,H_BAG{E}};

      h := hash(k);
      b := bucket(h);
      loop until!( void(b) );
	 if elt_key_eq(b.item,k) then
	    if b.data.has(e) then
	       total_size := total_size - 1;
	       if b.data.size > 1 then
		  b.data.delete(e)
	       else
		  if void(prev) then   set_bucket(h,b.next)
		  else  prev.next(b.next) end;
		  n_inds := n_inds - 1;
		  update_delete
	       end
	    end;
	    return
	 end;
	 prev := b;
	 b := b.next
      end
   end;

   delete(k:K)
   -- Delete all elements associated with element "k"
      pre ~void(self)
   is
      dummy ::= map_delete(k);
      total_size := total_size - dummy.size
   end;

   target!(once k:K): E
   -- Return the values associated with "k"
      pre ~void(self)
   is
      loop
	 b ::= bucket(hash(k)).list!;
	 if elt_key_eq(k,b.item) then
	    loop yield b.data.elt! end;
	    quit
	 end
      end
   end;

   elt!: E
      pre ~void(self)
   is
      loop
	 b ::= bucket( 0.upto!(asize-1) );
	 loop
	    bk ::= b.list!;
	    loop yield bk.data.elt! end;
	 end
      end
   end;

   pair!: TUP{K,E}
      pre ~void(self)
   is
      loop
	 b ::= bucket( 0.upto!(asize-1) );
	 loop
	    bk ::= b.list!;
	    loop yield #(b.item,bk.data.elt!) end;
	 end;
      end;
   end;

end; -- H_MULTIMAP