Data.Geometry.IntervalTree

Documentation

data NodeData i r

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)

Defined 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)

Defined in Data.Geometry.IntervalTree

Methods

compare :: 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)

Defined in Data.Geometry.IntervalTree

Methods

showsPrec :: Int -> NodeData i r -> ShowS

show :: NodeData i r -> String

showList :: [NodeData i r] -> ShowS

Generic (NodeData i r)

Defined in Data.Geometry.IntervalTree

Associated Types

type Rep (NodeData i r) :: Type -> Type

Methods

from :: NodeData i r -> Rep (NodeData i r) x

to :: Rep (NodeData i r) x -> NodeData i r

(NFData r, NFData i) => NFData (NodeData i r)

Defined in Data.Geometry.IntervalTree

Methods

rnf :: NodeData i r -> ()

type Rep (NodeData i r)

Defined in Data.Geometry.IntervalTree

type Rep (NodeData i r) = D1 (MetaData "NodeData" "Data.Geometry.IntervalTree" "hgeometry-0.8.0.0-2B18HmKepFxHOPvqiUEkND" 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

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 type, storing intervals of type i

Constructors

IntervalTree

Fields

• _unIntervalTree :: BinaryTree (NodeData i r)

Instances

(Eq r, Eq i) => Eq (IntervalTree i r)

Defined 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)

Defined in Data.Geometry.IntervalTree

Methods

showsPrec :: Int -> IntervalTree i r -> ShowS

show :: IntervalTree i r -> String

showList :: [IntervalTree i r] -> ShowS

Generic (IntervalTree i r)

Defined in Data.Geometry.IntervalTree

Associated Types

type Rep (IntervalTree i r) :: Type -> Type

Methods

from :: IntervalTree i r -> Rep (IntervalTree i r) x

to :: Rep (IntervalTree i r) x -> IntervalTree i r

(NFData r, NFData i) => NFData (IntervalTree i r)

Defined in Data.Geometry.IntervalTree

Methods

rnf :: IntervalTree i r -> ()

type Rep (IntervalTree i r)

Defined in Data.Geometry.IntervalTree

type Rep (IntervalTree i r) = D1 (MetaData "IntervalTree" "Data.Geometry.IntervalTree" "hgeometry-0.8.0.0-2B18HmKepFxHOPvqiUEkND" 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))

class IntervalLike i where

Anything that looks like an interval

Methods

toRange :: i -> Range (NumType i)

Instances

IntervalLike (Range r)

Defined in Data.Geometry.IntervalTree

Methods

toRange :: Range r -> Range (NumType (Range r))

IntervalLike a => IntervalLike (I a)

Defined in Data.Geometry.SegmentTree.Generic

Methods

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

IntervalLike (Interval p r)

Defined in Data.Geometry.IntervalTree

Methods

toRange :: Interval p r -> Range (NumType (Interval p r))

createTree :: Ord r => [r] -> IntervalTree i r

Given an ordered list of points, create an interval tree

\(O(n)\)

fromIntervals :: (Ord r, IntervalLike i, NumType i ~ r) => [i] -> IntervalTree i r

Build an interval tree

\(O(n \log n)\)

insert :: (Ord r, IntervalLike i, NumType i ~ r) => i -> IntervalTree i r -> IntervalTree i r

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

Delete an interval from the Tree

\(O(\log n)\) (under some general position assumption)

stab :: Ord r => r -> IntervalTree i r -> [i]

Find all intervals that stab x

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

search :: Ord r => r -> IntervalTree i r -> [i]

Find all intervals that stab x

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

toList :: IntervalTree i r -> [i]

Lists the intervals. We don't guarantee anything about the order

running time: \(O(n)\).