{-# Language ImportQualifiedPost, UnboxedTuples, MagicHash, MultiParamTypeClasses, DeriveDataTypeable, DeriveGeneric, TypeFamilies, TypeOperators, BlockArguments #-}
{-|
Module      : Advent.Coord
Description : Row-major coordinates
Copyright   : (c) Eric Mertens, 2018
License     : ISC
Maintainer  : emertens@gmail.com

2-dimensional coordinates commonly found in AoC problems
where y grows down, x grows right.

@
   -y
    ↑
-x ←0→ +x
    ↓
   +y
@

-}
module Advent.Coord where

import Control.Monad.ST ( ST, stToIO, runST )
import Data.Array.Base qualified as AB
import Data.Array.IO.Internals qualified as AB
import Data.Data (Data)
import Data.Foldable (toList)
import Data.Map (Map)
import Data.Map qualified as Map
import Data.MemoTrie (HasTrie(..))
import GHC.Exts (Int(I#), (+#), (*#), indexIntArray#, readIntArray#, writeIntArray#)
import GHC.Generics (Generic)
import GHC.Ix (Ix(unsafeIndex, range, index, inRange, unsafeRangeSize), indexError)
import GHC.ST (ST(ST))

-- | Two-dimensional coordinate
data Coord = C !Int !Int
  deriving (ReadPrec [Coord]
ReadPrec Coord
Int -> ReadS Coord
ReadS [Coord]
(Int -> ReadS Coord)
-> ReadS [Coord]
-> ReadPrec Coord
-> ReadPrec [Coord]
-> Read Coord
forall a.
(Int -> ReadS a)
-> ReadS [a] -> ReadPrec a -> ReadPrec [a] -> Read a
$creadsPrec :: Int -> ReadS Coord
readsPrec :: Int -> ReadS Coord
$creadList :: ReadS [Coord]
readList :: ReadS [Coord]
$creadPrec :: ReadPrec Coord
readPrec :: ReadPrec Coord
$creadListPrec :: ReadPrec [Coord]
readListPrec :: ReadPrec [Coord]
Read, Int -> Coord -> ShowS
[Coord] -> ShowS
Coord -> String
(Int -> Coord -> ShowS)
-> (Coord -> String) -> ([Coord] -> ShowS) -> Show Coord
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: Int -> Coord -> ShowS
showsPrec :: Int -> Coord -> ShowS
$cshow :: Coord -> String
show :: Coord -> String
$cshowList :: [Coord] -> ShowS
showList :: [Coord] -> ShowS
Show, Eq Coord
Eq Coord =>
(Coord -> Coord -> Ordering)
-> (Coord -> Coord -> Bool)
-> (Coord -> Coord -> Bool)
-> (Coord -> Coord -> Bool)
-> (Coord -> Coord -> Bool)
-> (Coord -> Coord -> Coord)
-> (Coord -> Coord -> Coord)
-> Ord Coord
Coord -> Coord -> Bool
Coord -> Coord -> Ordering
Coord -> Coord -> Coord
forall a.
Eq a =>
(a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
$ccompare :: Coord -> Coord -> Ordering
compare :: Coord -> Coord -> Ordering
$c< :: Coord -> Coord -> Bool
< :: Coord -> Coord -> Bool
$c<= :: Coord -> Coord -> Bool
<= :: Coord -> Coord -> Bool
$c> :: Coord -> Coord -> Bool
> :: Coord -> Coord -> Bool
$c>= :: Coord -> Coord -> Bool
>= :: Coord -> Coord -> Bool
$cmax :: Coord -> Coord -> Coord
max :: Coord -> Coord -> Coord
$cmin :: Coord -> Coord -> Coord
min :: Coord -> Coord -> Coord
Ord, Coord -> Coord -> Bool
(Coord -> Coord -> Bool) -> (Coord -> Coord -> Bool) -> Eq Coord
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: Coord -> Coord -> Bool
== :: Coord -> Coord -> Bool
$c/= :: Coord -> Coord -> Bool
/= :: Coord -> Coord -> Bool
Eq, (forall x. Coord -> Rep Coord x)
-> (forall x. Rep Coord x -> Coord) -> Generic Coord
forall x. Rep Coord x -> Coord
forall x. Coord -> Rep Coord x
forall a.
(forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
$cfrom :: forall x. Coord -> Rep Coord x
from :: forall x. Coord -> Rep Coord x
$cto :: forall x. Rep Coord x -> Coord
to :: forall x. Rep Coord x -> Coord
Generic, Typeable Coord
Typeable Coord =>
(forall (c :: * -> *).
 (forall d b. Data d => c (d -> b) -> d -> c b)
 -> (forall g. g -> c g) -> Coord -> c Coord)
-> (forall (c :: * -> *).
    (forall b r. Data b => c (b -> r) -> c r)
    -> (forall r. r -> c r) -> Constr -> c Coord)
-> (Coord -> Constr)
-> (Coord -> DataType)
-> (forall (t :: * -> *) (c :: * -> *).
    Typeable t =>
    (forall d. Data d => c (t d)) -> Maybe (c Coord))
-> (forall (t :: * -> * -> *) (c :: * -> *).
    Typeable t =>
    (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c Coord))
-> ((forall b. Data b => b -> b) -> Coord -> Coord)
-> (forall r r'.
    (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Coord -> r)
-> (forall r r'.
    (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Coord -> r)
-> (forall u. (forall d. Data d => d -> u) -> Coord -> [u])
-> (forall u. Int -> (forall d. Data d => d -> u) -> Coord -> u)
-> (forall (m :: * -> *).
    Monad m =>
    (forall d. Data d => d -> m d) -> Coord -> m Coord)
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> Coord -> m Coord)
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> Coord -> m Coord)
-> Data Coord
Coord -> Constr
Coord -> DataType
(forall b. Data b => b -> b) -> Coord -> Coord
forall a.
Typeable a =>
(forall (c :: * -> *).
 (forall d b. Data d => c (d -> b) -> d -> c b)
 -> (forall g. g -> c g) -> a -> c a)
-> (forall (c :: * -> *).
    (forall b r. Data b => c (b -> r) -> c r)
    -> (forall r. r -> c r) -> Constr -> c a)
-> (a -> Constr)
-> (a -> DataType)
-> (forall (t :: * -> *) (c :: * -> *).
    Typeable t =>
    (forall d. Data d => c (t d)) -> Maybe (c a))
-> (forall (t :: * -> * -> *) (c :: * -> *).
    Typeable t =>
    (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c a))
-> ((forall b. Data b => b -> b) -> a -> a)
-> (forall r r'.
    (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> a -> r)
-> (forall r r'.
    (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> a -> r)
-> (forall u. (forall d. Data d => d -> u) -> a -> [u])
-> (forall u. Int -> (forall d. Data d => d -> u) -> a -> u)
-> (forall (m :: * -> *).
    Monad m =>
    (forall d. Data d => d -> m d) -> a -> m a)
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> a -> m a)
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> a -> m a)
-> Data a
forall u. Int -> (forall d. Data d => d -> u) -> Coord -> u
forall u. (forall d. Data d => d -> u) -> Coord -> [u]
forall r r'.
(r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Coord -> r
forall r r'.
(r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Coord -> r
forall (m :: * -> *).
Monad m =>
(forall d. Data d => d -> m d) -> Coord -> m Coord
forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d) -> Coord -> m Coord
forall (c :: * -> *).
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c Coord
forall (c :: * -> *).
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> Coord -> c Coord
forall (t :: * -> *) (c :: * -> *).
Typeable t =>
(forall d. Data d => c (t d)) -> Maybe (c Coord)
forall (t :: * -> * -> *) (c :: * -> *).
Typeable t =>
(forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c Coord)
$cgfoldl :: forall (c :: * -> *).
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> Coord -> c Coord
gfoldl :: forall (c :: * -> *).
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> Coord -> c Coord
$cgunfold :: forall (c :: * -> *).
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c Coord
gunfold :: forall (c :: * -> *).
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c Coord
$ctoConstr :: Coord -> Constr
toConstr :: Coord -> Constr
$cdataTypeOf :: Coord -> DataType
dataTypeOf :: Coord -> DataType
$cdataCast1 :: forall (t :: * -> *) (c :: * -> *).
Typeable t =>
(forall d. Data d => c (t d)) -> Maybe (c Coord)
dataCast1 :: forall (t :: * -> *) (c :: * -> *).
Typeable t =>
(forall d. Data d => c (t d)) -> Maybe (c Coord)
$cdataCast2 :: forall (t :: * -> * -> *) (c :: * -> *).
Typeable t =>
(forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c Coord)
dataCast2 :: forall (t :: * -> * -> *) (c :: * -> *).
Typeable t =>
(forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c Coord)
$cgmapT :: (forall b. Data b => b -> b) -> Coord -> Coord
gmapT :: (forall b. Data b => b -> b) -> Coord -> Coord
$cgmapQl :: forall r r'.
(r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Coord -> r
gmapQl :: forall r r'.
(r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Coord -> r
$cgmapQr :: forall r r'.
(r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Coord -> r
gmapQr :: forall r r'.
(r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Coord -> r
$cgmapQ :: forall u. (forall d. Data d => d -> u) -> Coord -> [u]
gmapQ :: forall u. (forall d. Data d => d -> u) -> Coord -> [u]
$cgmapQi :: forall u. Int -> (forall d. Data d => d -> u) -> Coord -> u
gmapQi :: forall u. Int -> (forall d. Data d => d -> u) -> Coord -> u
$cgmapM :: forall (m :: * -> *).
Monad m =>
(forall d. Data d => d -> m d) -> Coord -> m Coord
gmapM :: forall (m :: * -> *).
Monad m =>
(forall d. Data d => d -> m d) -> Coord -> m Coord
$cgmapMp :: forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d) -> Coord -> m Coord
gmapMp :: forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d) -> Coord -> m Coord
$cgmapMo :: forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d) -> Coord -> m Coord
gmapMo :: forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d) -> Coord -> m Coord
Data)

-- | Row (y) of coordinate
coordRow :: Coord -> Int
coordRow :: Coord -> Int
coordRow (C Int
row Int
_) = Int
row

-- | Column (x) of coordinate
coordCol :: Coord -> Int
coordCol :: Coord -> Int
coordCol (C Int
_ Int
col) = Int
col

-- | Decrement y coordinate
above :: Coord -> Coord
above :: Coord -> Coord
above (C Int
y Int
x) = Int -> Int -> Coord
C (Int
yInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1) Int
x

-- | Increment y coordinate
below :: Coord -> Coord
below :: Coord -> Coord
below (C Int
y Int
x) = Int -> Int -> Coord
C (Int
yInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1) Int
x

-- | Decrement x coordinate
left :: Coord -> Coord
left :: Coord -> Coord
left  (C Int
y Int
x) = Int -> Int -> Coord
C Int
y (Int
xInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1)

-- | Increment x coordinate
right :: Coord -> Coord
right :: Coord -> Coord
right (C Int
y Int
x) = Int -> Int -> Coord
C Int
y (Int
xInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1)

-- | Swap x and y coordinates
invert :: Coord -> Coord
invert :: Coord -> Coord
invert (C Int
y Int
x) = Int -> Int -> Coord
C Int
x Int
y

-- | Swap x and y coordinates
invert' :: Coord -> Coord
invert' :: Coord -> Coord
invert' (C Int
y Int
x) = Int -> Int -> Coord
C (-Int
x) (-Int
y)

-- | Invert the x coordinate
flipX :: Coord -> Coord
flipX :: Coord -> Coord
flipX (C Int
y Int
x) = Int -> Int -> Coord
C Int
y (-Int
x)

-- | Invert the y coordinate
flipY :: Coord -> Coord
flipY :: Coord -> Coord
flipY (C Int
y Int
x) = Int -> Int -> Coord
C (-Int
y) Int
x

-- | Rotate coordinate 90-degrees CCW about the origin
turnLeft :: Coord -> Coord
turnLeft :: Coord -> Coord
turnLeft  (C Int
y Int
x) = Int -> Int -> Coord
C (-Int
x) Int
y

-- | Rotate coordinate 90-degrees CW about the origin
turnRight :: Coord -> Coord
turnRight :: Coord -> Coord
turnRight (C Int
y Int
x) = Int -> Int -> Coord
C Int
x (-Int
y)

-- | Rotate the coordinate 180-degrees about the origin
turnAround :: Coord -> Coord
turnAround :: Coord -> Coord
turnAround (C Int
y Int
x) = Int -> Int -> Coord
C (-Int
y) (-Int
x)

-- | Compute the Manhattan distance between two coordinates
manhattan :: Coord -> Coord -> Int
manhattan :: Coord -> Coord -> Int
manhattan Coord
a Coord
b = Coord -> Int
norm1 (Coord
a Coord -> Coord -> Coord
forall a. Num a => a -> a -> a
- Coord
b)

-- | Compute 1-norm between two coordinates (sum of magnitudes)
norm1 :: Coord -> Int
norm1 :: Coord -> Int
norm1 (C Int
y Int
x) = Int -> Int
forall a. Num a => a -> a
abs Int
y Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int -> Int
forall a. Num a => a -> a
abs Int
x

-- | Compute infinity-norm between two coordinates (max of magnitudes)
normInf :: Coord -> Int
normInf :: Coord -> Int
normInf (C Int
y Int
x) = Int -> Int -> Int
forall a. Ord a => a -> a -> a
max (Int -> Int
forall a. Num a => a -> a
abs Int
y) (Int -> Int
forall a. Num a => a -> a
abs Int
x)

-- | Compute the 4 cardinal neighbors of a coordinate: north, south, east, west
cardinal :: Coord -> [Coord]
cardinal :: Coord -> [Coord]
cardinal Coord
c = Coord
c Coord -> [Coord] -> [Coord]
forall a b. a -> b -> b
`seq` [Coord -> Coord
above Coord
c, Coord -> Coord
left Coord
c, Coord -> Coord
right Coord
c, Coord -> Coord
below Coord
c]

-- | Compute the 8 cardinal neighbors and diagonal neighbors
neighbors :: Coord -> [Coord]
neighbors :: Coord -> [Coord]
neighbors Coord
c = Coord
c Coord -> [Coord] -> [Coord]
forall a b. a -> b -> b
`seq` [Coord -> Coord
above Coord
c, Coord -> Coord
left Coord
c, Coord -> Coord
right Coord
c, Coord -> Coord
below Coord
c,
                       Coord -> Coord
above (Coord -> Coord
left Coord
c), Coord -> Coord
above (Coord -> Coord
right Coord
c),
                       Coord -> Coord
below (Coord -> Coord
left Coord
c), Coord -> Coord
below (Coord -> Coord
right Coord
c)]

-- | Find the upper-left and lower-right coordinates that
-- inclusively contain all the coordinates in a list of
-- coordinates.
boundingBox :: Foldable f => f Coord -> Maybe (Coord, Coord)
boundingBox :: forall (f :: * -> *). Foldable f => f Coord -> Maybe (Coord, Coord)
boundingBox f Coord
t =
  case f Coord -> [Coord]
forall a. f a -> [a]
forall (t :: * -> *) a. Foldable t => t a -> [a]
toList f Coord
t of
    []         -> Maybe (Coord, Coord)
forall a. Maybe a
Nothing
    C Int
y Int
x : [Coord]
cs -> Int -> Int -> Int -> Int -> [Coord] -> Maybe (Coord, Coord)
go Int
y Int
x Int
y Int
x [Coord]
cs
  where
    go :: Int -> Int -> Int -> Int -> [Coord] -> Maybe (Coord, Coord)
go Int
loy Int
lox Int
hiy Int
hix [] = Coord
lo Coord -> Maybe (Coord, Coord) -> Maybe (Coord, Coord)
forall a b. a -> b -> b
`seq` Coord
hi Coord -> Maybe (Coord, Coord) -> Maybe (Coord, Coord)
forall a b. a -> b -> b
`seq` (Coord, Coord) -> Maybe (Coord, Coord)
forall a. a -> Maybe a
Just (Coord
lo, Coord
hi)
      where
        lo :: Coord
lo = Int -> Int -> Coord
C Int
loy Int
lox
        hi :: Coord
hi = Int -> Int -> Coord
C Int
hiy Int
hix
    go Int
loy Int
lox Int
hiy Int
hix (C Int
y Int
x : [Coord]
cs) = Int -> Int -> Int -> Int -> [Coord] -> Maybe (Coord, Coord)
go (Int -> Int -> Int
forall a. Ord a => a -> a -> a
min Int
loy Int
y) (Int -> Int -> Int
forall a. Ord a => a -> a -> a
min Int
lox Int
x) (Int -> Int -> Int
forall a. Ord a => a -> a -> a
max Int
hiy Int
y) (Int -> Int -> Int
forall a. Ord a => a -> a -> a
max Int
hix Int
x) [Coord]
cs

-- | Coordinate at the origin
origin :: Coord
origin :: Coord
origin = Int -> Int -> Coord
C Int
0 Int
0

-- | Unit vector pointing up
north :: Coord
north :: Coord
north = Int -> Int -> Coord
C (-Int
1) Int
0

-- | Unit vector pointing right
east :: Coord
east :: Coord
east = Int -> Int -> Coord
C Int
0 Int
1

-- | Unit vector pointing down
south :: Coord
south :: Coord
south = Int -> Int -> Coord
C Int
1 Int
0

-- | Unit vector pointing left
west :: Coord
west :: Coord
west = Int -> Int -> Coord
C Int
0 (-Int
1)

-- | Scale a coordinate as a vector from the origin
scaleCoord :: Int -> Coord -> Coord
scaleCoord :: Int -> Coord -> Coord
scaleCoord Int
n = (Int -> Int) -> Coord -> Coord
mapCoord (Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
*)

-- | Render a minimal bounding box containing all the characters
-- at the given coordinates. Empty space filled with space characters.
drawPicture :: Map Coord Char -> String
drawPicture :: Map Coord Char -> String
drawPicture Map Coord Char
pixels =
  case [Coord] -> Maybe (Coord, Coord)
forall (f :: * -> *). Foldable f => f Coord -> Maybe (Coord, Coord)
boundingBox (Map Coord Char -> [Coord]
forall k a. Map k a -> [k]
Map.keys Map Coord Char
pixels) of
    Maybe (Coord, Coord)
Nothing -> String
""
    Just (C Int
miny Int
minx, C Int
maxy Int
maxx) ->
      [String] -> String
unlines [[Char -> Coord -> Map Coord Char -> Char
forall k a. Ord k => a -> k -> Map k a -> a
Map.findWithDefault Char
'·' (Int -> Int -> Coord
C Int
y Int
x) Map Coord Char
pixels | Int
x <- [Int
minx .. Int
maxx]] | Int
y <- [Int
miny .. Int
maxy]]

-- | Render a minimal bounding box containing boxes
-- at the given coordinates.
drawCoords :: Foldable t => t Coord -> String
drawCoords :: forall (t :: * -> *). Foldable t => t Coord -> String
drawCoords t Coord
coords = Map Coord Char -> String
drawPicture ([(Coord, Char)] -> Map Coord Char
forall k a. Ord k => [(k, a)] -> Map k a
Map.fromList [(Coord
c,Char
'█') | Coord
c <- t Coord -> [Coord]
forall a. t a -> [a]
forall (t :: * -> *) a. Foldable t => t a -> [a]
toList t Coord
coords])

-- | Given a list of lines pair up each character with
-- its position.
coordLines :: [String] -> [(Coord, Char)]
coordLines :: [String] -> [(Coord, Char)]
coordLines [String]
rows = [(Int -> Int -> Coord
C Int
y Int
x, Char
z) | (Int
y,String
row) <- [Int] -> [String] -> [(Int, String)]
forall a b. [a] -> [b] -> [(a, b)]
zip [Int
0..] [String]
rows, (Int
x,Char
z) <- [Int] -> String -> [(Int, Char)]
forall a b. [a] -> [b] -> [(a, b)]
zip [Int
0..] String
row]

-- | Apply a function to the y and x coordinate
mapCoord :: (Int -> Int) -> Coord -> Coord
mapCoord :: (Int -> Int) -> Coord -> Coord
mapCoord Int -> Int
f (C Int
y Int
x) = Int -> Int -> Coord
C (Int -> Int
f Int
y) (Int -> Int
f Int
x)

-- | Use a function pairwise on x and y coordinates of the two arguments
zipCoord :: (Int -> Int -> Int) -> Coord -> Coord -> Coord
zipCoord :: (Int -> Int -> Int) -> Coord -> Coord -> Coord
zipCoord Int -> Int -> Int
f (C Int
y1 Int
x1) (C Int
y2 Int
x2) = Int -> Int -> Coord
C (Int -> Int -> Int
f Int
y1 Int
y2) (Int -> Int -> Int
f Int
x1 Int
x2)

-- | Generate a unit vector corresponding to the arrow symbol: @^v<>@
charToVec :: Char -> Maybe Coord
charToVec :: Char -> Maybe Coord
charToVec Char
'^' = Coord -> Maybe Coord
forall a. a -> Maybe a
Just Coord
north
charToVec Char
'v' = Coord -> Maybe Coord
forall a. a -> Maybe a
Just Coord
south
charToVec Char
'>' = Coord -> Maybe Coord
forall a. a -> Maybe a
Just Coord
east
charToVec Char
'<' = Coord -> Maybe Coord
forall a. a -> Maybe a
Just Coord
west
charToVec  Char
_  = Maybe Coord
forall a. Maybe a
Nothing

-- | Vector arithmetic
instance Num Coord where
  + :: Coord -> Coord -> Coord
(+) = (Int -> Int -> Int) -> Coord -> Coord -> Coord
zipCoord Int -> Int -> Int
forall a. Num a => a -> a -> a
(+)
  {-# INLINE (+) #-}
  (-) = (Int -> Int -> Int) -> Coord -> Coord -> Coord
zipCoord (-)
  {-# INLINE (-) #-}
  * :: Coord -> Coord -> Coord
(*) = (Int -> Int -> Int) -> Coord -> Coord -> Coord
zipCoord Int -> Int -> Int
forall a. Num a => a -> a -> a
(*)
  {-# INLINE (*) #-}
  negate :: Coord -> Coord
negate = (Int -> Int) -> Coord -> Coord
mapCoord Int -> Int
forall a. Num a => a -> a
negate
  {-# INLINE negate #-}
  abs :: Coord -> Coord
abs = (Int -> Int) -> Coord -> Coord
mapCoord Int -> Int
forall a. Num a => a -> a
abs
  {-# INLINE abs #-}
  signum :: Coord -> Coord
signum = (Int -> Int) -> Coord -> Coord
mapCoord Int -> Int
forall a. Num a => a -> a
signum
  {-# INLINE signum #-}
  fromInteger :: Integer -> Coord
fromInteger = (\Int
i -> Int -> Int -> Coord
C Int
i Int
i) (Int -> Coord) -> (Integer -> Int) -> Integer -> Coord
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Integer -> Int
forall a. Num a => Integer -> a
fromInteger
  {-# INLINE fromInteger #-}

instance HasTrie Coord where
  newtype Coord :->: a = CT (Int :->: Int :->: a)
  trie :: forall b. (Coord -> b) -> Coord :->: b
trie Coord -> b
f = (Int :->: (Int :->: b)) -> Coord :->: b
forall a. (Int :->: (Int :->: a)) -> Coord :->: a
CT ((Int -> Int :->: b) -> Int :->: (Int :->: b)
forall a b. HasTrie a => (a -> b) -> a :->: b
forall b. (Int -> b) -> Int :->: b
trie \Int
y -> (Int -> b) -> Int :->: b
forall a b. HasTrie a => (a -> b) -> a :->: b
forall b. (Int -> b) -> Int :->: b
trie \Int
x -> Coord -> b
f (Int -> Int -> Coord
C Int
y Int
x))
  CT Int :->: (Int :->: b)
t untrie :: forall b. (Coord :->: b) -> Coord -> b
`untrie` C Int
y Int
x = Int :->: (Int :->: b)
t (Int :->: (Int :->: b)) -> Int -> Int :->: b
forall a b. HasTrie a => (a :->: b) -> a -> b
forall b. (Int :->: b) -> Int -> b
`untrie` Int
y (Int :->: b) -> Int -> b
forall a b. HasTrie a => (a :->: b) -> a -> b
forall b. (Int :->: b) -> Int -> b
`untrie` Int
x
  enumerate :: forall b. (Coord :->: b) -> [(Coord, b)]
enumerate (CT Int :->: (Int :->: b)
t) = [(Int -> Int -> Coord
C Int
y Int
x, b
a) | (Int
y, Int :->: b
xs) <- (Int :->: (Int :->: b)) -> [(Int, Int :->: b)]
forall a b. HasTrie a => (a :->: b) -> [(a, b)]
forall b. (Int :->: b) -> [(Int, b)]
enumerate Int :->: (Int :->: b)
t, (Int
x, b
a) <- (Int :->: b) -> [(Int, b)]
forall a b. HasTrie a => (a :->: b) -> [(a, b)]
forall b. (Int :->: b) -> [(Int, b)]
enumerate Int :->: b
xs]

-- Array package interoperability

-- | Row-major coordinate indexing
--
-- >>> range (C 1 1, C 2 2)
-- [C 1 1,C 1 2,C 2 1,C 2 2]
--
-- >>> index (C 1 1, C 2 2) <$> range (C 1 1, C 2 2)
-- [0,1,2,3]
instance Ix Coord where
  unsafeIndex :: (Coord, Coord) -> Coord -> Int
unsafeIndex (C Int
lorow Int
locol, C Int
hirow Int
hicol) (C Int
row Int
col) =
    (Int, Int) -> Int -> Int
forall a. Ix a => (a, a) -> a -> Int
unsafeIndex (Int
lorow,Int
hirow) Int
row Int -> Int -> Int
forall a. Num a => a -> a -> a
* (Int, Int) -> Int
forall a. Ix a => (a, a) -> Int
unsafeRangeSize (Int
locol,Int
hicol) Int -> Int -> Int
forall a. Num a => a -> a -> a
+ (Int, Int) -> Int -> Int
forall a. Ix a => (a, a) -> a -> Int
unsafeIndex (Int
locol,Int
hicol) Int
col
  {-# INLINE unsafeIndex #-}

  index :: (Coord, Coord) -> Coord -> Int
index (Coord, Coord)
b Coord
i
    | (Coord, Coord) -> Coord -> Bool
forall a. Ix a => (a, a) -> a -> Bool
inRange (Coord, Coord)
b Coord
i = (Coord, Coord) -> Coord -> Int
forall a. Ix a => (a, a) -> a -> Int
unsafeIndex (Coord, Coord)
b Coord
i
    | Bool
otherwise   = (Coord, Coord) -> Coord -> String -> Int
forall a b. Show a => (a, a) -> a -> String -> b
indexError (Coord, Coord)
b Coord
i String
"Coord"
  {-# INLINE index #-}

  inRange :: (Coord, Coord) -> Coord -> Bool
inRange (C Int
lorow Int
locol, C Int
hirow Int
hicol) (C Int
row Int
col) =
    (Int, Int) -> Int -> Bool
forall a. Ix a => (a, a) -> a -> Bool
inRange (Int
lorow,Int
hirow) Int
row Bool -> Bool -> Bool
&& (Int, Int) -> Int -> Bool
forall a. Ix a => (a, a) -> a -> Bool
inRange (Int
locol,Int
hicol) Int
col
  {-# INLINE inRange #-}

  range :: (Coord, Coord) -> [Coord]
range (C Int
lorow Int
locol, C Int
hirow Int
hicol) =
    [Int -> Int -> Coord
C Int
row Int
col | Int
row <- [Int
lorow..Int
hirow], Int
col <- [Int
locol..Int
hicol]]
  {-# INLINE range #-}

  unsafeRangeSize :: (Coord, Coord) -> Int
unsafeRangeSize (C Int
lorow Int
locol, C Int
hirow Int
hicol) =
    (Int
hirow Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
lorow Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1) Int -> Int -> Int
forall a. Num a => a -> a -> a
* (Int
hicol Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
locol Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1)
  {-# INLINE unsafeRangeSize #-}

instance AB.IArray AB.UArray Coord where
  {-# INLINE bounds #-}
  bounds :: forall i. Ix i => UArray i Coord -> (i, i)
bounds (AB.UArray i
l i
u Int
_ ByteArray#
_) = (i
l,i
u)
  {-# INLINE numElements #-}
  numElements :: forall i. Ix i => UArray i Coord -> Int
numElements (AB.UArray i
_ i
_ Int
n ByteArray#
_) = Int
n
  {-# INLINE unsafeArray #-}
  unsafeArray :: forall i. Ix i => (i, i) -> [(Int, Coord)] -> UArray i Coord
unsafeArray (i, i)
lu [(Int, Coord)]
ies = (forall s. ST s (UArray i Coord)) -> UArray i Coord
forall a. (forall s. ST s a) -> a
runST ((i, i) -> [(Int, Coord)] -> Coord -> ST s (UArray i Coord)
forall s e i.
(MArray (STUArray s) e (ST s), Ix i) =>
(i, i) -> [(Int, e)] -> e -> ST s (UArray i e)
AB.unsafeArrayUArray (i, i)
lu [(Int, Coord)]
ies Coord
0)
  {-# INLINE unsafeAt #-}
  unsafeAt :: forall i. Ix i => UArray i Coord -> Int -> Coord
unsafeAt (AB.UArray i
_ i
_ Int
_ ByteArray#
arr#) (I# Int#
i#) =
    Int -> Int -> Coord
C (Int# -> Int
I# (ByteArray# -> Int# -> Int#
indexIntArray# ByteArray#
arr# (Int#
2# Int# -> Int# -> Int#
*# Int#
i#)))
      (Int# -> Int
I# (ByteArray# -> Int# -> Int#
indexIntArray# ByteArray#
arr# (Int#
2# Int# -> Int# -> Int#
*# Int#
i# Int# -> Int# -> Int#
+# Int#
1#)))
  {-# INLINE unsafeReplace #-}
  unsafeReplace :: forall i.
Ix i =>
UArray i Coord -> [(Int, Coord)] -> UArray i Coord
unsafeReplace UArray i Coord
arr [(Int, Coord)]
ies = (forall s. ST s (UArray i Coord)) -> UArray i Coord
forall a. (forall s. ST s a) -> a
runST (UArray i Coord -> [(Int, Coord)] -> ST s (UArray i Coord)
forall s e i.
(MArray (STUArray s) e (ST s), Ix i) =>
UArray i e -> [(Int, e)] -> ST s (UArray i e)
AB.unsafeReplaceUArray UArray i Coord
arr [(Int, Coord)]
ies)
  {-# INLINE unsafeAccum #-}
  unsafeAccum :: forall i e'.
Ix i =>
(Coord -> e' -> Coord)
-> UArray i Coord -> [(Int, e')] -> UArray i Coord
unsafeAccum Coord -> e' -> Coord
f UArray i Coord
arr [(Int, e')]
ies = (forall s. ST s (UArray i Coord)) -> UArray i Coord
forall a. (forall s. ST s a) -> a
runST ((Coord -> e' -> Coord)
-> UArray i Coord -> [(Int, e')] -> ST s (UArray i Coord)
forall s e i e'.
(MArray (STUArray s) e (ST s), Ix i) =>
(e -> e' -> e) -> UArray i e -> [(Int, e')] -> ST s (UArray i e)
AB.unsafeAccumUArray Coord -> e' -> Coord
f UArray i Coord
arr [(Int, e')]
ies)
  {-# INLINE unsafeAccumArray #-}
  unsafeAccumArray :: forall i e'.
Ix i =>
(Coord -> e' -> Coord)
-> Coord -> (i, i) -> [(Int, e')] -> UArray i Coord
unsafeAccumArray Coord -> e' -> Coord
f Coord
initialValue (i, i)
lu [(Int, e')]
ies = (forall s. ST s (UArray i Coord)) -> UArray i Coord
forall a. (forall s. ST s a) -> a
runST ((Coord -> e' -> Coord)
-> Coord -> (i, i) -> [(Int, e')] -> ST s (UArray i Coord)
forall s e i e'.
(MArray (STUArray s) e (ST s), Ix i) =>
(e -> e' -> e) -> e -> (i, i) -> [(Int, e')] -> ST s (UArray i e)
AB.unsafeAccumArrayUArray Coord -> e' -> Coord
f Coord
initialValue (i, i)
lu [(Int, e')]
ies)

instance AB.MArray (AB.STUArray s) Coord (ST s) where
    {-# INLINE getBounds #-}
    getBounds :: forall i. Ix i => STUArray s i Coord -> ST s (i, i)
getBounds (AB.STUArray i
l i
u Int
_ MutableByteArray# s
_) = (i, i) -> ST s (i, i)
forall a. a -> ST s a
forall (m :: * -> *) a. Monad m => a -> m a
return (i
l,i
u)
    {-# INLINE getNumElements #-}
    getNumElements :: forall i. Ix i => STUArray s i Coord -> ST s Int
getNumElements (AB.STUArray i
_ i
_ Int
n MutableByteArray# s
_) = Int -> ST s Int
forall a. a -> ST s a
forall (m :: * -> *) a. Monad m => a -> m a
return Int
n
    {-# INLINE unsafeNewArray_ #-}
    unsafeNewArray_ :: forall i. Ix i => (i, i) -> ST s (STUArray s i Coord)
unsafeNewArray_ (i
l,i
u) = (i, i) -> (Int# -> Int#) -> ST s (STUArray s i Coord)
forall i s e.
Ix i =>
(i, i) -> (Int# -> Int#) -> ST s (STUArray s i e)
AB.unsafeNewArraySTUArray_ (i
l,i
u) (\Int#
x -> Int#
2# Int# -> Int# -> Int#
*# Int# -> Int#
AB.wORD_SCALE Int#
x)
    {-# INLINE newArray_ #-}
    newArray_ :: forall i. Ix i => (i, i) -> ST s (STUArray s i Coord)
newArray_ (i, i)
arrBounds = (i, i) -> Coord -> ST s (STUArray s i Coord)
forall i. Ix i => (i, i) -> Coord -> ST s (STUArray s i Coord)
forall (a :: * -> * -> *) e (m :: * -> *) i.
(MArray a e m, Ix i) =>
(i, i) -> e -> m (a i e)
AB.newArray (i, i)
arrBounds Coord
0
    {-# INLINE unsafeRead #-}
    unsafeRead :: forall i. Ix i => STUArray s i Coord -> Int -> ST s Coord
unsafeRead (AB.STUArray i
_ i
_ Int
_ MutableByteArray# s
marr#) (I# Int#
i#) = STRep s Coord -> ST s Coord
forall s a. STRep s a -> ST s a
ST (STRep s Coord -> ST s Coord) -> STRep s Coord -> ST s Coord
forall a b. (a -> b) -> a -> b
$ \State# s
s1# ->
        case MutableByteArray# s -> Int# -> State# s -> (# State# s, Int# #)
forall d.
MutableByteArray# d -> Int# -> State# d -> (# State# d, Int# #)
readIntArray# MutableByteArray# s
marr# (Int#
2# Int# -> Int# -> Int#
*# Int#
i#      ) State# s
s1# of { (# State# s
s2#, Int#
y# #) ->
        case MutableByteArray# s -> Int# -> State# s -> (# State# s, Int# #)
forall d.
MutableByteArray# d -> Int# -> State# d -> (# State# d, Int# #)
readIntArray# MutableByteArray# s
marr# (Int#
2# Int# -> Int# -> Int#
*# Int#
i# Int# -> Int# -> Int#
+# Int#
1#) State# s
s2# of { (# State# s
s3#, Int#
x# #) ->
        (# State# s
s3#, Int -> Int -> Coord
C (Int# -> Int
I# Int#
y#) (Int# -> Int
I# Int#
x#) #) }}
    {-# INLINE unsafeWrite #-}
    unsafeWrite :: forall i. Ix i => STUArray s i Coord -> Int -> Coord -> ST s ()
unsafeWrite (AB.STUArray i
_ i
_ Int
_ MutableByteArray# s
marr#) (I# Int#
i#) (C (I# Int#
y#) (I# Int#
x#)) = STRep s () -> ST s ()
forall s a. STRep s a -> ST s a
ST (STRep s () -> ST s ()) -> STRep s () -> ST s ()
forall a b. (a -> b) -> a -> b
$ \State# s
s1# ->
        case MutableByteArray# s -> Int# -> Int# -> State# s -> State# s
forall d.
MutableByteArray# d -> Int# -> Int# -> State# d -> State# d
writeIntArray# MutableByteArray# s
marr# (Int#
2# Int# -> Int# -> Int#
*# Int#
i#      ) Int#
y# State# s
s1# of { State# s
s2# ->
        case MutableByteArray# s -> Int# -> Int# -> State# s -> State# s
forall d.
MutableByteArray# d -> Int# -> Int# -> State# d -> State# d
writeIntArray# MutableByteArray# s
marr# (Int#
2# Int# -> Int# -> Int#
*# Int#
i# Int# -> Int# -> Int#
+# Int#
1#) Int#
x# State# s
s2# of { State# s
s3# ->
        (# State# s
s3#, () #) }}

instance AB.MArray AB.IOUArray Coord IO where
    {-# INLINE getBounds #-}
    getBounds :: forall i. Ix i => IOUArray i Coord -> IO (i, i)
getBounds (AB.IOUArray STUArray RealWorld i Coord
arr) = ST RealWorld (i, i) -> IO (i, i)
forall a. ST RealWorld a -> IO a
stToIO (STUArray RealWorld i Coord -> ST RealWorld (i, i)
forall i. Ix i => STUArray RealWorld i Coord -> ST RealWorld (i, i)
forall (a :: * -> * -> *) e (m :: * -> *) i.
(MArray a e m, Ix i) =>
a i e -> m (i, i)
AB.getBounds STUArray RealWorld i Coord
arr)
    {-# INLINE getNumElements #-}
    getNumElements :: forall i. Ix i => IOUArray i Coord -> IO Int
getNumElements (AB.IOUArray STUArray RealWorld i Coord
arr) = ST RealWorld Int -> IO Int
forall a. ST RealWorld a -> IO a
stToIO (STUArray RealWorld i Coord -> ST RealWorld Int
forall i. Ix i => STUArray RealWorld i Coord -> ST RealWorld Int
forall (a :: * -> * -> *) e (m :: * -> *) i.
(MArray a e m, Ix i) =>
a i e -> m Int
AB.getNumElements STUArray RealWorld i Coord
arr)
    {-# INLINE newArray #-}
    newArray :: forall i. Ix i => (i, i) -> Coord -> IO (IOUArray i Coord)
newArray (i, i)
lu Coord
initialValue = ST RealWorld (IOUArray i Coord) -> IO (IOUArray i Coord)
forall a. ST RealWorld a -> IO a
stToIO (STUArray RealWorld i Coord -> IOUArray i Coord
forall i e. STUArray RealWorld i e -> IOUArray i e
AB.IOUArray (STUArray RealWorld i Coord -> IOUArray i Coord)
-> ST RealWorld (STUArray RealWorld i Coord)
-> ST RealWorld (IOUArray i Coord)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (i, i) -> Coord -> ST RealWorld (STUArray RealWorld i Coord)
forall i.
Ix i =>
(i, i) -> Coord -> ST RealWorld (STUArray RealWorld i Coord)
forall (a :: * -> * -> *) e (m :: * -> *) i.
(MArray a e m, Ix i) =>
(i, i) -> e -> m (a i e)
AB.newArray (i, i)
lu Coord
initialValue)
    {-# INLINE unsafeNewArray_ #-}
    unsafeNewArray_ :: forall i. Ix i => (i, i) -> IO (IOUArray i Coord)
unsafeNewArray_ (i, i)
lu = ST RealWorld (IOUArray i Coord) -> IO (IOUArray i Coord)
forall a. ST RealWorld a -> IO a
stToIO (STUArray RealWorld i Coord -> IOUArray i Coord
forall i e. STUArray RealWorld i e -> IOUArray i e
AB.IOUArray (STUArray RealWorld i Coord -> IOUArray i Coord)
-> ST RealWorld (STUArray RealWorld i Coord)
-> ST RealWorld (IOUArray i Coord)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (i, i) -> ST RealWorld (STUArray RealWorld i Coord)
forall i.
Ix i =>
(i, i) -> ST RealWorld (STUArray RealWorld i Coord)
forall (a :: * -> * -> *) e (m :: * -> *) i.
(MArray a e m, Ix i) =>
(i, i) -> m (a i e)
AB.unsafeNewArray_ (i, i)
lu)
    {-# INLINE newArray_ #-}
    newArray_ :: forall i. Ix i => (i, i) -> IO (IOUArray i Coord)
newArray_ = (i, i) -> IO (IOUArray i Coord)
forall i. Ix i => (i, i) -> IO (IOUArray i Coord)
forall (a :: * -> * -> *) e (m :: * -> *) i.
(MArray a e m, Ix i) =>
(i, i) -> m (a i e)
AB.unsafeNewArray_
    {-# INLINE unsafeRead #-}
    unsafeRead :: forall i. Ix i => IOUArray i Coord -> Int -> IO Coord
unsafeRead (AB.IOUArray STUArray RealWorld i Coord
marr) Int
i = ST RealWorld Coord -> IO Coord
forall a. ST RealWorld a -> IO a
stToIO (STUArray RealWorld i Coord -> Int -> ST RealWorld Coord
forall i.
Ix i =>
STUArray RealWorld i Coord -> Int -> ST RealWorld Coord
forall (a :: * -> * -> *) e (m :: * -> *) i.
(MArray a e m, Ix i) =>
a i e -> Int -> m e
AB.unsafeRead STUArray RealWorld i Coord
marr Int
i)
    {-# INLINE unsafeWrite #-}
    unsafeWrite :: forall i. Ix i => IOUArray i Coord -> Int -> Coord -> IO ()
unsafeWrite (AB.IOUArray STUArray RealWorld i Coord
marr) Int
i Coord
e = ST RealWorld () -> IO ()
forall a. ST RealWorld a -> IO a
stToIO (STUArray RealWorld i Coord -> Int -> Coord -> ST RealWorld ()
forall i.
Ix i =>
STUArray RealWorld i Coord -> Int -> Coord -> ST RealWorld ()
forall (a :: * -> * -> *) e (m :: * -> *) i.
(MArray a e m, Ix i) =>
a i e -> Int -> e -> m ()
AB.unsafeWrite STUArray RealWorld i Coord
marr Int
i Coord
e)