heap 0.1.1 → 0.2

raw patch · 2 files changed

+119/−27 lines, 2 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

Files

• Data/Heap.hs +101/−14
• heap.cabal +18/−13

@@ -1,4 +1,4 @@-{-# LANGUAGE EmptyDataDecls, FlexibleInstances, MultiParamTypeClasses #-}+{-# LANGUAGE CPP, EmptyDataDecls, FlexibleInstances, MultiParamTypeClasses #-}  -- |  -- A flexible implementation of min-, max- or custom-priority heaps@@ -18,10 +18,15 @@ 	-- * Query 	null, isEmpty, size, head, 	-- * Construction-	empty, singleton,-	insert, deleteHead, extractHead,-	-- * Combine+	empty, singleton, insert,+	tail, extractHead,+	-- * Union 	union, unions,+	-- * Filter+	filter, partition,+	-- * Subranges+	take, drop, splitAt,+	takeWhile, span, break, 	-- * Conversion 	-- ** Lists 	fromList, toList, elems,@@ -31,9 +36,11 @@ 	check ) where +import Data.Foldable (Foldable(foldMap)) import Data.List (foldl') import Data.Monoid-import Prelude hiding (head, null)+import Prelude hiding (break, drop, filter, head, null, tail, span, splitAt, take, takeWhile)+import Text.Read  -- | -- The basic 'Heap' type.@@ -69,6 +76,24 @@ 	mappend = union 	mconcat = unions +instance Foldable (Heap p) where+	foldMap _ Empty          = mempty+	foldMap f (Tree _ x l r) = foldMap f l `mappend` f x `mappend` foldMap f r++instance (HeapPolicy p a, Read a) => Read (Heap p a) where+#ifdef __GLASGOW_HASKELL__+	readPrec = parens $ prec 10 $ do+		Ident "fromList" <- lexP+		xs <- readPrec+		return (fromList xs)+	readListPrec = readListPrecDefault+#else+	readsPrec p = readParen (p > 10) $ \r -> do+		("fromList", s) <- lex r+		(xs, t) <- reads s+		return (fromList xs, t)+#endif+ -- | -- The 'HeapPolicy' class defines an order on the elements contained within -- a 'Heap'.@@ -124,7 +149,7 @@ -- /O(n)/. The number of elements in the 'Heap'. size :: (Num n) => Heap p a -> n size Empty          = 0-size (Tree _ _ a b) = 1 + size a + size b+size (Tree _ _ l r) = 1 + size l + size r  -- | -- /O(1)/. Finds the minimum (depending on the 'HeapPolicy') of the 'Heap'.@@ -149,17 +174,61 @@ -- | -- /O(log n)/. Delete the minimum (depending on the 'HeapPolicy') -- from the 'Heap'.-deleteHead :: (HeapPolicy p a) => Heap p a -> Heap p a-deleteHead = snd . extractHead+tail :: (HeapPolicy p a) => Heap p a -> Heap p a+tail = snd . extractHead  -- | -- /O(log n)/. Find the minimum (depending on the 'HeapPolicy') and -- delete it from the 'Heap'. extractHead :: (HeapPolicy p a) => Heap p a -> (a, Heap p a)-extractHead Empty          = (error "Heap is empty", Empty)-extractHead (Tree _ x a b) = (x, union a b)+extractHead Empty          = (error "Heap is empty", empty)+extractHead (Tree _ x l r) = (x, union l r)  -- |+-- Take the lowest @n@ elements in ascending order of the+-- 'Heap' (according to the 'HeapPolicy').+take :: (HeapPolicy p a) => Int -> Heap p a -> [a]+take n = fst . (splitAt n)++-- |+-- Remove the lowest (according to the 'HeapPolicy') @n@ elements+-- from the 'Heap'.+drop :: (HeapPolicy p a) => Int -> Heap p a -> Heap p a+drop n = snd . (splitAt n)++-- |+-- @'splitAt' n h@ returns an ascending list of the lowest @n@+-- elements of @h@ (according to its 'HeapPolicy') and a 'Heap'+-- like @h@, lacking those elements.+splitAt :: (HeapPolicy p a) => Int -> Heap p a -> ([a], Heap p a)+splitAt _ Empty     = ([], empty)+splitAt n heap@(Tree _ x l r)+	| n > 0     = let (xs, heap') = splitAt (n-1) (union l r) in (x:xs, heap')+	| otherwise = ([], heap)++-- |+-- @'takeWhile' p h@ lists the longest prefix of elements in ascending+-- order (according to its 'HeapPolicy') of @h@ that satisfy @p@.+takeWhile :: (HeapPolicy p a) => (a -> Bool) -> Heap p a -> [a]+takeWhile p = fst . (span p)++-- |+-- @'span' p h@ returns the longest prefix of elements in ascending+-- order (according to its 'HeapPolicy') of @h@ that satisfy @p@ and+-- a 'Heap' like @h@, lacking those elements.+span :: (HeapPolicy p a) => (a -> Bool) -> Heap p a -> ([a], Heap p a)+span _ Empty        = ([], empty)+span p heap@(Tree _ x l r)+	| p x       = let (xs, heap') = span p (union l r) in (x:xs, heap')+	| otherwise = ([], heap)+-- |+-- @'break' p h@ returns the longest prefix of elements in ascending+-- order (according to its 'HeapPolicy') of @h@ that do /not/ satisfy @p@+-- and a 'Heap' like @h@, lacking those elements.+break :: (HeapPolicy p a) => (a -> Bool) -> Heap p a -> ([a], Heap p a)+break p = span (not . p)++-- | -- /O(log max(n, m))/. The union of two 'Heap's. union :: (HeapPolicy p a) => Heap p a -> Heap p a -> Heap p a union h Empty = h@@ -186,6 +255,24 @@ unions = foldl' union empty  -- |+-- Removes all elements from a given 'Heap' that do not fulfil the+-- predicate.+filter :: (HeapPolicy p a) => (a -> Bool) -> Heap p a -> Heap p a+filter p = fst . (partition p)++-- |+-- Partition the 'Heap' into two. @'partition' p h = (h1, h2)@:+-- All elements in @h1@ fulfil the predicate @p@, those in @h2@ don't.+-- @'union' h1 h2 = h@.+partition :: (HeapPolicy p a) => (a -> Bool) -> Heap p a -> (Heap p a, Heap p a)+partition _ Empty   = (empty, empty)+partition p (Tree _ x l r)+	| p x       = (makeT x l1 r1, union l2 r2)+	| otherwise = (union l1 r1, makeT x l2 r2)+	where	(l1, l2) = partition p l+		(r1, r2) = partition p r++-- | -- Builds a 'Heap' from the given elements. -- You may want to use 'fromAscList', if you have a sorted list. fromList :: (HeapPolicy p a) => [a] -> Heap p a@@ -195,7 +282,7 @@ -- /O(n)/. Lists elements of the 'Heap' in no specific order. toList :: Heap p a -> [a] toList Empty          = []-toList (Tree _ x a b) = x : toList a ++ toList b+toList (Tree _ x l r) = x : toList l ++ toList r  -- | -- /O(n)/. Lists elements of the 'Heap' in no specific order.@@ -208,8 +295,8 @@ -- 'Ord' instance declaration (if there is one). -- /The precondition is not checked/. fromAscList :: (HeapPolicy p a) => [a] -> Heap p a---fromAscList []     = Empty---fromAscList (x:xs) = Tree 1 x (fromAscList xs) Empty+--fromAscList []     = empty+--fromAscList (x:xs) = Tree 1 x (fromAscList xs) empty fromAscList = fromList -- Just as fast, but needs less memory. Why?  -- |@@ -217,7 +304,7 @@ -- to the 'HeapPolicy'). toAscList :: (HeapPolicy p a) => Heap p a -> [a] toAscList Empty            = []-toAscList h@(Tree _ e a b) = e : mergeLists (toAscList a) (toAscList b)+toAscList h@(Tree _ e l r) = e : mergeLists (toAscList l) (toAscList r) 	where	mergeLists [] ys = ys 		mergeLists xs [] = xs 		mergeLists xs@(x:xs') ys@(y:ys') = if LT == heapCompare (policy h) x y

@@ -1,13 +1,18 @@-Name:			heap-Version:		0.1.1-Stability:		beta-License:		BSD3-License-File:		LICENSE-Author:			Stephan Friedrichs-Maintainer:		stephan[dot]friedrichs[at]tu-bs[dot]de-Category:		Data-Synopsis:		Heaps in Haskell-Description:		A flexible Haskell heap implementation-Build-Depends:		base-Exposed-Modules:	Data.Heap-ghc-options:		-O -Wall+Name:          heap+Version:       0.2+Stability:     beta+Category:      Data+Synopsis:      Heaps in Haskell+Description:   A flexible Haskell heap implementation+License:       BSD3+License-File:  LICENSE+Copyright:     (c) 2008, Stephan Friedrichs+Author:        Stephan Friedrichs+Maintainer:    stephan[dot]friedrichs[at]tu-bs[dot]de+Build-Type:    Custom+Cabal-Version: >=1.2++Library+  Build-Depends:   base+  Exposed-Modules: Data.Heap+  ghc-options:     -O2 -Wall