Copyright | Copyright (c) 2015 Birte Wagner Sebastian Philipp Copyright (c) 2022 Oleksii Divak |
---|---|

License | MIT |

Maintainer | Oleksii Divak |

Stability | experimental |

Portability | not portable |

Safe Haskell | Safe-Inferred |

Language | Haskell2010 |

is a spine-strict two-dimensional spatial tree using `R2Tree`

a`Double`

s as keys.

R-trees have no notion of element order, as such:

- Duplicate
`MBR`

s are permitted. Inserting a duplicate may put it anywhere on the tree, there is no guarantee a successive`delete`

will pick the newer entry over the older one. - Updating an
`MBR`

of an entry requires a reinsertion of said entry. - Merge operations are not supported.

## Laziness

Evaluating the root of the tree (i.e. `(_ :: `

) to WHNF
evaluates the entire spine of the tree to normal form.`R2Tree`

a)

Functions do not perform any additional evaluations unless their documentation directly specifies so.

## Performance

Each function's time complexity is provided in the documentation.

\(n\) refers to the total number of entries in the tree.
Parts of the tree are denoted using subscripts: \(n_L\) refers to the left side,
\(n_R\) to the right side, \(n_I\) to a range (interval), and
\(n_M\) to entries collected with the use of a `Monoid`

.

## Inlining

Functions that produce and consume `Predicate`

s inline heavily.
To avoid unnecessary code duplication during compilation consider creating
helper functions that apply these functions one to another, e.g.

listIntersections ::`MBR`

->`R2Tree`

a -> [(`MBR`

, a)] listIntersections mbr = foldrRangeWithKey (intersects mbr) (a b -> (:) (a, b)) []

N.B. To inline properly functions that consume `Predicate`

s
must mention all of the arguments except for the tree.

## Implementation

The implementation is heavily specialized for constants \(m = 2, M = 4, p = 1, k = 1\).

Descriptions of the R-/R*-tree and of the algorithms implemented can be found within the following papers:

- Antonin Guttman (1984),
"
*R-Trees: A Dynamic Index Structure for Spatial Searching*", http://www-db.deis.unibo.it/courses/SI-LS/papers/Gut84.pdf - N. Beckmann, H.P. Kriegel, R. Schneider, B. Seeger (1990),
"
*The R*-tree: an efficient and robust access method for points and rectangles*", https://infolab.usc.edu/csci599/Fall2001/paper/rstar-tree.pdf - S.T. Leutenegger, J.M. Edgington, M.A. Lopez (1997),
"
*STR: A Simple and Efficient Algorithm for R-Tree Packing*", https://ia800900.us.archive.org/27/items/nasa_techdoc_19970016975/19970016975.pdf

## Synopsis

- data MBR where
- data R2Tree a
- empty :: R2Tree a
- singleton :: MBR -> a -> R2Tree a
- doubleton :: MBR -> a -> MBR -> a -> R2Tree a
- tripleton :: MBR -> a -> MBR -> a -> MBR -> a -> R2Tree a
- quadrupleton :: MBR -> a -> MBR -> a -> MBR -> a -> MBR -> a -> R2Tree a
- bulkSTR :: [(MBR, a)] -> R2Tree a
- insert :: MBR -> a -> R2Tree a -> R2Tree a
- insertGut :: MBR -> a -> R2Tree a -> R2Tree a
- delete :: MBR -> R2Tree a -> R2Tree a
- data Predicate
- equals :: MBR -> Predicate
- intersects :: MBR -> Predicate
- intersects' :: MBR -> Predicate
- contains :: MBR -> Predicate
- contains' :: MBR -> Predicate
- containedBy :: MBR -> Predicate
- containedBy' :: MBR -> Predicate
- adjustRangeWithKey :: Predicate -> (MBR -> a -> a) -> R2Tree a -> R2Tree a
- adjustRangeWithKey' :: Predicate -> (MBR -> a -> a) -> R2Tree a -> R2Tree a
- foldlRangeWithKey :: Predicate -> (b -> MBR -> a -> b) -> b -> R2Tree a -> b
- foldrRangeWithKey :: Predicate -> (MBR -> a -> b -> b) -> b -> R2Tree a -> b
- foldMapRangeWithKey :: Monoid m => Predicate -> (MBR -> a -> m) -> R2Tree a -> m
- foldlRangeWithKey' :: Predicate -> (b -> MBR -> a -> b) -> b -> R2Tree a -> b
- foldrRangeWithKey' :: Predicate -> (MBR -> a -> b -> b) -> b -> R2Tree a -> b
- traverseRangeWithKey :: Applicative f => Predicate -> (MBR -> a -> f a) -> R2Tree a -> f (R2Tree a)
- null :: R2Tree a -> Bool
- size :: R2Tree a -> Int
- map :: (a -> b) -> R2Tree a -> R2Tree b
- map' :: (a -> b) -> R2Tree a -> R2Tree b
- mapWithKey :: (MBR -> a -> b) -> R2Tree a -> R2Tree b
- mapWithKey' :: (MBR -> a -> b) -> R2Tree a -> R2Tree b
- foldl :: (b -> a -> b) -> b -> R2Tree a -> b
- foldl' :: (b -> a -> b) -> b -> R2Tree a -> b
- foldlWithKey :: (b -> MBR -> a -> b) -> b -> R2Tree a -> b
- foldlWithKey' :: (b -> MBR -> a -> b) -> b -> R2Tree a -> b
- foldr :: (a -> b -> b) -> b -> R2Tree a -> b
- foldr' :: (a -> b -> b) -> b -> R2Tree a -> b
- foldrWithKey :: (MBR -> a -> b -> b) -> b -> R2Tree a -> b
- foldrWithKey' :: (MBR -> a -> b -> b) -> b -> R2Tree a -> b
- foldMap :: Monoid m => (a -> m) -> R2Tree a -> m
- foldMapWithKey :: Monoid m => (MBR -> a -> m) -> R2Tree a -> m
- traverse :: Applicative f => (a -> f b) -> R2Tree a -> f (R2Tree b)
- traverseWithKey :: Applicative f => (MBR -> a -> f b) -> R2Tree a -> f (R2Tree b)

# Documentation

Two-dimensional minimum bounding rectangle is defined as two intervals, each along a separate axis, where every endpoint is either bounded and closed (i.e. \( [a, b] \)), or infinity (i.e. \((\pm \infty, b]\)).

Degenerate intervals (i.e. \([a,a]\)) are permitted.

pattern MBR | Reorders coordinates to fit internal invariants. Pattern matching guarantees \( x_{0} \le x_{1}, y_{0} \le y_{1} \). |

Spine-strict two-dimensional R-tree.

#### Instances

Foldable R2Tree Source # | |

Defined in Data.R2Tree.Double.Internal fold :: Monoid m => R2Tree m -> m # foldMap :: Monoid m => (a -> m) -> R2Tree a -> m # foldMap' :: Monoid m => (a -> m) -> R2Tree a -> m # foldr :: (a -> b -> b) -> b -> R2Tree a -> b # foldr' :: (a -> b -> b) -> b -> R2Tree a -> b # foldl :: (b -> a -> b) -> b -> R2Tree a -> b # foldl' :: (b -> a -> b) -> b -> R2Tree a -> b # foldr1 :: (a -> a -> a) -> R2Tree a -> a # foldl1 :: (a -> a -> a) -> R2Tree a -> a # elem :: Eq a => a -> R2Tree a -> Bool # maximum :: Ord a => R2Tree a -> a # minimum :: Ord a => R2Tree a -> a # | |

Eq1 R2Tree Source # | |

Show1 R2Tree Source # | |

Traversable R2Tree Source # | |

Functor R2Tree Source # | Uses |

NFData1 R2Tree Source # | |

Defined in Data.R2Tree.Double.Internal | |

Show a => Show (R2Tree a) Source # | |

NFData a => NFData (R2Tree a) Source # | |

Defined in Data.R2Tree.Double.Internal | |

Eq a => Eq (R2Tree a) Source # | |

# Construct

tripleton :: MBR -> a -> MBR -> a -> MBR -> a -> R2Tree a Source #

\(\mathcal{O}(1)\). Tree with three entries.

quadrupleton :: MBR -> a -> MBR -> a -> MBR -> a -> MBR -> a -> R2Tree a Source #

\(\mathcal{O}(1)\). Tree with four entries.

## Bulk-loading

bulkSTR :: [(MBR, a)] -> R2Tree a Source #

\(\mathcal{O}(n \log n)\). Bulk-load a tree.

`bulkSTR`

uses the Sort-Tile-Recursive algorithm.

# Single-key

## Insert

insert :: MBR -> a -> R2Tree a -> R2Tree a Source #

\(\mathcal{O}(\log n)\). Insert a value into the tree.

`insert`

uses the R*-tree insertion algorithm.

insertGut :: MBR -> a -> R2Tree a -> R2Tree a Source #

\(\mathcal{O}(\log n)\). Insert a value into the tree.

`insertGut`

uses the R-tree insertion algorithm with quadratic-cost splits.
Compared to `insert`

the resulting trees are of lower quality (see the
Wikipedia article
for a graphic example).

## Delete

# Range

intersects' :: MBR -> Predicate Source #

Matches any `MBR`

that intersects the provided one, if the
intersection is not a line or a point.

contains' :: MBR -> Predicate Source #

Matches any `MBR`

that contains the provided one,
excluding ones that touch it on one or more sides.

containedBy' :: MBR -> Predicate Source #

Matches any `MBR`

that is contained within the provided one,
excluding ones that touch it on one or more sides.

## Map

## Fold

## Traverse

traverseRangeWithKey :: Applicative f => Predicate -> (MBR -> a -> f a) -> R2Tree a -> f (R2Tree a) Source #

# Full tree

## Size

size :: R2Tree a -> Int Source #

\(\mathcal{O}(n)\). Calculate the number of elements stored in the tree. The returned number is guaranteed to be non-negative.

## Map

map' :: (a -> b) -> R2Tree a -> R2Tree b Source #

\(\mathcal{O}(n)\). Map a function over all values and evaluate the results to WHNF.

mapWithKey :: (MBR -> a -> b) -> R2Tree a -> R2Tree b Source #

\(\mathcal{O}(n)\).
Map a function over all `MBR`

s and their respective values.

mapWithKey' :: (MBR -> a -> b) -> R2Tree a -> R2Tree b Source #

\(\mathcal{O}(n)\).
Map a function over all `MBR`

s and their respective values
and evaluate the results to WHNF.

## Fold

### Left-to-right

foldl :: (b -> a -> b) -> b -> R2Tree a -> b Source #

\(\mathcal{O}(n_R)\). Fold left-to-right over all values.

foldl' :: (b -> a -> b) -> b -> R2Tree a -> b Source #

\(\mathcal{O}(n)\). Fold left-to-right over all values, applying the operator function strictly.

foldlWithKey :: (b -> MBR -> a -> b) -> b -> R2Tree a -> b Source #

\(\mathcal{O}(n_R)\).
Fold left-to-right over all `MBR`

s and their respective values.

foldlWithKey' :: (b -> MBR -> a -> b) -> b -> R2Tree a -> b Source #

\(\mathcal{O}(n)\).
Fold left-to-right over all `MBR`

s and their respective values,
applying the operator function strictly.

### Right-to-left

foldr :: (a -> b -> b) -> b -> R2Tree a -> b Source #

\(\mathcal{O}(n_L)\). Fold right-to-left over all values.

foldr' :: (a -> b -> b) -> b -> R2Tree a -> b Source #

\(\mathcal{O}(n)\). Fold right-to-left over all values, applying the operator function strictly.

foldrWithKey :: (MBR -> a -> b -> b) -> b -> R2Tree a -> b Source #

\(\mathcal{O}(n_L)\).
Fold right-to-left over all `MBR`

s and their respective values.

foldrWithKey' :: (MBR -> a -> b -> b) -> b -> R2Tree a -> b Source #

\(\mathcal{O}(n)\).
Fold right-to-left over all `MBR`

s and their respective values,
applying the operator function strictly.

### Monoid

foldMap :: Monoid m => (a -> m) -> R2Tree a -> m Source #

\(\mathcal{O}(n_M)\). Map each value to a monoid and combine the results.

foldMapWithKey :: Monoid m => (MBR -> a -> m) -> R2Tree a -> m Source #

\(\mathcal{O}(n_M)\).
Map each `MBR`

and its respective value to a monoid and combine the results.

## Traverse

traverse :: Applicative f => (a -> f b) -> R2Tree a -> f (R2Tree b) Source #

\(\mathcal{O}(n)\). Map each value to an action, evaluate the actions left-to-right and collect the results.

traverseWithKey :: Applicative f => (MBR -> a -> f b) -> R2Tree a -> f (R2Tree b) Source #

\(\mathcal{O}(n)\).
Map each `MBR`

and its respective value to an action,
evaluate the actions left-to-right and collect the results.