disjoint-set-stateful 0.1.0.0 → 0.1.1.0

raw patch · 4 files changed

+33/−5 lines, 4 files

Files

• disjoint-set-stateful.cabal +1/−1
• src/Data/DisjointSet/Int.hs +25/−2
• src/Data/DisjointSet/Int/Monadic.hs +6/−2
• test/Tests.hs +1/−0

@@ -1,5 +1,5 @@ name:                 disjoint-set-stateful-version:              0.1.0.0+version:              0.1.1.0 synopsis:             Monadic disjoint set description:   This package includes a monadic disjoint int set datatype, which can also be "frozen" into a non-monadic queriable

@@ -23,6 +23,8 @@ This package implements both of the above features. -} module Data.DisjointSet.Int (+  DisjointIntSet(DisjointIntSet),+  create,   find,   count,   findAndCount,@@ -34,8 +36,9 @@ where  import Data.Vector.Unboxed (Vector, (!))-import Data.DisjointSet.Int.Monadic (DisjointIntSet(DisjointIntSet))+import Data.DisjointSet.Int.Monadic (DisjointIntSet(DisjointIntSet), runDisjointIntSet, newDisjointIntSetFixed, union) import Data.DisjointSet.Int.Monadic.Impl (PointerOrCount(Pointer, Count), isPointer)+import Data.Foldable (Foldable, foldl', mapM_)  import Prelude (   Int,@@ -45,10 +48,14 @@   snd,   (/=),   Maybe (Just, Nothing),-  (.)+  (.), (+),+  max,+  ($),+  return   )  import Data.List (unfoldr)+import Data.Foldable (foldl')  type VectorT = Vector Int @@ -60,6 +67,22 @@     case (isPointer r) of       True -> Pointer r       False -> Count (negate r)++{-|+'create' creates a 'DisjointIntSet' from a list of int pairs, or indeed any 'Foldable' structure of @(Int, Int)@.++It basically calls 'union' for each of the pairs and freezes the result. Use this when you've got a list of pairs+for your disjoint set and you have no need to extend it later.+-}+create :: Foldable t => t (Int, Int) -> DisjointIntSet+create l =+  let+    maxElem = foldl' (\r (x1,x2) -> max r (max x1 x2)) (-1) l+  in+    runDisjointIntSet $ do+      v <- newDisjointIntSetFixed (maxElem + 1)+      mapM_ (\(x1,x2) -> union v x1 x2) l+      return v  {-| Both 'find' and 'count', but in one operation, so in theory faster than running them separately.

@@ -117,8 +117,12 @@  {-| This is the non-monadic disjoint int set. It can be created by using the monadic operations and then calling-'freeze', 'unsafeFreeze' or 'runDisjointIntSet' as appropriate. There's not a variable and fixed length version of this-because well, you can't modify the non-monadic version anyway.+'freeze', 'unsafeFreeze' or 'runDisjointIntSet' as appropriate.++Alternatively 'Data.DisjointSet.Int.create' can create a disjoint set+directly from any 'Foldable' structure of int pairs, e.g. and @[(Int, Int)]@.++There's not a variable and fixed length version of this because well, you can't modify the non-monadic version anyway. -} data DisjointIntSet = DisjointIntSet (Vector Int) (Vector Int) Int Int deriving Show 

@@ -36,3 +36,4 @@ main = hspec $ do   testds (ds (Just 10))   testds (ds Nothing)+  testds (create [(0,1), (3,2), (1,2), (8,9), (8,3), (7,4)])