Copyright	(c) Ashley Moni, 2015
License	BSD3
Maintainer	Ashley Moni <ashley.moni1@gmail.com>
Stability	Stable
Safe Haskell	Safe
Language	Haskell2010
Extensions	ScopedTypeVariables RankNTypes ExplicitForAll

Data.QuadTree

Contents

Data Type & Constructor
Index access
Functor
Foldable
- Tiles
- Tile functions
Printers
Miscellaneous helpers

Description

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

Synopsis

Data Type & Constructor

data QuadTree a Source

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 Source	`QuadTree`s are `Functor`s, and their elements can be fmapped over.
Foldable QuadTree Source	`QuadTree`s are `Foldable`, though the traversal path is a complex recursive enumeration of internal `Quadrant`s. Don't use folds that aren't ordering agnostic.
Eq a => Eq (QuadTree a) Source
Read a => Read (QuadTree a) Source
Show a => Show (QuadTree a) Source

makeTree Source

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) Source

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

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

Lens for accessing and manipulating data at a specific location.

getLocation :: Eq a => Location -> QuadTree a -> a Source

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

setLocation :: Eq a => Location -> a -> QuadTree a -> QuadTree a Source

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

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

mapLocation :: Eq a => Location -> (a -> a) -> QuadTree a -> QuadTree a Source

Modifies value at a given location for a QuadTree.

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

Functor

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

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 Source

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 them 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] Source

filters a list of the QuadTree 's elements.

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

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) Source

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) Source

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] Source

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

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

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 Source

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

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

filters a list of the Tiles of a QuadTree.

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

sortBys a list of the Tiles of a QuadTree.

Printers

showTree Source

Arguments

:: Eq a
=> (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 Source

Arguments

:: Eq a
=> (a -> Char)	Function to generate characters for each `QuadTree` element.
-> QuadTree a
-> IO ()

As showTree above, but also prints it.

Miscellaneous helpers

outOfBounds :: Location -> QuadTree a -> Bool Source

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

treeDimensions Source

Arguments

:: QuadTree a
-> (Int, Int)	(Length, Width)

Dimensions of a QuadTree, as an Int pair.

regionArea :: Region -> Int Source

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

inRegion :: Location -> Region -> Bool Source

Does the region contain this location?