hgeometry-0.10.0.0: Geometric Algorithms, Data structures, and Data types.

Data.Geometry.IntervalTree

Synopsis

# Documentation

data NodeData i r Source #

Information stored in a node of the Interval Tree

Constructors

 NodeData Fields_splitPoint :: !r _intervalsLeft :: !(Map (L r) [i]) _intervalsRight :: !(Map (R r) [i])
Instances
 (Eq r, Eq i) => Eq (NodeData i r) Source # Instance detailsDefined in Data.Geometry.IntervalTree Methods(==) :: NodeData i r -> NodeData i r -> Bool #(/=) :: NodeData i r -> NodeData i r -> Bool # (Ord r, Ord i) => Ord (NodeData i r) Source # Instance detailsDefined in Data.Geometry.IntervalTree Methodscompare :: NodeData i r -> NodeData i r -> Ordering #(<) :: NodeData i r -> NodeData i r -> Bool #(<=) :: NodeData i r -> NodeData i r -> Bool #(>) :: NodeData i r -> NodeData i r -> Bool #(>=) :: NodeData i r -> NodeData i r -> Bool #max :: NodeData i r -> NodeData i r -> NodeData i r #min :: NodeData i r -> NodeData i r -> NodeData i r # (Show r, Show i) => Show (NodeData i r) Source # Instance detailsDefined in Data.Geometry.IntervalTree MethodsshowsPrec :: Int -> NodeData i r -> ShowS #show :: NodeData i r -> String #showList :: [NodeData i r] -> ShowS # Generic (NodeData i r) Source # Instance detailsDefined in Data.Geometry.IntervalTree Associated Typestype Rep (NodeData i r) :: Type -> Type # Methodsfrom :: NodeData i r -> Rep (NodeData i r) x #to :: Rep (NodeData i r) x -> NodeData i r # (NFData i, NFData r) => NFData (NodeData i r) Source # Instance detailsDefined in Data.Geometry.IntervalTree Methodsrnf :: NodeData i r -> () # type Rep (NodeData i r) Source # Instance detailsDefined in Data.Geometry.IntervalTree type Rep (NodeData i r) = D1 (MetaData "NodeData" "Data.Geometry.IntervalTree" "hgeometry-0.10.0.0-58coE6gW4i4HcLJr7kmg1f" 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 #

intervalsLeft :: forall i r. Lens' (NodeData i r) (Map (L r) [i]) Source #

intervalsRight :: forall i r. Lens' (NodeData i r) (Map (R r) [i]) Source #

newtype IntervalTree i r Source #

IntervalTree type, storing intervals of type i

Constructors

 IntervalTree Fields_unIntervalTree :: BinaryTree (NodeData i r)
Instances
 (Eq r, Eq i) => Eq (IntervalTree i r) Source # Instance detailsDefined in Data.Geometry.IntervalTree Methods(==) :: IntervalTree i r -> IntervalTree i r -> Bool #(/=) :: IntervalTree i r -> IntervalTree i r -> Bool # (Show r, Show i) => Show (IntervalTree i r) Source # Instance detailsDefined in Data.Geometry.IntervalTree MethodsshowsPrec :: Int -> IntervalTree i r -> ShowS #show :: IntervalTree i r -> String #showList :: [IntervalTree i r] -> ShowS # Generic (IntervalTree i r) Source # Instance detailsDefined in Data.Geometry.IntervalTree Associated Typestype Rep (IntervalTree i r) :: Type -> Type # Methodsfrom :: IntervalTree i r -> Rep (IntervalTree i r) x #to :: Rep (IntervalTree i r) x -> IntervalTree i r # (NFData i, NFData r) => NFData (IntervalTree i r) Source # Instance detailsDefined in Data.Geometry.IntervalTree Methodsrnf :: IntervalTree i r -> () # type Rep (IntervalTree i r) Source # Instance detailsDefined in Data.Geometry.IntervalTree type Rep (IntervalTree i r) = D1 (MetaData "IntervalTree" "Data.Geometry.IntervalTree" "hgeometry-0.10.0.0-58coE6gW4i4HcLJr7kmg1f" True) (C1 (MetaCons "IntervalTree" PrefixI True) (S1 (MetaSel (Just "_unIntervalTree") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 (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)) Source #

class IntervalLike i where Source #

Anything that looks like an interval

Methods

toRange :: i -> Range (NumType i) Source #

Instances
 Source # Instance detailsDefined in Data.Geometry.IntervalTree MethodstoRange :: Range r -> Range (NumType (Range r)) Source # IntervalLike a => IntervalLike (I a) Source # Instance detailsDefined in Data.Geometry.SegmentTree.Generic MethodstoRange :: I a -> Range (NumType (I a)) Source # IntervalLike (Interval p r) Source # Instance detailsDefined in Data.Geometry.IntervalTree MethodstoRange :: Interval p r -> Range (NumType (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)$$.