Copyright	(C) Frank Staals
License	see the LICENSE file
Maintainer	Frank Staals
Safe Haskell	None
Language	Haskell2010

Data.Geometry.SegmentTree.Generic

Description

Description : Implementation of SegmentTrees

Synopsis

data NodeData v r = NodeData {
- _splitPoint :: !(EndPoint r)
- _range :: !(Range r)
- _assoc :: !v
}
splitPoint :: forall v r. Lens' (NodeData v r) (EndPoint r)
range :: forall v r. Lens' (NodeData v r) (Range r)
assoc :: forall v r v. Lens (NodeData v r) (NodeData v r) v v
data LeafData v r = LeafData {
- _atomicRange :: !(AtomicRange r)
- _leafAssoc :: !v
}
atomicRange :: forall v r r. Lens (LeafData v r) (LeafData v r) (AtomicRange r) (AtomicRange r)
leafAssoc :: forall v r v. Lens (LeafData v r) (LeafData v r) v v
newtype SegmentTree v r = SegmentTree {
- _unSegmentTree :: BinLeafTree (NodeData v r) (LeafData v r)
}
unSegmentTree :: forall v r v r. Iso (SegmentTree v r) (SegmentTree v r) (BinLeafTree (NodeData v r) (LeafData v r)) (BinLeafTree (NodeData v r) (LeafData v r))
class Measured v i => Assoc v i where
- insertAssoc :: i -> v -> v
- deleteAssoc :: i -> v -> v
createTree :: NonEmpty r -> v -> SegmentTree v r
fromIntervals :: (Ord r, Eq p, Assoc v i, IntervalLike i, Monoid v, NumType i ~ r) => (Interval p r -> i) -> NonEmpty (Interval p r) -> SegmentTree v r
insert :: (Assoc v i, NumType i ~ r, Ord r, IntervalLike i) => i -> SegmentTree v r -> SegmentTree v r
delete :: (Assoc v i, NumType i ~ r, Ord r, IntervalLike i) => i -> SegmentTree v r -> SegmentTree v r
search :: (Ord r, Monoid v) => r -> SegmentTree v r -> v
stab :: Ord r => r -> SegmentTree v r -> [v]
newtype I a = I {
- _unI :: a
}
fromIntervals' :: (Eq p, Ord r) => NonEmpty (Interval p r) -> SegmentTree [I (Interval p r)] r
newtype Count = Count {
- getCount :: Word
}

Documentation

data NodeData v r Source #

Internal nodes store a split point, the range, and an associated data structure

Constructors

NodeData
Fields _splitPoint :: !(EndPoint r) _range :: !(Range r) _assoc :: !v

Instances

Functor (NodeData v) Source #
Instance details Defined in Data.Geometry.SegmentTree.Generic Methods fmap :: (a -> b) -> NodeData v a -> NodeData v b # (<$) :: a -> NodeData v b -> NodeData v a #
(Eq r, Eq v) => Eq (NodeData v r) Source #
Instance details Defined in Data.Geometry.SegmentTree.Generic Methods (==) :: NodeData v r -> NodeData v r -> Bool # (/=) :: NodeData v r -> NodeData v r -> Bool #
(Show r, Show v) => Show (NodeData v r) Source #
Instance details Defined in Data.Geometry.SegmentTree.Generic Methods showsPrec :: Int -> NodeData v r -> ShowS # show :: NodeData v r -> String # showList :: [NodeData v r] -> ShowS #
Generic (NodeData v r) Source #
Instance details Defined in Data.Geometry.SegmentTree.Generic Associated Types type Rep (NodeData v r) :: Type -> Type # Methods from :: NodeData v r -> Rep (NodeData v r) x # to :: Rep (NodeData v r) x -> NodeData v r #
(NFData v, NFData r) => NFData (NodeData v r) Source #
Instance details Defined in Data.Geometry.SegmentTree.Generic Methods rnf :: NodeData v r -> () #
type Rep (NodeData v r) Source #
Instance details Defined in Data.Geometry.SegmentTree.Generic type Rep (NodeData v r) = D1 (MetaData "NodeData" "Data.Geometry.SegmentTree.Generic" "hgeometry-0.8.0.0-2B18HmKepFxHOPvqiUEkND" False) (C1 (MetaCons "NodeData" PrefixI True) (S1 (MetaSel (Just "_splitPoint") NoSourceUnpackedness SourceStrict DecidedStrict) (Rec0 (EndPoint r)) :: (S1 (MetaSel (Just "_range") NoSourceUnpackedness SourceStrict DecidedStrict) (Rec0 (Range r)) :: S1 (MetaSel (Just "_assoc") NoSourceUnpackedness SourceStrict DecidedStrict) (Rec0 v))))

splitPoint :: forall v r. Lens' (NodeData v r) (EndPoint r) Source #

range :: forall v r. Lens' (NodeData v r) (Range r) Source #

assoc :: forall v r v. Lens (NodeData v r) (NodeData v r) v v Source #

data LeafData v r Source #

Leaf nodes store an atomic range, and an associated data structure.

Constructors

LeafData
Fields _atomicRange :: !(AtomicRange r) _leafAssoc :: !v

Instances

Functor (LeafData v) Source #
Instance details Defined in Data.Geometry.SegmentTree.Generic Methods fmap :: (a -> b) -> LeafData v a -> LeafData v b # (<$) :: a -> LeafData v b -> LeafData v a #
(Eq r, Eq v) => Eq (LeafData v r) Source #
Instance details Defined in Data.Geometry.SegmentTree.Generic Methods (==) :: LeafData v r -> LeafData v r -> Bool # (/=) :: LeafData v r -> LeafData v r -> Bool #
(Show r, Show v) => Show (LeafData v r) Source #
Instance details Defined in Data.Geometry.SegmentTree.Generic Methods showsPrec :: Int -> LeafData v r -> ShowS # show :: LeafData v r -> String # showList :: [LeafData v r] -> ShowS #
Generic (LeafData v r) Source #
Instance details Defined in Data.Geometry.SegmentTree.Generic Associated Types type Rep (LeafData v r) :: Type -> Type # Methods from :: LeafData v r -> Rep (LeafData v r) x # to :: Rep (LeafData v r) x -> LeafData v r #
(NFData v, NFData r) => NFData (LeafData v r) Source #
Instance details Defined in Data.Geometry.SegmentTree.Generic Methods rnf :: LeafData v r -> () #
type Rep (LeafData v r) Source #
Instance details Defined in Data.Geometry.SegmentTree.Generic type Rep (LeafData v r)

atomicRange :: forall v r r. Lens (LeafData v r) (LeafData v r) (AtomicRange r) (AtomicRange r) Source #

leafAssoc :: forall v r v. Lens (LeafData v r) (LeafData v r) v v Source #

newtype SegmentTree v r Source #

Segment tree on a Fixed set of endpoints

Constructors

SegmentTree
Fields _unSegmentTree :: BinLeafTree (NodeData v r) (LeafData v r)

Instances

(Eq r, Eq v) => Eq (SegmentTree v r) Source #
Instance details Defined in Data.Geometry.SegmentTree.Generic Methods (==) :: SegmentTree v r -> SegmentTree v r -> Bool # (/=) :: SegmentTree v r -> SegmentTree v r -> Bool #
(Show r, Show v) => Show (SegmentTree v r) Source #
Instance details Defined in Data.Geometry.SegmentTree.Generic Methods showsPrec :: Int -> SegmentTree v r -> ShowS # show :: SegmentTree v r -> String # showList :: [SegmentTree v r] -> ShowS #
Generic (SegmentTree v r) Source #
Instance details Defined in Data.Geometry.SegmentTree.Generic Associated Types type Rep (SegmentTree v r) :: Type -> Type # Methods from :: SegmentTree v r -> Rep (SegmentTree v r) x # to :: Rep (SegmentTree v r) x -> SegmentTree v r #
(NFData v, NFData r) => NFData (SegmentTree v r) Source #
Instance details Defined in Data.Geometry.SegmentTree.Generic Methods rnf :: SegmentTree v r -> () #
type Rep (SegmentTree v r) Source #
Instance details Defined in Data.Geometry.SegmentTree.Generic type Rep (SegmentTree v r) = D1 (MetaData "SegmentTree" "Data.Geometry.SegmentTree.Generic" "hgeometry-0.8.0.0-2B18HmKepFxHOPvqiUEkND" True) (C1 (MetaCons "SegmentTree" PrefixI True) (S1 (MetaSel (Just "_unSegmentTree") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 (BinLeafTree (NodeData v r) (LeafData v r)))))

unSegmentTree :: forall v r v r. Iso (SegmentTree v r) (SegmentTree v r) (BinLeafTree (NodeData v r) (LeafData v r)) (BinLeafTree (NodeData v r) (LeafData v r)) Source #

class Measured v i => Assoc v i where Source #

Class for associcated data structures

Methods

insertAssoc :: i -> v -> v Source #

deleteAssoc :: i -> v -> v Source #

Instances

Eq a => Assoc [I a] (I a) Source #
Instance details Defined in Data.Geometry.SegmentTree.Generic Methods insertAssoc :: I a -> [I a] -> [I a] Source # deleteAssoc :: I a -> [I a] -> [I a] Source #

createTree :: NonEmpty r -> v -> SegmentTree v r Source #

Given a sorted list of endpoints, without duplicates, construct a segment tree

$O(n)$ time

fromIntervals :: (Ord r, Eq p, Assoc v i, IntervalLike i, Monoid v, NumType i ~ r) => (Interval p r -> i) -> NonEmpty (Interval p r) -> SegmentTree v r Source #

Build a SegmentTree

$O(n \log n)$

insert :: (Assoc v i, NumType i ~ r, Ord r, IntervalLike i) => i -> SegmentTree v r -> SegmentTree v r Source #

Pre: the interval should have one of the endpoints on which the tree is built.

delete :: (Assoc v i, NumType i ~ r, Ord r, IntervalLike i) => i -> SegmentTree v r -> SegmentTree v r Source #

Delete an interval from the tree

pre: The segment is in the tree!

search :: (Ord r, Monoid v) => r -> SegmentTree v r -> v Source #

Search for all intervals intersecting x

$O(\log n + k)$ where $k$ is the output size

stab :: Ord r => r -> SegmentTree v r -> [v] Source #

Returns the associated values of the nodes on the search path to x

$O(\log n)$

newtype I a Source #

Interval

Constructors

I
Fields _unI :: a

Instances

Eq a => Eq (I a) Source #
Instance details Defined in Data.Geometry.SegmentTree.Generic Methods (==) :: I a -> I a -> Bool # (/=) :: I a -> I a -> Bool #
Ord a => Ord (I a) Source #
Instance details Defined in Data.Geometry.SegmentTree.Generic Methods compare :: I a -> I a -> Ordering # (<) :: I a -> I a -> Bool # (<=) :: I a -> I a -> Bool # (>) :: I a -> I a -> Bool # (>=) :: I a -> I a -> Bool # max :: I a -> I a -> I a # min :: I a -> I a -> I a #
Read a => Read (I a) Source #
Instance details Defined in Data.Geometry.SegmentTree.Generic Methods readsPrec :: Int -> ReadS (I a) # readList :: ReadS [I a] # readPrec :: ReadPrec (I a) # readListPrec :: ReadPrec [I a] #
Show a => Show (I a) Source #
Instance details Defined in Data.Geometry.SegmentTree.Generic Methods showsPrec :: Int -> I a -> ShowS # show :: I a -> String # showList :: [I a] -> ShowS #
Generic (I a) Source #
Instance details Defined in Data.Geometry.SegmentTree.Generic Associated Types type Rep (I a) :: Type -> Type # Methods from :: I a -> Rep (I a) x # to :: Rep (I a) x -> I a #
NFData a => NFData (I a) Source #
Instance details Defined in Data.Geometry.SegmentTree.Generic Methods rnf :: I a -> () #
IntervalLike a => IntervalLike (I a) Source #
Instance details Defined in Data.Geometry.SegmentTree.Generic Methods toRange :: I a -> Range (NumType (I a)) Source #
Measured [I a] (I a) Source #
Instance details Defined in Data.Geometry.SegmentTree.Generic Methods measure :: I a -> [I a] Source #
Eq a => Assoc [I a] (I a) Source #
Instance details Defined in Data.Geometry.SegmentTree.Generic Methods insertAssoc :: I a -> [I a] -> [I a] Source # deleteAssoc :: I a -> [I a] -> [I a] Source #
type Rep (I a) Source #
Instance details Defined in Data.Geometry.SegmentTree.Generic type Rep (I a) = D1 (MetaData "I" "Data.Geometry.SegmentTree.Generic" "hgeometry-0.8.0.0-2B18HmKepFxHOPvqiUEkND" True) (C1 (MetaCons "I" PrefixI True) (S1 (MetaSel (Just "_unI") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 a)))
type NumType (I a) Source #
Instance details Defined in Data.Geometry.SegmentTree.Generic type NumType (I a) = NumType a

fromIntervals' :: (Eq p, Ord r) => NonEmpty (Interval p r) -> SegmentTree [I (Interval p r)] r Source #

newtype Count Source #

Constructors

Count
Fields getCount :: Word

Instances

Enum Count Source #
Instance details Defined in Data.Geometry.SegmentTree.Generic Methods succ :: Count -> Count # pred :: Count -> Count # toEnum :: Int -> Count # fromEnum :: Count -> Int # enumFrom :: Count -> [Count] # enumFromThen :: Count -> Count -> [Count] # enumFromTo :: Count -> Count -> [Count] # enumFromThenTo :: Count -> Count -> Count -> [Count] #
Eq Count Source #
Instance details Defined in Data.Geometry.SegmentTree.Generic Methods (==) :: Count -> Count -> Bool # (/=) :: Count -> Count -> Bool #
Integral Count Source #
Instance details Defined in Data.Geometry.SegmentTree.Generic Methods quot :: Count -> Count -> Count # rem :: Count -> Count -> Count # div :: Count -> Count -> Count # mod :: Count -> Count -> Count # quotRem :: Count -> Count -> (Count, Count) # divMod :: Count -> Count -> (Count, Count) # toInteger :: Count -> Integer #
Num Count Source #
Instance details Defined in Data.Geometry.SegmentTree.Generic Methods (+) :: Count -> Count -> Count # (-) :: Count -> Count -> Count # (*) :: Count -> Count -> Count # negate :: Count -> Count # abs :: Count -> Count # signum :: Count -> Count # fromInteger :: Integer -> Count #
Ord Count Source #
Instance details Defined in Data.Geometry.SegmentTree.Generic Methods compare :: Count -> Count -> Ordering # (<) :: Count -> Count -> Bool # (<=) :: Count -> Count -> Bool # (>) :: Count -> Count -> Bool # (>=) :: Count -> Count -> Bool # max :: Count -> Count -> Count # min :: Count -> Count -> Count #
Real Count Source #
Instance details Defined in Data.Geometry.SegmentTree.Generic Methods toRational :: Count -> Rational #
Show Count Source #
Instance details Defined in Data.Geometry.SegmentTree.Generic Methods showsPrec :: Int -> Count -> ShowS # show :: Count -> String # showList :: [Count] -> ShowS #
Generic Count Source #
Instance details Defined in Data.Geometry.SegmentTree.Generic Associated Types type Rep Count :: Type -> Type # Methods from :: Count -> Rep Count x # to :: Rep Count x -> Count #
Semigroup Count Source #
Instance details Defined in Data.Geometry.SegmentTree.Generic Methods (<>) :: Count -> Count -> Count # sconcat :: NonEmpty Count -> Count # stimes :: Integral b => b -> Count -> Count #
Monoid Count Source #
Instance details Defined in Data.Geometry.SegmentTree.Generic Methods mempty :: Count # mappend :: Count -> Count -> Count # mconcat :: [Count] -> Count #
NFData Count Source #
Instance details Defined in Data.Geometry.SegmentTree.Generic Methods rnf :: Count -> () #
type Rep Count Source #
Instance details Defined in Data.Geometry.SegmentTree.Generic type Rep Count = D1 (MetaData "Count" "Data.Geometry.SegmentTree.Generic" "hgeometry-0.8.0.0-2B18HmKepFxHOPvqiUEkND" True) (C1 (MetaCons "Count" PrefixI True) (S1 (MetaSel (Just "getCount") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 Word)))