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


-- | Data structures and algorithms for working with 2D graphics.
--   
--   Data structures and algorithms for working with 2D graphics.
@package brillo-algorithms
@version 1.13.3

module Brillo.Data.Quad

-- | Represents a Quadrant in the 2D plane.
data Quad

-- | North West
NW :: Quad

-- | North East
NE :: Quad

-- | South West
SW :: Quad

-- | South East
SE :: Quad

-- | A list of all quadrants. Same as <tt>[NW .. SE]</tt>.
allQuads :: [Quad]
instance GHC.Enum.Enum Brillo.Data.Quad.Quad
instance GHC.Classes.Eq Brillo.Data.Quad.Quad
instance GHC.Show.Show Brillo.Data.Quad.Quad


-- | Represents an integral rectangular area of the 2D plane. Using
--   <a>Int</a>s (instead of <a>Float</a>s) for the bounds means we can
--   safely compare extents for equality.
module Brillo.Data.Extent

-- | A rectangular area of the 2D plane. We keep the type abstract to
--   ensure that invalid extents cannot be constructed.
data Extent

-- | An integral coordinate.
type Coord = (Int, Int)

-- | Construct an extent. The north value must be &gt; south, and east &gt;
--   west, else <a>error</a>.
makeExtent :: Int -> Int -> Int -> Int -> Extent

-- | Take the NSEW components of an extent.
takeExtent :: Extent -> (Int, Int, Int, Int)

-- | A square extent of a given size.
squareExtent :: Int -> Extent

-- | Get the width and height of an extent.
sizeOfExtent :: Extent -> (Int, Int)

-- | Check if an extent is a square with a width and height of 1.
isUnitExtent :: Extent -> Bool

-- | Check whether a coordinate lies inside an extent.
coordInExtent :: Extent -> Coord -> Bool

-- | Check whether a point lies inside an extent.
pointInExtent :: Extent -> Point -> Bool

-- | Get the coordinate that lies at the center of an extent.
centerCoordOfExtent :: Extent -> (Int, Int)

-- | Cut one quadrant out of an extent.
cutQuadOfExtent :: Quad -> Extent -> Extent

-- | Get the quadrant that this coordinate lies in, if any.
quadOfCoord :: Extent -> Coord -> Maybe Quad

-- | Constuct a path to a particular coordinate in an extent.
pathToCoord :: Extent -> Coord -> Maybe [Quad]

-- | If a line segment (P1-P2) intersects the outer edge of an extent then
--   return the intersection point, that is closest to P1, if any. If P1 is
--   inside the extent then <a>Nothing</a>.
--   
--   <pre>
--              P2
--             /
--       ----/-
--       | /  |
--       +    |
--      /------
--    /
--   P1
--   
--   </pre>
intersectSegExtent :: Point -> Point -> Extent -> Maybe Point

-- | Check whether a line segment's endpoints are inside an extent, or if
--   it intersects with the boundary.
touchesSegExtent :: Point -> Point -> Extent -> Bool
instance GHC.Show.Show Brillo.Data.Extent.Extent
instance GHC.Classes.Eq Brillo.Data.Extent.Extent


-- | A QuadTree can be used to recursively divide up 2D space into
--   quadrants. The smallest division corresponds to an unit <a>Extent</a>,
--   so the total depth of the tree will depend on what sized <a>Extent</a>
--   you start with.
module Brillo.Data.QuadTree

-- | The quad tree structure.
data QuadTree a

-- | An empty node.
TNil :: QuadTree a

-- | A leaf containint some value.
TLeaf :: a -> QuadTree a

-- | A node with four children.
TNode :: QuadTree a -> QuadTree a -> QuadTree a -> QuadTree a -> QuadTree a

-- | A <a>TNil</a> tree.
emptyTree :: QuadTree a

-- | A node with <a>TNil</a>. for all its branches.
emptyNode :: QuadTree a

-- | Get a quadrant from a node. If the tree does not have an outer node
--   then <a>Nothing</a>.
takeQuadOfTree :: Quad -> QuadTree a -> Maybe (QuadTree a)

-- | Apply a function to a quadrant of a node. If the tree does not have an
--   outer node then return the original tree.
liftToQuad :: Quad -> (QuadTree a -> QuadTree a) -> QuadTree a -> QuadTree a

-- | Insert a value into the tree at the position given by a path. If the
--   path intersects an existing <a>TLeaf</a> then return the original
--   tree.
insertByPath :: [Quad] -> a -> QuadTree a -> QuadTree a

-- | Insert a value into the node containing this coordinate. The node is
--   created at maximum depth, corresponding to an unit <a>Extent</a>.
insertByCoord :: Extent -> Coord -> a -> QuadTree a -> Maybe (QuadTree a)

-- | Lookup a node based on a path to it.
lookupNodeByPath :: [Quad] -> QuadTree a -> Maybe (QuadTree a)

-- | Lookup an element based given a path to it.
lookupByPath :: [Quad] -> QuadTree a -> Maybe a

-- | Lookup a node if a tree given a coordinate which it contains.
lookupByCoord :: forall a. Extent -> Coord -> QuadTree a -> Maybe a

-- | Flatten a QuadTree into a list of its contained values, with
--   coordinates.
flattenQuadTree :: forall a. Extent -> QuadTree a -> [(Coord, a)]

-- | Flatten a QuadTree into a list of its contained values, with extents.
flattenQuadTreeWithExtents :: forall a. Extent -> QuadTree a -> [(Extent, a)]
instance GHC.Show.Show a => GHC.Show.Show (Brillo.Data.QuadTree.QuadTree a)


-- | Various ray casting algorithms.
module Brillo.Algorithms.RayCast

-- | The quadtree contains cells of unit extent (NetHack style). Given a
--   line segement (P1-P2) through the tree, get the cell closest to P1
--   that intersects the segment, if any.
castSegIntoCellularQuadTree :: forall a. Point -> Point -> Extent -> QuadTree a -> Maybe (Point, Extent, a)

-- | The quadtree contains cells of unit extent (NetHack style). Given a
--   line segment (P1-P2) through the tree, return the list of cells that
--   intersect the segment.
traceSegIntoCellularQuadTree :: forall a. Point -> Point -> Extent -> QuadTree a -> [(Point, Extent, a)]