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

Data.Geometry.RangeTree.Generic

Description

 
Synopsis

Documentation

data NodeData v r Source #

Constructors

NodeData 

Fields

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

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

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 #

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

Perform a counting query