------------------------->  GNU Sather - sourcefile  <-------------------------
-- Copyright (C) 1994 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>  <--------------

abstract class $RO_MULTIMAP{ITP,TTP} < $RO_BAG{TUP{ITP,TTP}}
-- An unordered container of tuples of {index:ITP,target:TTP}.  
-- It may be viewed as a mapping from indices of type ITP to
-- targets fo type TTP, where each index may have multiple targets
-- It is essentially a one-to-many mapping, that allows for
-- repetitions.  
-- 
-- Definition: A multimap is simply a bag of tuples. It imposes
-- no additional constraints, but does provide some extra accessing
-- mechanisms
-- 
-- This is a read-only abstraction in which no modifying operations
-- are available. However, subtypes may provide modifying operations
-- For documentation see:
--    The overall organization of container classes
--    The organization and usage of multimaps and related classes
-- 
-- In the comments that follow, underscores are used to indicate 
-- a value that takes on all possible bindings.
is
   

   add(k:ITP,e:TTP):$RO_MULTIMAP{ITP,TTP};
   -- Shortcut for for add(#TUP{ITP,TTP}(k,e))
   
   delete(k:ITP,e:TTP):$RO_MULTIMAP{ITP,TTP};
   -- Shortcut for for delete(e:TUP{ITP,TTP})
   
   delete_ind(k:ITP):$RO_MULTIMAP{ITP,TTP};
   -- Returns a new multimap in which all occurences of the tuple
   -- (k,_) have been deleted
   
   has_ind(k:ITP): BOOL;
   -- Returns true if this map has an index equal to 'k'
   -- 
   -- return true iff self contains a tuple (k,_)
   
   n_targets(k:ITP): INT;
   -- Returns the number of targets associated with the index 'k'
   
   n_ind:INT;
   -- Return the number of unique indices in 'self'
   -- 
   -- return size of  {i s.t. self.has((i,_))}
   
   ind!:ITP;
   -- Yields all the indices of self i.e. first elements of every
   -- tuple in self - but without repetitions, in an unspecified order
   -- 
   -- yield all i s.t. self.has((i,_))
   
   target!(once k:ITP):TTP;
   -- Yields all the target associated with index 'k'
   -- 
   -- yield all t s.t. self.has((k,t))
   
   pair!: TUP{ITP,TTP};
   -- Yields all elements of self in an unspecified order. An alias for
   -- "elt!"

   add(e:TUP{ITP,TTP}):$RO_MULTIMAP{ITP,TTP};
   -- Result is a new multimap containing all the elements of self and 'e'

   delete(e:TUP{ITP,TTP}):$RO_MULTIMAP{ITP,TTP};
   -- Result is a new multimap containing all the elements of self except for
   -- an element equal to 'e', if one exists. If more than one element
   -- is equal to 'e', delete only one of them
   
   delete_all(e:TUP{ITP,TTP}):$RO_MULTIMAP{ITP,TTP};
   -- Result is a new multimap ontaining all the elements of self except for
   -- any elements equal to 'e'

   count(e:TUP{ITP,TTP}):INT;
   -- Return the number of occurences of 'e' in self
   
   unique!:TUP{ITP,TTP};
   -- Yield the unique elements of self. Equivalent to self.as_set.elt!
   
   n_unique: INT;
   -- Returns the number of unique elements in the bag 

   is_subset_of(arg: $RO_BAG{TUP{ITP,TTP}}): BOOL;
   -- 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
   -- 
   -- return true iff for all e in self: count(e) <= arg.count(e)

   concat(arg:$ELT{TUP{ITP,TTP}}):$RO_MULTIMAP{ITP,TTP};
   -- Returns a multimap 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=mmap of all e s.t. result.count(e)=self.count(e)+arg.count(e)
   
   union(arg: $RO_BAG{TUP{ITP,TTP}}): $RO_MULTIMAP{ITP,TTP};
   -- Returns a multimap 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'
   -- 
   -- result=mmap of all e s.t. result.count(e)=max(self.count(e),arg.count(e))
   
   intersection(arg: $RO_BAG{TUP{ITP,TTP}}):$RO_MULTIMAP{ITP,TTP};
   -- Returns a multimap  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=mmap of all e s.t. result.count(e)=min(self.count(e),arg.count(e))
   
   is_empty:BOOL;
   -- Returns true if the size of the container = 0

   size: INT;
   -- Number of elements contained
   
   copy: SAME;
    -- Return a copy of the current container

   has(e: TUP{ITP,TTP}): BOOL;
   -- True if the container contains the element "e"
   
   equals(c:$RO_BAG{TUP{ITP,TTP}}):BOOL;
   -- Return true if both containers contain the same elements with
   -- the same number of repetitions, irrespective of the order of the
   -- elements
   
   as_array:ARRAY{TUP{ITP,TTP}};
   -- Return the elements of the container in an array

   elt!:TUP{ITP,TTP};
   -- Yield all the elements of self. The order is not defined.
   
   str:STR;
   -- Yield a string version of self

end;
--------------------------------------------------------------------------
abstract class $VMULTIMAP{ITP,TTP}<$RO_MULTIMAP{ITP,TTP},$VBAG{TUP{ITP,TTP}} 
-- An unordered container of tuples of {index:ITP,target:TTP} such
-- that the indices of all tuples are unique. Indices may be used
-- to retrieve targets
-- 
-- IMPORTANT: This is a value abstraction and is stricter than the
-- read-only abstraction. Subtypes must not support *any*
-- operations that modify self. The language cannot enforce this
-- restriction. 
-- 
-- For pointers to other documentation please see the class comment in
-- the read-only abstraction
is

   add(k:ITP,e:TTP):$VMULTIMAP{ITP,TTP};
   -- Shortcut for for add(#TUP{ITP,TTP}(k,e))
   
   delete(k:ITP,e:TTP):$VMULTIMAP{ITP,TTP};
   -- Shortcut for for delete(e:TUP{ITP,TTP})

   delete_ind(k:ITP):$VMULTIMAP{ITP,TTP};
   -- Returns a new multimap in which all occurences of the tuple
   -- (k,_) have been deleted

   has_ind(k:ITP): BOOL;
   -- Returns true if this map has an index equal to 'k'
   --    result is true iff self contains a tuple (k,_)
   
   n_targets(k:ITP): INT;
   -- Returns the number of targets associated with the index 'k'
   
   ind!:ITP;
   -- Yields all the indices of self i.e. first elements of every
   -- tuple in self without repetitions, in an unspecified order
   --    yield all i s.t. self.has((i,_))
   
   target!(once k:ITP):TTP;
   -- Yields all the target associated with index 'k'
   -- 
   -- yield all t s.t. self.has((k,t))

   pair!: TUP{ITP,TTP};
   -- Yields all elements of self in an unspecified order. An alias for
   -- "elt!"

   add(e:TUP{ITP,TTP}):$VMULTIMAP{ITP,TTP};
   -- Result is a new multimap containing all the elements of self and 'e'

   delete(e:TUP{ITP,TTP}):$VMULTIMAP{ITP,TTP};
   -- Result is a new multimap containing all the elements of self except for
   -- an element equal to 'e', if one exists. If more than one element
   -- is equal to 'e', delete only one of them
   
   delete_all(e:TUP{ITP,TTP}):$VMULTIMAP{ITP,TTP};
   -- Result is a new multimap containing all the elements of self except for
   -- all elements equal to 'e'
   
   count(e:TUP{ITP,TTP}):INT;
   -- Return the number of occurences of 'e' in self
   
   unique!:TUP{ITP,TTP};
   -- Yield the unique elements of self. Equivalent to self.as_set.elt!
   
   n_unique: INT;
   -- Returns the number of unique elements in the bag 
   -- 
   -- result = number of unique elements

   is_subset_of(arg: $RO_BAG{TUP{ITP,TTP}}): BOOL;
   -- 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: count(e) <= arg.count(e)

   concat(arg:$ELT{TUP{ITP,TTP}}):$VMULTIMAP{ITP,TTP};
   -- 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=mmap of all e s.t. result.count(e)=self.count(e)+arg.count(e)
   
   union(arg: $RO_BAG{TUP{ITP,TTP}}): $VMULTIMAP{ITP,TTP};
   -- Returns a multimap 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'
   -- 
   -- result=mmap of all e s.t. result.count(e)=max(self.count(e),arg.count(e))
   
   intersection(arg: $RO_BAG{TUP{ITP,TTP}}):$VMULTIMAP{ITP,TTP};
   -- Returns a multimap  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=mmap of all e s.t. result.count(e)=min(self.count(e),arg.count(e))
   
   is_empty:BOOL;
   -- Returns true if the size of the container = 0

   size: INT;
   -- Number of elements contained
   
   copy: SAME;
    -- Return a copy of the current container

   has(e: TUP{ITP,TTP}): BOOL;
   -- True if the container contains the element "e"
   
   equals(c:$RO_BAG{TUP{ITP,TTP}}):BOOL;
   -- Return true if both containers contain the same elements with
   -- the same number of repetitions, irrespective of the order of the
   -- elements
   
   as_array:ARRAY{TUP{ITP,TTP}};
   -- Return the elements of the container in an array

   elt!:TUP{ITP,TTP};
   -- Yield all the elements of self. The order is not defined.
   
   str:STR;
   -- Yield a string version of self
   
end;
--------------------------------------------------------------------------
abstract class $MULTIMAP{ITP,TTP}<$RO_MULTIMAP{ITP,TTP}, $VAR
-- An unordered container of tuples of {index:ITP,target:TTP}.  
-- It may be viewed as a mapping from indices of type ITP to
-- targets fo type TTP, where each index may have multiple targets
-- It is essentially a one-to-many mapping, that allows for
-- repetitions.  
-- 
-- This is a reference abstraction and supports operations that modify
-- self. Instances of subtypes may be viewed as variables with a value
-- of $VMULTIMAP{ITP,TTP}
-- 
-- For pointers to other documentation please see the class comment in
-- the read-only abstraction of $RO_MULTIMAP{ITP,TTP}
-- 
is

   as_value:$VMULTIMAP{ITP,TTP};
   -- Return the current value associated with self

   aset(k:ITP,e:TTP);
   -- Adds the tuple (k,e) to self, if it does not already exist
   -- self<-initial(self).insert({k,e})

   delete(k:ITP,e:TTP);
   -- Removes the tuple (k,e) from self if it exists
   -- self<-initial(self).delete({k,e})

   delete(k:ITP);
   -- Removes any  tuple (k,_) from self if it exists
   -- self<-initial(self).delete(k)

   clear;
   -- Delete all elements from the multimap
   
   to_union(arg: $RO_MULTIMAP{ITP,TTP});
   -- Turn this bag into the union of self and 'arg'
   -- self <- initial(self).union(arg)
   
   to_intersection(arg:$RO_MULTIMAP{ITP,TTP});
   -- Turn this bag into the intersection of self and 'arg'
   -- self <- initial(self).intersection(arg)
   
   add(k:ITP,e:TTP):$MULTIMAP{ITP,TTP};
   -- Shortcut for for add(#TUP{ITP,TTP}(k,e))
   
   delete(k:ITP,e:TTP):$MULTIMAP{ITP,TTP};
   -- Shortcut for for delete(e:TUP{ITP,TTP})

   delete_ind(k:ITP):$MULTIMAP{ITP,TTP};
   -- Returns a new multimap in which all occurences of the tuple
   -- (k,_) have been deleted
   
   has_ind(k:ITP): BOOL;
   -- Returns true if this map has an index equal to 'k'
   -- 
   -- result is true iff self contains a tuple (k,_)
   
   n_targets(k:ITP): INT;
   -- Returns the number of targets associated with the index 'k'
   -- 
   -- result is targets.as_set.size
   
   ind!:ITP;
   -- Yields all the indices of self i.e. first elements of every
   -- tuple in self without repetitions
   -- 
   -- yield all i s.t. self.has((i,_))
   
   target!(once k:ITP):TTP;
   -- Yields all the targets associated with index 'k', with repetitions
   -- 
   -- yield all t s.t. self.has((k,t))
   
   pair!: TUP{ITP,TTP};
   -- Yields all elements of self in an unspecified order. An alias for
   -- "elt!"
   
   add(e:TUP{ITP,TTP}):$MULTIMAP{ITP,TTP};
   -- Result is a new bag containing all the elements of self and 'e'

   delete(e:TUP{ITP,TTP}):$MULTIMAP{ITP,TTP};
   -- Result is a new multimap containing all the elements of self except for
   -- an element equal to 'e', if one exists. If more than one element
   -- is equal to 'e', delete only one of them
   
   delete_all(e:TUP{ITP,TTP}):$MULTIMAP{ITP,TTP};
   -- Result is a new multimap containing all the elements of self except for
   -- all elements equal to 'e'
   
   count(e:TUP{ITP,TTP}):INT;
   -- Return the number of occurences of 'e' in self
   
   unique!:TUP{ITP,TTP};
   -- Yield the unique elements of self. Equivalent to self.as_set.elt!
   
   n_unique: INT;
   -- Returns the number of unique elements in the bag 
   -- 
   -- result = number of unique elements
   
   is_subset_of(arg: $RO_BAG{TUP{ITP,TTP}}): BOOL;
   -- 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: count(e) <= arg.count(e)

   concat(arg:$RO_BAG{TUP{ITP,TTP}}):$MULTIMAP{ITP,TTP};
   -- Returns a multimap 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=mmap of all e s.t. result.count(e)=self.count(e)+arg.count(e)
   
   union(arg: $RO_BAG{TUP{ITP,TTP}}):$MULTIMAP{ITP,TTP};
   -- Returns a multimap 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'
   -- 
   -- result=map of all e s.t. result.count(e)=max(self.count(e),arg.count(e))
   
   intersection(arg: $RO_BAG{TUP{ITP,TTP}}):$MULTIMAP{ITP,TTP};
   -- 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=map of all e s.t. result.count(e)=min(self.count(e),arg.count(e))

   is_empty:BOOL;
   -- Returns true if the size of the container = 0

   size: INT;
   -- Number of elements contained
   
   copy: SAME;
    -- Return a copy of the current container

   has(e: TUP{ITP,TTP}): BOOL;
   -- True if the container contains the element "e"
   
   equals(c:$RO_BAG{TUP{ITP,TTP}}):BOOL;
   -- Return true if both containers contain the same elements with
   -- the same number of repetitions, irrespective of the order of the
   -- elements
   
   as_array:ARRAY{TUP{ITP,TTP}};
   -- Return the elements of the container in an array

   elt!:TUP{ITP,TTP};
   -- Yield all the elements of self. The order is not defined.
   
   str:STR;
   -- Yield a string version of self
   
end; -- $MULTIMAP{ITP,TTP}
--------------------------------------------------------------------------
