fingertree 0.1.3.1 → 0.1.4.0

raw patch · 5 files changed

+94/−13 lines, 5 filesdep ~basePVP ok

version bump matches the API change (PVP)

Dependency ranges changed: base

API changes (from Hackage documentation)

Files

• Data/FingerTree.hs +49/−8
• Data/IntervalMap/FingerTree.hs +27/−3
• Data/PriorityQueue/FingerTree.hs +14/−1
• changelog +3/−0
• fingertree.cabal +1/−1

@@ -1,6 +1,10 @@ {-# LANGUAGE CPP #-}-{-# LANGUAGE MultiParamTypeClasses, FunctionalDependencies, FlexibleInstances, UndecidableInstances #-}+{-# LANGUAGE FlexibleInstances #-}+{-# LANGUAGE FunctionalDependencies #-}+{-# LANGUAGE MultiParamTypeClasses #-}+{-# LANGUAGE UndecidableInstances #-} #if __GLASGOW_HASKELL__ >= 702+{-# LANGUAGE DeriveGeneric #-} {-# LANGUAGE Safe #-} #endif #if __GLASGOW_HASKELL__ >= 710@@ -69,6 +73,9 @@     ) where  import Prelude hiding (null, reverse)+#if MIN_VERSION_base(4,6,0)+import GHC.Generics+#endif #if MIN_VERSION_base(4,8,0) import qualified Prelude (null) #else@@ -76,7 +83,7 @@ import Data.Monoid import Data.Foldable (Foldable(foldMap)) #endif-#if MIN_VERSION_base(4,9,0)+#if (MIN_VERSION_base(4,9,0)) && !(MIN_VERSION_base(4,11,0)) import Data.Semigroup #endif import Data.Foldable (toList)@@ -89,14 +96,22 @@ data ViewL s a     = EmptyL        -- ^ empty sequence     | a :< s a      -- ^ leftmost element and the rest of the sequence-    deriving (Eq, Ord, Show, Read)+    deriving (Eq, Ord, Show, Read+#if __GLASGOW_HASKELL__ >= 702+        , Generic+#endif+        )  -- | View of the right end of a sequence. data ViewR s a     = EmptyR        -- ^ empty sequence     | s a :> a      -- ^ the sequence minus the rightmost element,                     -- and the rightmost element-    deriving (Eq, Ord, Show, Read)+    deriving (Eq, Ord, Show, Read+#if __GLASGOW_HASKELL__ >= 702+        , Generic+#endif+        )  instance (Functor s) => Functor (ViewL s) where     fmap _ EmptyL    = EmptyL@@ -125,7 +140,11 @@     | Two a a     | Three a a a     | Four a a a a-    deriving Show+    deriving (Show+#if __GLASGOW_HASKELL__ >= 702+        , Generic+#endif+        )  instance Foldable Digit where     foldMap f (One a) = f a@@ -149,7 +168,11 @@ ---------------------------  data Node v a = Node2 !v a a | Node3 !v a a a-    deriving Show+    deriving (Show+#if __GLASGOW_HASKELL__ >= 702+        , Generic+#endif+        )  instance Foldable (Node v) where     foldMap f (Node2 _ a b) = f a `mappend` f b@@ -185,8 +208,14 @@     | Single a     | Deep !v !(Digit a) (FingerTree v (Node v a)) !(Digit a) #if TESTING-    deriving Show+    deriving (Show+#if __GLASGOW_HASKELL__ >= 702+        , Generic #endif+        )+#elif __GLASGOW_HASKELL__ >= 702+    deriving (Generic)+#endif  deep ::  (Measured v a) =>      Digit a -> FingerTree v (Node v a) -> Digit a -> FingerTree v a@@ -293,6 +322,8 @@ -- | Map all elements of the tree with a function that also takes the -- measure of the prefix to the left and of the suffix to the right of -- the element.+--+-- @since 0.1.2.0 fmapWithContext :: (Measured v1 a1, Measured v2 a2) =>     (v1 -> a1 -> v1 -> a2) -> FingerTree v1 a1 -> FingerTree v2 a2 fmapWithContext f t = mapWCTree f mempty t mempty@@ -427,6 +458,8 @@ -- | Traverse the tree from left to right with a function that also -- takes the measure of the prefix to the left and the measure of the -- suffix to the right of the element.+--+-- @since 0.1.2.0 traverseWithContext :: (Measured v1 a1, Measured v2 a2, Applicative f) =>     (v1 -> a1 -> v1 -> f a2) -> FingerTree v1 a1 -> f (FingerTree v2 a2) traverseWithContext f t = traverseWCTree f mempty t mempty@@ -847,6 +880,8 @@  -- | A result of 'search', attempting to find a point where a predicate -- on splits of the sequence changes from 'False' to 'True'.+--+-- @since 0.1.2.0 data SearchResult v a     = Position (FingerTree v a) a (FingerTree v a)         -- ^ A tree opened at a particular element: the prefix to the@@ -861,7 +896,11 @@         -- ^ No position in the tree, returned if the predicate is 'True'         -- at the left end and 'False' at the right end.  This will not         -- occur if the predicate in monotonic on the tree.-    deriving (Eq, Ord, Show)+    deriving (Eq, Ord, Show+#if __GLASGOW_HASKELL__ >= 702+        , Generic+#endif+        )  -- | /O(log(min(i,n-i)))/. Search a sequence for a point where a predicate -- on splits of the sequence changes from 'False' to 'True'.@@ -891,6 +930,8 @@ -- -- For predictable results, one should ensure that there is only one such -- point, i.e. that the predicate is /monotonic/ on @t@.+--+-- @since 0.1.2.0 search :: (Measured v a) =>     (v -> v -> Bool) -> FingerTree v a -> SearchResult v a search p t

@@ -1,6 +1,7 @@ {-# LANGUAGE CPP #-} {-# LANGUAGE MultiParamTypeClasses #-} #if __GLASGOW_HASKELL__ >= 702+{-# LANGUAGE DeriveGeneric #-} {-# LANGUAGE Safe #-} #endif #if __GLASGOW_HASKELL__ >= 710@@ -48,6 +49,9 @@ import Data.FingerTree (FingerTree, Measured(..), ViewL(..), (<|), (><))  import Prelude hiding (null)+#if MIN_VERSION_base(4,6,0)+import GHC.Generics+#endif #if MIN_VERSION_base(4,8,0) import qualified Prelude (null) #else@@ -56,7 +60,7 @@ import Data.Monoid import Data.Traversable (Traversable(traverse)) #endif-#if MIN_VERSION_base(4,9,0)+#if (MIN_VERSION_base(4,9,0)) && !(MIN_VERSION_base(4,11,0)) import Data.Semigroup #endif import Data.Foldable (toList)@@ -68,7 +72,11 @@ -- | A closed interval.  The lower bound should be less than or equal -- to the upper bound. data Interval v = Interval v v -- ^ Lower and upper bounds of the interval.-    deriving (Eq, Ord, Show)+    deriving (Eq, Ord, Show, Read+#if __GLASGOW_HASKELL__ >= 702+        , Generic+#endif+        )  -- | Lower bound of the interval low :: Interval v -> v@@ -83,7 +91,11 @@ point v = Interval v v  data Node v a = Node (Interval v) a-    deriving (Eq, Ord, Show)+    deriving (Eq, Ord, Show, Read+#if __GLASGOW_HASKELL__ >= 702+        , Generic+#endif+        )  instance Functor (Node v) where     fmap f (Node i x) = Node i (f x)@@ -96,6 +108,9 @@  -- rightmost interval (including largest lower bound) and largest upper bound. data IntInterval v = NoInterval | IntInterval (Interval v) v+#if __GLASGOW_HASKELL__ >= 702+    deriving (Generic)+#endif  #if MIN_VERSION_base(4,9,0) instance Ord v => Semigroup (IntInterval v) where@@ -120,6 +135,9 @@ -- | Map of closed intervals, possibly with duplicates. newtype IntervalMap v a =     IntervalMap (FingerTree (IntInterval v) (Node v a))+#if __GLASGOW_HASKELL__ >= 702+    deriving (Generic)+#endif -- ordered lexicographically by interval  instance Functor (IntervalMap v) where@@ -236,6 +254,8 @@ -- | /O(1)/.  @'bounds' m@ returns @'Nothing'@ if @m@ is empty, and -- otherwise @'Just' i@, where @i@ is the smallest interval containing -- all the intervals in the map.+--+-- @since 0.1.3.0 bounds :: (Ord v) => IntervalMap v a -> Maybe (Interval v) bounds (IntervalMap t) = case measure t of     NoInterval -> Nothing@@ -246,6 +266,8 @@ -- | /O(1)/.  @'leastView' m@ returns @'Nothing'@ if @m@ is empty, and -- otherwise @'Just' ((i, x), m')@, where @i@ is the least interval, -- @x@ is the associated value, and @m'@ is the rest of the map.+--+-- @since 0.1.3.0 leastView :: Ord v =>     IntervalMap v a -> Maybe ((Interval v, a), IntervalMap v a) leastView (IntervalMap t) = case FT.viewl t of@@ -255,6 +277,8 @@ -- | /O(log(min(i,n-i)))/.  @'splitAfter' k m@ returns a pair of submaps, -- one consisting of intervals whose lower bound is less than or equal -- to @k@, and the other of those whose lower bound is greater.+--+-- @since 0.1.3.0 splitAfter :: Ord v =>     v -> IntervalMap v a -> (IntervalMap v a, IntervalMap v a) splitAfter k (IntervalMap t) = (IntervalMap before, IntervalMap after)

@@ -1,6 +1,7 @@ {-# LANGUAGE CPP #-} {-# LANGUAGE MultiParamTypeClasses #-} #if __GLASGOW_HASKELL__ >= 702+{-# LANGUAGE DeriveGeneric #-} {-# LANGUAGE Safe #-} #endif #if __GLASGOW_HASKELL__ >= 710@@ -58,19 +59,25 @@ import Data.FingerTree (FingerTree, (<|), (|>), (><), ViewL(..), Measured(..))  import Prelude hiding (null)+#if MIN_VERSION_base(4,6,0)+import GHC.Generics+#endif #if MIN_VERSION_base(4,8,0) import qualified Prelude (null) #else import Data.Foldable (Foldable(foldMap)) import Data.Monoid #endif-#if MIN_VERSION_base(4,9,0)+#if (MIN_VERSION_base(4,9,0)) && !(MIN_VERSION_base(4,11,0)) import Data.Semigroup #endif import Control.Arrow ((***)) import Data.List (unfoldr)  data Entry k v = Entry k v+#if __GLASGOW_HASKELL__ >= 702+    deriving (Generic)+#endif  instance Functor (Entry k) where     fmap f (Entry k v) = Entry k (f v)@@ -79,6 +86,9 @@     foldMap f (Entry _ v) = f v  data Prio k v = NoPrio | Prio k v+#if __GLASGOW_HASKELL__ >= 702+    deriving (Generic)+#endif  #if MIN_VERSION_base(4,9,0) instance Ord k => Semigroup (Prio k v) where@@ -103,6 +113,9 @@  -- | Priority queues. newtype PQueue k v = PQueue (FingerTree (Prio k v) (Entry k v))+#if __GLASGOW_HASKELL__ >= 702+    deriving (Generic)+#endif  instance Ord k => Functor (PQueue k) where     fmap f (PQueue xs) = PQueue (FT.fmap' (fmap f) xs)

@@ -1,5 +1,8 @@ -*-change-log-*- +0.1.4.0 Ross Paterson <R.Paterson@city.ac.uk> Mar 2018+	* Added Generic instances+ 0.1.3.1 Ross Paterson <R.Paterson@city.ac.uk> Dec 2017 	* Fixed Data.IntervalMap.FingerTree.bounds 

@@ -1,5 +1,5 @@ Name:           fingertree-Version:        0.1.3.1+Version:        0.1.4.0 Cabal-Version:  >= 1.18 Copyright:      (c) 2006 Ross Paterson, Ralf Hinze License:        BSD3