hw-fingertree-strict 0.1.1.0 → 0.1.1.1

raw patch · 6 files changed

+49/−48 lines, 6 filesPVP: major bump suggested

API removals or changes: PVP suggests a major version bump

API changes (from Hackage documentation)

Files

• hw-fingertree-strict.cabal +3/−2
• src/HaskellWorks/Data/FingerTree/Strict.hs +38/−38
• src/HaskellWorks/Data/IntervalMap/Strict.hs +2/−2
• src/HaskellWorks/Data/PriorityQueue/Strict.hs +2/−2
• src/HaskellWorks/Data/SegmentMap/Strict.hs +2/−2
• src/HaskellWorks/Data/SegmentSet/Strict.hs +2/−2

@@ -2,10 +2,10 @@ -- -- see: https://github.com/sol/hpack ----- hash: 5c497b01164dee762c3873fb69ffef4ce5f924eaed8074380983ce4362edd761+-- hash: 1a9f8c64ec2369530869030e8871c1280ef0345df0b89a6a286c8bcb125cd482  name:           hw-fingertree-strict-version:        0.1.1.0+version:        0.1.1.1 synopsis:       Generic strict finger-tree structure description:    A general sequence representation with arbitrary                 annotations, for use as a base for implementations of@@ -42,6 +42,7 @@ library   hs-source-dirs:       src+  other-extensions: DeriveAnyClass   build-depends:       base >=4.7 && <5     , deepseq

@@ -132,7 +132,7 @@ class (Monoid v) => Measured v a | a -> v where     measure :: a -> v -instance (Measured v a) => Measured v (Digit a) where+instance Measured v a => Measured v (Digit a) where     measure = foldMap measure  ---------------------------@@ -146,10 +146,10 @@     foldMap f (Node2 _ a b)   = f a `mappend` f b     foldMap f (Node3 _ a b c) = f a `mappend` f b `mappend` f c -node2        ::  (Measured v a) => a -> a -> Node v a+node2        ::  Measured v a => a -> a -> Node v a node2 a b    =   Node2 (measure a `mappend` measure b) a b -node3        ::  (Measured v a) => a -> a -> a -> Node v a+node3        ::  Measured v a => a -> a -> a -> Node v a node3 a b c  =   Node3 (measure a `mappend` measure b `mappend` measure c) a b c  instance (Monoid v) => Measured v (Node v a) where@@ -177,12 +177,12 @@     | Deep !v !(Digit a) !(FingerTree v (Node v a)) !(Digit a)     deriving (Show, Generic, NFData) -deep ::  (Measured v a) =>+deep ::  Measured v a =>      Digit a -> FingerTree v (Node v a) -> Digit a -> FingerTree v a deep pr m sf = Deep ((measure pr `mappendVal` m) `mappend` measure sf) pr m sf  -- | /O(1)/. The cached measure of a tree.-instance (Measured v a) => Measured v (FingerTree v a) where+instance Measured v a => Measured v (FingerTree v a) where     measure Empty          =  mempty     measure (Single x)     =  measure x     measure (Deep v _ _ _) =  v@@ -256,7 +256,7 @@     va      = v `mappend` measure a     vab     = va `mappend` measure b -mapWPDigit :: (Measured v a) => (v -> a -> b) -> v -> Digit a -> Digit b+mapWPDigit :: Measured v a => (v -> a -> b) -> v -> Digit a -> Digit b mapWPDigit f v (One a) = One (f v a) mapWPDigit f v (Two a b) = Two (f v a) (f va b)   where@@ -365,20 +365,20 @@ -----------------------------------------------------  -- | /O(1)/. The empty sequence.-empty :: Measured v a => FingerTree v a+empty :: FingerTree v a empty = Empty  -- | /O(1)/. A singleton sequence.-singleton :: Measured v a => a -> FingerTree v a+singleton :: a -> FingerTree v a singleton = Single  -- | /O(n)/. Create a sequence from a finite list of elements.-fromList :: (Measured v a) => [a] -> FingerTree v a+fromList :: Measured v a => [a] -> FingerTree v a fromList = foldr' (<|) Empty  -- | /O(1)/. Add an element to the left end of a sequence. -- Mnemonic: a triangle with the single element at the pointy end.-(<|) :: (Measured v a) => a -> FingerTree v a -> FingerTree v a+(<|) :: Measured v a => a -> FingerTree v a -> FingerTree v a a <| Empty              =  Single a a <| Single b           =  deep (One a) Empty (One b) a <| Deep v (Four b c d e) m sf = m `seq`@@ -394,7 +394,7 @@  -- | /O(1)/. Add an element to the right end of a sequence. -- Mnemonic: a triangle with the single element at the pointy end.-(|>) :: (Measured v a) => FingerTree v a -> a -> FingerTree v a+(|>) :: Measured v a => FingerTree v a -> a -> FingerTree v a Empty |> a              =  Single a Single a |> b           =  deep (One a) Empty (One b) Deep v pr m (Four a b c d) |> e = m `seq`@@ -409,18 +409,18 @@ snocDigit (Four _ _ _ _) _ = illegal_argument "snocDigit"  -- | /O(1)/. Is this the empty sequence?-null :: (Measured v a) => FingerTree v a -> Bool+null :: FingerTree v a -> Bool null Empty = True null _     = False  -- | /O(1)/. Analyse the left end of a sequence.-viewl :: (Measured v a) => FingerTree v a -> ViewL (FingerTree v) a+viewl :: Measured v a => FingerTree v a -> ViewL (FingerTree v) a viewl Empty                 =  EmptyL viewl (Single x)            =  x :< Empty viewl (Deep _ (One x) m sf) =  x :< rotL m sf viewl (Deep _ pr m sf)      =  lheadDigit pr :< deep (ltailDigit pr) m sf -rotL :: (Measured v a) => FingerTree v (Node v a) -> Digit a -> FingerTree v a+rotL :: Measured v a => FingerTree v (Node v a) -> Digit a -> FingerTree v a rotL m sf      =   case viewl m of     EmptyL  ->  digitToTree sf     a :< m' ->  Deep (measure m `mappend` measure sf) (nodeToDigit a) m' sf@@ -438,13 +438,13 @@ ltailDigit (Four _ b c d) = Three b c d  -- | /O(1)/. Analyse the right end of a sequence.-viewr :: (Measured v a) => FingerTree v a -> ViewR (FingerTree v) a+viewr :: Measured v a => FingerTree v a -> ViewR (FingerTree v) a viewr Empty                 =  EmptyR viewr (Single x)            =  Empty :> x viewr (Deep _ pr m (One x)) =  rotR pr m :> x viewr (Deep _ pr m sf)      =  deep pr m (rtailDigit sf) :> rheadDigit sf -rotR :: (Measured v a) => Digit a -> FingerTree v (Node v a) -> FingerTree v a+rotR :: Measured v a => Digit a -> FingerTree v (Node v a) -> FingerTree v a rotR pr m = case viewr m of     EmptyR  ->  digitToTree pr     m' :> a ->  Deep (measure pr `mappendVal` m) pr m' (nodeToDigit a)@@ -461,7 +461,7 @@ rtailDigit (Three a b _)  = Two a b rtailDigit (Four a b c _) = Three a b c -digitToTree :: (Measured v a) => Digit a -> FingerTree v a+digitToTree :: Measured v a => Digit a -> FingerTree v a digitToTree (One a)        = Single a digitToTree (Two a b)      = deep (One a) Empty (One b) digitToTree (Three a b c)  = deep (Two a b) Empty (One c)@@ -472,10 +472,10 @@ ----------------  -- | /O(log(min(n1,n2)))/. Concatenate two sequences.-(><) :: (Measured v a) => FingerTree v a -> FingerTree v a -> FingerTree v a+(><) :: Measured v a => FingerTree v a -> FingerTree v a -> FingerTree v a (><) =  appendTree0 -appendTree0 :: (Measured v a) => FingerTree v a -> FingerTree v a -> FingerTree v a+appendTree0 :: Measured v a => FingerTree v a -> FingerTree v a -> FingerTree v a appendTree0 Empty xs =     xs appendTree0 xs Empty =@@ -487,7 +487,7 @@ appendTree0 (Deep _ pr1 m1 sf1) (Deep _ pr2 m2 sf2) =     deep pr1 (addDigits0 m1 sf1 pr2 m2) sf2 -addDigits0 :: (Measured v a) => FingerTree v (Node v a) -> Digit a -> Digit a -> FingerTree v (Node v a) -> FingerTree v (Node v a)+addDigits0 :: Measured v a => FingerTree v (Node v a) -> Digit a -> Digit a -> FingerTree v (Node v a) -> FingerTree v (Node v a) addDigits0 m1 (One a) (One b) m2 =     appendTree1 m1 (node2 a b) m2 addDigits0 m1 (One a) (Two b c) m2 =@@ -521,7 +521,7 @@ addDigits0 m1 (Four a b c d) (Four e f g h) m2 =     appendTree3 m1 (node3 a b c) (node3 d e f) (node2 g h) m2 -appendTree1 :: (Measured v a) => FingerTree v a -> a -> FingerTree v a -> FingerTree v a+appendTree1 :: Measured v a => FingerTree v a -> a -> FingerTree v a -> FingerTree v a appendTree1 Empty a xs =     a <| xs appendTree1 xs a Empty =@@ -533,7 +533,7 @@ appendTree1 (Deep _ pr1 m1 sf1) a (Deep _ pr2 m2 sf2) =     deep pr1 (addDigits1 m1 sf1 a pr2 m2) sf2 -addDigits1 :: (Measured v a) => FingerTree v (Node v a) -> Digit a -> a -> Digit a -> FingerTree v (Node v a) -> FingerTree v (Node v a)+addDigits1 :: Measured v a => FingerTree v (Node v a) -> Digit a -> a -> Digit a -> FingerTree v (Node v a) -> FingerTree v (Node v a) addDigits1 m1 (One a) b (One c) m2 =     appendTree1 m1 (node3 a b c) m2 addDigits1 m1 (One a) b (Two c d) m2 =@@ -567,7 +567,7 @@ addDigits1 m1 (Four a b c d) e (Four f g h i) m2 =     appendTree3 m1 (node3 a b c) (node3 d e f) (node3 g h i) m2 -appendTree2 :: (Measured v a) => FingerTree v a -> a -> a -> FingerTree v a -> FingerTree v a+appendTree2 :: Measured v a => FingerTree v a -> a -> a -> FingerTree v a -> FingerTree v a appendTree2 Empty a b xs =     a <| b <| xs appendTree2 xs a b Empty =@@ -579,7 +579,7 @@ appendTree2 (Deep _ pr1 m1 sf1) a b (Deep _ pr2 m2 sf2) =     deep pr1 (addDigits2 m1 sf1 a b pr2 m2) sf2 -addDigits2 :: (Measured v a) => FingerTree v (Node v a) -> Digit a -> a -> a -> Digit a -> FingerTree v (Node v a) -> FingerTree v (Node v a)+addDigits2 :: Measured v a => FingerTree v (Node v a) -> Digit a -> a -> a -> Digit a -> FingerTree v (Node v a) -> FingerTree v (Node v a) addDigits2 m1 (One a) b c (One d) m2 =     appendTree2 m1 (node2 a b) (node2 c d) m2 addDigits2 m1 (One a) b c (Two d e) m2 =@@ -613,7 +613,7 @@ addDigits2 m1 (Four a b c d) e f (Four g h i j) m2 =     appendTree4 m1 (node3 a b c) (node3 d e f) (node2 g h) (node2 i j) m2 -appendTree3 :: (Measured v a) => FingerTree v a -> a -> a -> a -> FingerTree v a -> FingerTree v a+appendTree3 :: Measured v a => FingerTree v a -> a -> a -> a -> FingerTree v a -> FingerTree v a appendTree3 Empty a b c xs =     a <| b <| c <| xs appendTree3 xs a b c Empty =@@ -625,7 +625,7 @@ appendTree3 (Deep _ pr1 m1 sf1) a b c (Deep _ pr2 m2 sf2) =     deep pr1 (addDigits3 m1 sf1 a b c pr2 m2) sf2 -addDigits3 :: (Measured v a) => FingerTree v (Node v a) -> Digit a -> a -> a -> a -> Digit a -> FingerTree v (Node v a) -> FingerTree v (Node v a)+addDigits3 :: Measured v a => FingerTree v (Node v a) -> Digit a -> a -> a -> a -> Digit a -> FingerTree v (Node v a) -> FingerTree v (Node v a) addDigits3 m1 (One a) b c d (One e) m2 =     appendTree2 m1 (node3 a b c) (node2 d e) m2 addDigits3 m1 (One a) b c d (Two e f) m2 =@@ -659,7 +659,7 @@ addDigits3 m1 (Four a b c d) e f g (Four h i j k) m2 =     appendTree4 m1 (node3 a b c) (node3 d e f) (node3 g h i) (node2 j k) m2 -appendTree4 :: (Measured v a) => FingerTree v a -> a -> a -> a -> a -> FingerTree v a -> FingerTree v a+appendTree4 :: Measured v a => FingerTree v a -> a -> a -> a -> a -> FingerTree v a -> FingerTree v a appendTree4 Empty a b c d xs =     a <| b <| c <| d <| xs appendTree4 xs a b c d Empty =@@ -671,7 +671,7 @@ appendTree4 (Deep _ pr1 m1 sf1) a b c d (Deep _ pr2 m2 sf2) =     deep pr1 (addDigits4 m1 sf1 a b c d pr2 m2) sf2 -addDigits4 :: (Measured v a) => FingerTree v (Node v a) -> Digit a -> a -> a -> a -> a -> Digit a -> FingerTree v (Node v a) -> FingerTree v (Node v a)+addDigits4 :: Measured v a => FingerTree v (Node v a) -> Digit a -> a -> a -> a -> a -> Digit a -> FingerTree v (Node v a) -> FingerTree v (Node v a) addDigits4 m1 (One a) b c d e (One f) m2 =     appendTree2 m1 (node3 a b c) (node3 d e f) m2 addDigits4 m1 (One a) b c d e (Two f g) m2 =@@ -714,7 +714,7 @@ -- -- For predictable results, one should ensure that there is only one such -- point, i.e. that the predicate is /monotonic/.-split ::  (Measured v a) =>+split ::  Measured v a =>       (v -> Bool) -> FingerTree v a -> (FingerTree v a, FingerTree v a) split _ Empty  =  (Empty, Empty) split p xs@@ -728,7 +728,7 @@ -- prefix of @t@ whose measure does not satisfy @p@. -- -- *  @'takeUntil' p t = 'fst' ('split' p t)@-takeUntil :: (Measured v a) => (v -> Bool) -> FingerTree v a -> FingerTree v a+takeUntil :: Measured v a => (v -> Bool) -> FingerTree v a -> FingerTree v a takeUntil p  =  fst . split p  -- | /O(log(min(i,n-i)))/.@@ -736,12 +736,12 @@ -- after removing the largest prefix whose measure does not satisfy @p@. -- -- * @'dropUntil' p t = 'snd' ('split' p t)@-dropUntil :: (Measured v a) => (v -> Bool) -> FingerTree v a -> FingerTree v a+dropUntil :: Measured v a => (v -> Bool) -> FingerTree v a -> FingerTree v a dropUntil p  =  snd . split p  data Split t a = Split !t !a !t deriving (Eq, Show, Generic, NFData) -splitTree :: (Measured v a) =>+splitTree :: Measured v a =>     (v -> Bool) -> v -> FingerTree v a -> Split (FingerTree v a) a splitTree _ _ Empty = illegal_argument "splitTree" splitTree _ _ (Single x) = Split Empty x Empty@@ -758,21 +758,21 @@     vm      =  vpr  `mappendVal` m  -- Avoid relying on right identity (cf Exercise 7)-mappendVal :: (Measured v a) => v -> FingerTree v a -> v+mappendVal :: Measured v a => v -> FingerTree v a -> v mappendVal v Empty = v mappendVal v t     = v `mappend` measure t -deepL :: (Measured v a) =>+deepL :: Measured v a =>     Maybe (Digit a) -> FingerTree v (Node v a) -> Digit a -> FingerTree v a deepL Nothing m sf   =   rotL m sf deepL (Just pr) m sf =   deep pr m sf -deepR :: (Measured v a) =>+deepR :: Measured v a =>     Digit a -> FingerTree v (Node v a) -> Maybe (Digit a) -> FingerTree v a deepR pr m Nothing   =   rotR pr m deepR pr m (Just sf) =   deep pr m sf -splitNode :: (Measured v a) => (v -> Bool) -> v -> Node v a ->+splitNode :: Measured v a => (v -> Bool) -> v -> Node v a ->     Split (Maybe (Digit a)) a splitNode p i (Node2 _ a b)   | p va        = Split Nothing a (Just (One b))@@ -787,7 +787,7 @@     va      = i `mappend` measure a     vab     = va `mappend` measure b -splitDigit :: (Measured v a) => (v -> Bool) -> v -> Digit a ->+splitDigit :: Measured v a => (v -> Bool) -> v -> Digit a ->     Split (Maybe (Digit a)) a splitDigit _ i (One a) = i `seq` Split Nothing a Nothing splitDigit p i (Two a b)@@ -817,7 +817,7 @@ ------------------  -- | /O(n)/. The reverse of a sequence.-reverse :: (Measured v a) => FingerTree v a -> FingerTree v a+reverse :: Measured v a => FingerTree v a -> FingerTree v a reverse = reverseTree id  reverseTree :: (Measured v2 a2) => (a1 -> a2) -> FingerTree v1 a1 -> FingerTree v2 a2

@@ -134,11 +134,11 @@     {-# INLINE mappend #-}  -- | /O(1)/.  The empty interval map.-empty :: (Ord v) => IntervalMap v a+empty :: IntervalMap v a empty = IntervalMap FT.empty  -- | /O(1)/.  Interval map with a single entry.-singleton :: (Ord v) => Interval v -> a -> IntervalMap v a+singleton :: Interval v -> a -> IntervalMap v a singleton i x = IntervalMap (FT.singleton (Node i x))  -- | /O(log n)/.  Insert an interval into a map.

@@ -118,7 +118,7 @@   {-# INLINE mappend #-}  -- | /O(1)/. The empty priority queue.-empty :: Ord k => PQueue k v+empty :: PQueue k v empty = PQueue FT.empty  -- | /O(1)/. A singleton priority queue.@@ -157,7 +157,7 @@ fromList = foldr (uncurry insert) empty  -- | /O(1)/. Is this the empty priority queue?-null :: Ord k => PQueue k v -> Bool+null :: PQueue k v -> Bool null (PQueue q) = FT.null q  -- | /O(1)/ for the element, /O(log(n))/ for the reduced queue.

@@ -108,11 +108,11 @@ --         SegmentMap <$> FT.unsafeTraverse (traverse f) t  -- | /O(1)/.  The empty segment map.-empty :: (Ord k, Bounded k) => SegmentMap k a+empty :: SegmentMap k a empty = SegmentMap (OrderedMap FT.empty)  -- | /O(1)/.  Segment map with a single entry.-singleton :: (Bounded k, Ord k) => Segment k -> a -> SegmentMap k a+singleton :: Segment k -> a -> SegmentMap k a singleton s@(Segment lo hi) a = SegmentMap $ OrderedMap $ FT.singleton $ Item (Max lo) (s, a)  delete :: forall k a. (Bounded k, Ord k, Enum k, Eq a, Show k, Show a)

@@ -110,11 +110,11 @@ --         SegmentSet <$> FT.unsafeTraverse (traverse f) t  -- | /O(1)/.  The empty segment set.-empty :: (Ord k, Bounded k) => SegmentSet k+empty :: SegmentSet k empty = SegmentSet (OrderedMap FT.empty)  -- | /O(1)/.  Segment set with a single entry.-singleton :: (Bounded k, Ord k) => Segment k -> SegmentSet k+singleton :: Segment k -> SegmentSet k singleton s@(Segment lo hi) = SegmentSet $ OrderedMap $ FT.singleton $ Item (Max lo) s  -- | /O(log(n))/. Remove a segment from the set.