Data.Geometry.PrioritySearchTree

Implements a linear size data structure for three-sided range queries in \(\mathbb{R}^2\). See

McCreight, Edward (May 1985). "Priority search trees". SIAM Journal on Scientific Computing. 14 (2): 257-276.

for more details.

Documentation

newtype PrioritySearchTree p r

A priority search tree storing points in (mathbb{R}^2) that have an additional payload of type p.

Constructors

PrioritySearchTree

Fields

• _unPrioritySearchTree :: BinLeafTree (NodeData p r) (LeafData p r)

Instances

Bifunctor PrioritySearchTree

Defined in Data.Geometry.PrioritySearchTree

Methods

bimap :: (a -> b) -> (c -> d) -> PrioritySearchTree a c -> PrioritySearchTree b d

first :: (a -> b) -> PrioritySearchTree a c -> PrioritySearchTree b c

second :: (b -> c) -> PrioritySearchTree a b -> PrioritySearchTree a c

(Eq r, Eq p) => Eq (PrioritySearchTree p r)

Defined in Data.Geometry.PrioritySearchTree

Methods

(==) :: PrioritySearchTree p r -> PrioritySearchTree p r -> Bool

(/=) :: PrioritySearchTree p r -> PrioritySearchTree p r -> Bool

(Show r, Show p) => Show (PrioritySearchTree p r)

Defined in Data.Geometry.PrioritySearchTree

Methods

showsPrec :: Int -> PrioritySearchTree p r -> ShowS

show :: PrioritySearchTree p r -> String

showList :: [PrioritySearchTree p r] -> ShowS

createTree :: Ord r => NonEmpty (Point 2 r :+ p) -> PrioritySearchTree p r

Creates a Priority Search Tree for 3-sided range queries of the form \([x_l,x_r] \times [y,\infty)\).

the base tree will be static.

pre: all points have unique x-coordinates

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

queryRange :: Ord r => (Range r, r) -> PrioritySearchTree p r -> [Point 2 r :+ p]

Given a three sided range \([x_l,x_r],y\) report all points in the range \([x_l,x_r] \times [y,\infty)\). The points are reported in decreasing order of \(y\)-coordinate.

running time: \(O(\log n + k)\), where \(k\) is the number of reported points.