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


-- | Persistent equivalence relations (aka union-find)
--   
--   This is a semi-persistent data structure for equivalence relations
--   (known in the imperative world as union-find or disjoint set union).
--   It exhibits optimal performance when used in a linear pattern, but
--   degrades when other access patterns are used.
--   
--   The basic idea is as given by Conchon and Filliatre in their 2007
--   paper, "A persistent union-find data structure." Unlike the
--   implementation given in the paper, this version is safe with multiple
--   threads, but does not optimize for backtracking.
--   
--   Version 0.2 removes unnecessary atomic operations when doing updates
--   that are never semantically meaningful, hopefully leading to better
--   scalability in a parallel setting.
@package persistent-equivalence
@version 0.2


-- | Code for manipulation of equivalence classes on index types. An
--   <a>Equivalence</a> is an equivalence relation. The empty equivalence
--   relation is constructed over a ranges of values using
--   <a>emptyEquivalence</a>. Less discerning equivalence relations can be
--   obtained with <a>equate</a> and <a>equateAll</a>. The relation can be
--   tested with <a>equiv</a> and <a>equivalent</a>, and canonical
--   representatives can be chosen with <a>repr</a>.
--   
--   An example follows:
--   
--   <pre>
--   import Data.Equivalence.Persistent
--   
--   rel = equateAll [1,3,5,7,9]
--       . equate 5 6
--       . equate 2 4
--       $ emptyEquivalence (1,10)
--   
--   test1 = equiv rel 3 5 -- This is True
--   test2 = equiv rel 1 6 -- This is True
--   test3 = equiv rel 4 6 -- This is False
--   </pre>
module Data.Equivalence.Persistent

-- | An <a>Equivalence</a> is an equivalence relation on a range of values
--   of some index type.
data Equivalence i

-- | <a>emptyEquivalence</a> is an equivalence relation that equates two
--   values only when they are equal to each other. It is the most
--   discerning such relation possible.
emptyEquivalence :: Ix i => (i, i) -> Equivalence i

-- | Gets the domain of an equivalence relation, as the ordered pair of
--   index bounds.
domain :: Ix i => Equivalence i -> (i, i)

-- | <a>repr</a> gives a canonical representative of the equivalence class
--   containing <tt>x</tt>. It is chosen arbitrarily, but is always the
--   same for a given class and <a>Equivalence</a> value.
--   
--   If you are using this function, you're probably doing something wrong.
--   Please note that:
--   
--   <ul>
--   <li>The representative chosen depends on the order in which the
--   equivalence relation was built, and is not always the same for values
--   that represent the same relation.</li>
--   <li>The representative is not particularly stable. Uses of
--   <a>equate</a> are highly likely to change it.</li>
--   <li>If all you need is some representative of the equivalence class,
--   you have to provide one as input to the function anyway, so you may as
--   well use that.</li>
--   </ul>
--   
--   Because of this, the function may be removed in a future version.
--   Please contact me if you have a compelling use for it.
repr :: Ix i => Equivalence i -> i -> i

-- | Determines if two values are equivalent under the given equivalence
--   relation.
equiv :: Ix i => Equivalence i -> i -> i -> Bool

-- | Determines if all of the given values are equivalent under the given
--   equivalence relation.
equivalent :: Ix i => Equivalence i -> [i] -> Bool

-- | Construct the equivalence relation obtained by equating the given two
--   values. This combines equivalence classes.
equate :: Ix i => i -> i -> Equivalence i -> Equivalence i

-- | Construct the equivalence relation obtained by equating all of the
--   given values. This combines equivalence classes.
equateAll :: Ix i => [i] -> Equivalence i -> Equivalence i