Data.RTree.Strict

This is the Strict version of RTree

the following property should be true (by using isNF ) :

>>> propNF :: RTree a -> IO Bool
>>> propNF e = isNF $! e

MBB

data MBB

Minimal bounding box

Instances

Eq MBB

Show MBB

Generic MBB

Binary MBB

mbb

Arguments

:: Double

x - coordinate of first point

-> Double

y - coordinate of first point

-> Double

x - coordinate of second point

-> Double

x - coordinate of second point

-> MBB

created a minimal bounding box (or a rectangle) The first point must be smaller, than the second one. This is unchecked.

Data Type

data RTree a

Instances

Functor RTree

RTree is not really a Functor. Because thsi law dowsn't hold:

fmap id = id

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)

toLazy :: RTree a -> RTree a

converts a strict RTree into a lazy RTree O(1)

toStrict :: RTree a -> RTree a

converts a lazy RTree into a strict RTree O(n)

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)