content: {-# LANGUAGE PatternGuards #-}
  
  -- | Represents an integral rectangular area of the 2D plane.
  --   Using `Int`s (instead of `Float`s) for the bounds means we can safely
  --   compare extents for equality.
  module Graphics.Gloss.Data.Extent
          ( Extent
          , Coord
          , makeExtent
          , takeExtent
          , squareExtent
          , sizeOfExtent
          , isUnitExtent
          , coordInExtent
          , pointInExtent
          , centerCoordOfExtent
          , cutQuadOfExtent
          , quadOfCoord
          , pathToCoord
          , intersectSegExtent
          , touchesSegExtent)
  where
  import Graphics.Gloss.Data.Point
  import Graphics.Gloss.Data.Quad
  import Graphics.Gloss.Geometry.Line
  import Data.Maybe
  
  
  -- | A rectangular area of the 2D plane.
  --   We keep the type abstract to ensure that invalid extents cannot be
  --   constructed.
  data Extent
          = Extent Int Int Int Int
          deriving (Eq, Show)
  
  
  -- | An integral coordinate.
  type Coord
          = (Int, Int)
  
  
  -- | Construct an extent.
  --      The north value must be > south, and east > west, else `error`.
  makeExtent
          :: Int  -- ^ y max (north)
          -> Int  -- ^ y min (south)
          -> Int  -- ^ x max (east)
          -> Int  -- ^ x min (west)
          -> Extent
  
  makeExtent n s e w
          | n >= s, e >= w
          = Extent n s e w
  
          | otherwise
          = error "Graphics.Gloss.Geometry.Extent.makeExtent: invalid extent"
  
  
  -- | Take the NSEW components of an extent.
  takeExtent :: Extent -> (Int, Int, Int, Int)
  takeExtent (Extent n s e w)
          = (n, s, e, w)
  
  
  -- | A square extent of a given size.
  squareExtent :: Int -> Extent
  squareExtent i
          = Extent i 0 i 0
  
  
  -- | Get the width and height of an extent.
  sizeOfExtent :: Extent -> (Int, Int)
  sizeOfExtent (Extent n s e w)
          = (e - w, n - s)
  
  
  -- | Check if an extent is a square with a width and height of 1.
  isUnitExtent :: Extent -> Bool
  isUnitExtent extent
          = sizeOfExtent extent == (1, 1)
  
  
  -- | Check whether a coordinate lies inside an extent.
  coordInExtent :: Extent -> Coord -> Bool
  coordInExtent (Extent n s e w) (x, y)
          =  x >= w && x < e
          && y >= s && y < n
  
  
  -- | Check whether a point lies inside an extent.
  pointInExtent :: Extent -> Point -> Bool
  pointInExtent (Extent n s e w) (x, y)
   = let  n'      = fromIntegral n
          s'      = fromIntegral s
          e'      = fromIntegral e
          w'      = fromIntegral w
  
     in   x >= w' && x <= e'
       && y >= s' && y <= n'
  
  
  -- | Get the coordinate that lies at the center of an extent.
  centerCoordOfExtent :: Extent -> (Int, Int)
  centerCoordOfExtent (Extent n s e w)
   =      ( w + (e - w) `div` 2
          , s + (n - s) `div` 2)
  
  
  -- | Cut one quadrant out of an extent.
  cutQuadOfExtent :: Quad -> Extent -> Extent
  cutQuadOfExtent quad (Extent n s e w)
   = let  hheight = (n - s) `div` 2
          hwidth  = (e - w) `div` 2
     in   case quad of
                  NW -> Extent n (s + hheight)  (e - hwidth) w
                  NE -> Extent n (s + hheight)  e (w + hwidth)
                  SW -> Extent (n - hheight) s  (e - hwidth) w
                  SE -> Extent (n - hheight) s  e (w + hwidth)
  
  
  -- | Get the quadrant that this coordinate lies in, if any.
  quadOfCoord :: Extent -> Coord -> Maybe Quad
  quadOfCoord extent coord
          = listToMaybe
          $ filter (\q -> coordInExtent (cutQuadOfExtent q extent) coord)
          $ allQuads
  
  
  -- | Constuct a path to a particular coordinate in an extent.
  pathToCoord :: Extent -> Coord -> Maybe [Quad]
  pathToCoord extent coord
          | isUnitExtent extent
          = Just []
  
          | otherwise
          = do    quad    <- quadOfCoord extent coord
                  rest    <- pathToCoord (cutQuadOfExtent quad extent) coord
                  return  $ quad : rest
  
  
  -- | 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 `Nothing`.
  --
  --   @
  --                   P2
  --                  /
  --            ----/-
  --            | /  |
  --            +    |
  --           /------
  --         /
  --        P1
  --   @
  --
  intersectSegExtent :: Point -> Point -> Extent -> Maybe Point
  intersectSegExtent p1@(x1, y1) p2 (Extent n' s' e' w')
          -- starts below extent
          | y1 < s
          , Just pos      <- intersectSegHorzSeg p1 p2 s w e
          = Just pos
  
          -- starts above extent
          | y1 > n
          , Just pos      <- intersectSegHorzSeg p1 p2 n w e
          = Just pos
  
          -- starts left of extent
          | x1 < w
          , Just pos      <- intersectSegVertSeg p1 p2 w s n
          = Just pos
  
          -- starts right of extent
          | x1 > e
          , Just pos      <- intersectSegVertSeg p1 p2 e s n
          = Just pos
  
          -- must be starting inside extent.
          | otherwise
          = Nothing
  
          where   n       = fromIntegral n'
                  s       = fromIntegral s'
                  e       = fromIntegral e'
                  w       = fromIntegral w'
  
  
  -- | Check whether a line segment's endpoints are inside an extent, or if it
  --   intersects with the boundary.
  touchesSegExtent :: Point -> Point -> Extent -> Bool
  touchesSegExtent p1 p2 extent
          =   pointInExtent extent p1
           || pointInExtent extent p2
           || isJust (intersectSegExtent p1 p2 extent)
  
  