-- 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. We use a two Maps that allows fast searching either
--   by the key element or the value element.
@package relation
@version 0.4


-- | 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>"S.Set (a,b)"</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

-- | Intersection of two relations: <tt>a</tt> and <tt>b</tt> are related
--   by <tt>intersection r s</tt> exactly when <tt>a</tt> and <tt>b</tt>
--   are related by <tt>r</tt> and <tt>s</tt>.
intersection :: (Ord a, Ord b) => Relation a 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 -> Set b

-- | The Set of values associated with a value in the range.
lookupRan :: Ord b => b -> Relation a b -> 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

-- | Returns the converse of the relation.
c :: Relation a b -> Relation b a

-- | 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 (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 (GHC.Classes.Ord a, GHC.Classes.Ord b) => GHC.Classes.Ord (Data.Relation.Relation a b)
instance (GHC.Classes.Eq a, GHC.Classes.Eq b) => GHC.Classes.Eq (Data.Relation.Relation a b)
instance (GHC.Show.Show a, GHC.Show.Show b) => GHC.Show.Show (Data.Relation.Relation a b)