set_views.sa

 
---------------------------> Sather 1.1 source file <--------------------------
-- Author: Benedict A. Gomes <gomes@samosa.ICSI.Berkeley.EDU>
-- Copyright (C) 1995, International Computer Science Institute
-- $Id: set_views.sa,v 1.5 1996/04/09 10:05:28 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.
-- -------------------------------------------------------------------
-- 
--  Views of Sets
--  -------------
-- Several of the set operations return a "view" of the result
-- instead of actually computing it.
-- A view behaves just like any read-only set. However, it operates 
-- by having pointers into the original sets, and hence will change 
-- whenever the original sets change.  
-- This creates a new set a_union_b, which has the actual elements of
-- a and b.
-- Views are defined by the classes BINOP_SET_VIEW and FILTER_SET_VIEW
-- 
-- The conventional set operations such as union and intersection
-- are provided for convenience, but can be easily and more flexibly 
-- achieved (with control over exactly what type of set is created) 
-- using set views:
--   a_union_b ::=  #SET{E}(a.union_view(b);
--  
-- Design notes on views:
--       class MY_SET_VIEW{T} < $SET{T} is
--            -- A particular implementation must define the following
--            -- routines. See SET_INCL
--            include SET_INCL{T};
--            private create_from_internal(s: $ELT{T}): $SET{T} is 
--                  ... ability to create a new set of the same type
--            copy: SAME is ...
--            has(e: E): BOOL is ...
--            size: INT is ...
--            elt!: E is ...
--            insert(e: E);
--            delete(e: E);
--            clear;
--       end;
--  + Low space
--  + Very fast to create - computations are performed at a query
--  + Sometimes the operation need not be even computed
--    (e.g. a.union_view(b).is_empty can return a result as long
--          as there is a single element in either a or b without computing
--          the union at all)
--  + All the set operations may be performed on the result, including
--   getting further views of the result.
--  ? Different semantics
--  - Slightly slower access (extra indirection that might be inlined
--                            away once SAME works properly).
--  - Much slower if set is going to be used repeatedly - instead,
--    convert into a standard set by  #SET{E}(a.union_view(b))


class FILTER_SET_VIEW{ETP} < $RO_SET{ETP} 
class FILTER_SET_VIEW{ETP} < $RO_SET{ETP} is
   include RO_SET_INCL{ETP};
   
   private attr pred: ROUT{ETP}:BOOL;
   private attr source: $RO_SET{ETP};
   
   create(s: $RO_SET{ETP}, predicate: ROUT{ETP}:BOOL): SAME  pre ~void(s) is
      res ::= new;
      res.pred := predicate;
      res.source := s;
      return res;
   end;
   
   copy: SAME is return create(source,pred) end;
   -- Copy returns a copy of the same type of set
   
   has(e: ETP): BOOL is
      if source.has(e) then return pred.call(e)  else return false; end;
   end;
   
   elt!: ETP is
      loop e ::= source.elt!; if pred.call(e) then yield e end; end;
   end;
	
end;