depq (empty) → 0.1.0.0

raw patch · 6 files changed

+223/−0 lines, 6 filesdep +basedep +containersdep +deepseqsetup-changed

Dependencies added: base, containers, deepseq, psqueues

Files

ChangeLog.md +4/−0
LICENSE +30/−0
README.md +1/−0
Setup.hs +2/−0
depq.cabal +48/−0
src/Data/DEPQ.hs +138/−0

+ ChangeLog.md view

@@ -0,0 +1,4 @@+# Changelog for depq++## 0.1+First release

+ LICENSE view

@@ -0,0 +1,30 @@+Copyright Marco Zocca (c) 2020++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.++    * Neither the name of Marco Zocca nor the names of other+      contributors may be used to endorse or promote products derived+      from this software without specific prior written permission.++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.

+ README.md view

@@ -0,0 +1,1 @@+# depq

+ Setup.hs view

@@ -0,0 +1,2 @@+import Distribution.Simple+main = defaultMain

+ depq.cabal view

@@ -0,0 +1,48 @@+name:           depq+version:        0.1.0.0+synopsis:       Double-ended priority queues+description:    Double-ended priority queues, for efficient retrieval of minimum and maximum elements in ordered collections of items.+homepage:       https://github.com/ocramz/depq+bug-reports:    https://github.com/ocramz/depq/issues+author:         Marco Zocca+maintainer:     ocramz+category:       Data, Data Structures, Data Mining+cabal-version:  >=1.10+tested-with:    GHC == 8.6.5+copyright:      2020 Marco Zocca+license:        BSD3+license-file:   LICENSE+build-type:     Simple+extra-source-files:+    README.md+    ChangeLog.md++source-repository head+  type: git+  location: https://github.com/ocramz/depq++library+  exposed-modules: Data.DEPQ+  hs-source-dirs:+      src+  build-depends:+      base >=4.7 && <5+    , containers+    , deepseq+    , psqueues+  default-language: Haskell2010++++-- test-suite depq-test+--   type: exitcode-stdio-1.0+--   main-is: Spec.hs+--   other-modules:+--       Paths_depq+--   hs-source-dirs:+--       test+--   ghc-options: -threaded -rtsopts -with-rtsopts=-N+--   build-depends:+--       base >=4.7 && <5+--     , depq+--   default-language: Haskell2010

+ src/Data/DEPQ.hs view

@@ -0,0 +1,138 @@+{-| Double-ended priority queue (DEPQ)++Allows for efficiently finding and removing both the minimum and maximum priority elements, due to the min-heap invariant property of the underlying representation.++See https://en.wikipedia.org/wiki/Double-ended_priority_queue for definitions; the current implementation is based on the "dual structure" method outlined in the wikipedia page.++Based on `P.IntPSQ` : https://hackage.haskell.org/package/psqueues-0.2.7.2/docs/Data-IntPSQ.html+-}+module Data.DEPQ (+   DEPQ,+   -- * Creation+   empty, fromList,+   -- * Predicates+   null,+   -- * Modification+   insert, deleteMin, deleteMax, popMin, popMax,+   -- * Lookup+   findMin, findMax,+   -- ** Top-K lookup+   topK, bottomK+  ) where++import Data.Maybe (fromMaybe)+import Data.Ord (Down(..))++-- containers+import qualified Data.Sequence as S (Seq, empty, (|>))+-- deepseq+import Control.DeepSeq     (NFData (rnf))+-- psqueues+import qualified Data.IntPSQ as P (IntPSQ, empty, null, insert, delete, member, toList, fromList, findMin, delete, deleteMin)++import Prelude hiding (null)++++-- | A double-ended priority queue+data DEPQ p a = DEPQ {+    minHeap :: P.IntPSQ p a+  , maxHeap :: P.IntPSQ (Down p) a+                     } deriving (Eq, Show)++instance (NFData p, NFData a) => NFData (DEPQ p a) where+  rnf (DEPQ mi ma) = rnf mi `seq` rnf ma+++-- | Insert an element+insert :: (Ord p) =>+          Int -- ^ key+       -> p -- ^ priority+       -> a -- ^ value+       -> DEPQ p a -> DEPQ p a+insert k p v (DEPQ mi ma) = DEPQ mi' ma'+  where+    mi' = P.insert k p  v mi+    ma' = P.insert k (Down p) v ma+{-# INLINE insert #-}+++-- | The empty DEPQ+empty :: DEPQ p a+empty = DEPQ P.empty P.empty++-- | Populate a DEPQ from a 'Foldable' container (e.g. a list)+fromList :: (Foldable t, Ord p) =>+            t (Int, p, a) -- ^ (key, priority, value)+         -> DEPQ p a+fromList = foldl insf empty where+  insf acc (k,p,v) = insert k p v acc+{-# inline fromList #-}++-- | Is the DEPQ empty ?+null :: DEPQ p v -> Bool+null (DEPQ mi ma) = P.null mi && P.null ma+++-- | Delete the minimum-priority element in the DEPQ+deleteMin :: Ord p => DEPQ p a -> DEPQ p a+deleteMin de@(DEPQ mi ma) = case P.findMin mi of+  Nothing -> de+  Just (imin, _, _) -> DEPQ mi' ma' where+    mi' = P.deleteMin mi+    ma' = P.delete imin ma+{-# INLINE deleteMin #-}++-- | Delete the maximum-priority element in the DEPQ+deleteMax :: Ord p => DEPQ p a -> DEPQ p a+deleteMax de@(DEPQ mi ma) = case P.findMin ma of+  Nothing -> de+  Just (imax, _, _) -> DEPQ mi' ma' where+    ma' = P.deleteMin ma+    mi' = P.delete imax mi+{-# INLINE deleteMax #-}++-- | /O(1)/ Find the minimum-priority element in the DEPQ+findMin :: Ord p => DEPQ p v -> Maybe (Int, p, v)+findMin (DEPQ mi _) = P.findMin mi+{-# inline findMin #-}++-- | /O(1)/ Find the maximum-priority element in the DEPQ+findMax :: Ord p => DEPQ p v -> Maybe (Int, p, v)+findMax (DEPQ _ ma) = f <$> P.findMin ma+  where+    f (i, Down p, v) = (i, p, v)+{-# inline findMax #-}+++-- | Return the minimum along with a new DEPQ without that element+popMin :: Ord p => DEPQ p v -> Maybe ((Int, p, v), DEPQ p v)+popMin q = do+  x <- findMin q+  let q' = deleteMin q+  pure (x, q')++-- | Return the maximum along with a new DEPQ without that element+popMax :: Ord p => DEPQ p v -> Maybe ((Int, p, v), DEPQ p v)+popMax q = do+  x <- findMax q+  let q' = deleteMax q+  pure (x, q')++-- | K highest-scoring entries in the DEPQ+topK :: Ord p => Int -> DEPQ p v -> S.Seq (Int, p, v)+topK = popK popMax++-- | K lowest-scoring entries in the DEPQ+bottomK :: Ord p => Int -> DEPQ p v -> S.Seq (Int, p, v)+bottomK = popK popMin++popK :: (q -> Maybe (a, q))+     -> Int+     -> q+     -> S.Seq a+popK pop kk qq = fromMaybe S.empty $ go qq kk S.empty where+  go _ 0 acc = pure acc+  go q k acc = do+    (x, q') <- pop q+    go q' (k - 1) (acc S.|> x)