impure-containers 0.2 → 0.3

raw patch · 2 files changed

+44/−11 lines, 2 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

Files

• impure-containers.cabal +1/−1
• src/Data/Graph/Immutable.hs +43/−10

@@ -1,5 +1,5 @@ name:                impure-containers-version:             0.2+version:             0.3 synopsis:            Mutable containers in haskell description:         Please see README.md homepage:            https://github.com/andrewthad/impure-containers#readme

@@ -6,12 +6,14 @@  import Data.Graph.Types import Control.Monad.Primitive+import Data.Foldable import Data.Vector (Vector) import Data.Vector.Mutable (MVector) import Control.Monad import Data.Word import Control.Monad.ST (runST) import Data.Primitive.MutVar+import Data.Coerce (coerce) import qualified Data.Graph.Mutable as Mutable import qualified Data.ArrayList.Generic as ArrayList import qualified Data.HashMap.Mutable.Basic as HashTable@@ -21,8 +23,8 @@ import qualified Data.Vector.Unboxed as U import qualified Data.Vector.Unboxed.Mutable as MU -mapVertices :: (v -> w) -> Graph g e v -> Graph g e w-mapVertices = fmap+-- mapVertices :: (v -> w) -> Graph g e v -> Graph g e w+-- mapVertices = fmap  dijkstra :: (Ord s, Monoid s)   => (v -> v -> s -> e -> s)@@ -66,7 +68,7 @@                 value = verticesRead oldVertices vertex             Mutable.verticesUWrite visited vertex True             Mutable.verticesWrite newVertices vertex s-            traverseNeighbors_ (\theEdge neighborVertex neighborValue -> do+            traverseNeighbors_ (\neighborVertex neighborValue theEdge -> do                 alreadyVisited <- Mutable.verticesURead visited neighborVertex                 when (not alreadyVisited) $ Heap.unsafePush                   (f value neighborValue s theEdge)@@ -85,21 +87,43 @@ lookupVertex :: Eq v => v -> Graph g e v -> Maybe (Vertex g) lookupVertex val (Graph g) = fmap Vertex (V.elemIndex val (graphVertices g)) +-- | Not the same as fmap because the function also takes the vertex id.+mapVertices :: (Vertex g -> a -> b) -> Graph g e a -> Graph g e b+mapVertices f (Graph sg) = Graph sg+  { graphVertices = V.imap (coerce f) (graphVertices sg) }++traverseVertices_ :: Applicative m => (Vertex g -> v -> m a) -> Graph g e v -> m ()+traverseVertices_ f g = verticesTraverse_ f (vertices g)++-- | This traverses every edge in the entire graph.+traverseEdges_ :: Applicative m+  => (Vertex g -> Vertex g -> v -> v -> e -> m a)+  -> Graph g e v+  -> m ()+traverseEdges_ f g =+  let allVertices = vertices g+   in verticesTraverse_+        (\vertex value -> traverseNeighbors_+          (\neighborVertex neighborValue e -> f vertex neighborVertex value neighborValue e)+          vertex g+        ) allVertices++-- | Change this to use unsafeRead some time soon. traverseNeighbors_ :: Applicative m-  => (e -> Vertex g -> v -> m a)+  => (Vertex g -> v -> e -> m a)   -> Vertex g   -> Graph g e v   -> m () traverseNeighbors_ f (Vertex x) (Graph g) =-  let allVertices = graphVertices g-      theVertices = graphOutboundNeighborVertices g V.! x-      edges    = graphOutboundNeighborEdges g V.! x+  let allVertices  = graphVertices g+      theVertices  = graphOutboundNeighborVertices g V.! x+      edges        = graphOutboundNeighborEdges g V.! x       numNeighbors = U.length theVertices       go !i = if i < numNeighbors         then let vertexNum = theVertices U.! i                  vertexVal = allVertices V.! vertexNum                  edgeVal = edges V.! i-              in f edgeVal (Vertex vertexNum) vertexVal *> go (i + 1)+              in f (Vertex vertexNum) vertexVal edgeVal *> go (i + 1)         else pure ()    in go 0 @@ -139,8 +163,17 @@ verticesToVertexList :: Vertices g v -> [Vertex g] verticesToVertexList (Vertices v) = map Vertex (take (V.length v) [0..]) -verticesTraverse_ :: Monad m => (Vertex g -> v -> m a) -> Vertices g v -> m ()-verticesTraverse_ f (Vertices v) = V.imapM_ (\i -> f (Vertex i)) v+-- | This is currently inefficient. If an @itraverse@ gets added+--   to @vector@, this can be made faster.+verticesTraverse :: Applicative m => (Vertex g -> v -> m a) -> Vertices g v -> m (Vertices g a)+verticesTraverse f (Vertices v) = fmap (Vertices . V.fromList) $ traverse (\(i,b) -> f (Vertex i) b) (zip [0..] (V.toList v))+  -- Vertices (V.imapM (\i -> f (Vertex i)) v)++-- | This is currently inefficient. If an @itraverse@ gets added+--   to @vector@, this can be made faster.+verticesTraverse_ :: Applicative m => (Vertex g -> v -> m a) -> Vertices g v -> m ()+verticesTraverse_ f (Vertices v) = traverse_ (\(i,b) -> f (Vertex i) b) (zip [0..] (V.toList v))+  -- V.imapM_ (\i -> f (Vertex i)) v  verticesToVector :: Vertices g v -> Vector v verticesToVector (Vertices v) = v