{-
	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@]	Records the number of times each /position/ has been encountered since the last unrepeatable move.
-}

module BishBosh.State.InstancesByPosition(
-- * Types
-- ** Type-synonyms
--	NBoardsByPosition,
--	Transformation.
-- * Constants
	leastCyclicPlies,
-- ** Data-types
	InstancesByPosition(),
-- * Functions
	countConsecutiveRepeatablePlies,
	countPositionRepetitions,
	getNDistinctPositions,
	findMaximumInstances,
-- ** Constructors
	mkInstancesByPosition,
	mkSingleton,
-- ** Mutators
	insertPosition,
	deletePosition,
-- ** Predicates
	anyInstancesByPosition
) where

import qualified	BishBosh.Component.Move		as Component.Move
import qualified	BishBosh.Data.Exception		as Data.Exception
import qualified	BishBosh.Property.Reflectable	as Property.Reflectable
import qualified	BishBosh.State.Board		as State.Board
import qualified	Control.DeepSeq
import qualified	Control.Exception
import qualified	Data.Foldable
import qualified	Data.Map.Strict

-- | The smallest number of repeatable plies required to form a cycle.
leastCyclicPlies :: Component.Move.NPlies
leastCyclicPlies :: NPlies
leastCyclicPlies	= NPlies
4

{- |
	* The number of times each /position/ has been encountered.

	* The /position/ can either be represented by a physical 'State.Position.Position', or by proxy using a hash.
-}
type NBoardsByPosition position	= Data.Map.Strict.Map position State.Board.NBoards

{- |
	* A count of the number of instances of /position/s which have occurred.

	* N.B.: a number greater than @1@ represents repetition.
-}
newtype InstancesByPosition position	= MkInstancesByPosition {
	InstancesByPosition position -> NBoardsByPosition position
getNBoardsByPosition	:: NBoardsByPosition position
} deriving InstancesByPosition position
-> InstancesByPosition position -> Bool
(InstancesByPosition position
 -> InstancesByPosition position -> Bool)
-> (InstancesByPosition position
    -> InstancesByPosition position -> Bool)
-> Eq (InstancesByPosition position)
forall position.
Eq position =>
InstancesByPosition position
-> InstancesByPosition position -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: InstancesByPosition position
-> InstancesByPosition position -> Bool
$c/= :: forall position.
Eq position =>
InstancesByPosition position
-> InstancesByPosition position -> Bool
== :: InstancesByPosition position
-> InstancesByPosition position -> Bool
$c== :: forall position.
Eq position =>
InstancesByPosition position
-> InstancesByPosition position -> Bool
Eq

instance Control.DeepSeq.NFData position => Control.DeepSeq.NFData (InstancesByPosition position) where
	rnf :: InstancesByPosition position -> ()
rnf MkInstancesByPosition { getNBoardsByPosition :: forall position.
InstancesByPosition position -> NBoardsByPosition position
getNBoardsByPosition = NBoardsByPosition position
m }	= NBoardsByPosition position -> ()
forall a. NFData a => a -> ()
Control.DeepSeq.rnf NBoardsByPosition position
m

instance (
	Ord					position,
	Property.Reflectable.ReflectableOnX	position
 ) => Property.Reflectable.ReflectableOnX (InstancesByPosition position) where
	reflectOnX :: InstancesByPosition position -> InstancesByPosition position
reflectOnX MkInstancesByPosition { getNBoardsByPosition :: forall position.
InstancesByPosition position -> NBoardsByPosition position
getNBoardsByPosition = NBoardsByPosition position
m }	= NBoardsByPosition position -> InstancesByPosition position
forall position.
NBoardsByPosition position -> InstancesByPosition position
MkInstancesByPosition (NBoardsByPosition position -> InstancesByPosition position)
-> NBoardsByPosition position -> InstancesByPosition position
forall a b. (a -> b) -> a -> b
$ (position -> position)
-> NBoardsByPosition position -> NBoardsByPosition position
forall k2 k1 a. Ord k2 => (k1 -> k2) -> Map k1 a -> Map k2 a
Data.Map.Strict.mapKeys position -> position
forall a. ReflectableOnX a => a -> a
Property.Reflectable.reflectOnX NBoardsByPosition position
m

-- | Smart constructor.
mkInstancesByPosition :: NBoardsByPosition position -> InstancesByPosition position
mkInstancesByPosition :: NBoardsByPosition position -> InstancesByPosition position
mkInstancesByPosition NBoardsByPosition position
nBoardsByPosition
	| (NPlies -> Bool) -> NBoardsByPosition position -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
Data.Foldable.any (NPlies -> NPlies -> Bool
forall a. Ord a => a -> a -> Bool
< NPlies
1) NBoardsByPosition position
nBoardsByPosition	= Exception -> InstancesByPosition position
forall a e. Exception e => e -> a
Control.Exception.throw (Exception -> InstancesByPosition position)
-> Exception -> InstancesByPosition position
forall a b. (a -> b) -> a -> b
$ String -> Exception
Data.Exception.mkOutOfBounds String
"BishBosh.State.InstancesByPosition.mkInstancesByPosition:\teach specified position must have been visited at least once."
	| Bool
otherwise					= NBoardsByPosition position -> InstancesByPosition position
forall position.
NBoardsByPosition position -> InstancesByPosition position
MkInstancesByPosition NBoardsByPosition position
nBoardsByPosition

-- | Constructor.
mkSingleton :: position -> InstancesByPosition position
mkSingleton :: position -> InstancesByPosition position
mkSingleton position
position	= NBoardsByPosition position -> InstancesByPosition position
forall position.
NBoardsByPosition position -> InstancesByPosition position
MkInstancesByPosition (NBoardsByPosition position -> InstancesByPosition position)
-> NBoardsByPosition position -> InstancesByPosition position
forall a b. (a -> b) -> a -> b
$ position -> NPlies -> NBoardsByPosition position
forall k a. k -> a -> Map k a
Data.Map.Strict.singleton position
position NPlies
1

{- |
	* Count the total number of consecutive repeatable plies amongst recent moves.

	* This is equivalent to the number of entries in the map, since adding a non-repeatable move triggers a purge.
-}
countConsecutiveRepeatablePlies :: InstancesByPosition position -> Component.Move.NPlies
countConsecutiveRepeatablePlies :: InstancesByPosition position -> NPlies
countConsecutiveRepeatablePlies MkInstancesByPosition { getNBoardsByPosition :: forall position.
InstancesByPosition position -> NBoardsByPosition position
getNBoardsByPosition = NBoardsByPosition position
m }	= (NPlies -> NPlies -> NPlies)
-> NPlies -> NBoardsByPosition position -> NPlies
forall a b k. (a -> b -> a) -> a -> Map k b -> a
Data.Map.Strict.foldl' NPlies -> NPlies -> NPlies
forall a. Num a => a -> a -> a
(+) (
	NPlies -> NPlies
forall a. Num a => a -> a
negate NPlies
1	-- The map is never empty, since before the first move a singleton is constructed with the initial position.
 ) NBoardsByPosition position
m

-- | Count the total number of repetitions of /position/s.
countPositionRepetitions :: InstancesByPosition position -> State.Board.NBoards
countPositionRepetitions :: InstancesByPosition position -> NPlies
countPositionRepetitions MkInstancesByPosition { getNBoardsByPosition :: forall position.
InstancesByPosition position -> NBoardsByPosition position
getNBoardsByPosition = NBoardsByPosition position
m }	= (NPlies -> NPlies -> NPlies)
-> NPlies -> NBoardsByPosition position -> NPlies
forall a b k. (a -> b -> a) -> a -> Map k b -> a
Data.Map.Strict.foldl' (
	NPlies -> NPlies -> NPlies
forall a. Num a => a -> a -> a
(+) (NPlies -> NPlies -> NPlies)
-> (NPlies -> NPlies) -> NPlies -> NPlies -> NPlies
forall b c a. (b -> c) -> (a -> b) -> a -> c
. NPlies -> NPlies
forall a. Enum a => a -> a
pred	-- The initial instance isn't a repetition.
 ) NPlies
0 NBoardsByPosition position
m

-- | The number of distinct /position/s.
getNDistinctPositions :: InstancesByPosition position -> State.Board.NBoards
getNDistinctPositions :: InstancesByPosition position -> NPlies
getNDistinctPositions MkInstancesByPosition { getNBoardsByPosition :: forall position.
InstancesByPosition position -> NBoardsByPosition position
getNBoardsByPosition = NBoardsByPosition position
m }	= NBoardsByPosition position -> NPlies
forall k a. Map k a -> NPlies
Data.Map.Strict.size NBoardsByPosition position
m

-- | Predicate: apply the specified predicate to the map.
anyInstancesByPosition
	:: (State.Board.NBoards -> Bool)
	-> InstancesByPosition position
	-> Bool
anyInstancesByPosition :: (NPlies -> Bool) -> InstancesByPosition position -> Bool
anyInstancesByPosition NPlies -> Bool
predicate MkInstancesByPosition { getNBoardsByPosition :: forall position.
InstancesByPosition position -> NBoardsByPosition position
getNBoardsByPosition = NBoardsByPosition position
m }	= (NPlies -> Bool) -> NBoardsByPosition position -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
Data.Foldable.any NPlies -> Bool
predicate NBoardsByPosition position
m

{- |
	* Find the maximum number of times any one position has already been visited.

	* CAVEAT: only those positions that can still be reached are considered.
-}
findMaximumInstances :: InstancesByPosition position -> State.Board.NBoards
findMaximumInstances :: InstancesByPosition position -> NPlies
findMaximumInstances MkInstancesByPosition { getNBoardsByPosition :: forall position.
InstancesByPosition position -> NBoardsByPosition position
getNBoardsByPosition = NBoardsByPosition position
m }
	| NBoardsByPosition position -> Bool
forall k a. Map k a -> Bool
Data.Map.Strict.null NBoardsByPosition position
m	= NPlies
0	-- CAVEAT: this shouldn't happen.
	| Bool
otherwise			= NBoardsByPosition position -> NPlies
forall (t :: * -> *) a. (Foldable t, Ord a) => t a -> a
Data.Foldable.maximum NBoardsByPosition position
m

-- | The type of a function which transforms the collection.
type Transformation position	= InstancesByPosition position -> InstancesByPosition position

-- | Insert a /position/ into the collection.
insertPosition
	:: Ord position
	=> Bool	-- ^ Whether the /turn/ which led to the specified /position/, was repeatable.
	-> position
	-> Transformation position
insertPosition :: Bool -> position -> Transformation position
insertPosition Bool
isRepeatable position
position MkInstancesByPosition { getNBoardsByPosition :: forall position.
InstancesByPosition position -> NBoardsByPosition position
getNBoardsByPosition = NBoardsByPosition position
m }
	| Bool
isRepeatable	= NBoardsByPosition position -> InstancesByPosition position
forall position.
NBoardsByPosition position -> InstancesByPosition position
MkInstancesByPosition (NBoardsByPosition position -> InstancesByPosition position)
-> NBoardsByPosition position -> InstancesByPosition position
forall a b. (a -> b) -> a -> b
$ (NPlies -> NPlies -> NPlies)
-> position
-> NPlies
-> NBoardsByPosition position
-> NBoardsByPosition position
forall k a. Ord k => (a -> a -> a) -> k -> a -> Map k a -> Map k a
Data.Map.Strict.insertWith ((NPlies -> NPlies) -> NPlies -> NPlies -> NPlies
forall a b. a -> b -> a
const NPlies -> NPlies
forall a. Enum a => a -> a
succ) position
position NPlies
1 NBoardsByPosition position
m	-- Include this position.
	| Bool
otherwise	= position -> InstancesByPosition position
forall position. position -> InstancesByPosition position
mkSingleton position
position								-- The previous position can't be revisited without rolling-back.

-- | Remove a /position/ from the collection, as required to implement rollback.
deletePosition :: Ord position => position -> Transformation position
deletePosition :: position -> Transformation position
deletePosition position
position MkInstancesByPosition { getNBoardsByPosition :: forall position.
InstancesByPosition position -> NBoardsByPosition position
getNBoardsByPosition = NBoardsByPosition position
m }	= NBoardsByPosition position -> InstancesByPosition position
forall position.
NBoardsByPosition position -> InstancesByPosition position
MkInstancesByPosition (NBoardsByPosition position -> InstancesByPosition position)
-> (NBoardsByPosition position -> NBoardsByPosition position)
-> NBoardsByPosition position
-> InstancesByPosition position
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (NPlies -> Maybe NPlies)
-> position
-> NBoardsByPosition position
-> NBoardsByPosition position
forall k a. Ord k => (a -> Maybe a) -> k -> Map k a -> Map k a
Data.Map.Strict.update (
	\NPlies
n -> if NPlies
n NPlies -> NPlies -> Bool
forall a. Eq a => a -> a -> Bool
== NPlies
1
		then Maybe NPlies
forall a. Maybe a
Nothing		-- Delete the entry.
		else NPlies -> Maybe NPlies
forall a. a -> Maybe a
Just (NPlies -> Maybe NPlies) -> NPlies -> Maybe NPlies
forall a b. (a -> b) -> a -> b
$ NPlies -> NPlies
forall a. Enum a => a -> a
pred NPlies
n	-- Decrement the number of instances.
 ) position
position (NBoardsByPosition position -> InstancesByPosition position)
-> NBoardsByPosition position -> InstancesByPosition position
forall a b. (a -> b) -> a -> b
$ Bool -> NBoardsByPosition position -> NBoardsByPosition position
forall a. (?callStack::CallStack) => Bool -> a -> a
Control.Exception.assert (position -> NBoardsByPosition position -> Bool
forall k a. Ord k => k -> Map k a -> Bool
Data.Map.Strict.member position
position NBoardsByPosition position
m) NBoardsByPosition position
m