heap 0.1 → 0.1.1

raw patch · 3 files changed

+45/−18 lines, 3 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

Files

Data/Heap.hs +20/−16
LICENSE +22/−0
heap.cabal +3/−2

Data/Heap.hs view

@@ -1,7 +1,7 @@-{-# LANGUAGE MultiParamTypeClasses, FlexibleInstances #-}+{-# LANGUAGE EmptyDataDecls, FlexibleInstances, MultiParamTypeClasses #-}  -- | --- An efficent implementation of min-, max- or custom-priority heaps+-- A flexible implementation of min-, max- or custom-priority heaps -- based on the leftist-heaps from Chris Okasaki's book \"Purely Functional Data -- Structures\", Cambridge University Press, 1998, chapter 3.1. --@@ -33,7 +33,6 @@  import Data.List (foldl') import Data.Monoid-import Data.Ord import Prelude hiding (head, null)  -- |@@ -75,20 +74,25 @@ -- a 'Heap'. class HeapPolicy p a where 	-- |-	-- Compare two elements, just like 'compare' of the 'Ord' class.-	-- /The first parameter must be ignored by the implementation/.-	heapCompare :: p -> a -> a -> Ordering+	-- Compare two elements, just like 'compare' of the 'Ord' class,+	-- so this function has to define a mathematical ordering.+	-- When using a 'HeapPolicy' for a 'Heap', the minimal value+	-- (defined by this order) will be the 'head' of the 'Heap'.+	heapCompare :: p    -- ^ /Must not be used/.+		-> a        -- ^ Must be compared to 3rd parameter.+		-> a        -- ^ Must be compared to 2nd parameter.+		-> Ordering -- ^ Result of the comparison.  -- | -- Policy type for a 'MinHeap'.-data MinPolicy = MinPolicy+data MinPolicy  instance (Ord a) => HeapPolicy MinPolicy a where 	heapCompare = const compare  -- | -- Policy type for a 'MaxHeap'-data MaxPolicy = MaxPolicy+data MaxPolicy  instance (Ord a) => HeapPolicy MaxPolicy a where 	heapCompare = const (flip compare)@@ -119,7 +123,7 @@ -- | -- /O(n)/. The number of elements in the 'Heap'. size :: (Num n) => Heap p a -> n-size Empty = 0+size Empty          = 0 size (Tree _ _ a b) = 1 + size a + size b  -- |@@ -165,7 +169,7 @@ 	else makeT y l2 (union r2 heap1) -- heap into the right branch, it's shorter  -- |--- Combines a value x and two 'Heaps' to one 'Heap'. Therefore, x has to+-- Combines a value @x@ and two 'Heaps' 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/. makeT :: a -> Heap p a -> Heap p a -> Heap p a@@ -200,7 +204,7 @@  -- | -- /O(n)/. Creates a 'Heap' from an ascending list. Note that the list--- has to be ascending corresponding to the 'HeapPolicy', not to it's+-- has to be ascending corresponding to the 'HeapPolicy', not to its -- 'Ord' instance declaration (if there is one). -- /The precondition is not checked/. fromAscList :: (HeapPolicy p a) => [a] -> Heap p a@@ -213,7 +217,7 @@ -- to the 'HeapPolicy'). toAscList :: (HeapPolicy p a) => Heap p a -> [a] toAscList Empty            = []-toAscList h@(Tree _ x a b) = x : mergeLists (toAscList a) (toAscList b)+toAscList h@(Tree _ e a b) = e : mergeLists (toAscList a) (toAscList b) 	where	mergeLists [] ys = ys 		mergeLists xs [] = xs 		mergeLists xs@(x:xs') ys@(y:ys') = if LT == heapCompare (policy h) x y@@ -228,10 +232,10 @@ check h@(Tree r x left right) = let 		leftRank  = rank left 		rightRank = rank right-	in (isEmpty left || LT /= heapCompare (policy h) (head left) x)-		&& (isEmpty right || LT /= heapCompare (policy h) (head right) x)-		&& r == 1 + rightRank-		&& leftRank >= rightRank+	in (null left || LT /= heapCompare (policy h) (head left) x) -- heap property+		&& (null right || LT /= heapCompare (policy h) (head right) x) -- dito+		&& r == 1 + rightRank    -- rank = length of right spine+		&& leftRank >= rightRank -- leftist property 		&& check left 		&& check right

+ LICENSE view

@@ -0,0 +1,22 @@+Copyright (c) 2008, Stephan Friedrichs+All rights reserved.++Redistribution and use in source and binary forms, with or without+modification, are permitted provided that the following conditions are met:+    * Redistributions of source code must retain the above copyright+      notice, this list of conditions and the following disclaimer.+    * Redistributions in binary form must reproduce the above copyright+      notice, this list of conditions and the following disclaimer in the+      documentation and/or other materials provided with the distribution.++THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS+"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT+LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR+A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR+CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,+EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,+PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR+PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF+LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING+NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS+SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

heap.cabal view

@@ -1,7 +1,8 @@ Name:			heap-Version:		0.1+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@@ -9,4 +10,4 @@ Description:		A flexible Haskell heap implementation Build-Depends:		base Exposed-Modules:	Data.Heap-ghc-options:		-O+ghc-options:		-O -Wall