| Safe Haskell | None |
|---|---|
| Language | Haskell2010 |
Data.Geometry.IntervalTree
- 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
Constructors
| NodeData | |
Fields
| |
splitPoint :: forall i r. Lens' (NodeData i r) r Source #
newtype IntervalTree i r Source #
IntervalTree type, storing intervals of type i
Constructors
| IntervalTree | |
Fields
| |
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
Minimal complete definition
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)\).