Data.RTree.Base

Internal implementations. Use RTree instead or use at you own risc.

Data Type

data RTree a

Constructors

Node4

Fields

getMBB :: !MBB

getC1 :: !(RTree a)

getC2 :: !(RTree a)

getC3 :: !(RTree a)

getC4 :: !(RTree a)

Node3

Fields

getMBB :: !MBB

getC1 :: !(RTree a)

getC2 :: !(RTree a)

getC3 :: !(RTree a)

Node2

Fields

getMBB :: !MBB

getC1 :: !(RTree a)

getC2 :: !(RTree a)

Node

Fields

getMBB :: MBB

getChildren' :: [RTree a]

Leaf

Fields

getMBB :: !MBB

getElem :: a

Empty

Instances

Functor RTree

Typeable1 RTree

Eq a => Eq (RTree a)

Show a => Show (RTree a)

Generic (RTree a)

Monoid a => Monoid (RTree a)

Binary a => Binary (RTree a)

NFData a => NFData (RTree a)

Constructors

empty :: RTree a

creates an empty tree

singleton :: MBB -> a -> RTree a

creates a single element tree

Modification

insert :: MBB -> a -> RTree a -> RTree a

Inserts an element whith the given MBB and a value in a tree. An existing value will be overwritten with the given one.

insert = insertWith const

insertWith :: (a -> a -> a) -> MBB -> a -> RTree a -> RTree a

Inserts an element whith the given MBB and a value in a tree. The combining function will be used if the value already exists.

delete :: MBB -> 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.

mapMaybe :: (a -> Maybe b) -> RTree a -> RTree b

map, which also filters Nothing values

Merging

union :: RTree a -> RTree a -> RTree a

Unifies the first and the second tree into one. If an MBB is a key in both trees, the value from the left tree is chosen.

union = unionWith const

unionWith :: (a -> a -> a) -> 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.

Searching and Properties

lookup :: MBB -> RTree a -> Maybe a

returns the value if it exists in the tree

lookupRange :: MBB -> RTree a -> [a]

returns all values, which are located in the given bounding box.

lookupRangeWithKey :: MBB -> RTree a -> [(MBB, a)]

returns all keys and values, which are located in the given bounding box.

length :: RTree a -> Int

returns the number of elements in a tree

null :: RTree a -> Bool

returns True, if empty

null empty = True

keys :: RTree a -> [MBB]

returns all keys in this tree

toList t = zip (keys t) (values t)

values :: RTree a -> [a]

returns all values in this tree

toList t = zip (keys t) (values t)

Lists

fromList :: [(MBB, a)] -> RTree a

creates a tree out of pairs

toList :: RTree a -> [(MBB, a)]

creates a list of pairs out of a tree

toList t = zip (keys t) (values t)

Internal and Testing

foldWithMBB :: (MBB -> a -> b) -> (MBB -> [b] -> b) -> b -> RTree a -> b

pp :: Show a => RTree a -> IO ()

isValid :: Show b => b -> RTree a -> Bool

unionDistinct :: RTree a -> RTree a -> RTree a

unionDistinctWith :: (a -> a -> a) -> RTree a -> RTree a -> RTree a

Unifies left and right RTree. Will create invalid trees, if the tree is not a leaf and contains MBBs which also exists in the left tree. Much faster than union, though.

fromList' :: [RTree a] -> RTree a

merges all singletons into a single tree.

unionDistinctSplit :: (a -> a -> a) -> RTree a -> RTree a -> [RTree a]

depth :: RTree a -> Int

areaIncreasesWith :: RTree a -> RTree a -> Double

partition :: (a -> Bool) -> [a] -> ([a], [a])

The partition 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.,

 partition p xs == (filter p xs, filter (not . p) xs)

getChildren :: RTree a -> [RTree a]

unionMBB' :: RTree a -> RTree a -> MBB

createNodeWithChildren :: [RTree a] -> RTree a

n :: Int

It is possible, to change these constants, but the tree won't be space optimal anymore.

splitNode :: RTree a -> [RTree a]

O(n² solution

node :: MBB -> [RTree a] -> RTree a