Data.Geometry.SegmentTree.Generic

Description : Implementation of SegmentTrees

Documentation

data NodeData v r

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)

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)

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)

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)

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)

Defined in Data.Geometry.SegmentTree.Generic

Methods

rnf :: NodeData v r -> ()

type Rep (NodeData v r)

Defined in Data.Geometry.SegmentTree.Generic

type Rep (NodeData v r) = D1 (MetaData "NodeData" "Data.Geometry.SegmentTree.Generic" "hgeometry-0.10.0.0-58coE6gW4i4HcLJr7kmg1f" 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)

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

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

Constructors

LeafData

Fields

• _atomicRange :: !(AtomicRange r)
• _leafAssoc :: !v

Instances

Functor (LeafData v)

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)

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)

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)

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)

Defined in Data.Geometry.SegmentTree.Generic

Methods

rnf :: LeafData v r -> ()

type Rep (LeafData v r)

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)

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

newtype SegmentTree v r

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)

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)

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)

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)

Defined in Data.Geometry.SegmentTree.Generic

Methods

rnf :: SegmentTree v r -> ()

type Rep (SegmentTree v r)

Defined in Data.Geometry.SegmentTree.Generic

type Rep (SegmentTree v r) = D1 (MetaData "SegmentTree" "Data.Geometry.SegmentTree.Generic" "hgeometry-0.10.0.0-58coE6gW4i4HcLJr7kmg1f" 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))

class Measured v i => Assoc v i where

Class for associcated data structures

Methods

insertAssoc :: i -> v -> v

deleteAssoc :: i -> v -> v

Instances

Eq a => Assoc [I a] (I a)

Defined in Data.Geometry.SegmentTree.Generic

Methods

insertAssoc :: I a -> [I a] -> [I a]

deleteAssoc :: I a -> [I a] -> [I a]

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

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

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

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

Delete an interval from the tree

pre: The segment is in the tree!

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

Search for all intervals intersecting x

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

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

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

\(O(\log n)\)

newtype I a

Interval

Constructors

I

Fields

• _unI :: a

Instances

Eq a => Eq (I a)

Defined in Data.Geometry.SegmentTree.Generic

Methods

(==) :: I a -> I a -> Bool

(/=) :: I a -> I a -> Bool

Ord a => Ord (I a)

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)

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)

Defined in Data.Geometry.SegmentTree.Generic

Methods

showsPrec :: Int -> I a -> ShowS

show :: I a -> String

showList :: [I a] -> ShowS

Generic (I a)

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)

Defined in Data.Geometry.SegmentTree.Generic

Methods

rnf :: I a -> ()

IntervalLike a => IntervalLike (I a)

Defined in Data.Geometry.SegmentTree.Generic

Methods

toRange :: I a -> Range (NumType (I a))

Measured [I a] (I a)

Defined in Data.Geometry.SegmentTree.Generic

Methods

measure :: I a -> [I a]

Eq a => Assoc [I a] (I a)

Defined in Data.Geometry.SegmentTree.Generic

Methods

insertAssoc :: I a -> [I a] -> [I a]

deleteAssoc :: I a -> [I a] -> [I a]

type Rep (I a)

Defined in Data.Geometry.SegmentTree.Generic

type Rep (I a) = D1 (MetaData "I" "Data.Geometry.SegmentTree.Generic" "hgeometry-0.10.0.0-58coE6gW4i4HcLJr7kmg1f" True) (C1 (MetaCons "I" PrefixI True) (S1 (MetaSel (Just "_unI") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 a)))

type NumType (I a)

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

newtype Count

Constructors

Count

Fields

• getCount :: Word

Instances

Enum Count

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

Defined in Data.Geometry.SegmentTree.Generic

Methods

(==) :: Count -> Count -> Bool

(/=) :: Count -> Count -> Bool

Integral Count

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

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

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

Defined in Data.Geometry.SegmentTree.Generic

Methods

toRational :: Count -> Rational

Show Count

Defined in Data.Geometry.SegmentTree.Generic

Methods

showsPrec :: Int -> Count -> ShowS

show :: Count -> String

showList :: [Count] -> ShowS

Generic Count

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

Defined in Data.Geometry.SegmentTree.Generic

Methods

(<>) :: Count -> Count -> Count

sconcat :: NonEmpty Count -> Count

stimes :: Integral b => b -> Count -> Count

Monoid Count

Defined in Data.Geometry.SegmentTree.Generic

Methods

mempty :: Count

mappend :: Count -> Count -> Count

mconcat :: [Count] -> Count

NFData Count

Defined in Data.Geometry.SegmentTree.Generic

Methods

rnf :: Count -> ()

type Rep Count

Defined in Data.Geometry.SegmentTree.Generic

type Rep Count = D1 (MetaData "Count" "Data.Geometry.SegmentTree.Generic" "hgeometry-0.10.0.0-58coE6gW4i4HcLJr7kmg1f" True) (C1 (MetaCons "Count" PrefixI True) (S1 (MetaSel (Just "getCount") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 Word)))