Naive.hs

-----------------------------------------------------------------------------
-- |
-- Module      :  Squares.BruteForce
-- Copyright   :  (c) Dmitry Astapov 2010
-- License     :  BSD-style
-- Maintainer  :  dastapov@gmail.com
-- Stability   :  experimental
-- Portability :  portable
--
-- Brute-force stabbing query
-----------------------------------------------------------------------------
module Stabbing.Naive (counts) where

import Data.List (genericLength)

-- Naive implementation of stabbing count:
-- check points against all ranges, count the hits
counts :: [(Rational, Rational)] -> [Rational] -> [Integer]
counts ranges points = map (stabCount ranges) points
  where stabCount ranges point = genericLength $ filter (point `inside`) ranges
        inside point (lower, upper) = lower <= point && point <= upper