Copyright | (C) Frank Staals |
---|---|
License | see the LICENSE file |
Maintainer | Frank Staals |
Safe Haskell | None |
Language | Haskell2010 |
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 {}
Documentation
Internal nodes store a split point, the range, and an associated data structure
Instances
Functor (NodeData v) Source # | |
(Eq r, Eq v) => Eq (NodeData v r) Source # | |
(Show r, Show v) => Show (NodeData v r) Source # | |
Generic (NodeData v r) Source # | |
(NFData v, NFData r) => NFData (NodeData v r) Source # | |
Defined in Data.Geometry.SegmentTree.Generic | |
type Rep (NodeData v r) Source # | |
Defined in Data.Geometry.SegmentTree.Generic type Rep (NodeData v r) = D1 ('MetaData "NodeData" "Data.Geometry.SegmentTree.Generic" "hgeometry-0.12.0.0-3A6BqD11e4bE4Mwo2IplDZ" '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)))) |
Leaf nodes store an atomic range, and an associated data structure.
LeafData | |
|
Instances
Functor (LeafData v) Source # | |
(Eq r, Eq v) => Eq (LeafData v r) Source # | |
(Show r, Show v) => Show (LeafData v r) Source # | |
Generic (LeafData v r) Source # | |
(NFData v, NFData r) => NFData (LeafData v r) Source # | |
Defined in Data.Geometry.SegmentTree.Generic | |
type Rep (LeafData v r) Source # | |
Defined in Data.Geometry.SegmentTree.Generic |
atomicRange :: forall v r r. Lens (LeafData v r) (LeafData v r) (AtomicRange r) (AtomicRange r) Source #
newtype SegmentTree v r Source #
Segment tree on a Fixed set of endpoints
SegmentTree | |
|
Instances
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
insertAssoc :: i -> v -> v Source #
deleteAssoc :: i -> v -> v 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)\)
Interval
Instances
Eq a => Eq (I a) Source # | |
Ord a => Ord (I a) Source # | |
Read a => Read (I a) Source # | |
Show a => Show (I a) Source # | |
Generic (I a) Source # | |
NFData a => NFData (I a) Source # | |
Defined in Data.Geometry.SegmentTree.Generic | |
IntervalLike a => IntervalLike (I a) Source # | |
Measured [I a] (I a) Source # | |
Defined in Data.Geometry.SegmentTree.Generic | |
Eq a => Assoc [I a] (I a) Source # | |
Defined in Data.Geometry.SegmentTree.Generic | |
type Rep (I a) Source # | |
Defined in Data.Geometry.SegmentTree.Generic | |
type NumType (I a) Source # | |
Defined in Data.Geometry.SegmentTree.Generic |
fromIntervals' :: (Eq p, Ord r) => NonEmpty (Interval p r) -> SegmentTree [I (Interval p r)] r Source #
Instances
Enum Count Source # | |
Defined in Data.Geometry.SegmentTree.Generic | |
Eq Count Source # | |
Integral Count Source # | |
Num Count Source # | |
Ord Count Source # | |
Real Count Source # | |
Defined in Data.Geometry.SegmentTree.Generic toRational :: Count -> Rational # | |
Show Count Source # | |
Generic Count Source # | |
Semigroup Count Source # | |
Monoid Count Source # | |
NFData Count Source # | |
Defined in Data.Geometry.SegmentTree.Generic | |
type Rep Count Source # | |
Defined in Data.Geometry.SegmentTree.Generic |