{-
	Copyright (C) 2018 Dr. Alistair Ward

	This file is part of BishBosh.

	BishBosh is free software: you can redistribute it and/or modify
	it under the terms of the GNU General Public License as published by
	the Free Software Foundation, either version 3 of the License, or
	(at your option) any later version.

	BishBosh is distributed in the hope that it will be useful,
	but WITHOUT ANY WARRANTY; without even the implied warranty of
	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
	GNU General Public License for more details.

	You should have received a copy of the GNU General Public License
	along with BishBosh.  If not, see <http://www.gnu.org/licenses/>.
-}
{- |
 [@AUTHOR@]	Dr. Alistair Ward

 [@DESCRIPTION@]
-}

module BishBosh.Model.PositionHashTree(
-- * Types
-- ** Type-synonyms
--	BarePositionHashTree,
-- ** Data-types
        PositionHashTree(),
-- * Function
        countDistinctPositions,
-- ** Constructors
        mkPositionHashTree
) where

import qualified        BishBosh.Component.Zobrist      as Component.Zobrist
import qualified        BishBosh.Data.Exception         as Data.Exception
import qualified        BishBosh.Model.Game             as Model.Game
import qualified        BishBosh.Model.GameTree         as Model.GameTree
import qualified        BishBosh.Property.Tree          as Property.Tree
import qualified        BishBosh.Text.ShowList          as Text.ShowList
import qualified        BishBosh.Types                  as T
import qualified        Control.Exception
import qualified        Data.Array.IArray
import qualified        Data.Bits
import qualified        Data.Default
import qualified        Data.List
import qualified        Data.Set
import qualified        Data.Tree
import qualified        System.Random

-- | The hash of a /game-tree/.
type BarePositionHashTree positionHash  = Data.Tree.Tree positionHash

-- | Wrap a 'BarePositionHashTree'.
newtype PositionHashTree positionHash   = MkPositionHashTree {
        deconstruct     :: BarePositionHashTree positionHash
}

instance (
        Data.Bits.FiniteBits    positionHash,
        Num                     positionHash,
        System.Random.Random    positionHash
 ) => Data.Default.Default (PositionHashTree positionHash) where
        def     = mkPositionHashTree Data.Default.def (Data.Default.def :: Model.GameTree.GameTree T.X T.Y)

-- | Hash the specified 'game-tree/.
mkPositionHashTree :: (
        Data.Array.IArray.Ix    x,
        Data.Bits.Bits          positionHash,
        Enum                    x,
        Enum                    y,
        Ord                     y
 )
        => Component.Zobrist.Zobrist x y positionHash
        -> Model.GameTree.GameTree x y
        -> PositionHashTree positionHash
mkPositionHashTree zobrist      = MkPositionHashTree . fmap (`Component.Zobrist.hash2D` zobrist) . Model.GameTree.deconstruct

-- | Count the number of distinct games, irrespective of the sequence of moves taken to reach that state.
countDistinctPositions
        :: Ord positionHash
        => Property.Tree.Depth
        -> PositionHashTree positionHash
        -> Model.Game.NGames
{-# SPECIALISE countDistinctPositions :: Property.Tree.Depth -> PositionHashTree T.PositionHash -> Model.Game.NGames #-}
countDistinctPositions depth MkPositionHashTree { deconstruct = barePositionHashTree }
        | depth < 0     = Control.Exception.throw . Data.Exception.mkOutOfBounds . showString "BishBosh.Component.PositionHashTree.countDistinctPositions:\tdepth" . Text.ShowList.showsAssociation $ shows depth "must be positive"
        | otherwise     = Data.Set.size $ slave depth barePositionHashTree
        where
                slave 0 Data.Tree.Node { Data.Tree.rootLabel = hash }           = Data.Set.singleton hash       -- Having reached the maximum depth, include this game's hash.
                slave _ Data.Tree.Node {
                        Data.Tree.rootLabel     = hash,
                        Data.Tree.subForest     = []
                }                                                               = Data.Set.singleton hash       -- Being unable to descend further, include the terminal game's hash.
                slave depth' Data.Tree.Node { Data.Tree.subForest = forest }    = Data.List.foldl' (
                        \s -> Data.Set.union s . slave (pred depth') {-recurse-}
                 ) Data.Set.empty forest