{-
	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
--	Transformation.
-- * Constants
	leastCyclicPlies,
-- ** Data-types
	InstancesByPosition(),
-- * Functions
	countConsecutiveRepeatablePlies,
	countPositionRepetitions,
	getNDistinctPositions,
	findMaximumInstances,
-- ** Constructors
	mkInstancesByPosition,
	mkSingleton,
-- ** Mutators
	insertPosition,
	deletePosition,
-- ** Predicates
	anyInstancesByPosition
) where

import qualified	BishBosh.Data.Exception		as Data.Exception
import qualified	BishBosh.Property.Reflectable	as Property.Reflectable
import qualified	BishBosh.Type.Count		as Type.Count
import qualified	Control.DeepSeq
import qualified	Control.Exception
import qualified	Data.Foldable
import qualified	Data.Map.Strict

-- | The smallest number of repeatable plies (applied by alternating players) required to form a cycle.
leastCyclicPlies :: Type.Count.NPlies
leastCyclicPlies :: NPlies
leastCyclicPlies	= NPlies
4

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

	* N.B.: a number greater than @1@ represents repetition.

	* The /position/ can either be represented by a physical 'State.Position.Position', or by proxy using a hash.
-}
newtype InstancesByPosition position	= MkInstancesByPosition {
	InstancesByPosition position -> Map position NPlies
getNPositionsByPosition	:: Data.Map.Strict.Map position Type.Count.NPositions
} 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 { getNPositionsByPosition :: forall position.
InstancesByPosition position -> Map position NPlies
getNPositionsByPosition = Map position NPlies
m }	= Map position NPlies -> ()
forall a. NFData a => a -> ()
Control.DeepSeq.rnf Map position NPlies
m

instance (
	Ord					position,
	Property.Reflectable.ReflectableOnX	position
 ) => Property.Reflectable.ReflectableOnX (InstancesByPosition position) where
	reflectOnX :: InstancesByPosition position -> InstancesByPosition position
reflectOnX MkInstancesByPosition { getNPositionsByPosition :: forall position.
InstancesByPosition position -> Map position NPlies
getNPositionsByPosition = Map position NPlies
m }	= Map position NPlies -> InstancesByPosition position
forall position.
Map position NPlies -> InstancesByPosition position
MkInstancesByPosition (Map position NPlies -> InstancesByPosition position)
-> Map position NPlies -> InstancesByPosition position
forall a b. (a -> b) -> a -> b
$ (position -> position)
-> Map position NPlies -> Map position NPlies
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 Map position NPlies
m

-- | Smart constructor.
mkInstancesByPosition :: Data.Map.Strict.Map position Type.Count.NPositions -> InstancesByPosition position
mkInstancesByPosition :: Map position NPlies -> InstancesByPosition position
mkInstancesByPosition Map position NPlies
nPositionsByPosition
	| (NPlies -> Bool) -> Map position NPlies -> 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) Map position NPlies
nPositionsByPosition	= 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					= Map position NPlies -> InstancesByPosition position
forall position.
Map position NPlies -> InstancesByPosition position
MkInstancesByPosition Map position NPlies
nPositionsByPosition

-- | Constructor.
mkSingleton :: position -> InstancesByPosition position
mkSingleton :: position -> InstancesByPosition position
mkSingleton position
position	= Map position NPlies -> InstancesByPosition position
forall position.
Map position NPlies -> InstancesByPosition position
MkInstancesByPosition (Map position NPlies -> InstancesByPosition position)
-> Map position NPlies -> InstancesByPosition position
forall a b. (a -> b) -> a -> b
$ position -> NPlies -> Map position NPlies
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 -> Type.Count.NPlies
countConsecutiveRepeatablePlies :: InstancesByPosition position -> NPlies
countConsecutiveRepeatablePlies MkInstancesByPosition { getNPositionsByPosition :: forall position.
InstancesByPosition position -> Map position NPlies
getNPositionsByPosition = Map position NPlies
m }	= NPlies -> NPlies
forall a b. (Integral a, Num b) => a -> b
fromIntegral (NPlies -> NPlies) -> NPlies -> NPlies
forall a b. (a -> b) -> a -> b
$ (NPlies -> NPlies -> NPlies)
-> NPlies -> Map position NPlies -> 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.
 ) Map position NPlies
m

-- | Count the total number of repetitions of /position/s.
countPositionRepetitions :: InstancesByPosition position -> Type.Count.NPositions
countPositionRepetitions :: InstancesByPosition position -> NPlies
countPositionRepetitions MkInstancesByPosition { getNPositionsByPosition :: forall position.
InstancesByPosition position -> Map position NPlies
getNPositionsByPosition = Map position NPlies
m }	= (NPlies -> NPlies -> NPlies)
-> NPlies -> Map position NPlies -> 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 Map position NPlies
m

-- | The number of distinct /position/s.
getNDistinctPositions :: InstancesByPosition position -> Type.Count.NPositions
getNDistinctPositions :: InstancesByPosition position -> NPlies
getNDistinctPositions MkInstancesByPosition { getNPositionsByPosition :: forall position.
InstancesByPosition position -> Map position NPlies
getNPositionsByPosition = Map position NPlies
m }	= NPlies -> NPlies
forall a b. (Integral a, Num b) => a -> b
fromIntegral (NPlies -> NPlies) -> NPlies -> NPlies
forall a b. (a -> b) -> a -> b
$ Map position NPlies -> NPlies
forall k a. Map k a -> NPlies
Data.Map.Strict.size Map position NPlies
m {-the number of keys-}

-- | Predicate: apply the specified predicate to the map.
anyInstancesByPosition
	:: (Type.Count.NPositions -> Bool)
	-> InstancesByPosition position
	-> Bool
anyInstancesByPosition :: (NPlies -> Bool) -> InstancesByPosition position -> Bool
anyInstancesByPosition NPlies -> Bool
predicate MkInstancesByPosition { getNPositionsByPosition :: forall position.
InstancesByPosition position -> Map position NPlies
getNPositionsByPosition = Map position NPlies
m }	= (NPlies -> Bool) -> Map position NPlies -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
Data.Foldable.any NPlies -> Bool
predicate Map position NPlies
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 -> Type.Count.NPositions
findMaximumInstances :: InstancesByPosition position -> NPlies
findMaximumInstances MkInstancesByPosition { getNPositionsByPosition :: forall position.
InstancesByPosition position -> Map position NPlies
getNPositionsByPosition = Map position NPlies
m }
	| Map position NPlies -> Bool
forall k a. Map k a -> Bool
Data.Map.Strict.null Map position NPlies
m	= NPlies
0	-- CAVEAT: this shouldn't happen.
	| Bool
otherwise			= Map position NPlies -> NPlies
forall (t :: * -> *) a. (Foldable t, Ord a) => t a -> a
Data.Foldable.maximum Map position NPlies
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 { getNPositionsByPosition :: forall position.
InstancesByPosition position -> Map position NPlies
getNPositionsByPosition = Map position NPlies
m }
	| Bool
isRepeatable	= Map position NPlies -> InstancesByPosition position
forall position.
Map position NPlies -> InstancesByPosition position
MkInstancesByPosition (Map position NPlies -> InstancesByPosition position)
-> Map position NPlies -> InstancesByPosition position
forall a b. (a -> b) -> a -> b
$ (NPlies -> NPlies -> NPlies)
-> position -> NPlies -> Map position NPlies -> Map position NPlies
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 Map position NPlies
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 { getNPositionsByPosition :: forall position.
InstancesByPosition position -> Map position NPlies
getNPositionsByPosition = Map position NPlies
m }	= Map position NPlies -> InstancesByPosition position
forall position.
Map position NPlies -> InstancesByPosition position
MkInstancesByPosition (Map position NPlies -> InstancesByPosition position)
-> (Map position NPlies -> Map position NPlies)
-> Map position NPlies
-> InstancesByPosition position
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (NPlies -> Maybe NPlies)
-> position -> Map position NPlies -> Map position NPlies
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 (Map position NPlies -> InstancesByPosition position)
-> Map position NPlies -> InstancesByPosition position
forall a b. (a -> b) -> a -> b
$ Bool -> Map position NPlies -> Map position NPlies
forall a. (?callStack::CallStack) => Bool -> a -> a
Control.Exception.assert (position -> Map position NPlies -> Bool
forall k a. Ord k => k -> Map k a -> Bool
Data.Map.Strict.member position
position Map position NPlies
m) Map position NPlies
m