ranges 0.1 → 0.2

raw patch · 3 files changed

+51/−16 lines, 3 filesdep +containersPVP ok

version bump matches the API change (PVP)

Dependencies added: containers

API changes (from Hackage documentation)

Files

• Data/Ranges.hs +44/−13
• LICENSE +1/−0
• ranges.cabal +6/−3

@@ -1,37 +1,68 @@ {-# LANGUAGE FlexibleInstances #-} module Data.Ranges -(range, ranges, Range, Ranges, inRange, inRanges)+(range, ranges, Range, Ranges, inRange, inRanges, toSet,single) where -newtype Ord a => Range a = Range { unRange :: (a, a) }-newtype Ord a => Ranges a = Ranges [Range a]+import Data.Set (Set)+import qualified Data.Set as Set +data Ord a => Range a = Single !a | Range !a !a+instance (Ord a, Show a) => Show (Range a) where+	show (Single x) = "(" ++ show x ++ ")"+	show (Range x y) = "(" ++ show x ++ "-" ++ show y ++ ")"++newtype Ord a => Ranges a = Ranges [Range a] deriving Show++-- | A rather hacked-up instance.+--   This is to support fast lookups using 'Data.Set' (see 'toSet').+instance (Ord a) => Eq (Range a) where+	(Single x) == (Single y) = x == y+	(Single a) == (Range x y) = x <= a && a <= y+	(Range x y) == (Single a) = x <= a && a <= y+	(Range lx ux) == (Range ly uy) = (lx <= uy && ux >= ly) || (ly <= ux && uy >= lx)++instance (Ord a) => Ord (Range a) where+	(Single x) <= (Single y) = x <= y+	(Single x) <= (Range y _) = x <= y+	(Range _ x) <= (Single y) = x <= y+	(Range _ x) <= (Range y _) = x <= y++-- | A range consisting of a single value.+single :: (Ord a) => a -> Range a+single x = Single x+ -- | Construct a 'Range' from a lower and upper bound. range :: (Ord a) => a -> a -> Range a range l u-	| l <= u = Range (l,u)+	| l <= u = Range l u 	| otherwise = error "lower bound must be smaller than upper bound"  -- | Construct a 'Ranges' from a list of lower and upper bounds. ranges :: (Ord a) => [(a,a)] -> Ranges a-ranges = Ranges . map Range . foldr (\x xs -> map unRange $ mergeRanges (map Range xs) (uncurry range x)) []+ranges = Ranges . foldr (flip mergeRanges) [] . map (uncurry range)  -- | Tests if a given range contains a particular value. inRange :: (Ord a) => a -> Range a -> Bool-inRange x (Range (l,u)) = x >= l && x <= u+inRange x y = Single x == y  -- | Tests if any of the ranges contains a particular value. inRanges :: (Ord a) => a -> Ranges a -> Bool inRanges x (Ranges xs) = or . map (x `inRange`) $ xs  mergeRange :: (Ord a) => Range a -> Range a -> Either (Range a) (Range a)-mergeRange x y-	| lx <= uy && ux >= ly ||-	  ly <= ux && uy >= lx = Right $ Range (min lx ly, max ux uy)-	| otherwise = Left $ x-	where -	(lx,ux) = unRange x-	(ly,uy) = unRange y+mergeRange x y =+	if x == y+		then Right $ minMax x y+		else Left $ x++minMax :: (Ord a) => Range a -> Range a -> Range a+minMax (Range lx ux) (Range ly uy) = Range (min lx ly) (max ux uy)+minMax (Single _) y = y+minMax x@(Range _ _) (Single _) = x++-- | Allows quick lookups using ranges.+toSet :: (Ord a) => Ranges a -> Set (Range a)+toSet (Ranges x) = Set.fromList x  mergeRanges :: (Ord a) => [Range a] -> Range a -> [Range a] mergeRanges [] y = [y]

@@ -0,0 +1,1 @@+Do what you will.

@@ -1,14 +1,17 @@ Name: ranges-Version: 0.1-Description: Ranges and various functions on them.+Version: 0.2+Description: Ranges and some functions allowing things like fast membership+	lookup on ranges with holes in them and so on.+Synopsis: Ranges and various functions on them. License: BSD3 Author: George Pollard <porges@porg.es> Maintainer: George Pollard <porges@porg.es> Build-Type: Simple Cabal-Version: >=1.2+License-file: LICENSE Category: data  Library- Build-Depends: base+ Build-Depends: base, containers>=0.2  Exposed-modules: Data.Ranges  ghc-options: -O2 -Wall