Safe Haskell	Safe

LSC.SegmentTree

Synopsis

data SegmentTree a
fromList :: Ord a => [(a, a)] -> SegmentTree a
constructSegmentTree :: Ord a => [a] -> [(a, a)] -> SegmentTree a
endpoints :: Ord a => [(a, a)] -> [a]
maxDensity :: SegmentTree a -> Int
densityRatio :: Ord a => (a, a) -> SegmentTree a -> Rational
densityOn :: Ord a => a -> SegmentTree a -> Int
densityOver :: Ord a => (a, a) -> SegmentTree a -> Int
unsafeDensityRatio :: Ord a => (a, a) -> SegmentTree a -> Rational
unsafeDensityOver :: Ord a => (a, a) -> SegmentTree a -> Int
push :: Ord a => (a, a) -> SegmentTree a -> SegmentTree a
pull :: Ord a => (a, a) -> SegmentTree a -> SegmentTree a
unsafePush :: Ord a => (a, a) -> SegmentTree a -> SegmentTree a
unsafePull :: Ord a => (a, a) -> SegmentTree a -> SegmentTree a
showTree :: Show a => SegmentTree a -> String
data Stabs a m
skeleton :: (Ord a, Monoid m) => [a] -> Stabs a m
append :: (Ord a, Semigroup m) => (a, a) -> m -> Stabs a m -> Stabs a m
unsafeAppend :: (Ord a, Semigroup m) => (a, a) -> m -> Stabs a m -> Stabs a m
adjust :: Ord a => (a, a) -> (m -> m) -> Stabs a m -> Stabs a m
unsafeAdjust :: Ord a => (a, a) -> (m -> m) -> Stabs a m -> Stabs a m
stab :: (Ord a, Monoid m) => a -> Stabs a m -> m
stabOver :: (Ord a, Monoid m) => (a, a) -> Stabs a m -> m
unsafeStabOver :: (Ord a, Monoid m) => (a, a) -> Stabs a m -> m

Documentation

data SegmentTree a Source #

An implementation closer to the literature

Instances

Instances details

Foldable SegmentTree Source #	Fold over non-empty endpoints
Instance details Defined in LSC.SegmentTree Methods fold :: Monoid m => SegmentTree m -> m foldMap :: Monoid m => (a -> m) -> SegmentTree a -> m foldMap' :: Monoid m => (a -> m) -> SegmentTree a -> m foldr :: (a -> b -> b) -> b -> SegmentTree a -> b foldr' :: (a -> b -> b) -> b -> SegmentTree a -> b foldl :: (b -> a -> b) -> b -> SegmentTree a -> b foldl' :: (b -> a -> b) -> b -> SegmentTree a -> b foldr1 :: (a -> a -> a) -> SegmentTree a -> a foldl1 :: (a -> a -> a) -> SegmentTree a -> a toList :: SegmentTree a -> [a] null :: SegmentTree a -> Bool length :: SegmentTree a -> Int elem :: Eq a => a -> SegmentTree a -> Bool maximum :: Ord a => SegmentTree a -> a minimum :: Ord a => SegmentTree a -> a sum :: Num a => SegmentTree a -> a product :: Num a => SegmentTree a -> a
Show a => Show (SegmentTree a) Source #
Instance details Defined in LSC.SegmentTree Methods showsPrec :: Int -> SegmentTree a -> ShowS show :: SegmentTree a -> String showList :: [SegmentTree a] -> ShowS

fromList :: Ord a => [(a, a)] -> SegmentTree a Source #

constructSegmentTree :: Ord a => [a] -> [(a, a)] -> SegmentTree a Source #

This is unsafe: constructSegmentTree assumes its first argument to be distinct and in ascending order

endpoints :: Ord a => [(a, a)] -> [a] Source #

maxDensity :: SegmentTree a -> Int Source #

densityRatio :: Ord a => (a, a) -> SegmentTree a -> Rational Source #

densityOn :: Ord a => a -> SegmentTree a -> Int Source #

densityOver :: Ord a => (a, a) -> SegmentTree a -> Int Source #

unsafeDensityRatio :: Ord a => (a, a) -> SegmentTree a -> Rational Source #

unsafeDensityOver :: Ord a => (a, a) -> SegmentTree a -> Int Source #

push :: Ord a => (a, a) -> SegmentTree a -> SegmentTree a Source #

Insert an edge, mnemonic: to push a needle into the haystack

pull :: Ord a => (a, a) -> SegmentTree a -> SegmentTree a Source #

Delete an edge, mnemonic: to pull a needle from the haystack

unsafePush :: Ord a => (a, a) -> SegmentTree a -> SegmentTree a Source #

Insert an edge, mnemonic: to push a needle into the haystack

unsafePull :: Ord a => (a, a) -> SegmentTree a -> SegmentTree a Source #

Delete an edge, mnemonic: to pull a needle from the haystack

showTree :: Show a => SegmentTree a -> String Source #

data Stabs a m Source #

Custom tree data type for creating stabbing queries over monoids, e. g. always appending `Sum 1` counts the number of intervals intersecting the stabbing abscissa.

Note that the underlying monoid type may be changed by using fmap.

Instances

Instances details

Functor (Stabs a) Source #
Instance details Defined in LSC.SegmentTree Methods fmap :: (a0 -> b) -> Stabs a a0 -> Stabs a b (<$) :: a0 -> Stabs a b -> Stabs a a0
(Show m, Show a) => Show (Stabs a m) Source #
Instance details Defined in LSC.SegmentTree Methods showsPrec :: Int -> Stabs a m -> ShowS show :: Stabs a m -> String showList :: [Stabs a m] -> ShowS

skeleton :: (Ord a, Monoid m) => [a] -> Stabs a m Source #

append :: (Ord a, Semigroup m) => (a, a) -> m -> Stabs a m -> Stabs a m Source #

unsafeAppend :: (Ord a, Semigroup m) => (a, a) -> m -> Stabs a m -> Stabs a m Source #

adjust :: Ord a => (a, a) -> (m -> m) -> Stabs a m -> Stabs a m Source #

unsafeAdjust :: Ord a => (a, a) -> (m -> m) -> Stabs a m -> Stabs a m Source #

stab :: (Ord a, Monoid m) => a -> Stabs a m -> m Source #

stabOver :: (Ord a, Monoid m) => (a, a) -> Stabs a m -> m Source #

unsafeStabOver :: (Ord a, Monoid m) => (a, a) -> Stabs a m -> m Source #