-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | R-Tree is a spatial data structure similar to Quadtrees or B-Trees.
--   
--   R-Tree is a spatial data structure similar to Quadtrees or B-Trees. An
--   R-Tree is a balanced tree and optimized for lookups. This
--   implemetation useses an R-Tree to privide a map to arbitrary values.
@package data-r-tree
@version 0.6.0


-- | This module provides a minimal bounding box.
module Data.RTree.MBB

-- | Minimal bounding box
data MBB
MBB :: {-# UNPACK #-} !Double -> {-# UNPACK #-} !Double -> {-# UNPACK #-} !Double -> {-# UNPACK #-} !Double -> MBB
[getUlx] :: MBB -> {-# UNPACK #-} !Double
[getUly] :: MBB -> {-# UNPACK #-} !Double
[getBrx] :: MBB -> {-# UNPACK #-} !Double
[getBry] :: MBB -> {-# UNPACK #-} !Double

-- | created a minimal bounding box (or a rectangle) The first point must
--   be smaller, than the second one. This is unchecked.
mbb :: Double -> Double -> Double -> Double -> MBB

-- | calculates the area of the rect
area :: MBB -> Double

-- | returns True, when the first mbb contains the second
containsMBB :: MBB -> MBB -> Bool

-- | unifies two MBBs into one
unionMBB :: MBB -> MBB -> MBB

-- | internal only.
unionsMBB :: [MBB] -> MBB

-- | returns the intersection of both mbbs. Returns Nothing, if they don't
--   intersect.
intersectMBB :: MBB -> MBB -> Maybe MBB

-- | the property, that a <a>MBB</a> must hold
isValidMBB :: MBB -> Bool
isPointMBB :: MBB -> Bool
instance GHC.Classes.Ord Data.RTree.MBB.MBB
instance GHC.Generics.Generic Data.RTree.MBB.MBB
instance GHC.Classes.Eq Data.RTree.MBB.MBB
instance GHC.Show.Show Data.RTree.MBB.MBB
instance Data.Binary.Class.Binary Data.RTree.MBB.MBB


-- | Internal implementations. Use <a>RTree</a> instead or use at you own
--   risc.
module Data.RTree.Base
data RTree a
Node4 :: {-# UNPACK #-} !MBB -> !RTree a -> !RTree a -> !RTree a -> !RTree a -> RTree a
[getMBB] :: RTree a -> {-# UNPACK #-} !MBB
[getC1] :: RTree a -> !RTree a
[getC2] :: RTree a -> !RTree a
[getC3] :: RTree a -> !RTree a
[getC4] :: RTree a -> !RTree a
Node3 :: {-# UNPACK #-} !MBB -> !RTree a -> !RTree a -> !RTree a -> RTree a
[getMBB] :: RTree a -> {-# UNPACK #-} !MBB
[getC1] :: RTree a -> !RTree a
[getC2] :: RTree a -> !RTree a
[getC3] :: RTree a -> !RTree a
Node2 :: {-# UNPACK #-} !MBB -> !RTree a -> !RTree a -> RTree a
[getMBB] :: RTree a -> {-# UNPACK #-} !MBB
[getC1] :: RTree a -> !RTree a
[getC2] :: RTree a -> !RTree a
Node :: MBB -> [RTree a] -> RTree a
[getMBB] :: RTree a -> MBB
[getChildren'] :: RTree a -> [RTree a]
Leaf :: {-# UNPACK #-} !MBB -> a -> RTree a
[getMBB] :: RTree a -> {-# UNPACK #-} !MBB
[getElem] :: RTree a -> a
Empty :: RTree a

-- | creates an empty tree
empty :: RTree a

-- | creates a single element tree
singleton :: MBB -> a -> RTree a

-- | Inserts an element whith the given <a>MBB</a> and a value in a tree.
--   An existing value will be overwritten with the given one.
--   
--   <pre>
--   insert = insertWith const
--   </pre>
insert :: MBB -> a -> RTree a -> RTree a

-- | Inserts an element whith the given <a>MBB</a> and a value in a tree.
--   The combining function will be used if the value already exists.
insertWith :: (a -> a -> a) -> MBB -> a -> RTree a -> RTree a

-- | Delete a key and its value from the RTree. When the key is not a
--   member of the tree, the original tree is returned.
delete :: MBB -> RTree a -> RTree a

-- | map, which also filters Nothing values
mapMaybe :: (a -> Maybe b) -> RTree a -> RTree b

-- | Unifies the first and the second tree into one. If an <a>MBB</a> is a
--   key in both trees, the value from the left tree is chosen.
--   
--   <pre>
--   union = unionWith const
--   </pre>
union :: RTree a -> RTree a -> RTree a

-- | Unifies the first and the second tree into one. The combining function
--   is used for elemets which exists in both trees.
unionWith :: (a -> a -> a) -> RTree a -> RTree a -> RTree a

-- | returns the value if it exists in the tree
lookup :: MBB -> RTree a -> Maybe a

-- | returns all keys and values, which intersects with the given bounding
--   box.
intersectWithKey :: MBB -> RTree a -> [(MBB, a)]

-- | returns all values, which intersects with the given bounding box.
intersect :: MBB -> RTree a -> [a]

-- | returns all values, which are located in the given bounding box.
lookupRange :: MBB -> RTree a -> [a]

-- | returns all keys and values, which are located in the given bounding
--   box.
lookupRangeWithKey :: MBB -> RTree a -> [(MBB, a)]

-- | returns all keys and values containing the given bounding box
lookupContainsRangeWithKey :: MBB -> RTree a -> [(MBB, a)]

-- | returns all values containing the given bounding box
lookupContainsRange :: MBB -> RTree a -> [a]

-- | returns the number of elements in a tree
length :: RTree a -> Int

-- | returns <a>True</a>, if empty
--   
--   <pre>
--   null empty = True
--   </pre>
null :: RTree a -> Bool

-- | returns all keys in this tree
--   
--   <pre>
--   toList t = zip (keys t) (values t)
--   </pre>
keys :: RTree a -> [MBB]

-- | returns all values in this tree
--   
--   <pre>
--   toList t = zip (keys t) (values t)
--   </pre>
values :: RTree a -> [a]

-- | creates a tree out of pairs
fromList :: [(MBB, a)] -> RTree a

-- | creates a list of pairs out of a tree
--   
--   <pre>
--   toList t = zip (keys t) (values t)
--   </pre>
toList :: RTree a -> [(MBB, a)]
foldWithMBB :: (MBB -> a -> b) -> (MBB -> [b] -> b) -> b -> RTree a -> b
pp :: Show a => RTree a -> IO ()
isValid :: Show b => b -> RTree a -> Bool

-- | Únifies left and right <a>RTree</a>. Will create invalid trees, if the
--   tree is not a leaf and contains <a>MBB</a>s which also exists in the
--   left tree. Much faster than union, though.
unionDistinct :: RTree a -> RTree a -> RTree a

-- | Unifies left and right <a>RTree</a>. Will create invalid trees, if the
--   tree is not a leaf and contains <a>MBB</a>s which also exists in the
--   left tree. Much faster than union, though.
unionDistinctWith :: (a -> a -> a) -> RTree a -> RTree a -> RTree a

-- | merges all singletons into a single tree.
fromList' :: [RTree a] -> RTree a
unionDistinctSplit :: (a -> a -> a) -> RTree a -> RTree a -> [RTree a]
depth :: RTree a -> Int
areaIncreasesWith :: RTree a -> RTree a -> Double

-- | The <a>partition</a> function takes a predicate a list and returns the
--   pair of lists of elements which do and do not satisfy the predicate,
--   respectively; i.e.,
--   
--   <pre>
--   partition p xs == (filter p xs, filter (not . p) xs)
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; partition (`elem` "aeiou") "Hello World!"
--   ("eoo","Hll Wrld!")
--   </pre>
partition :: () => (a -> Bool) -> [a] -> ([a], [a])
getChildren :: RTree a -> [RTree a]
unionMBB' :: RTree a -> RTree a -> MBB
createNodeWithChildren :: [RTree a] -> RTree a

-- | It is possible, to change these constants, but the tree won't be space
--   optimal anymore.
n :: Int

-- | <i>O(n²)</i> solution
splitNode :: RTree a -> [RTree a]
node :: MBB -> [RTree a] -> RTree a
instance GHC.Base.Functor Data.RTree.Base.RTree
instance GHC.Generics.Generic (Data.RTree.Base.RTree a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.RTree.Base.RTree a)
instance GHC.Show.Show a => GHC.Show.Show (Data.RTree.Base.RTree a)
instance Control.DeepSeq.NFData a => Control.DeepSeq.NFData (Data.RTree.Base.RTree a)
instance Data.Binary.Class.Binary a => Data.Binary.Class.Binary (Data.RTree.Base.RTree a)
instance GHC.Base.Semigroup a => GHC.Base.Semigroup (Data.RTree.Base.RTree a)
instance GHC.Base.Monoid a => GHC.Base.Monoid (Data.RTree.Base.RTree a)


-- | R-Tree is a spatial data structure similar to Quadtrees or B-Trees.
--   
--   An R-Tree is a balanced tree and optimized for lookups. This
--   implemetation useses an R-Tree to privide a map to arbitrary values.
--   
--   Some function names clash with <a>Prelude</a> names, therefore this
--   module is usually imported <tt>qualified</tt>, e.g.
--   
--   <pre>
--   import           Data.RTree (RTree)
--   import qualified Data.RTree as RT
--   </pre>
--   
--   this implemetation is incomplete at the moment. Feel free to send
--   comments, patches or merge requests.
module Data.RTree

-- | Minimal bounding box
data MBB

-- | created a minimal bounding box (or a rectangle) The first point must
--   be smaller, than the second one. This is unchecked.
mbb :: Double -> Double -> Double -> Double -> MBB
data RTree a

-- | creates an empty tree
empty :: RTree a

-- | creates a single element tree
singleton :: MBB -> a -> RTree a

-- | Inserts an element whith the given <a>MBB</a> and a value in a tree.
--   An existing value will be overwritten with the given one.
--   
--   <pre>
--   insert = insertWith const
--   </pre>
insert :: MBB -> a -> RTree a -> RTree a

-- | Inserts an element whith the given <a>MBB</a> and a value in a tree.
--   The combining function will be used if the value already exists.
insertWith :: (a -> a -> a) -> MBB -> a -> RTree a -> RTree a

-- | Delete a key and its value from the RTree. When the key is not a
--   member of the tree, the original tree is returned.
delete :: MBB -> RTree a -> RTree a

-- | map, which also filters Nothing values
mapMaybe :: (a -> Maybe b) -> RTree a -> RTree b

-- | Unifies the first and the second tree into one. If an <a>MBB</a> is a
--   key in both trees, the value from the left tree is chosen.
--   
--   <pre>
--   union = unionWith const
--   </pre>
union :: RTree a -> RTree a -> RTree a

-- | Unifies the first and the second tree into one. The combining function
--   is used for elemets which exists in both trees.
unionWith :: (a -> a -> a) -> RTree a -> RTree a -> RTree a

-- | returns the value if it exists in the tree
lookup :: MBB -> RTree a -> Maybe a

-- | returns all keys and values, which intersects with the given bounding
--   box.
intersectWithKey :: MBB -> RTree a -> [(MBB, a)]

-- | returns all values, which intersects with the given bounding box.
intersect :: MBB -> RTree a -> [a]

-- | returns all values, which are located in the given bounding box.
lookupRange :: MBB -> RTree a -> [a]

-- | returns all keys and values, which are located in the given bounding
--   box.
lookupRangeWithKey :: MBB -> RTree a -> [(MBB, a)]

-- | returns all values containing the given bounding box
lookupContainsRange :: MBB -> RTree a -> [a]

-- | returns all keys and values containing the given bounding box
lookupContainsRangeWithKey :: MBB -> RTree a -> [(MBB, a)]

-- | returns the number of elements in a tree
length :: RTree a -> Int

-- | returns <a>True</a>, if empty
--   
--   <pre>
--   null empty = True
--   </pre>
null :: RTree a -> Bool

-- | returns all keys in this tree
--   
--   <pre>
--   toList t = zip (keys t) (values t)
--   </pre>
keys :: RTree a -> [MBB]

-- | returns all values in this tree
--   
--   <pre>
--   toList t = zip (keys t) (values t)
--   </pre>
values :: RTree a -> [a]

-- | creates a tree out of pairs
fromList :: [(MBB, a)] -> RTree a

-- | creates a list of pairs out of a tree
--   
--   <pre>
--   toList t = zip (keys t) (values t)
--   </pre>
toList :: RTree a -> [(MBB, a)]


-- | This is the Strict version of <a>RTree</a>
--   
--   the following property should be true (by using <a>isNF</a> ) :
--   
--   <pre>
--   &gt;&gt;&gt; propNF :: RTree a -&gt; IO Bool
--   
--   &gt;&gt;&gt; propNF e = isNF $! e
--   </pre>
module Data.RTree.Strict

-- | Minimal bounding box
data MBB

-- | created a minimal bounding box (or a rectangle) The first point must
--   be smaller, than the second one. This is unchecked.
mbb :: Double -> Double -> Double -> Double -> MBB
data RTree a

-- | converts a strict RTree into a lazy RTree <i>O(1)</i>
toLazy :: RTree a -> RTree a

-- | converts a lazy RTree into a strict RTree <i>O(n)</i>
toStrict :: RTree a -> RTree a

-- | creates an empty tree
empty :: RTree a

-- | creates a single element tree
singleton :: MBB -> a -> RTree a

-- | Inserts an element whith the given <a>MBB</a> and a value in a tree.
--   An existing value will be overwritten with the given one.
--   
--   <pre>
--   insert = insertWith const
--   </pre>
insert :: MBB -> a -> RTree a -> RTree a

-- | Inserts an element whith the given <a>MBB</a> and a value in a tree.
--   The combining function will be used if the value already exists.
insertWith :: (a -> a -> a) -> MBB -> a -> RTree a -> RTree a

-- | Delete a key and its value from the RTree. When the key is not a
--   member of the tree, the original tree is returned.
delete :: MBB -> RTree a -> RTree a

-- | map, which also filters Nothing values
mapMaybe :: (a -> Maybe b) -> RTree a -> RTree b

-- | Unifies the first and the second tree into one. If an <a>MBB</a> is a
--   key in both trees, the value from the left tree is chosen.
--   
--   <pre>
--   union = unionWith const
--   </pre>
union :: RTree a -> RTree a -> RTree a

-- | Unifies the first and the second tree into one. The combining function
--   is used for elemets which exists in both trees.
unionWith :: (a -> a -> a) -> RTree a -> RTree a -> RTree a

-- | returns the value if it exists in the tree
lookup :: MBB -> RTree a -> Maybe a

-- | returns all keys and values, which intersect with the given bounding
--   box.
intersectWithKey :: MBB -> RTree a -> [(MBB, a)]

-- | returns all values, which intersect with the given bounding box
intersect :: MBB -> RTree a -> [a]

-- | returns all values, which are located in the given bounding box.
lookupRange :: MBB -> RTree a -> [a]

-- | returns all keys and values, which are located in the given bounding
--   box.
lookupRangeWithKey :: MBB -> RTree a -> [(MBB, a)]

-- | returns all values containing the given bounding box
lookupContainsRange :: MBB -> RTree a -> [a]

-- | returns all keys and values containing the given bounding box
lookupContainsRangeWithKey :: MBB -> RTree a -> [(MBB, a)]

-- | returns the number of elements in a tree
length :: RTree a -> Int

-- | returns <a>True</a>, if empty
--   
--   <pre>
--   null empty = True
--   </pre>
null :: RTree a -> Bool

-- | returns all keys in this tree
--   
--   <pre>
--   toList t = zip (keys t) (values t)
--   </pre>
keys :: RTree a -> [MBB]

-- | returns all values in this tree
--   
--   <pre>
--   toList t = zip (keys t) (values t)
--   </pre>
values :: RTree a -> [a]

-- | creates a tree out of pairs
fromList :: [(MBB, a)] -> RTree a

-- | creates a list of pairs out of a tree
--   
--   <pre>
--   toList t = zip (keys t) (values t)
--   </pre>
toList :: RTree a -> [(MBB, a)]
instance GHC.Base.Semigroup a => GHC.Base.Semigroup (Data.RTree.Strict.RTree a)
instance GHC.Base.Monoid a => GHC.Base.Monoid (Data.RTree.Strict.RTree a)
instance Data.Binary.Class.Binary a => Data.Binary.Class.Binary (Data.RTree.Strict.RTree a)
instance Control.DeepSeq.NFData a => Control.DeepSeq.NFData (Data.RTree.Strict.RTree a)
instance GHC.Generics.Generic (Data.RTree.Strict.RTree a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.RTree.Strict.RTree a)
instance GHC.Show.Show a => GHC.Show.Show (Data.RTree.Strict.RTree a)
instance GHC.Base.Functor Data.RTree.Strict.RTree