hgeometry-0.12.0.4: Geometric Algorithms, Data structures, and Data types.
Copyright(C) Frank Staals
Licensesee the LICENSE file
MaintainerFrank Staals
Safe HaskellNone
LanguageHaskell2010

Data.Geometry.IntervalTree

Description

 
Synopsis

Documentation

data NodeData i r Source #

Information stored in a node of the Interval Tree

Constructors

NodeData 

Fields

Instances

Instances details
(Eq r, Eq i) => Eq (NodeData i r) Source # 
Instance details

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) Source # 
Instance details

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) Source # 
Instance details

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) Source # 
Instance details

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 i, NFData r) => NFData (NodeData i r) Source # 
Instance details

Defined in Data.Geometry.IntervalTree

Methods

rnf :: NodeData i r -> () #

type Rep (NodeData i r) Source # 
Instance details

Defined in Data.Geometry.IntervalTree

type Rep (NodeData i r) = D1 ('MetaData "NodeData" "Data.Geometry.IntervalTree" "hgeometry-0.12.0.4-4wzlMfvn1ROGs9ccdWmQbR" '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 

Instances

Instances details
(Eq r, Eq i) => Eq (IntervalTree i r) Source # 
Instance details

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) Source # 
Instance details

Defined in Data.Geometry.IntervalTree

Generic (IntervalTree i r) Source # 
Instance details

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 i, NFData r) => NFData (IntervalTree i r) Source # 
Instance details

Defined in Data.Geometry.IntervalTree

Methods

rnf :: IntervalTree i r -> () #

type Rep (IntervalTree i r) Source # 
Instance details

Defined in Data.Geometry.IntervalTree

type Rep (IntervalTree i r) = D1 ('MetaData "IntervalTree" "Data.Geometry.IntervalTree" "hgeometry-0.12.0.4-4wzlMfvn1ROGs9ccdWmQbR" '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

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

Instances

Instances details
IntervalLike (Range r) Source # 
Instance details

Defined in Data.Geometry.IntervalTree

Methods

asRange :: Range r -> Range (NumType (Range r)) Source #

IntervalLike a => IntervalLike (I a) Source # 
Instance details

Defined in Data.Geometry.SegmentTree.Generic

Methods

asRange :: I a -> Range (NumType (I a)) Source #

IntervalLike (Interval p r) Source # 
Instance details

Defined in Data.Geometry.IntervalTree

Methods

asRange :: 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)\).