-- 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>
--   0.2 -&gt; 0.2.1 2012.06.07.  DD. Added Doctests, Example02. Added <a>Text.Groom</a> dependency.
--   
--   0.1 -&gt; 0.2   2012.06.06.  DD. Translated to English.
--   
--   0.1          2009.11.09. LFL. Corrected the definition of delete.
--   
--   0.0          2009.11.26. LFL. Construction
--   </pre>
@package relation
@version 0.2.1


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


module Data.Relation.Examples.E02

-- | Documentation Tests
--   
--   All examples in this module are tested automatically with Doctest, and
--   pretty printed with <a>Text.Groom</a>.
--   
--   This output is provided as proof of the correctness of the REPL
--   (<tt>&gt;&gt;&gt;</tt>) text:
--   
--   <pre>
--   There are 12 tests, with 12 total interactions.
--   Examples: 12  Tried: 12  Errors: 0  Failures: 0
--   </pre>
p :: Show a => a -> IO ()

-- | Example 2:
--   
--   A student x can take n classes.
--   
--   <ul>
--   <li>Each student must take at least 1 class</li>
--   <li>Each class must have at least one student.</li>
--   </ul>
--   
--   <pre>
--   &gt;&gt;&gt; p enrollment
--   Relation{domain =
--              fromList
--                [("Antonio", fromList ["History"]),
--                 ("Rebeca", fromList ["History", "Mathematics"]),
--                 ("Rolando", fromList ["Comunication", "Religion"]),
--                 ("Teresa", fromList ["Architecture", "Religion"])],
--            range =
--              fromList
--                [("Architecture", fromList ["Teresa"]),
--                 ("Comunication", fromList ["Rolando"]),
--                 ("History", fromList ["Antonio", "Rebeca"]),
--                 ("Mathematics", fromList ["Rebeca"]),
--                 ("Religion", fromList ["Rolando", "Teresa"])]}
--   </pre>
enrollment :: Relation [Char] [Char]

-- | <pre>
--   &gt;&gt;&gt; p rebecaenrollment
--   fromList ["History", "Mathematics"]
--   </pre>
rebecaenrollment :: Set [Char]

-- | <pre>
--   &gt;&gt;&gt; p takingreligion
--   fromList ["Rolando", "Teresa"]
--   </pre>
takingreligion :: Set [Char]

-- | <pre>
--   &gt;&gt;&gt; p others
--   fromList ["Architecture", "Comunication", "Religion"]
--   </pre>
others :: Set [Char]

-- | <pre>
--   &gt;&gt;&gt; p test1
--   True
--   </pre>
test1 :: Bool

-- | <pre>
--   &gt;&gt;&gt; p takingreligion2
--   Relation{domain =
--              fromList
--                [("Rolando", fromList ["Religion"]),
--                 ("Teresa", fromList ["Religion"])],
--            range = fromList [("Religion", fromList ["Rolando", "Teresa"])]}
--   </pre>
takingreligion2 :: Relation [Char] [Char]
id1 :: Set [Char] -> (Bool, Set [Char])
id2 :: Set [Char] -> (Bool, Set [Char])
id3 :: Set [Char] -> (Bool, Set [Char])
id4 :: Set [Char] -> (Bool, Set [Char])
religion :: Set [Char]

-- | <pre>
--   &gt;&gt;&gt; p religion
--   fromList ["Religion"]
--   </pre>
teresa :: Set [Char]

-- | <pre>
--   &gt;&gt;&gt; p t11
--   (True, fromList ["Religion"])
--   </pre>
t11 :: (Bool, Set [Char])

-- | <pre>
--   &gt;&gt;&gt; p t12
--   (True, fromList ["Rolando", "Teresa"])
--   </pre>
t12 :: (Bool, Set [Char])

-- | <pre>
--   &gt;&gt;&gt; p t13
--   (True, fromList ["Teresa"])
--   </pre>
t13 :: (Bool, Set [Char])

-- | <pre>
--   &gt;&gt;&gt; p t14
--   (True, fromList ["Architecture", "Religion"])
--   </pre>
t14 :: (Bool, Set [Char])
id1R, id2R :: (Ord a, Ord b) => Set b -> Relation a b -> Bool
id3R, id4R :: (Ord a, Ord b) => Set a -> Relation a b -> Bool

-- | <pre>
--   &gt;&gt;&gt; p testAll
--   True
--   </pre>
testAll :: Bool