{-# Language DeriveGeneric, DeriveDataTypeable #-}
{-|
Module      : Advent.Coord3
Description : 3D coordinates
Copyright   : (c) Eric Mertens, 2018
License     : ISC
Maintainer  : emertens@gmail.com

-}
module Advent.Coord3 where

import Data.Data (Data)
import Data.Foldable (toList)
import GHC.Generics (Generic)
import GHC.Ix (Ix(unsafeIndex, range, index, inRange, unsafeRangeSize), indexError)

-- | Three-dimensional coordinate: x, y, z
data Coord3 = C3 !Int !Int !Int
  deriving (Coord3 -> Coord3 -> Bool
(Coord3 -> Coord3 -> Bool)
-> (Coord3 -> Coord3 -> Bool) -> Eq Coord3
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: Coord3 -> Coord3 -> Bool
== :: Coord3 -> Coord3 -> Bool
$c/= :: Coord3 -> Coord3 -> Bool
/= :: Coord3 -> Coord3 -> Bool
Eq, Eq Coord3
Eq Coord3 =>
(Coord3 -> Coord3 -> Ordering)
-> (Coord3 -> Coord3 -> Bool)
-> (Coord3 -> Coord3 -> Bool)
-> (Coord3 -> Coord3 -> Bool)
-> (Coord3 -> Coord3 -> Bool)
-> (Coord3 -> Coord3 -> Coord3)
-> (Coord3 -> Coord3 -> Coord3)
-> Ord Coord3
Coord3 -> Coord3 -> Bool
Coord3 -> Coord3 -> Ordering
Coord3 -> Coord3 -> Coord3
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 :: Coord3 -> Coord3 -> Ordering
compare :: Coord3 -> Coord3 -> Ordering
$c< :: Coord3 -> Coord3 -> Bool
< :: Coord3 -> Coord3 -> Bool
$c<= :: Coord3 -> Coord3 -> Bool
<= :: Coord3 -> Coord3 -> Bool
$c> :: Coord3 -> Coord3 -> Bool
> :: Coord3 -> Coord3 -> Bool
$c>= :: Coord3 -> Coord3 -> Bool
>= :: Coord3 -> Coord3 -> Bool
$cmax :: Coord3 -> Coord3 -> Coord3
max :: Coord3 -> Coord3 -> Coord3
$cmin :: Coord3 -> Coord3 -> Coord3
min :: Coord3 -> Coord3 -> Coord3
Ord, Int -> Coord3 -> ShowS
[Coord3] -> ShowS
Coord3 -> String
(Int -> Coord3 -> ShowS)
-> (Coord3 -> String) -> ([Coord3] -> ShowS) -> Show Coord3
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: Int -> Coord3 -> ShowS
showsPrec :: Int -> Coord3 -> ShowS
$cshow :: Coord3 -> String
show :: Coord3 -> String
$cshowList :: [Coord3] -> ShowS
showList :: [Coord3] -> ShowS
Show, (forall x. Coord3 -> Rep Coord3 x)
-> (forall x. Rep Coord3 x -> Coord3) -> Generic Coord3
forall x. Rep Coord3 x -> Coord3
forall x. Coord3 -> Rep Coord3 x
forall a.
(forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
$cfrom :: forall x. Coord3 -> Rep Coord3 x
from :: forall x. Coord3 -> Rep Coord3 x
$cto :: forall x. Rep Coord3 x -> Coord3
to :: forall x. Rep Coord3 x -> Coord3
Generic, Typeable Coord3
Typeable Coord3 =>
(forall (c :: * -> *).
 (forall d b. Data d => c (d -> b) -> d -> c b)
 -> (forall g. g -> c g) -> Coord3 -> c Coord3)
-> (forall (c :: * -> *).
    (forall b r. Data b => c (b -> r) -> c r)
    -> (forall r. r -> c r) -> Constr -> c Coord3)
-> (Coord3 -> Constr)
-> (Coord3 -> DataType)
-> (forall (t :: * -> *) (c :: * -> *).
    Typeable t =>
    (forall d. Data d => c (t d)) -> Maybe (c Coord3))
-> (forall (t :: * -> * -> *) (c :: * -> *).
    Typeable t =>
    (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c Coord3))
-> ((forall b. Data b => b -> b) -> Coord3 -> Coord3)
-> (forall r r'.
    (r -> r' -> r)
    -> r -> (forall d. Data d => d -> r') -> Coord3 -> r)
-> (forall r r'.
    (r' -> r -> r)
    -> r -> (forall d. Data d => d -> r') -> Coord3 -> r)
-> (forall u. (forall d. Data d => d -> u) -> Coord3 -> [u])
-> (forall u. Int -> (forall d. Data d => d -> u) -> Coord3 -> u)
-> (forall (m :: * -> *).
    Monad m =>
    (forall d. Data d => d -> m d) -> Coord3 -> m Coord3)
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> Coord3 -> m Coord3)
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> Coord3 -> m Coord3)
-> Data Coord3
Coord3 -> Constr
Coord3 -> DataType
(forall b. Data b => b -> b) -> Coord3 -> Coord3
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) -> Coord3 -> u
forall u. (forall d. Data d => d -> u) -> Coord3 -> [u]
forall r r'.
(r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Coord3 -> r
forall r r'.
(r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Coord3 -> r
forall (m :: * -> *).
Monad m =>
(forall d. Data d => d -> m d) -> Coord3 -> m Coord3
forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d) -> Coord3 -> m Coord3
forall (c :: * -> *).
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c Coord3
forall (c :: * -> *).
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> Coord3 -> c Coord3
forall (t :: * -> *) (c :: * -> *).
Typeable t =>
(forall d. Data d => c (t d)) -> Maybe (c Coord3)
forall (t :: * -> * -> *) (c :: * -> *).
Typeable t =>
(forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c Coord3)
$cgfoldl :: forall (c :: * -> *).
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> Coord3 -> c Coord3
gfoldl :: forall (c :: * -> *).
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> Coord3 -> c Coord3
$cgunfold :: forall (c :: * -> *).
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c Coord3
gunfold :: forall (c :: * -> *).
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c Coord3
$ctoConstr :: Coord3 -> Constr
toConstr :: Coord3 -> Constr
$cdataTypeOf :: Coord3 -> DataType
dataTypeOf :: Coord3 -> DataType
$cdataCast1 :: forall (t :: * -> *) (c :: * -> *).
Typeable t =>
(forall d. Data d => c (t d)) -> Maybe (c Coord3)
dataCast1 :: forall (t :: * -> *) (c :: * -> *).
Typeable t =>
(forall d. Data d => c (t d)) -> Maybe (c Coord3)
$cdataCast2 :: forall (t :: * -> * -> *) (c :: * -> *).
Typeable t =>
(forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c Coord3)
dataCast2 :: forall (t :: * -> * -> *) (c :: * -> *).
Typeable t =>
(forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c Coord3)
$cgmapT :: (forall b. Data b => b -> b) -> Coord3 -> Coord3
gmapT :: (forall b. Data b => b -> b) -> Coord3 -> Coord3
$cgmapQl :: forall r r'.
(r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Coord3 -> r
gmapQl :: forall r r'.
(r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Coord3 -> r
$cgmapQr :: forall r r'.
(r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Coord3 -> r
gmapQr :: forall r r'.
(r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Coord3 -> r
$cgmapQ :: forall u. (forall d. Data d => d -> u) -> Coord3 -> [u]
gmapQ :: forall u. (forall d. Data d => d -> u) -> Coord3 -> [u]
$cgmapQi :: forall u. Int -> (forall d. Data d => d -> u) -> Coord3 -> u
gmapQi :: forall u. Int -> (forall d. Data d => d -> u) -> Coord3 -> u
$cgmapM :: forall (m :: * -> *).
Monad m =>
(forall d. Data d => d -> m d) -> Coord3 -> m Coord3
gmapM :: forall (m :: * -> *).
Monad m =>
(forall d. Data d => d -> m d) -> Coord3 -> m Coord3
$cgmapMp :: forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d) -> Coord3 -> m Coord3
gmapMp :: forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d) -> Coord3 -> m Coord3
$cgmapMo :: forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d) -> Coord3 -> m Coord3
gmapMo :: forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d) -> Coord3 -> m Coord3
Data)

-- | Alias for @0, 0, 0@
origin :: Coord3
origin :: Coord3
origin = Int -> Int -> Int -> Coord3
C3 Int
0 Int
0 Int
0

-- | Sum of absolute value of differences in each of the 3 axes.
manhattan :: Coord3 -> Coord3 -> Int
manhattan :: Coord3 -> Coord3 -> Int
manhattan (C3 Int
x1 Int
y1 Int
z1) (C3 Int
x2 Int
y2 Int
z2) = Int -> Int
forall a. Num a => a -> a
abs (Int
x1 Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
x2) Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int -> Int
forall a. Num a => a -> a
abs (Int
y1 Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
y2) Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int -> Int
forall a. Num a => a -> a
abs (Int
z1 Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
z2)

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

-- | Apply a function to the y and x coordinate
mapCoord :: (Int -> Int) -> Coord3 -> Coord3
mapCoord :: (Int -> Int) -> Coord3 -> Coord3
mapCoord Int -> Int
f (C3 Int
x Int
y Int
z) = Int -> Int -> Int -> Coord3
C3 (Int -> Int
f Int
x) (Int -> Int
f Int
y) (Int -> Int
f Int
z)

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

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

instance Ix Coord3 where
    range :: (Coord3, Coord3) -> [Coord3]
range (C3 Int
l1 Int
l2 Int
l3, C3 Int
u1 Int
u2 Int
u3) =
        [Int -> Int -> Int -> Coord3
C3 Int
i1 Int
i2 Int
i3 
                | Int
i1 <- (Int, Int) -> [Int]
forall a. Ix a => (a, a) -> [a]
range (Int
l1,Int
u1),
                  Int
i2 <- (Int, Int) -> [Int]
forall a. Ix a => (a, a) -> [a]
range (Int
l2,Int
u2),
                  Int
i3 <- (Int, Int) -> [Int]
forall a. Ix a => (a, a) -> [a]
range (Int
l3,Int
u3)]

    unsafeIndex :: (Coord3, Coord3) -> Coord3 -> Int
unsafeIndex (C3 Int
l1 Int
l2 Int
l3, C3 Int
u1 Int
u2 Int
u3) (C3 Int
i1 Int
i2 Int
i3) =
      (Int, Int) -> Int -> Int
forall a. Ix a => (a, a) -> a -> Int
unsafeIndex (Int
l3,Int
u3) Int
i3 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ (Int, Int) -> Int
forall a. Ix a => (a, a) -> Int
unsafeRangeSize (Int
l3,Int
u3) Int -> Int -> Int
forall a. Num a => a -> a -> a
* (
      (Int, Int) -> Int -> Int
forall a. Ix a => (a, a) -> a -> Int
unsafeIndex (Int
l2,Int
u2) Int
i2 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ (Int, Int) -> Int
forall a. Ix a => (a, a) -> Int
unsafeRangeSize (Int
l2,Int
u2) Int -> Int -> Int
forall a. Num a => a -> a -> a
* (
      (Int, Int) -> Int -> Int
forall a. Ix a => (a, a) -> a -> Int
unsafeIndex (Int
l1,Int
u1) Int
i1))

    inRange :: (Coord3, Coord3) -> Coord3 -> Bool
inRange (C3 Int
l1 Int
l2 Int
l3, C3 Int
u1 Int
u2 Int
u3) (C3 Int
i1 Int
i2 Int
i3) =
      (Int, Int) -> Int -> Bool
forall a. Ix a => (a, a) -> a -> Bool
inRange (Int
l1,Int
u1) Int
i1 Bool -> Bool -> Bool
&& (Int, Int) -> Int -> Bool
forall a. Ix a => (a, a) -> a -> Bool
inRange (Int
l2,Int
u2) Int
i2 Bool -> Bool -> Bool
&&
      (Int, Int) -> Int -> Bool
forall a. Ix a => (a, a) -> a -> Bool
inRange (Int
l3,Int
u3) Int
i3