Copyright	(C) Frank Staals
License	see the LICENSE file
Maintainer	Frank Staals
Safe Haskell	None
Language	Haskell2010

Data.Geometry.RangeTree.Generic

Contents

Converting to a List
Querying x
Updates

Description

Synopsis

data NodeData v r = NodeData {
- _minVal :: !(Min r)
- _maxVal :: !(Max r)
- _assoc :: !v
}
newtype RangeTree v q r = RangeTree {
- _unRangeTree :: BinLeafTree (NodeData v r) (NodeData (v, q) r)
}
createTree :: (Ord r, Measured v p, Semigroup p) => NonEmpty (r :+ p) -> RangeTree v p r
createTree' :: (Ord r, Measured v p) => NonEmpty (r :+ p) -> RangeTree v p r
toAscList :: RangeTree v p r -> NonEmpty (r :+ p)
search :: (Ord r, Monoid v) => Range r -> RangeTree v p r -> v
search' :: Ord r => Range r -> RangeTree v p r -> [v]
search'' :: Ord r => Range r -> BinLeafTree (NodeData v r) (NodeData (v, q) r) -> [v]
rangeOf :: BinLeafTree (NodeData v r) (NodeData v' r) -> Range r
rangeOf' :: NodeData v r -> Range r
createReportingTree :: Ord r => NonEmpty (r :+ [p]) -> RangeTree (Report p) (Report p) r
report :: Ord r => Range r -> RangeTree (Report p) q r -> [p]
newtype CountOf p = CountOf [p]
createCountingTree :: Ord r => NonEmpty (r :+ [p]) -> RangeTree (Count p) (CountOf p) r
count :: Ord r => Range r -> RangeTree (Count p) q r -> Int

Documentation

data NodeData v r Source #

Constructors

NodeData
Fields _minVal :: !(Min r) _maxVal :: !(Max r) _assoc :: !v

Instances

Instances details

Functor (NodeData v) Source #
Instance details Defined in Data.Geometry.RangeTree.Generic Methods fmap :: (a -> b) -> NodeData v a -> NodeData v b # (<$) :: a -> NodeData v b -> NodeData v a #
(Eq r, Eq v) => Eq (NodeData v r) Source #
Instance details Defined in Data.Geometry.RangeTree.Generic Methods (==) :: NodeData v r -> NodeData v r -> Bool # (/=) :: NodeData v r -> NodeData v r -> Bool #
(Show r, Show v) => Show (NodeData v r) Source #
Instance details Defined in Data.Geometry.RangeTree.Generic Methods showsPrec :: Int -> NodeData v r -> ShowS # show :: NodeData v r -> String # showList :: [NodeData v r] -> ShowS #
(Semigroup v, Ord r) => Semigroup (NodeData v r) Source #
Instance details Defined in Data.Geometry.RangeTree.Generic Methods (<>) :: NodeData v r -> NodeData v r -> NodeData v r # sconcat :: NonEmpty (NodeData v r) -> NodeData v r # stimes :: Integral b => b -> NodeData v r -> NodeData v r #

newtype RangeTree v q r Source #

A generic (1D) range tree. The r parameter indicates the type of the coordinates of the points. The q represents any associated data values with those points (stored in the leaves), and the v types represents the data stored at internal nodes.

Constructors

RangeTree
Fields _unRangeTree :: BinLeafTree (NodeData v r) (NodeData (v, q) r)

Instances

Instances details

(Eq r, Eq v, Eq q) => Eq (RangeTree v q r) Source #
Instance details Defined in Data.Geometry.RangeTree.Generic Methods (==) :: RangeTree v q r -> RangeTree v q r -> Bool # (/=) :: RangeTree v q r -> RangeTree v q r -> Bool #
(Show r, Show v, Show q) => Show (RangeTree v q r) Source #
Instance details Defined in Data.Geometry.RangeTree.Generic Methods showsPrec :: Int -> RangeTree v q r -> ShowS # show :: RangeTree v q r -> String # showList :: [RangeTree v q r] -> ShowS #

createTree :: (Ord r, Measured v p, Semigroup p) => NonEmpty (r :+ p) -> RangeTree v p r Source #

Creates a range tree

createTree' :: (Ord r, Measured v p) => NonEmpty (r :+ p) -> RangeTree v p r Source #

pre: input is sorted and grouped by x-coord

Converting to a List

toAscList :: RangeTree v p r -> NonEmpty (r :+ p) Source #

Lists all points in increasing order

running time: $O(n)$

Querying x

search :: (Ord r, Monoid v) => Range r -> RangeTree v p r -> v Source #

Range search

running time: $O(\log n)$

search' :: Ord r => Range r -> RangeTree v p r -> [v] Source #

Range search, report the (associated data structures of the) $O(\log n)$ nodes that form the disjoint union of the range we are querying with.

running time: $O(\log n)$

search'' :: Ord r => Range r -> BinLeafTree (NodeData v r) (NodeData (v, q) r) -> [v] Source #

The actual search

rangeOf :: BinLeafTree (NodeData v r) (NodeData v' r) -> Range r Source #

Helper function to get the range of a binary leaf tree

rangeOf' :: NodeData v r -> Range r Source #

Get the range of a node

Updates

createReportingTree :: Ord r => NonEmpty (r :+ [p]) -> RangeTree (Report p) (Report p) r Source #

report :: Ord r => Range r -> RangeTree (Report p) q r -> [p] Source #

newtype CountOf p Source #

Constructors

CountOf [p]

Instances

Instances details

Functor CountOf Source #
Instance details Defined in Data.Geometry.RangeTree.Generic Methods fmap :: (a -> b) -> CountOf a -> CountOf b # (<$) :: a -> CountOf b -> CountOf a #
Foldable CountOf Source #
Instance details Defined in Data.Geometry.RangeTree.Generic Methods fold :: Monoid m => CountOf m -> m # foldMap :: Monoid m => (a -> m) -> CountOf a -> m # foldMap' :: Monoid m => (a -> m) -> CountOf a -> m # foldr :: (a -> b -> b) -> b -> CountOf a -> b # foldr' :: (a -> b -> b) -> b -> CountOf a -> b # foldl :: (b -> a -> b) -> b -> CountOf a -> b # foldl' :: (b -> a -> b) -> b -> CountOf a -> b # foldr1 :: (a -> a -> a) -> CountOf a -> a # foldl1 :: (a -> a -> a) -> CountOf a -> a # toList :: CountOf a -> [a] # null :: CountOf a -> Bool # length :: CountOf a -> Int # elem :: Eq a => a -> CountOf a -> Bool # maximum :: Ord a => CountOf a -> a # minimum :: Ord a => CountOf a -> a # sum :: Num a => CountOf a -> a # product :: Num a => CountOf a -> a #
Eq p => Eq (CountOf p) Source #
Instance details Defined in Data.Geometry.RangeTree.Generic Methods (==) :: CountOf p -> CountOf p -> Bool # (/=) :: CountOf p -> CountOf p -> Bool #
Ord p => Ord (CountOf p) Source #
Instance details Defined in Data.Geometry.RangeTree.Generic Methods compare :: CountOf p -> CountOf p -> Ordering # (<) :: CountOf p -> CountOf p -> Bool # (<=) :: CountOf p -> CountOf p -> Bool # (>) :: CountOf p -> CountOf p -> Bool # (>=) :: CountOf p -> CountOf p -> Bool # max :: CountOf p -> CountOf p -> CountOf p # min :: CountOf p -> CountOf p -> CountOf p #
Show p => Show (CountOf p) Source #
Instance details Defined in Data.Geometry.RangeTree.Generic Methods showsPrec :: Int -> CountOf p -> ShowS # show :: CountOf p -> String # showList :: [CountOf p] -> ShowS #
Semigroup (CountOf p) Source #
Instance details Defined in Data.Geometry.RangeTree.Generic Methods (<>) :: CountOf p -> CountOf p -> CountOf p # sconcat :: NonEmpty (CountOf p) -> CountOf p # stimes :: Integral b => b -> CountOf p -> CountOf p #
Monoid (CountOf p) Source #
Instance details Defined in Data.Geometry.RangeTree.Generic Methods mempty :: CountOf p # mappend :: CountOf p -> CountOf p -> CountOf p # mconcat :: [CountOf p] -> CountOf p #
Measured (Count p) (CountOf p) Source #
Instance details Defined in Data.Geometry.RangeTree.Generic Methods measure :: CountOf p -> Count p #

createCountingTree :: Ord r => NonEmpty (r :+ [p]) -> RangeTree (Count p) (CountOf p) r Source #

count :: Ord r => Range r -> RangeTree (Count p) q r -> Int Source #

Perform a counting query