heap 0.5.0 → 0.6.0

raw patch · 6 files changed

+125/−80 lines, 6 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

Files

• Data/Heap.hs +77/−35
• LICENSE +1/−1
• Test.lhs +11/−0
• Test/Heap.hs +30/−28
• Tests.lhs +0/−11
• heap.cabal +6/−5

@@ -10,10 +10,10 @@ --  * Choose 'MinHeap' or 'MaxHeap' if you need a simple minimum or maximum heap --    (which always keeps the minimum/maximum element at the head of the 'Heap'). -----  * If you wish to manually annotate a value with a priority, e. g. an---    @'IO' ()@ action with an 'Int' use 'MinPrioHeap' or 'MaxPrioHeap'. They---    manage @(priority, value)@ tuples so that only the priority (and not the---    value) influences the order of elements.+--  * If you wish to manually annotate a value with a priority, e. g. an @IO ()@+--    action with an 'Int' use 'MinPrioHeap' or 'MaxPrioHeap'. They manage+--    @(priority, value)@ tuples so that only the priority (and not the value)+--    influences the order of elements. -- --  * If you still need something different, define a custom order for the heap --    elements by implementing a 'HeapPolicy' and let the maintainer know,@@ -35,9 +35,7 @@       -- * Query     , null, isEmpty, size, head, tail, view, extractHead       -- * Construction-    , empty, singleton, insert-      -- * Union-    , union, unions+    , empty, singleton, insert, union, unions       -- * Filter     , filter, partition       -- * Subranges@@ -48,14 +46,18 @@     , fromList, toList, elems       -- ** Ordered list     , fromAscList, toAscList+    , fromDescList, toDescList     ) where  import Data.Foldable ( foldl' )-import Data.Monoid-import Data.Ord+import Data.List ( sortBy )+import Data.Monoid ( Monoid(..) )+import Data.Ord ( comparing ) import Prelude hiding ( break, drop, dropWhile, filter, head, null, tail, span                       , splitAt, take, takeWhile )+#ifdef __GLASGOW_HASKELL__ import Text.Read+#endif  -- | The basic 'Heap' type. data Heap p a@@ -65,7 +67,7 @@ -- | A 'Heap' which will always extract the minimum first. type MinHeap a = Heap MinPolicy a --- | A 'Heap' with inverted order: The maximum will be extracted first.+-- | A 'Heap' which will always extract the maximum first. type MaxHeap a = Heap MaxPolicy a  -- | A 'Heap' storing priority-value-associations. It only regards the priority@@ -81,6 +83,20 @@ instance (Show a) => Show (Heap p a) where     show = ("fromList " ++) . show . toList +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+ instance (HeapPolicy p a) => Eq (Heap p a) where     h1 == h2 = EQ == compare h1 h2 @@ -98,20 +114,6 @@     mappend = union     mconcat = unions -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'. class HeapPolicy p a where@@ -175,14 +177,14 @@ -- | /O(1)/. Returns the first item of the 'Heap', according to its 'HeapPolicy'. -- -- /Warning:/ This function issues an 'error' for empty 'Heap's, please consider--- using the 'view' function instead, it's not partial.+-- using the 'view' function instead, it's safe. head :: (HeapPolicy p a) => Heap p a -> a head = fst . extractHead  -- | /O(log n)/. Returns the 'Heap' with the 'head' removed. -- -- /Warning:/ This function issues an 'error' for empty 'Heap's, please consider--- using the 'view' function instead, it's not partial.+-- using the 'view' function instead, it's safe. tail :: (HeapPolicy p a) => Heap p a -> Heap p a tail = snd . extractHead @@ -192,13 +194,12 @@ view :: (HeapPolicy p a) => Heap p a -> Maybe (a, Heap p a) view Empty            = Nothing view (Tree _ _ x l r) = Just (x, union l r)- {-# INLINE view #-}  -- | /O(log n)/. Returns 'head' and 'tail' of a 'Heap'. -- -- /Warning:/ This function issues an 'error' for empty 'Heap's, please consider--- using the 'view' function instead, it's not partial.+-- using the 'view' function instead, it's safe. extractHead :: (HeapPolicy p a) => Heap p a -> (a, Heap p a) extractHead heap = maybe (error (__FILE__ ++ ": empty heap in extractHead")) id (view heap) @@ -214,6 +215,14 @@ insert :: (HeapPolicy p a) => a -> Heap p a -> Heap p a insert x h = union h (singleton x) +-- | /O(1)/. Insert an element into the 'Heap' that is smaller than all elements+-- currently in the 'Heap' (according to the 'HeapPolicy'), i. e. an element+-- that will be the new 'head' of the 'Heap'.+--+-- /The precondition is not checked/.+insertMin :: (HeapPolicy p a) => a -> Heap p a -> Heap p a+insertMin h hs = Tree 1 (1 + size hs) h hs empty+ -- | Take the lowest @n@ elements in ascending order of the 'Heap' (according -- to the 'HeapPolicy'). take :: (HeapPolicy p a) => Int -> Heap p a -> [a]@@ -270,7 +279,9 @@  -- | Combines a value @x@ and two 'Heap's to one 'Heap'. Therefore, @x@ has to -- be less or equal the minima (depending on the 'HeapPolicy') of both 'Heap'--- parameters. /The precondition is not checked/.+-- parameters.+--+-- /The precondition is not checked/. makeT :: a -> Heap p a -> Heap p a -> Heap p a makeT x a b = let     ra = rank a@@ -279,10 +290,19 @@     in if ra > rb         then Tree (rb + 1) s x a b         else Tree (ra + 1) s x b a+{-# INLINE makeT #-}  -- | Builds the union over all given 'Heap's. unions :: (HeapPolicy p a) => [Heap p a] -> Heap p a-unions = foldl' union empty+unions heaps = case tournamentFold' heaps of+    []  -> empty+    [h] -> h+    hs  -> unions hs+    where+    tournamentFold' :: (Monoid m) => [m] -> [m]+    tournamentFold' (x1:x2:xs) = (: tournamentFold' xs) $! mappend x1 x2+    tournamentFold' xs         = xs+    {-# INLINE tournamentFold' #-}  -- | 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@@ -299,10 +319,13 @@     (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.+-- | Builds a 'Heap' from the given elements. Assuming you have a sorted list,+-- you may want to use 'fromDescList' or 'fromAscList', they are both faster+-- than this function. fromList :: (HeapPolicy p a) => [a] -> Heap p a-fromList = unions . (map singleton)+fromList xs = let+    heap = fromDescList $ sortBy (flip (heapCompare (policy heap))) xs+    in heap  -- | /O(n)/. Lists elements of the 'Heap' in no specific order. toList :: Heap p a -> [a]@@ -317,11 +340,30 @@  -- | /O(n)/. Creates a 'Heap' from an ascending list. Note that the list has to -- be ascending corresponding to the 'HeapPolicy', not to its 'Ord' instance--- declaration (if there is one). /The precondition is not checked/.+-- declaration (if there is one). This function is faster than 'fromList' but+-- not as fast as 'fromDescList'.+--+-- /The precondition is not checked/. fromAscList :: (HeapPolicy p a) => [a] -> Heap p a-fromAscList = fromList+fromAscList = fromDescList . reverse  -- | /O(n)/. Lists elements of the 'Heap' in ascending order (corresponding to -- the 'HeapPolicy'). toAscList :: (HeapPolicy p a) => Heap p a -> [a] toAscList = takeWhile (const True)++-- | /O(n)/. Create a 'Heap' from a descending list. Note that the list has to+-- be descending corresponding to the 'HeapPolicy', not to its 'Ord' instance+-- declaration (if there is one). This function is provided, because it is much+-- faster than 'fromList' and 'fromAscList'.+--+-- /The precondition is not checked/.+fromDescList :: (HeapPolicy p a) => [a] -> Heap p a+fromDescList = foldl' (flip insertMin) empty++-- | /O(n)/. Lists the elements on the 'Heap' in descending order (corresponding+-- to the 'HeapPolicy'). Note that this function is not especially efficient (it+-- is implemented as @'reverse' . 'toAscList'@), it is just provided as a+-- counterpart of the very efficient 'fromDescList' function.+toDescList :: (HeapPolicy p a) => Heap p a -> [a]+toDescList = reverse . toAscList

@@ -1,4 +1,4 @@-Copyright (c) 2008, Stephan Friedrichs+Copyright (c) 2008-2009, Stephan Friedrichs All rights reserved.  Redistribution and use in source and binary forms, with or without

@@ -0,0 +1,11 @@+#! /usr/bin/runghc -D__DEBUG__++>+> module Main where+>+> import Test.Heap+>+> main :: IO ()+> main = testHeap+>+

@@ -8,31 +8,26 @@  testHeap :: IO () testHeap = do-    putStr "Leftist property of MinHeap Int: "-    quickCheck (leftistHeapProperty :: MinHeap Int -> Bool)-    putStr "Leftist property of MaxHeap Int: "-    quickCheck (leftistHeapProperty :: MaxHeap Int -> Bool)-    putStr "Size property:                   "-    quickCheck sizeProperty-    putStr "Order property:                  "-    quickCheck orderProperty-    putStr "head/tail property:              "-    quickCheck headTailProperty-    putStr "take/drop/splitAt                "-    quickCheck (takeDropSplitAtProperty :: Int -> MinHeap Int -> Bool)-    putStr "takeWhile/span/break             "-    quickCheck takeWhileSpanBreakProperty-    putStr "read . show === id               "-    quickCheck (readShowProperty :: MinHeap Int -> Bool)-    putStr "fromList vs. fromAscList         "-    quickCheck (fromListProperty :: [Int] -> Bool)-    putStr "toList === elems                 "-    quickCheck (toListProperty :: MaxHeap Int -> Bool)-    putStr "partition and filter             "-    quickCheck (partitionFilterProperty (\x -> x `mod` 2 == 0) :: MinHeap Int -> Bool)-    putStr "ordering property                "-    quickCheck (orderingProperty :: MinHeap Int -> MinHeap Int -> Bool)+    qc "Leftist property of MinHeap Int" (leftistHeapProperty :: MinHeap Int -> Bool)+    qc "Leftist property of MaxHeap Int" (leftistHeapProperty :: MaxHeap Int -> Bool)+    qc "Size property" sizeProperty+    qc "Order property" orderProperty+    qc "head/tail property" headTailProperty+    qc "take/drop/splitAt" (takeDropSplitAtProperty :: Int -> MinHeap Int -> Bool)+    qc "takeWhile/span/break" takeWhileSpanBreakProperty+    qc "read . show === id" (readShowProperty :: MinHeap Int -> Bool)+    qc "{from,to}{,Asc,Desc}List" (listProperty :: [Int] -> Bool)+    qc "toList === elems" (toListProperty :: MaxHeap Int -> Bool)+    qc "partition and filter" (partitionFilterProperty testProperty :: MinHeap Int -> Bool)+    qc "ordering property" (orderingProperty :: MinHeap Int -> MinHeap Int -> Bool)+    where+    testProperty x = x `mod` 2 == 0 +qc :: (Testable prop) => String -> prop -> IO ()+qc msg prop = quickCheck+    $ whenFail (putStrLn msg)+    $ label msg prop+ instance (Arbitrary a, HeapPolicy p a) => Arbitrary (Heap p a) where     arbitrary = do         len  <- choose (0, 100)@@ -109,11 +104,18 @@ readShowProperty :: (HeapPolicy p a, Show a, Read a) => Heap p a -> Bool readShowProperty heap = heap == read (show heap) -fromListProperty :: [Int] -> Bool-fromListProperty xs = let-    xs' = sort xs+listProperty :: [Int] -> Bool+listProperty xs = let+    xsAsc  = sort xs+    xsDesc = reverse xsAsc+    h1     = fromList xs         :: MinHeap Int+    h2     = fromAscList xsAsc   :: MinHeap Int+    h3     = fromDescList xsDesc :: MinHeap Int     in-    (fromList xs' :: MinHeap Int) == (fromAscList xs' :: MinHeap Int)+    (h1 == h2) && (h2 == h3)+        && (and (map leftistHeapProperty [h1, h2, h3]))+        && (and (map ((== xsAsc) . toAscList) [h1, h2, h3]))+        && (and (map ((== xsDesc) . toDescList) [h1, h2, h3]))  toListProperty :: (HeapPolicy p a, Eq a) => Heap p a -> Bool toListProperty heap = toList heap == elems heap

@@ -1,11 +0,0 @@-#! /usr/bin/runghc -D__DEBUG__-->-> module Main where->-> import Test.Heap->-> main :: IO ()-> main = testHeap->-

@@ -1,6 +1,6 @@  Name:                heap-Version:             0.5.0+Version:             0.6.0 Stability:           beta  Category:            Data Structures@@ -9,18 +9,19 @@  License:             BSD3 License-File:        LICENSE-Copyright:           (c) 2008, Stephan Friedrichs+Copyright:           (c) 2008-2009, Stephan Friedrichs  Author:              Stephan Friedrichs Maintainer:          Stephan Friedrichs (deduktionstheorem at web dot de)  Build-Type:          Simple Cabal-Version:       >= 1.2-Extra-Source-Files:  Tests.lhs, Test/Heap.hs+Extra-Source-Files:  Test.lhs, Test/Heap.hs+Tested-With:         GHC, Hugs  Library   Build-Depends:     base   Exposed-Modules:   Data.Heap-  ghc-options:       -O2 -Wall-  Extensions:        CPP+  GHC-Options:       -Wall -fwarn-tabs+  Extensions:        CPP, EmptyDataDecls, FlexibleInstances, MultiParamTypeClasses