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

Defined in Data.RTree.MBB

Methods

(==) :: MBB -> MBB -> Bool

(/=) :: MBB -> MBB -> Bool

Ord MBB

Defined in Data.RTree.MBB

Methods

compare :: MBB -> MBB -> Ordering

(<) :: MBB -> MBB -> Bool

(<=) :: MBB -> MBB -> Bool

(>) :: MBB -> MBB -> Bool

(>=) :: MBB -> MBB -> Bool

max :: MBB -> MBB -> MBB

min :: MBB -> MBB -> MBB

Show MBB

Defined in Data.RTree.MBB

Methods

showsPrec :: Int -> MBB -> ShowS

show :: MBB -> String

showList :: [MBB] -> ShowS

Generic MBB

Defined in Data.RTree.MBB

Associated Types

type Rep MBB :: Type -> Type

Methods

from :: MBB -> Rep MBB x

to :: Rep MBB x -> MBB

Binary MBB

Defined in Data.RTree.MBB

Methods

put :: MBB -> Put

get :: Get MBB

putList :: [MBB] -> Put

type Rep MBB

Defined in Data.RTree.MBB

type Rep MBB = D1 (MetaData "MBB" "Data.RTree.MBB" "data-r-tree-0.6.0-HxW7KWxwR847heBr9qHG8D" False) (C1 (MetaCons "MBB" PrefixI True) ((S1 (MetaSel (Just "getUlx") SourceUnpack SourceStrict DecidedStrict) (Rec0 Double) :*: S1 (MetaSel (Just "getUly") SourceUnpack SourceStrict DecidedStrict) (Rec0 Double)) :*: (S1 (MetaSel (Just "getBrx") SourceUnpack SourceStrict DecidedStrict) (Rec0 Double) :*: S1 (MetaSel (Just "getBry") SourceUnpack SourceStrict DecidedStrict) (Rec0 Double))))

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 this law doesn't hold:

fmap id = id

Defined in Data.RTree.Strict

Methods

fmap :: (a -> b) -> RTree a -> RTree b

(<$) :: a -> RTree b -> RTree a

Eq a => Eq (RTree a)

Defined in Data.RTree.Strict

Methods

(==) :: RTree a -> RTree a -> Bool

(/=) :: RTree a -> RTree a -> Bool

Show a => Show (RTree a)

Defined in Data.RTree.Strict

Methods

showsPrec :: Int -> RTree a -> ShowS

show :: RTree a -> String

showList :: [RTree a] -> ShowS

Generic (RTree a)

Defined in Data.RTree.Strict

Associated Types

type Rep (RTree a) :: Type -> Type

Methods

from :: RTree a -> Rep (RTree a) x

to :: Rep (RTree a) x -> RTree a

Semigroup a => Semigroup (RTree a)

Defined in Data.RTree.Strict

Methods

(<>) :: RTree a -> RTree a -> RTree a

sconcat :: NonEmpty (RTree a) -> RTree a

stimes :: Integral b => b -> RTree a -> RTree a

Monoid a => Monoid (RTree a)

Defined in Data.RTree.Strict

Methods

mempty :: RTree a

mappend :: RTree a -> RTree a -> RTree a

mconcat :: [RTree a] -> RTree a

Binary a => Binary (RTree a)

Defined in Data.RTree.Strict

Methods

put :: RTree a -> Put

get :: Get (RTree a)

putList :: [RTree a] -> Put

NFData a => NFData (RTree a)

Defined in Data.RTree.Strict

Methods

rnf :: RTree a -> ()

type Rep (RTree a)

Defined in Data.RTree.Strict

type Rep (RTree a) = D1 (MetaData "RTree" "Data.RTree.Strict" "data-r-tree-0.6.0-HxW7KWxwR847heBr9qHG8D" True) (C1 (MetaCons "RTree" PrefixI True) (S1 (MetaSel (Just "toLazy'") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 (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

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

returns all keys and values, which intersect with the given bounding box.

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

returns all values, which intersect with the given bounding box

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.

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

returns all values containing the given bounding box

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

returns all keys and values containing 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)