Copyright | (C) Frank Staals |
---|---|
License | see the LICENSE file |
Maintainer | Frank Staals |
Safe Haskell | None |
Language | Haskell2010 |
Synopsis
- data NodeData i r = NodeData {
- _splitPoint :: !r
- _intervalsLeft :: !(Map (L r) [i])
- _intervalsRight :: !(Map (R r) [i])
- splitPoint :: forall i r. Lens' (NodeData i r) r
- intervalsLeft :: forall i r. Lens' (NodeData i r) (Map (L r) [i])
- intervalsRight :: forall i r. Lens' (NodeData i r) (Map (R r) [i])
- newtype IntervalTree i r = IntervalTree {
- _unIntervalTree :: BinaryTree (NodeData i r)
- unIntervalTree :: forall i r i r. Iso (IntervalTree i r) (IntervalTree i r) (BinaryTree (NodeData i r)) (BinaryTree (NodeData i r))
- class IntervalLike i where
- createTree :: Ord r => [r] -> IntervalTree i r
- fromIntervals :: (Ord r, IntervalLike i, NumType i ~ r) => [i] -> IntervalTree i r
- insert :: (Ord r, IntervalLike i, NumType i ~ r) => i -> IntervalTree i r -> IntervalTree i r
- delete :: (Ord r, IntervalLike i, NumType i ~ r, Eq i) => i -> IntervalTree i r -> IntervalTree i r
- stab :: Ord r => r -> IntervalTree i r -> [i]
- search :: Ord r => r -> IntervalTree i r -> [i]
- toList :: IntervalTree i r -> [i]
Documentation
Information stored in a node of the Interval Tree
NodeData | |
|
Instances
(Eq r, Eq i) => Eq (NodeData i r) Source # | |
(Ord r, Ord i) => Ord (NodeData i r) Source # | |
Defined in Data.Geometry.IntervalTree | |
(Show r, Show i) => Show (NodeData i r) Source # | |
Generic (NodeData i r) Source # | |
(NFData i, NFData r) => NFData (NodeData i r) Source # | |
Defined in Data.Geometry.IntervalTree | |
type Rep (NodeData i r) Source # | |
Defined in Data.Geometry.IntervalTree type Rep (NodeData i r) = D1 ('MetaData "NodeData" "Data.Geometry.IntervalTree" "hgeometry-0.12.0.0-3A6BqD11e4bE4Mwo2IplDZ" 'False) (C1 ('MetaCons "NodeData" 'PrefixI 'True) (S1 ('MetaSel ('Just "_splitPoint") 'NoSourceUnpackedness 'SourceStrict 'DecidedStrict) (Rec0 r) :*: (S1 ('MetaSel ('Just "_intervalsLeft") 'NoSourceUnpackedness 'SourceStrict 'DecidedStrict) (Rec0 (Map (L r) [i])) :*: S1 ('MetaSel ('Just "_intervalsRight") 'NoSourceUnpackedness 'SourceStrict 'DecidedStrict) (Rec0 (Map (R r) [i]))))) |
splitPoint :: forall i r. Lens' (NodeData i r) r Source #
newtype IntervalTree i r Source #
IntervalTree type, storing intervals of type i
IntervalTree | |
|
Instances
unIntervalTree :: forall i r i r. Iso (IntervalTree i r) (IntervalTree i r) (BinaryTree (NodeData i r)) (BinaryTree (NodeData i r)) Source #
class IntervalLike i where Source #
Anything that looks like an interval
Instances
IntervalLike (Range r) Source # | |
IntervalLike a => IntervalLike (I a) Source # | |
IntervalLike (Interval p r) Source # | |
createTree :: Ord r => [r] -> IntervalTree i r Source #
Given an ordered list of points, create an interval tree
\(O(n)\)
fromIntervals :: (Ord r, IntervalLike i, NumType i ~ r) => [i] -> IntervalTree i r Source #
Build an interval tree
\(O(n \log n)\)
insert :: (Ord r, IntervalLike i, NumType i ~ r) => i -> IntervalTree i r -> IntervalTree i r Source #
Insert : pre: the interval intersects some midpoint in the tree
\(O(\log n)\)
delete :: (Ord r, IntervalLike i, NumType i ~ r, Eq i) => i -> IntervalTree i r -> IntervalTree i r Source #
Delete an interval from the Tree
\(O(\log n)\) (under some general position assumption)
stab :: Ord r => r -> IntervalTree i r -> [i] Source #
Find all intervals that stab x
\(O(\log n + k)\), where k is the output size
search :: Ord r => r -> IntervalTree i r -> [i] Source #
Find all intervals that stab x
\(O(\log n + k)\), where k is the output size
toList :: IntervalTree i r -> [i] Source #
Lists the intervals. We don't guarantee anything about the order
running time: \(O(n)\).