data-partition 0.1.0.0 → 0.2.0.0

raw patch · 2 files changed

+29/−13 lines, 2 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

Files

• Data/Partition.hs +28/−12
• data-partition.cabal +1/−1

@@ -14,7 +14,7 @@ ---------------------------------------------------------------------------  module Data.Partition -    ( Partition, discrete, empty, join, find )+    ( Partition, discrete, empty, fromSets, nontrivialSets, join, find, rep )  where  import qualified Data.Map as Map@@ -32,6 +32,9 @@                         -- computable total ordering on Partitions, and that is helpful                         -- sometimes. +instance (Show a) => Show (Partition a) where+    show p = "fromSets " ++ show (nontrivialSets p)+ -- | A partition in which every element of @a@ is in its own set.  Semantics: -- @[[discrete]] = { { x } | x in a }@ discrete :: Partition a@@ -41,38 +44,51 @@ empty :: Partition a empty = discrete +-- | Takes a list of disjoint sets and constructs a partition containing those sets,+-- with every remaining element being given its own set.+fromSets :: (Ord a) => [Set.Set a] -> Partition a+fromSets sets = Partition { +        forwardMap = Map.fromList [ (x, Set.findMin s) | s <- sets, x <- Set.toList s ],+        backwardMap = Map.fromList [ (Set.findMin s, s) | s <- sets ]+    }++-- | Returns a list of all nontrivial sets (sets with more than one element) in the +-- partition.+nontrivialSets :: Partition a -> [Set.Set a]+nontrivialSets = Map.elems . backwardMap+ -- | @join x y@ merges the two sets containing @x@ and @y@ into a single set.  Semantics:--- @[[join x y p]] = (p `minus` find x `minus` find y) `union` { find x `union` find y }@+-- @[[join x y p]] = (p \`minus\` find x \`minus\` find y) \`union\` { find x \`union\` find y }@ join :: (Ord a) => a -> a -> Partition a -> Partition a join x y p = case compare x' y' of                  LT -> go x' y'                  EQ -> p                  GT -> go y' x'     where-    x' = repr p x-    y' = repr p y+    x' = rep p x+    y' = rep p y      go into other = Partition {                          forwardMap = compose [ Map.insert o into | o <- Set.toList otherSrc ] (forwardMap p),-                        backwardMap = Map.insert into (Set.union (reprFind p into) otherSrc) +                        backwardMap = Map.insert into (Set.union (repFind p into) otherSrc)                                      . Map.delete other                                     $ backwardMap p                     }         where-        otherSrc = reprFind p other+        otherSrc = repFind p other  -- | @find p x@ finds the set that the element @x@ is associated with.  Semantics:  -- @[[find p x]] = the unique s in p such that x in s@. find :: (Ord a) => Partition a -> a -> Set.Set a-find p = reprFind p . repr p+find p = repFind p . rep p --- Find the representative element for an element.-repr :: (Ord a) => Partition a -> a -> a-repr p x = fromMaybe x (Map.lookup x (forwardMap p))+-- | @rep p x@ finds the minimum element in the set containing @x@.+rep :: (Ord a) => Partition a -> a -> a+rep p x = fromMaybe x (Map.lookup x (forwardMap p))  -- Find the set that x is in given that x is already a representative element.-reprFind :: (Ord a) => Partition a -> a -> Set.Set a-reprFind p x = fromMaybe (Set.singleton x) (Map.lookup x (backwardMap p))+repFind :: (Ord a) => Partition a -> a -> Set.Set a+repFind p x = fromMaybe (Set.singleton x) (Map.lookup x (backwardMap p))  compose :: [a -> a] -> a -> a compose = foldr (.) id

@@ -2,7 +2,7 @@ -- documentation, see http://haskell.org/cabal/users-guide/  name:                data-partition-version:             0.1.0.0+version:             0.2.0.0 synopsis:            A pure disjoint set (union find) data structure -- description:          homepage:            https://github.com/luqui/data-partition