fmultimap.sa


Generated by gen_html_sa_files from ICSI. Contact gomes@icsi.berkeley.edu for details
 
---------------------------> Sather 1.1 source file <--------------------------
-- fmultimap.sa: Map from K -> FLIST{T}
-- Author: Benedict A. Gomes <gomes@tiramisu.ICSI.Berkeley.EDU>
-- Copyright (C) 1995, International Computer Science Institute
-- $Id: fmultimap.sa,v 1.4 1996/04/09 10:04:58 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 FMULTIMAP{KTP,ETP} < $STR

class FMULTIMAP{KTP,ETP} < $STR is -- A mapping from elements of type K to lists of elements of type T -- Unlike FMAP, this class is NOT meant to be used when void -- and must be created initially. -- -- Implementation: Most of the primitive FMAP routines have been -- made private and renamed with a multi_ prefix. We do permit one -- operation that violates the interface, danger_multi_get which -- returns the actual flist associated with a particular key (not a -- copy of the flist). This list must *not* be modified and may -- well become invalid when other operations are performed upon the -- multi-map private include FMAP{KTP,FLIST{ETP}} target!-> private multi_target!, -- Called in filter pair!-> private multi_pair!, -- Called in double, halve, str pairs!->private pairs!, targets!->private targets!, keys!->private keys!, -- Obsolete insert->private multi_insert, -- Called by insert_pair insert_pair->private multi_insert_pair, create->private old_create, delete->private multi_delete, filter_not!->, filter!->, -- Unchanged private: key_eq, elt_nil,key_nil, is_key_nil, test -- get_pair, delete -- Publicly included copy->copy, get-> danger_multi_get, -- Public, but DANGEROUS. is_empty->is_empty, has_ind->has_ind, clear->clear, ind!->ind!, n_inds->n_inds, str->; private const initially_provide_for: INT := 1; private attr total_n_targets: INT; -- ------ Initialization/Duplication ------ create: SAME is -- Create must be called before use res ::= old_create(2); res.total_n_targets := 0; return res; end; copy: SAME is res ::= old_create(size); res.total_n_targets := 0; loop res := res.insert_pair(pair!) end; res.hsize := hsize; return res; end; -- ------ Insertion/Removal --------------- insert(k: KTP, t: ETP): SAME is -- Insert a new element "t" associated with "k" l: FLIST{ETP}; if has_ind(k) then l := danger_multi_get(k); else l := #; end; l := l.push(t); total_n_targets := total_n_targets+1; return multi_insert(k,l); end; insert_pair(p: TUP{KTP,ETP}): SAME is return insert(p.t1,p.t2); end; delete(k: KTP, t: ETP): SAME is -- Delete an element "t" from the elements associated with k -- Do nothing if the target does not exist for "k" l: FLIST{ETP}; if has_ind(k) then l := danger_multi_get(k); else l := #; end; if ~l.has(t) then -- Do nothing if the target does not exist return self end; l.delete_elt(t); total_n_targets := total_n_targets-1; if l.size = 0 then return multi_delete(k); else return multi_insert(k,l); end; end; delete_all(k: KTP): SAME is -- Delete all elements associated with element "k" if has_ind(k) then return multi_delete(k); end; end; -- ------ Access/Measurement -------------- get_all(k: KTP): FLIST{ETP} is -- Return a copy of internal list associated with element "k" if has_ind(k) then return danger_multi_get(k).copy; else return #FLIST{ETP} end; end; n_targets: INT is return total_n_targets end; -- Return the total number of targets n_targets(k: KTP): INT is -- Return the number of targets for the key "k" if has_ind(k) then return danger_multi_get(k).size else return 0 end; end; size: INT is return n_targets end; -- Alias for n_targets to satisfy "CONTAINER{KTP}" -- ------ Queries/Comparison -------------- equals(b: $RO_MULTIMAP{KTP,ETP}): BOOL is -- Returns true if all of "e"'s elements are equal to self's elts -- Ordering is an issue. Should be redefined to be more -- precise for particular descendants if n_inds /= b.n_inds then return false end; if size /= b.size then return false end; loop e ::= ind!; if n_targets(e) /= b.n_targets(e) then return false end; end; return true ; end; has_pair(k:KTP,t:ETP): BOOL is if has_ind(k) then return danger_multi_get(k).has(t) else return false end; end; -- ------ Cursor -------------------------- pair!: TUP{KTP, ETP} is -- Yields pairs of keys and elements - keys may repeat loop p: TUP{KTP,FLIST{ETP}} := multi_pair!; loop yield #TUP{KTP,ETP}(p.t1,p.t2.elt!); end; end; end; elt!: ETP is loop yield target!; end; end; target!: ETP is -- Return all the targets in the current multi-map loop t: FLIST{ETP} := multi_target!; loop yield t.elt! end; end; end; target!(once k: KTP): ETP is -- Return the elements associated with k l: FLIST{ETP}; if has_ind(k) then l := danger_multi_get(k); else l := #; end; loop yield l.elt! end; end; -- ------ Conversion ---------------------- str: STR is -- Prints out a string version of the array of the components -- that are under $STR, and their associated indices res ::= #FSTR("{"); loop p ::= pair!; key ::= p.t1; elt ::= p.t2; res := res+",".separate!("["+ind_str(key)+"]="+elt_str(elt)); end; res := res +"}"; return(res.str); end; -- ------ Private Implementation --------------- private ind_str(i: KTP): STR is typecase i when $STR then return i.str else return "Unprintable Index" end; end; private elt_str(e: ETP): STR is typecase e when $STR then return e.str else return "Unprintable Element" end; end; private multi_insert_pair(p:TUP{KTP,FLIST{ETP}}):SAME is return multi_insert(p.t1,p.t2) end; private halve_size:SAME -- A new table of half the size of self with self's entries -- copied over. pre ~void(self) and hsize<(asize-1)/4 is ns::=(asize-1)/2+1; r::=allocate(ns); loop r:=r.multi_insert_pair(multi_pair!) end; r.total_n_targets := total_n_targets; SYS::destroy(self); -- The old one should never be used now. return r end; private double_size:SAME -- A new table of twice the size of self with self's entries -- copied over. pre ~void(self) is ns::=(asize-1)*2+1; r::=allocate(ns); loop r:=r.multi_insert_pair(multi_pair!) end; r.total_n_targets := total_n_targets; SYS::destroy(self); -- The old one should never be used now. return r end; end; -- class FMULTIMAP{KTP,ETP}