-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | QuadTree library for Haskell, with lens support.
--   
--   The purpose of this package is to provide discrete region quadtrees
--   that can be used as effective functional alternatives to 2D arrays,
--   with lens support.
@package QuadTree
@version 0.10.0


-- | 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.
--   
--   <pre>
--   test = set (<a>atLocation</a> (0,0)) 'd' $
--          set (<a>atLocation</a> (5,5)) 'c' $
--          set (<a>atLocation</a> (3,2)) 'b' $
--          set (<a>atLocation</a> (2,4)) 'a' $
--          <a>makeTree</a> (6,6) '.'
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; printTree id test
--   d.....
--   ......
--   ...b..
--   ......
--   ..a...
--   .....c
--   </pre>
module Data.QuadTree

-- | The eponymous data type.
--   
--   <a>QuadTree</a> 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.
data QuadTree a

-- | Constructor that generates a <a>QuadTree</a> of the given dimensions,
--   with all cells filled with a default value.
makeTree :: (Int, Int) -> a -> QuadTree a

-- | Tuple corresponds to (X, Y) co-ordinates.
type Location = (Int, Int)

-- | Getter for the value at a given location for a <a>QuadTree</a>.
getLocation :: Location -> QuadTree a -> a

-- | Setter for the value at a given location for a <a>QuadTree</a>.
--   
--   This automatically compresses the <a>QuadTree</a> nodes if possible
--   with the new value.
setLocation :: Eq a => Location -> QuadTree a -> a -> QuadTree a

-- | Lens for accessing and manipulating data at a specific location.
--   
--   This is simply <a>getLocation</a> and <a>setLocation</a> wrapped into
--   a lens.
atLocation :: Eq a => Location -> Lens' (QuadTree a) a

-- | Cleanup function for use after any <a>fmap</a>.
--   
--   When elements of a <a>QuadTree</a> are modified by <a>setLocation</a>
--   (or the <a>atLocation</a> lens), it automatically compresses identical
--   adjacent nodes into larger ones. This keeps the <a>QuadTree</a> from
--   bloating over constant use.
--   
--   <a>fmap</a> does not do this. If you wish to treat the <a>QuadTree</a>
--   as a <a>Functor</a>, you should compose this function after to
--   collapse it down to its minimum size.
--   
--   Example: <tt> <a>fuseTree</a> $ <a>fmap</a> fn tree </tt> This
--   particular example is reified in the function below.
fuseTree :: Eq a => QuadTree a -> QuadTree a

-- | tmap is simply <a>fmap</a> with <a>fuseTree</a> applied after.
--   
--   <pre>
--   tmap fn tree == fuseTree $ fmap fn tree
--   </pre>
tmap :: Eq b => (a -> b) -> QuadTree a -> QuadTree b

-- | <a>filter</a>s a list of the <a>QuadTree</a> 's elements.
filterTree :: (a -> Bool) -> QuadTree a -> [a]

-- | <a>sortBy</a>s a list of the <a>QuadTree</a> 's elements.
sortTreeBy :: (a -> a -> Ordering) -> QuadTree a -> [a]

-- | 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.
--   
--   <pre>
--   regionArea (x, y, x, y) == 1
--   </pre>
type Region = (Int, Int, Int, Int)

-- | Each <a>Tile</a> is a tuple of an element from a <a>QuadTree</a> and
--   the <a>Region</a> it subtends.
type Tile a = (a, Region)

-- | Returns a list of <a>Tile</a>s. The block equivalent of <a>toList</a>.
tile :: QuadTree a -> [Tile a]

-- | Takes a list of <a>Tile</a>s and then decomposes them into a list of
--   all their elements, properly weighted by <a>Tile</a> size.
expand :: [Tile a] -> [a]

-- | Decomposes a <a>QuadTree</a> into its constituent <a>Tile</a>s, before
--   folding a <a>Tile</a> consuming function over all of them.
foldTiles :: (Tile a -> b -> b) -> b -> QuadTree a -> b

-- | <a>filter</a>s a list of the <a>Tile</a>s of a <a>QuadTree</a>.
filterTiles :: (a -> Bool) -> [Tile a] -> [Tile a]

-- | <a>sortBy</a>s a list of the <a>Tile</a>s of a <a>QuadTree</a>.
sortTilesBy :: (a -> a -> Ordering) -> [Tile a] -> [Tile a]

-- | Generates a newline delimited string representing a <a>QuadTree</a> as
--   a 2D block of characters.
--   
--   Note that despite the word <a>show</a> in the function name, this does
--   not <a>show</a> the <a>QuadTree</a>. It pretty prints it. The name is
--   simply a mnemonic for its <tt><a>QuadTree</a> -&gt; String</tt>
--   behaviour.
showTree :: (a -> Char) -> QuadTree a -> String

-- | As <a>showTree</a> above, but also prints it.
printTree :: (a -> Char) -> QuadTree a -> IO ()

-- | Checks if a <a>Location</a> is outside the boundaries of a
--   <a>QuadTree</a>.
outOfBounds :: QuadTree a -> Location -> Bool

-- | Dimensions of a <a>QuadTree</a>, as an Int pair.
treeDimensions :: QuadTree a -> (Int, Int)

-- | Simple helper function that lets you calculate the area of a
--   <a>Region</a>, usually for <a>replicate</a> purposes.
regionArea :: Region -> Int

-- | Does the region contain this location?
inRegion :: Location -> Region -> Bool
instance [safe] Show a => Show (Quadrant a)
instance [safe] Read a => Read (Quadrant a)
instance [safe] Show a => Show (QuadTree a)
instance [safe] Read a => Read (QuadTree a)
instance [safe] Functor Quadrant
instance [safe] Foldable QuadTree
instance [safe] Functor QuadTree