Data.QuadTree

The purpose of this module is to provide discrete region quadtrees that can be used as simple functional alternatives to 2D arrays, with lens support.

test = set (atLocation (0,0)) 'd' $
       set (atLocation (5,5)) 'c' $
       set (atLocation (3,2)) 'b' $
       set (atLocation (2,4)) 'a' $
       makeTree (6,6) '.'

>>> printTree id test
d.....
......
...b..
......
..a...
.....c

Data Type & Constructor

data QuadTree a

The eponymous data type.

QuadTree is itself a wrapper around an internal tree structure along with spatial metadata about the boundaries and depth of the 2D area it maps to.

Instances

Functor QuadTree

Foldable QuadTree

Read a => Read (QuadTree a)

Show a => Show (QuadTree a)

makeTree

Arguments

:: (Int, Int)

(Length, Width)

-> a

Initial element to fill

-> QuadTree a

Constructor that generates a QuadTree of the given dimensions, with all cells filled with a default value.

Index access

This provides an array-style interface to the QuadTree, albeit with an O(log n) lookup and insertion speed. This is both faster and slower than an actual array (O(1) lookup and O(n) insertion respectively).

The user can imagine a two dimensional grid that can be modified or queried via co-ordinate pair indices.

type Location = (Int, Int)

Tuple corresponds to (X, Y) co-ordinates.

getLocation :: Location -> QuadTree a -> a

Getter for the value at a given location for a QuadTree.

setLocation :: forall a. Eq a => Location -> QuadTree a -> a -> QuadTree a

Setter for the value at a given location for a QuadTree.

This automatically compresses the QuadTree nodes if possible with the new value.

atLocation :: Eq a => Location -> Lens' (QuadTree a) a

Lens for accessing and manipulating data at a specific location.

This is simply getLocation and setLocation wrapped into a lens.

Functor

fuseTree :: Eq a => QuadTree a -> QuadTree a

Cleanup function for use after any fmap.

When elements of a QuadTree are modified by setLocation (or the atLocation lens), it automatically compresses identical adjacent nodes into larger ones. This keeps the QuadTree from bloating over constant use.

fmap does not do this. If you wish to treat the QuadTree as a Functor, you should compose this function after to collapse it down to its minimum size.

Example: fuseTree $ fmap fn tree This particular example is reified in the function below.

tmap :: Eq b => (a -> b) -> QuadTree a -> QuadTree b

tmap is simply fmap with fuseTree applied after.

tmap fn tree == fuseTree $ fmap fn tree

Foldable

QuadTrees can be folded just like lists. If you simply replace the Prelude fold functions with Data.Foldable ones...

import Data.Foldable
import Prelude hiding (foldr, foldl, any, sum, find...)

... Then you can directly call then on QuadTrees without qualification. No list functionality will be lost since the Data.Foldable functions also work exactly like the Prelude folds for list processing.

In addition you also get some extras like toList.

filterTree :: (a -> Bool) -> QuadTree a -> [a]

filters a list of the QuadTree 's elements.

sortTreeBy :: (a -> a -> Ordering) -> QuadTree a -> [a]

sortBys a list of the QuadTree 's elements.

Tiles

Directly folding a QuadTree will expand it into a sequence of elements that are then folded over. For some types of operations this can be incredibly inefficient; it may be faster to simply manipulate a sequence of leaves and then later decompose the results into a list of elements.

For these operations, we can use Tiles. Tiles are simply blocks of elements, represented by a tuple of the leaf data and some information on the spatial location and dimensions of the block.

type Region = (Int, Int, Int, Int)

Rectangular area, represented by a tuple of four Ints.

They correspond to (X floor, Y floor, X ceiling, Y ceiling).

The co-ordinates are inclusive of all the rows and columns in all four Ints.

regionArea (x, y, x, y) == 1

type Tile a = (a, Region)

Each Tile is a tuple of an element from a QuadTree and the Region it subtends.

Tile functions

The bread and butter method of manipulating Tiles is to first decompose a QuadTree with tile, process the intermediate representation, and then decompose it into a final list of elements with expand.

expand . fn . tile $ tree

tile :: QuadTree a -> [Tile a]

Returns a list of Tiles. The block equivalent of toList.

expand :: [Tile a] -> [a]

Takes a list of Tiles and then decomposes them into a list of all their elements, properly weighted by Tile size.

foldTiles :: forall a b. (Tile a -> b -> b) -> b -> QuadTree a -> b

Decomposes a QuadTree into its constituent Tiles, before folding a Tile consuming function over all of them.

filterTiles :: (a -> Bool) -> [Tile a] -> [Tile a]

filters a list of the Tiles of a QuadTree.

sortTilesBy :: (a -> a -> Ordering) -> [Tile a] -> [Tile a]

sortBys a list of the Tiles of a QuadTree.

Printers

showTree

Arguments

:: (a -> Char)

Function to generate characters for each QuadTree element.

-> QuadTree a

-> String

Generates a newline delimited string representing a QuadTree as a 2D block of characters.

Note that despite the word show in the function name, this does not show the QuadTree. It pretty prints it. The name is simply a mnemonic for its QuadTree -> String behaviour.

printTree

Arguments

:: (a -> Char)

Function to generate characters for each QuadTree element.

-> QuadTree a

-> IO ()

As showTree above, but also prints it.

Miscellaneous helpers

outOfBounds :: QuadTree a -> Location -> Bool

Checks if a Location is outside the boundaries of a QuadTree.

treeDimensions

Arguments

:: QuadTree a

-> (Int, Int)

(Length, Width)

Dimensions of a QuadTree, as an Int pair.

regionArea :: Region -> Int

Simple helper function that lets you calculate the area of a Region, usually for replicate purposes.

inRegion :: Location -> Region -> Bool

Does the region contain this location?