module Node
  ( Node(..)
  , children
  , heuristic
  , toList
  ) where

import Control.Arrow
import Data.Ix
import Data.List
import Data.Maybe

import Data.Map.Strict(Map, (!))

data Node = Node {boardState::[[Int]], searchDepth::Int, parent::Node}
          | EmptyNode

instance Eq Node where
  (==) EmptyNode EmptyNode = True
  (==) EmptyNode Node{} = False
  (==) Node{} EmptyNode = False
  (==) (Node state1 _ _) (Node state2 _ _) = state1 == state2

instance Ord Node where
  compare EmptyNode EmptyNode = EQ
  compare EmptyNode Node{} = LT
  compare Node{} EmptyNode = GT
  compare (Node state1 _ _) (Node state2 _ _) = compare state1 state2

instance Show Node where
  show EmptyNode = ""
  show (Node state _ _) = concatMap ((++ "\n") . show) state

-- | Generates a node's children.
children::Node -> [Node]
children EmptyNode = []
children node@(Node state depth _) = makeChild <$> childStates state
  where makeChild childState = Node childState (depth + 1) node

-- | Calculates the h-score of a node.
heuristic::Node -- ^ The node.
         -> Map Int (Int, Int) -- ^ A map mapping each number to its goal position.
         -> Int -- ^ The h-score of the node.
heuristic EmptyNode _ = 0
heuristic (Node state _ _) goalMap =
  sum [disp (indexToPosition i) (goalMap!n) | (i, n) <- zip [0..] (concat state)]
  where disp (r, c) (r', c') = abs (r - r') + abs (c - c')

-- | Converts a given node into a list of nodes,
-- with parents coming before their children.
toList::Node -> [Node]
toList EmptyNode = []
toList node = toList (parent node) ++ [node]

-- | Converts a given index for a 1D board representation into
-- the corresponding (row, column) 2D index pair on the 8-Puzzle.
indexToPosition::Int -- ^ The index of the 1D board representation.
               -> (Int, Int) -- ^ The corresponding position on the 8-Puzzle.
indexToPosition = (`quot` 3) &&& (`rem` 3)

-- | Moves the empty tile to the specified position.
moveTile:: (Int, Int) -- ^ The new position (row, column).
        -> [[Int]] -- ^ The current board.
        -> [[Int]] -- ^ The updated board.
moveTile (r, c) board = (updateTile ((board!!r)!!c) <$>) <$> board
  where updateTile val x -- val is the current value at the new position
          | x == val = 0
          | x == 0 = val
          | otherwise = x

-- | Generates possible moves for a given state.
possibleMoves::[[Int]] -- ^ The state.
             -> [(Int, Int)] -- ^ The possible positions for the moved empty tile.
possibleMoves state = filter isInBounds [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]
  where (r, c) = indexToPosition $ fromJust . elemIndex 0 . concat $ state
        isInBounds (r', c') = all (inRange (0, 2)) [r', c']

-- | Generates a board state's child states.
childStates::[[Int]] -> [[[Int]]]
childStates state = (`moveTile` state) <$> possibleMoves state
