------------------------->  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>  <--------------

-- Set include partial classes
-- Author: Benedict A. Gomes <gomes@samosa.ICSI.Berkeley.EDU>

partial class RO_SET_INCL{ETP}<$RO_SET{ETP}
-- Partial class that for the read only set abstraction, class
-- $RO_SET{ETP}.  For more information on the relationship between
-- the abstract classes, partial classes and actual implementations
-- please see the class comment class in the abstraction.
-- 
-- This partial class implements some of the operations required by
-- the abstraction in terms of a set of core functions which are
-- stubs in this partial class. These stubs must be replaced by
-- real function in any descendant that actually implements the
-- abstraction. Particular implementations may replace also some of
-- the non-stub operations by substantially more efficient
-- versions, that make use of properties of the actual
-- implementation.
-- 
is
   include COMPARE{ETP};
   
   -- 
   -- Stubs
   -- 
   stub size:INT;

   stub insert(e:ETP):SAME;

   stub delete(e:ETP):SAME;

   stub has(e:ETP):BOOL;
   
   stub copy:SAME;

   stub elt!: ETP;
   
   stub create:SAME;
   
   create(arg:$ELT{ETP}):SAME is
      -- Create a new bag out of the elements of 'arg'
      res: SAME := #;
      loop res := res.insert(arg.elt!) end;
      return res;
   end;

   create(arg:ARRAY{ETP}):SAME is
      -- Create a new bag from the elements of the array 'arg'
      -- The reason for having a separate routine in this case is to
      -- permit type inference to be used so that a user may write
      --    a:BAG{INT} := #(|1,2,3|);
      res: SAME := #;
      loop res := res.insert(arg.elt!) end;
      return res;
   end; 
   
   add(e:ETP):VBAG{ETP} is
      -- Result is a new bag containing all the elements of self and 'e'
      -- From $RO_BAG
      res ::= #VBAG{ETP}(self);
      return res.add(e);
   end;
      
   delete_all(e:ETP):SAME is  return delete(e); end;
   -- Result is a new set containing all the elements of self except for
   -- any elements equal to 'e'
   -- Redefined from $RO_BAG to change the return type from $RO_BAG to $RO_SET
   
   count(e:ETP):INT is if has(e) then return 1 else return 0 end; end;
   
   unique!:ETP is 
      -- Yield the elements of 'self'
      loop yield elt!; end;
   end;
   
   n_unique:INT is return size; end;
   -- Return teh number of elements in self
   
   is_subset_of(arg:$RO_BAG{ETP}):BOOL is
      -- Returns true if 'self' is a subset of 'arg'. For elements that occur
      -- multiple times, the number of occurences of the element in 'arg'
      -- must be greater than or equal to the number of occurences in self
      -- 
      -- result=true iff for all e in self: arg.has(e)
      loop e ::= elt!;
	 if ~arg.has(e) then return false; end;
      end;
      return true;
   end;
   
   concat(arg:$ELT{ETP}):VBAG{ETP} is
      -- Returns a bag containing all the elements of self and 'arg'.
      -- For elements that occur multiple times, the result contains
      -- the sum of the number of occurences in self and 'arg'
      -- 
      -- result=bag of all e s.t. result.count(e)=self.count(e)+arg.count(e)>0 
      res ::= #VBAG{ETP}(self);
      loop e ::= arg.elt!;
	 res := res.add(e);
      end;
      return res;
   end;
   
   union(arg: $RO_BAG{ETP}):VBAG{ETP} is
      -- Returns a bag containing the elements of 'self' and 'arg'. 
      -- For elements that occur multiple times, the result contains
      -- the maximum number of occurences in either self or 'arg'
      -- This definition permits the union of sets to be consistent
      -- with the union of bags.
      -- 
      -- result=bag of all e s.t. 
      --             result.count(e)= max(self.count(e),arg.count(e)) > 0
      res ::= #VBAG{ETP}(self);
      loop arg_elt:ETP := arg.elt!;
	 if ~res.has(arg_elt) then res := res.add(arg_elt);
	 else
	    if arg.count(arg_elt) > res.count(arg_elt) then
	       res := res.add(arg_elt);
	    end;
	 end;
      end;
      return res
   end;
   
   union(arg: $RO_SET{ETP}):SAME is
      -- Returns a set  containing all elements in 'self' or 'arg'. 
      -- Overloads the function in $RO_BAG which has an argument and
      -- return value of $RO_BAG
      -- 
      -- result=set of all e s.t. self.has(e) or arg.has(e)
      res ::= copy;
      loop res := res.insert(arg.elt!); end;
      return res;
   end;

   intersection(arg: $RO_BAG{ETP}):VBAG{ETP} is
      -- Returns a bag containing the elements common to self and 'arg'
      -- For elements that occur multiple times, the result contains
      -- the minimum number of occurrences in either self or 'arg'
      -- 
      -- result=bag of all e s.t. 
      --              result.count(e)=min(self.count(e),arg.count(e)) > 0 
      res ::= #VBAG{ETP}(self);
      loop
	 e ::= unique!;
	 num_to_delete: INT := (count(e) - arg.count(e));
	 if num_to_delete > 0 then
	    loop num_to_delete.times!;  res := res.delete(e); end;
	 end;
      end;
      return res
   end;

   intersection(arg: $RO_SET{ETP}):SAME is
      -- Returns a set containing the elements of 'self' and in 'arg'
      -- Overloads the function in $RO_BAG which has an argument and
      -- return value of $RO_BAG
      -- 
      -- result=set of all e s.t. self.has(e) and arg.has(e)
      res ::= copy;
      loop e ::= elt!; 
	 if ~arg.has(e) then res := res.delete(e) end;
      end;
      return res;
   end;
   
   diff(arg: $RO_SET{ETP}):SAME is
      -- Returns a set containing the elements of 'self' not in 'arg'
      -- 
      -- result=set of all e s.t. self.has(e) and ~arg.has(e)
      res ::= copy;
      loop a ::= arg.elt!; 
	 if has(a) then res := res.delete(a); end;
      end;
      return res;
   end;

   sym_diff(arg: $RO_SET{ETP}): SAME is
      -- Returns a set containing the elements of 'self' and not in 'arg'
      -- or  in 'arg' but not in self
      -- 
      -- result=set of all e s.t. self.has(e) xor arg.has(e)
      res ::= copy;
      loop a ::= arg.elt!;
	 if has(a) then res := res.delete(a); else res := res.insert(a); end;
      end;
      return res;
   end;

   is_empty:BOOL is 
      -- Return true if the size = 0. 
      return size=0
   end;
   
   equals(c:$RO_BAG{ETP}):BOOL is
      -- Return true if self contains all the elements of 'c' and vice
      -- versa. 
      if size /= c.size then return false end;
      loop ce ::= c.elt!; 
	 if ~has(ce) then return false end; 
      end;
      return true;
   end;
   
   as_array:ARRAY{ETP} is
      -- Return the elements of the container as an array
      res ::= #ARRAY{ETP}(size);
      loop res.set!(elt!) end;
      return res;
   end;
   
   str: STR is return ELT_ALG{ETP}::str(self); end;
   -- Return a string representation of self 
   
end;
-------------------------------------------------------------------
partial class SET_INCL{ETP} is
   -- Partial class for the set abstraction, class $SET{ETP}.
   -- For more information on the relationship between the abstract
   -- classes, partial classes and actual implementations please see
   -- the class comment class in the abstraction.
   -- 
   -- This partial class implements some of the operations required by
   -- the abstraction in terms of a set of core functions which are
   -- stubs in this partial class. These stubs must be replaced by
   -- real function in any descendant that actually implements the
   -- abstraction. Particular implementations may replace also some of
   -- the non-stub operations by substantially more efficient
   -- versions, that make use of properties of the actual
   -- implementation.
   include RO_SET_INCL{ETP};

   stub size:INT;
   
   stub insert(e:ETP); 
   -- Insert element "e" into the set
   
   stub delete(e:ETP);
   -- Delete element "e" from the set

   stub has(e:ETP):BOOL;
   
   stub copy:SAME;
   
   stub elt!: ETP;
   
   -- 
   -- Methods not required by the $SET abstraction
   -- 
   stub create:SAME;
   
   create(arg:$ELT{ETP}):SAME is
      -- Create a new bag out of the elements of 'arg'
      res: SAME := #;
      loop res.insert(arg.elt!) end;
      return res;
   end;

   create(arg:ARRAY{ETP}):SAME is
      -- Create a new bag from the elements of the array 'arg'
      -- The reason for having a separate routine in this case is to
      -- permit type inference to be used so that a user may write
      --    a:BAG{INT} := #(|1,2,3|);
      res: SAME := #;
      loop res.insert(arg.elt!) end;
      return res;
   end; 
      
   -- 
   -- Methods required by the $SET abstraction
   -- 
   as_value:VSET{ETP} is return #VSET{ETP}(self) end;
   -- Return the value associated with this reference to a set
   
   clear post size = 0 is
      -- Delete all elements of self
      -- Expensive! To make sure that we don't overwrite while
      -- reading, use a seperate array. Implementations should
      -- redefine for better efficiency
	 f:ARRAY{ETP} := #(size);
      loop f.set!(elt!); end;
      loop delete_all(f.elt!); end;
   end;

   --              ------ Basic Operations ----------------
   -- Versions that modify self, special cased when the arg is SAME
   -- for efficiency
   to_union(arg:$ELT{ETP}) pre ~void(self) and ~void(arg) is
      -- Convert this set into the union of self and 'arg'
      -- 
      -- self <- initial(self).union(arg)
      loop e ::= arg.elt!; if ~has(e) then insert(e) end; end;
   end;

   to_diff(arg: $RO_SET{ETP}) pre ~void(self) and ~void(arg) is
      -- Convert this set into the diff of self and 'arg'
      -- 
      -- self <- initial(self).diff(arg)
      loop e ::= arg.elt!; if has(e) then delete(e) end; end;
   end;

   to_sym_diff(arg: $RO_SET{ETP}) pre ~void(self) and ~void(arg) is
      -- Convert this set into the diff of self and 'arg'
      -- 
      -- self <- initial(self).sym_diff(arg)
      loop e ::= arg.elt!; if has(e) then delete(e) else insert(e) end; end;
   end;

   to_intersection(arg: $RO_SET{ETP}) pre ~void(self) and ~void(arg) is
      -- Convert this set into the intersection of self and 'arg'
      -- 
      -- self <- initial(self).intersection(arg)
      loop e ::= elt!; if ~arg.has(e) then delete(e) end; end;
   end;

   insert(e:ETP):SAME is
      res ::= copy;    res.insert(e);     return res;
   end;
   
   delete(e:ETP):SAME is
      res ::= copy;  res.delete(e); return res;
   end;

end; -- SET_INCL{ETP}
-------------------------------------------------------------------
