module Numeric.StreamingHistogram.Internal
( shrink
) where
import qualified Data.List as L
-- Internal: Lossy compression of histogram by finding the pair of
-- values that would introduce minimum error when merged and then do a
-- weighted merge.
shrink :: [(Double, Int)] -> [(Double, Int)]
shrink m
| length m == 0 = m
| otherwise = shrunk'
where
deltas = L.zipWith (\(x, _) (y, _)-> y - x) (init m) (L.tail m)
minDelta = L.minimum deltas
shrunk' = shrunk (init m) (L.tail m)
shrunk :: [(Double, Int)] -> [(Double, Int)] -> [(Double, Int)]
shrunk [] [] = []
shrunk ((lq, lk):ls) ((rq, rk):rs)
| rq - lq == minDelta = ((lq * (fromIntegral lk) + rq * (fromIntegral rk)) / (fromIntegral (lk + rk)), lk + rk) : rs
| otherwise = (lq, lk) : (shrunk ls rs)