-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | A data structure representing Relations on Sets.
--   
--   A library to model relationships between two objects that are
--   subclasses of Ord.
--   
--   Instead using a Map structure we use a two Maps that allows fast
--   searching either by the key element or the value element.
--   
--   Each of Map is between an element and a set of values. Thus careful
--   coordination of operations is required.
--   
--   This library lacks of extensive testing, formal testing or automated
--   testing. Also in comparison to Data.Set or Data.Map (which provide the
--   underlying infrastructure used) there are some missing methods.
--   
--   Two small examples are currently provided.
--   
--   Changes:
--   
--   <pre>
--   2012.06.06.  DD. Translated to English.
--   
--   2009.11.09. LFL. Corrected the definition of delete.
--   
--   2009.11.26. LFL. Construction
--   </pre>
@package relation
@version 0.2


-- | Relations are modeled as assciations between two elements.
--   
--   Relations offer efficient search for any of the two elements.
--   
--   Unlike <a>Data.Map</a>, an element ca be associated more than once.
--   
--   The two purposes of this structure are:
--   
--   <ol>
--   <li>Associating elements</li>
--   <li>Provide efficient searches for either of the two elements.</li>
--   </ol>
--   
--   Since neither <a>map</a> nor <tt>fold</tt> are implemented, you
--   <i>must</i> convert the structure to a list to process sequentially.
module Data.Relation

-- | This implementation avoids using <tt><a>S.Set (a,b)</a></tt> because
--   it it is necessary to search for an item without knowing both
--   <tt>D</tt> and <tt>R</tt>.
--   
--   In <a>S.Set</a>, you must know both values to search.
--   
--   Thus, we have are two maps to updated together.
--   
--   <ol>
--   <li>Always be careful with the associated set of the key.</li>
--   <li>If you union two relations, apply union to the set of values.</li>
--   <li>If you subtract, take care when handling the set of values.</li>
--   </ol>
--   
--   As a multi-map, each key is asscoated with a Set of values v.
--   
--   We do not allow the associations with the <a>empty</a> Set.
data Relation a b

-- | <tt>size r</tt> returns the number of tuples in the relation.
size :: Relation a b -> Int

-- | True if the relation <tt>r</tt> is the <a>empty</a> relation.
null :: Relation a b -> Bool

-- | Construct a relation with no elements.
empty :: Relation a b

-- | The list must be formatted like: [(k1, v1), (k2, v2),..,(kn, vn)].
fromList :: (Ord a, Ord b) => [(a, b)] -> Relation a b

-- | Builds a <a>Relation</a> consiting of an association between:
--   <tt>x</tt> and <tt>y</tt>.
singleton :: a -> b -> Relation a b

-- | The <a>Relation</a> that results from the union of two relations:
--   <tt>r</tt> and <tt>s</tt>.
union :: (Ord a, Ord b) => Relation a b -> Relation a b -> Relation a b

-- | Union a list of relations using the <a>empty</a> relation.
unions :: (Ord a, Ord b) => [Relation a b] -> Relation a b

-- | Insert a relation <tt> x </tt> and <tt> y </tt> in the relation <tt> r
--   </tt>
insert :: (Ord a, Ord b) => a -> b -> Relation a b -> Relation a b

-- | Delete an association in the relation.
delete :: (Ord a, Ord b) => a -> b -> Relation a b -> Relation a b

-- | The Set of values associated with a value in the domain.
lookupDom :: Ord a => a -> Relation a b -> Maybe (Set b)

-- | The Set of values associated with a value in the range.
lookupRan :: Ord b => b -> Relation a b -> Maybe (Set a)

-- | True if the element <tt> x </tt> exists in the domain of <tt> r </tt>.
memberDom :: Ord a => a -> Relation a b -> Bool

-- | True if the element exists in the range.
memberRan :: Ord b => b -> Relation a b -> Bool

-- | True if the relation contains the association <tt>x</tt> and
--   <tt>y</tt>
member :: (Ord a, Ord b) => a -> b -> Relation a b -> Bool

-- | True if the relation <i>does not</i> contain the association
--   <tt>x</tt> and <tt>y</tt>
notMember :: (Ord a, Ord b) => a -> b -> Relation a b -> Bool

-- | Builds a List from a Relation.
toList :: Relation a b -> [(a, b)]

-- | Returns the domain in the relation, as a Set, in its entirety.
dom :: Relation a b -> Set a

-- | Returns the range of the relation, as a Set, in its entirety.
ran :: Relation a b -> Set b

-- | A compact set of sets the values of which can be <tt>Just (Set x)</tt>
--   or <tt>Nothing</tt>.
--   
--   The cases of <a>Nothing</a> are purged.
--   
--   It is similar to <a>concat</a>.
compactSet :: Ord a => Set (Maybe (Set a)) -> Set a

-- | <pre>
--   ( Case a |&gt; r b )
--   </pre>
(|$>) :: (Ord a, Ord b) => Set a -> Set b -> Relation a b -> Set b

-- | <pre>
--   (Case b &lt;| r a)
--   </pre>
(<$|) :: (Ord a, Ord b) => Set a -> Set b -> Relation a b -> Set a

-- | Domain restriction for a relation. Modeled on z.
(<|) :: (Ord a, Ord b) => Set a -> Relation a b -> Relation a b

-- | Range restriction for a relation. Modeled on z.
(|>) :: (Ord a, Ord b) => Relation a b -> Set b -> Relation a b
instance (Show a, Show b) => Show (Relation a b)
instance (Eq a, Eq b) => Eq (Relation a b)
instance (Ord a, Ord b) => Ord (Relation a b)