```{-# LANGUAGE DeriveGeneric #-}
-- | Basic operations on 2D points represented as linear offsets.
module Game.LambdaHack.Common.Point
( X, Y, Point(..), maxLevelDimExponent
, chessDist, euclidDistSq, adjacent, inside, bla, fromTo
, originPoint
#ifdef EXPOSE_INTERNAL
-- * Internal operations
, maxLevelDim, blaXY, balancedWord
#endif
) where

import Prelude ()

import Game.LambdaHack.Common.Prelude

import Data.Binary
import Data.Bits (unsafeShiftL, unsafeShiftR, (.&.))
import Data.Int (Int32)
import GHC.Generics (Generic)

-- | Spacial dimension for points and vectors.
type X = Int

-- | Spacial dimension for points and vectors.
type Y = Int

-- | 2D points in cartesian representation. Coordinates grow to the right
-- and down, so that the (0, 0) point is in the top-left corner of the screen.
-- Coordinates are never negative.
data Point = Point
{ px :: X
, py :: Y
}
deriving (Eq, Ord, Generic)

instance Show Point where
show (Point x y) = show (x, y)

instance Binary Point where
put = put . (fromIntegral :: Int -> Int32) . fromEnum
get = fmap (toEnum . (fromIntegral :: Int32 -> Int)) get

-- This conversion cannot be used for PointArray indexing,
-- because it is not contiguous --- we don't know the horizontal
-- width of the levels nor of the screen.
-- The conversion is implemented mainly for @EnumMap@ and @EnumSet@.
-- Note that the conversion is not monotonic wrt the natural @Ord@ instance,
-- because we want adjacent points in line to have adjacent enumerations,
-- because some of the screen layout and most of processing is line-by-line.
-- Consequently, one can use EM.fromAscList on @(1, 8)..(10, 8)@, but not on
-- @(1, 7)..(10, 9)@.
instance Enum Point where
#ifdef WITH_EXPENSIVE_ASSERTIONS
assert (x >= 0 && y >= 0 && x <= maxLevelDim && y <= maxLevelDim
`blame` "invalid point coordinates"
`swith` (x, y))
#endif
(x + unsafeShiftL y maxLevelDimExponent)
toEnum n = Point (n .&. maxLevelDim) (unsafeShiftR n maxLevelDimExponent)

-- | The maximum number of bits for level X and Y dimension (16).
-- The value is chosen to support architectures with 32-bit Ints.
maxLevelDimExponent :: Int
{-# INLINE maxLevelDimExponent #-}
maxLevelDimExponent = 16

-- | Maximal supported level X and Y dimension. Not checked anywhere.
-- The value is chosen to support architectures with 32-bit Ints.
maxLevelDim :: Int
{-# INLINE maxLevelDim #-}
maxLevelDim = 2 ^ maxLevelDimExponent - 1

-- | The distance between two points in the chessboard metric.
chessDist :: Point -> Point -> Int
chessDist (Point x0 y0) (Point x1 y1) = max (abs (x1 - x0)) (abs (y1 - y0))

-- | Squared euclidean distance between two points.
euclidDistSq :: Point -> Point -> Int
euclidDistSq (Point x0 y0) (Point x1 y1) =
(x1 - x0) ^ (2 :: Int) + (y1 - y0) ^ (2 :: Int)

-- | Checks whether two points are adjacent on the map
-- (horizontally, vertically or diagonally).
adjacent :: Point -> Point -> Bool
adjacent s t = chessDist s t == 1

-- | Checks that a point belongs to an area.
inside :: Point -> (X, Y, X, Y) -> Bool
inside (Point x y) (x0, y0, x1, y1) = x1 >= x && x >= x0 && y1 >= y && y >= y0

-- | Bresenham's line algorithm generalized to arbitrary starting @eps@
-- (@eps@ value of 0 gives the standard BLA).
-- Skips the source point and goes through the second point
-- to the edge of the level. GIves @Nothing@ if the points are equal.
-- The target is given as @Point@ to permit aiming out of the level,
-- e.g., to get uniform distributions of directions for explosions
-- close to the edge of the level.
bla :: X -> Y -> Int -> Point -> Point -> Maybe [Point]
bla lxsize lysize eps source target =
if source == target then Nothing
else Just \$
let inBounds p@(Point x y) =
lxsize > x && x >= 0 && lysize > y && y >= 0 && p /= source
in takeWhile inBounds \$ tail \$ blaXY eps source target

-- | Bresenham's line algorithm generalized to arbitrary starting @eps@
-- (@eps@ value of 0 gives the standard BLA). Includes the source point
-- and goes through the target point to infinity.
blaXY :: Int -> Point -> Point -> [Point]
blaXY eps (Point x0 y0) (Point x1 y1) =
let (dx, dy) = (x1 - x0, y1 - y0)
xyStep b (x, y) = (x + signum dx,     y + signum dy * b)
yxStep b (x, y) = (x + signum dx * b, y + signum dy)
(p, q, step) | abs dx > abs dy = (abs dy, abs dx, xyStep)
| otherwise       = (abs dx, abs dy, yxStep)
bw = balancedWord p q (eps `mod` max 1 q)
walk w xy = xy : walk (tail w) (step (head w) xy)
in map (uncurry Point) \$ walk bw (x0, y0)

-- | See <http://roguebasin.roguelikedevelopment.org/index.php/Digital_lines>.
balancedWord :: Int -> Int -> Int -> [Int]
balancedWord p q eps | eps + p < q = 0 : balancedWord p q (eps + p)
balancedWord p q eps               = 1 : balancedWord p q (eps + p - q)

-- | A list of all points on a straight vertical or straight horizontal line
-- between two points. Fails if no such line exists.
fromTo :: Point -> Point -> [Point]
fromTo (Point x0 y0) (Point x1 y1) =
let fromTo1 :: Int -> Int -> [Int]
fromTo1 z0 z1
| z0 <= z1  = [z0..z1]
| otherwise = [z0,z0-1..z1]
result
| x0 == x1 = map (Point x0) (fromTo1 y0 y1)
| y0 == y1 = map (`Point` y0) (fromTo1 x0 x1)
| otherwise = error \$ "diagonal fromTo"
`showFailure` ((x0, y0), (x1, y1))
in result

originPoint :: Point
originPoint = Point 0 0
```