| Copyright | (C) Frank Staals |
|---|---|
| License | see the LICENSE file |
| Maintainer | Frank Staals |
| Safe Haskell | None |
| Language | Haskell2010 |
Data.Geometry.PrioritySearchTree
Description
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.
Synopsis
- newtype PrioritySearchTree p r = PrioritySearchTree {
- _unPrioritySearchTree :: BinLeafTree (NodeData p r) (LeafData p r)
- createTree :: Ord r => NonEmpty (Point 2 r :+ p) -> PrioritySearchTree p r
- queryRange :: Ord r => (Range r, r) -> PrioritySearchTree p r -> [Point 2 r :+ p]
Documentation
newtype PrioritySearchTree p r Source #
A priority search tree storing points in (mathbb{R}^2) that have an additional payload of type p.
Constructors
| PrioritySearchTree | |
Fields
| |
Instances
| Bifunctor PrioritySearchTree Source # | |
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) Source # | |
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) Source # | |
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 Source #
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] Source #
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.