Safe Haskell	None
Language	GHC2021

Data.IntervalSet

Synopsis

newtype IntervalSet = IntervalSet (IntMap Int)
nullIS :: IntervalSet -> Bool
sizeIS :: IntervalSet -> Int
emptyIS :: IntervalSet
singletonIS :: Int -> IntervalSet
intervalIS :: (Int, Int) -> IntervalSet
insertIS :: Int -> IntervalSet -> IntervalSet
insertIntervalIS :: (Int, Int) -> IntervalSet -> IntervalSet
deleteIS :: Int -> IntervalSet -> IntervalSet
deleteIntervalIS :: (Int, Int) -> IntervalSet -> IntervalSet
unionIS :: IntervalSet -> IntervalSet -> IntervalSet
differenceIS :: IntervalSet -> IntervalSet -> IntervalSet
intersectionIS :: IntervalSet -> IntervalSet -> IntervalSet
memberIS :: Int -> IntervalSet -> Bool
lookupIS :: Int -> IntervalSet -> Maybe (Int, Int)
lookupIntervalIS :: (Int, Int) -> IntervalSet -> [(Int, Int)]
minimumIS :: IntervalSet -> Int
maximumIS :: IntervalSet -> Int
mex :: IntervalSet -> Int
fromListIS :: [(Int, Int)] -> IntervalSet
toListIS :: IntervalSet -> [(Int, Int)]

Documentation

newtype IntervalSet Source #

Constructors

IntervalSet (IntMap Int)

Instances

Instances details

IsList IntervalSet Source #

Instance details

Defined in Data.IntervalSet

Associated Types

type Item IntervalSet
Instance details Defined in Data.IntervalSet type Item IntervalSet = (Int, Int)

Methods

fromList :: [Item IntervalSet] -> IntervalSet #

fromListN :: Int -> [Item IntervalSet] -> IntervalSet #

toList :: IntervalSet -> [Item IntervalSet] #

Show IntervalSet Source #

Instance details

Defined in Data.IntervalSet

Methods

showsPrec :: Int -> IntervalSet -> ShowS #

show :: IntervalSet -> String #

showList :: [IntervalSet] -> ShowS #

Eq IntervalSet Source #

Instance details

Defined in Data.IntervalSet

Methods

(==) :: IntervalSet -> IntervalSet -> Bool #

(/=) :: IntervalSet -> IntervalSet -> Bool #

type Item IntervalSet Source #

Instance details

Defined in Data.IntervalSet

type Item IntervalSet = (Int, Int)

nullIS :: IntervalSet -> Bool Source #

sizeIS :: IntervalSet -> Int Source #

O(n)

>>> sizeIS (fromList [(1,2),(4,5)])
4
>>> sizeIS emptyIS
0

emptyIS :: IntervalSet Source #

singletonIS :: Int -> IntervalSet Source #

intervalIS :: (Int, Int) -> IntervalSet Source #

>>> intervalIS (0, 1)
[(0,1)]
>>> intervalIS (1, 0)
[]

insertIS :: Int -> IntervalSet -> IntervalSet Source #

>>> insertIS 2 $ fromListIS [(0,1),(3,4)]
[(0,4)]
>>> insertIS 1 $ fromListIS [(0,1)]
[(0,1)]

insertIntervalIS :: (Int, Int) -> IntervalSet -> IntervalSet Source #

>>> insertIntervalIS (2,4) $ fromListIS [(1,1),(3,3),(5,5)]
[(1,5)]

deleteIS :: Int -> IntervalSet -> IntervalSet Source #

>>> deleteIS 1 $ fromListIS [0..2]
[(0,0),(2,2)]

deleteIntervalIS :: (Int, Int) -> IntervalSet -> IntervalSet Source #

>>> deleteIntervalIS (1,7) $ fromListIS [(0,1),(3,5),(7,8)]
[(0,0),(8,8)]
>>> deleteIntervalIS (1,1) $ fromListIS [(0,0)]
[(0,0)]

unionIS :: IntervalSet -> IntervalSet -> IntervalSet Source #

>>> unionIS (fromList [(0, 1), (3, 4)]) (fromList [(2, 2)])
[(0,4)]
>>> unionIS (fromList [(0, 1)]) (fromList [(3, 4)])
[(0,1),(3,4)]

differenceIS :: IntervalSet -> IntervalSet -> IntervalSet Source #

>>> differenceIS (fromList [(0,9)]) (fromList [(1,4),(6,8)])
[(0,0),(5,5),(9,9)]
>>> differenceIS (fromList [(0,1)]) (fromList[(0,2)])
[]

intersectionIS :: IntervalSet -> IntervalSet -> IntervalSet Source #

>>> intersectionIS (fromList [(0, 1), (3, 4)]) (fromList [(1, 3)])
[(1,1),(3,3)]
>>> intersectionIS (fromList [(0, 1)]) (fromList [(2, 3)])
[]
>>> intersectionIS (fromList [(0, 1)]) (fromList [(1, 2)])
[(1,1)]

memberIS :: Int -> IntervalSet -> Bool Source #

>>> memberIS 0 (fromListIS [(-1,1)])
True
>>> memberIS 1 (fromListIS [(-1,1)])
True
>>> memberIS 2 (fromListIS [(-1,1)])
False

lookupIS :: Int -> IntervalSet -> Maybe (Int, Int) Source #

>>> lookupIS (-2) $ intervalIS (-1,1)
Nothing
>>> lookupIS (-1) $ intervalIS (-1,1)
Just (-1,1)
>>> lookupIS 0 $ intervalIS (-1,1)
Just (-1,1)
>>> lookupIS 1 $ intervalIS (-1,1)
Just (-1,1)
>>> lookupIS 2 $ intervalIS (-1,1)
Nothing

lookupIntervalIS :: (Int, Int) -> IntervalSet -> [(Int, Int)] Source #

>>> lookupIntervalIS (1,8) $ fromList [(0,2),(4,5),(7,9)]
[(0,2),(4,5),(7,9)]
>>> lookupIntervalIS (3,6) $ fromList [(0,2),(4,5),(7,9)]
[(4,5)]
>>> lookupIntervalIS (3,3) $ fromList [(0,2),(4,5),(7,9)]
[]
>>> lookupIntervalIS (0, 1) $ fromList [(1, 2)]
[(1,2)]
>>> lookupIntervalIS (0, 1) $ fromList [(-1, 0)]
[(-1,0)]

minimumIS :: IntervalSet -> Int Source #

>>> minimumIS (intervalIS (0,9))
0
>>> minimumIS (fromListIS [(0,2),(5,9)])
0
>>> minimumIS emptyIS
*** Exception: findMin: empty map has no minimal element

maximumIS :: IntervalSet -> Int Source #

>>> maximumIS (intervalIS (0,9))
9
>>> maximumIS (fromListIS [(0,2),(5,9)])
9
>>> maximumIS emptyIS
*** Exception: findMax: empty map has no maximal element

mex :: IntervalSet -> Int Source #

minimum excluded value

>>> mex $ fromListIS [(0,1),(3,5)]
2
>>> mex $ intervalIS (1, 5)
0
>>> mex $ singletonIS 0
1

fromListIS :: [(Int, Int)] -> IntervalSet Source #

toListIS :: IntervalSet -> [(Int, Int)] Source #