hgeometry-0.10.0.0: Geometric Algorithms, Data structures, and Data types.

Data.Geometry.RangeTree.Generic

Synopsis

# Documentation

data NodeData v r Source #

Constructors

 NodeData Fields_minVal :: !(Min r) _maxVal :: !(Max r) _assoc :: !v
Instances
 Source # Instance detailsDefined in Data.Geometry.RangeTree.Generic Methodsfmap :: (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 detailsDefined 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 detailsDefined in Data.Geometry.RangeTree.Generic MethodsshowsPrec :: 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 detailsDefined 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  (Eq r, Eq v, Eq q) => Eq (RangeTree v q r) Source # Instance detailsDefined 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 detailsDefined in Data.Geometry.RangeTree.Generic MethodsshowsPrec :: 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  Source # Instance detailsDefined in Data.Geometry.RangeTree.Generic Methodsfmap :: (a -> b) -> CountOf a -> CountOf b #(<$) :: a -> CountOf b -> CountOf a # Source # Instance detailsDefined in Data.Geometry.RangeTree.Generic Methodsfold :: 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) Source # Instance detailsDefined in Data.Geometry.RangeTree.Generic Methods(==) :: CountOf p -> CountOf p -> Bool #(/=) :: CountOf p -> CountOf p -> Bool # Ord p => Ord (CountOf p) Source # Instance detailsDefined in Data.Geometry.RangeTree.Generic Methodscompare :: 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 detailsDefined in Data.Geometry.RangeTree.Generic MethodsshowsPrec :: Int -> CountOf p -> ShowS #show :: CountOf p -> String #showList :: [CountOf p] -> ShowS # Source # Instance detailsDefined 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 # Source # Instance detailsDefined in Data.Geometry.RangeTree.Generic Methodsmappend :: CountOf p -> CountOf p -> CountOf p #mconcat :: [CountOf p] -> CountOf p # Measured (Count p) (CountOf p) Source # Instance detailsDefined in Data.Geometry.RangeTree.Generic Methodsmeasure :: CountOf p -> Count p #

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

Perform a counting query