Data.Geometry.RangeTree.Generic

Documentation

data NodeData v r

Constructors

NodeData

Fields

• _minVal :: !(Min r)
• _maxVal :: !(Max r)
• _assoc :: !v

Instances

Functor (NodeData v)

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)

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)

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)

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

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

(Eq r, Eq v, Eq q) => Eq (RangeTree v q r)

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)

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

Creates a range tree

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

pre: input is sorted and grouped by x-coord

Converting to a List

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

Lists all points in increasing order

running time: \(O(n)\)

Querying x

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

Range search

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

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

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]

The actual search

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

Helper function to get the range of a binary leaf tree

rangeOf' :: NodeData v r -> Range r

Get the range of a node

Updates

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

Constructors

CountOf [p]

Instances

Functor CountOf

Defined in Data.Geometry.RangeTree.Generic

Methods

fmap :: (a -> b) -> CountOf a -> CountOf b

(<$) :: a -> CountOf b -> CountOf a

Foldable CountOf

Defined in Data.Geometry.RangeTree.Generic

Methods

fold :: Monoid m => CountOf m -> 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)

Defined in Data.Geometry.RangeTree.Generic

Methods

(==) :: CountOf p -> CountOf p -> Bool

(/=) :: CountOf p -> CountOf p -> Bool

Ord p => Ord (CountOf p)

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)

Defined in Data.Geometry.RangeTree.Generic

Methods

showsPrec :: Int -> CountOf p -> ShowS

show :: CountOf p -> String

showList :: [CountOf p] -> ShowS

Semigroup (CountOf p)

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)

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)

Defined in Data.Geometry.RangeTree.Generic

Methods

measure :: CountOf p -> Count p

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

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

Perform a counting query