h_set.sa


Generated by gen_html_sa_files from ICSI. Contact gomes@icsi.berkeley.edu for details
 
---------------------------> Sather 1.1 source file <--------------------------
-- Author: Benedict A. Gomes <gomes@samosa.ICSI.Berkeley.EDU>
--    Much of the implementation was written by Holger
-- Copyright (C) 1995, International Computer Science Institute
-- $Id: h_set.sa,v 1.6 1996/04/09 10:05:06 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 SET{E} < $SET{E} is include H_SET{E}; end;

class H_SET{E} < $SET{E}

class H_SET{E} < $SET{E} is -- Implementation of sets using dynamic hash tables. -- This implementation is also available of dealing with equal but -- not same objects. include SET_INCL{E} create->,size->; private include DYNAMIC_BUCKET_TABLE{E,BUCKET{E}} map_copy->copy, create->create; create_from(a: ARRAY{E}): SAME is return create(a); end; create(e: $ELT{E}): SAME is res ::= create; loop res.insert(e.elt!) end; return res; end; size: INT is return n_inds end; -- ------ Insertion/Removal --------------- insert(e:E) pre ~void(self) is h ::= hash(e); loop if elt_key_eq(bucket(h).list!.item,e) then return end; end; set_bucket( h, #BUCKET{E}(e,bucket(h)) ); n_inds := n_inds + 1; update_insert end; delete(e: E) is discard ::= delete(e) end; clear is -- Extremely inefficient. Must be rewritten by someone who has -- looked at the implementation (delete(elt!) may have problems) -- Creates a separate list of elements to delete to separte out -- iteration from modification elts: ARRAY{E} := #(n_inds); loop elts.set!(elt!) end; loop delete(elts.elt!) end; end; -- The next routines deal with the problem of elements -- being equal but not same. delete(e:E): E pre ~void(self) is -- Removes an element from the set. Returns the deleted element. -- Returns void (or E::nil if E inherits $NIL{E}) if there is -- no element to delete. h ::= hash(e); b ::= bucket(h); prev ::= b; prev := void; -- NASTY HACK loop until!( void(b) or elt_key_eq(b.item,e) ); prev := b; b := b.next end; if void(b) then return void end; res ::= b.item; if void(prev) then set_bucket( h, b.next ) else prev.next(b.next) end; n_inds := n_inds - 1; update_delete; return res end; insert_replace(e:E) pre ~void(self) is -- Inserts e into the set. If there is already an -- element equal to e in the set, the old element -- will be replaced. dummy ::= insert_replace(e) end; insert_replace(e:E): E pre ~void(self) is -- Does the same like insert_replace but returns -- the old element which is being replaced or the -- same object if there was no old one. old: E; h ::= hash(e); firstb ::= bucket(h); loop b ::= firstb.list!; old := b.item; if elt_key_eq(old,e) then b.item(e); return old end end; set_bucket(h,#BUCKET{E}(e,firstb)); n_inds := n_inds + 1; update_insert; return e end; -- ------ Access/Measurement -------------- has(e:E): BOOL pre ~void(self) is loop if elt_key_eq(bucket(hash(e)).list!.item,e) then return true end; end; return false; end; get(e:E): E pre ~void(self) is -- Returns the element equal to 'e' from the set. -- Returns void or E::nil if there is no such element. -- Self may not be void. loop i ::= bucket(hash(e)).list!.item; if elt_key_eq(i,e) then return i end end; return elt_key_nil end; union(s: $RO_SET{E}): SAME is res ::= copy; loop res.insert(s.elt!) end; return res; end; intersection(s:$RO_SET{E}): SAME is res ::= #SAME; loop e ::= elt!; if s.has(e) then res.insert(e) end; end; return res; end; diff(s: $RO_SET{E}): SAME is res ::= #SAME; loop e ::= elt!; if ~s.has(e) then res.insert(e) end; end; return res; end; sym_diff(s: $RO_SET{E}): SAME is res ::= #SAME; loop e ::= elt!; if ~s.has(e) then res.insert(e) end; end; loop e ::= s.elt!; if ~has(e) then res.insert(e) end; end; return res; end; -------- Iterators -------------------------- elt!: E pre ~void(self) is loop b ::= bucket( 0.upto!(bound+split_pos-1) ); loop yield b.list!.item; end end end; end; -- H_SET{E}