median-stream (empty) → 0.1.0.0

raw patch · 5 files changed

+200/−0 lines, 5 filesdep +QuickCheckdep +basedep +heapsetup-changed

Dependencies added: QuickCheck, base, heap, median-stream

Files

LICENSE +29/−0
Setup.hs +2/−0
median-stream.cabal +36/−0
src/Data/MedianStream.hs +91/−0
test/Spec.hs +42/−0

+ LICENSE view

@@ -0,0 +1,29 @@+BSD 3-Clause License++Copyright (c) 2016, Joe Canero+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 the copyright holder nor the names of its+  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 HOLDER 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.

+ Setup.hs view

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

+ median-stream.cabal view

@@ -0,0 +1,36 @@+name:                median-stream+version:             0.1.0.0+synopsis:            Constant-time queries for the median of a stream of numeric+                     data.+description:         Uses the two-heap approach to support O(lg n) insertions+                     and O(1) queries for the median.+homepage:            https://github.com/caneroj1/median-stream#readme+license:             BSD3+license-file:        LICENSE+author:              Joe Canero+maintainer:          jmc41493@gmail.com+copyright:           Copyright: (c) 2016 Joe Canero+category:            Data+build-type:          Simple+cabal-version:       >=1.10++library+  hs-source-dirs:      src+  exposed-modules:     Data.MedianStream+  build-depends:       base >= 4.7 && < 5+                     , heap+  default-language:    Haskell2010++test-suite median-stream-test+  type:                exitcode-stdio-1.0+  hs-source-dirs:      test+  main-is:             Spec.hs+  build-depends:       base+                     , median-stream+                     , QuickCheck+  ghc-options:         -threaded -rtsopts -with-rtsopts=-N+  default-language:    Haskell2010++source-repository head+  type:     git+  location: https://github.com/caneroj1/median-stream

+ src/Data/MedianStream.hs view

@@ -0,0 +1,91 @@+{-|+Module      : Data.MedianStream+Description : Main module+Copyright   : (c) Joseph Canero, 2016+License     : BSD-3+Maintainer  : jmc41493@gmail.com+Stability   : experimental+Portability : POSIX+-}++{-# LANGUAGE GADTs #-}++module Data.MedianStream+(+  MedianStream+, (+>)+, (<+)+, empty+, insert+, median+, size+) where++import Data.Heap (MaxHeap, MinHeap, Heap)+import qualified Data.Heap as Heap hiding (MaxHeap, MinHeap, Heap)+import Data.Maybe (fromJust)++type Left a  = MaxHeap a+type Right a = MinHeap a++-- | A MedianStream is a data type that can be inserted into and queried+-- to get a median of a stream of numeric values.+data MedianStream a where+  MedianStream :: (Real a, Eq a) => Left a -> Right a -> MedianStream a++-- Infix wrapper around insert with the MedianStream on the left.+-- Complexity: O(lgn)+(+>) :: MedianStream a -> a -> MedianStream a+(+>) ms a = insert a ms++-- Infix wrapper around insert with the MedianStream on the right.+-- Complexity: O(lgn)+(<+) :: a -> MedianStream a -> MedianStream a+(<+) = insert++-- Create an empty MedianStream with no values.+-- Complexity: O(1)+empty :: (Real a, Eq a) => MedianStream a+empty = MedianStream Heap.empty Heap.empty++-- Insert a new numeric value into the median stream.+-- Complexity: O(lgn)+insert :: a -> MedianStream a -> MedianStream a+insert a ms@(MedianStream lh rh)+  | even $ size ms = oddMedianStream+  | otherwise      = evenMedianStream+    where+      oddMedianStream+        | maybe False (a >=) $ Heap.viewHead rh =+          uncurry MedianStream $ popAndSwap lh rh a+        | otherwise = MedianStream (Heap.insert a lh) rh+      evenMedianStream+        | maybe False (a < ) $ Heap.viewHead lh =+          uncurry (flip MedianStream) $ popAndSwap rh lh a+        | otherwise = MedianStream lh (Heap.insert a rh)++median :: MedianStream a -> Maybe Double+median ms@(MedianStream lh rh)+  | even $ size ms = average <$> Heap.viewHead lh <*> Heap.viewHead rh+  | otherwise      = (fromRational . toRational) <$> Heap.viewHead lh++-- Returns the number of elements in the MedianStream.+-- Complexity: O(1)+size :: MedianStream a -> Int+size (MedianStream lh rh) = Heap.size lh + Heap.size rh++popAndSwap :: (Heap.HeapItem pol1 a,+               Heap.HeapItem pol2 a)+           => Heap pol1 a+           -> Heap pol2 a+           -> a+           -> (Heap pol1 a, Heap pol2 a)+popAndSwap lh rh a =+  let+    ([top], srh) = Heap.splitAt 1 rh+    nlh          = Heap.insert top lh+    nrh          = Heap.insert a   srh+    in (nlh, nrh)++average :: (Real a) => a -> a -> Double+average x l = (/2 ) . fromRational $ toRational (x + l)

+ test/Spec.hs view

@@ -0,0 +1,42 @@+{-# LANGUAGE TemplateHaskell #-}++import Data.List hiding (insert)+import Data.MedianStream+import Test.QuickCheck++prop_medianStreamOnInts :: [Int] -> Bool+prop_medianStreamOnInts xs = medianOf xs == median (foldr insert empty xs)++prop_medianStreamOnDoubles :: [Double] -> Bool+prop_medianStreamOnDoubles xs = medianOf xs == median (foldr insert empty xs)++prop_medianStreamOnIntsV2 :: [Int] -> Bool+prop_medianStreamOnIntsV2 xs = medianOf xs == median (foldr (<+) empty xs)++prop_medianStreamOnDoublesV2 :: [Double] -> Bool+prop_medianStreamOnDoublesV2 xs = medianOf xs == median (foldr (<+) empty xs)++prop_medianStreamOnIntsV3 :: [Int] -> Bool+prop_medianStreamOnIntsV3 xs = medianOf xs == median (foldl' (+>) empty xs)++prop_medianStreamOnDoublesV3 :: [Double] -> Bool+prop_medianStreamOnDoublesV3 xs = medianOf xs == median (foldl' (+>) empty xs)++medianOf :: (Real a, Eq a) => [a] -> Maybe Double+medianOf []  = Nothing+medianOf [x] = Just . fromRational $ toRational x+medianOf xs  =+  let sorted = sort xs+      len    = length xs+    in case even len of+      True  -> let [x, y] = take 2 $ drop (len `div` 2 - 1) sorted+                in Just $ average x y+      False -> medianOf . take 1 $ drop (len `div` 2) sorted++average :: (Real a) => a -> a -> Double+average x l = (/2) . fromRational $ toRational (x + l)++return []+runTests = $quickCheckAll++main = runTests