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

import qualified	BishBosh.Property.Empty		as Property.Empty
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			as Map

-- | 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.
-}
type NPositionsByPosition position	= Map.Map position Type.Count.NPositions

-- | Insert a position into the unwrapped collection.
insertPosition' :: Ord position => position -> NPositionsByPosition position -> NPositionsByPosition position
insertPosition' :: position
-> NPositionsByPosition position -> NPositionsByPosition position
insertPosition'	= (position
 -> NPlies
 -> NPositionsByPosition position
 -> NPositionsByPosition position)
-> NPlies
-> position
-> NPositionsByPosition position
-> NPositionsByPosition position
forall a b c. (a -> b -> c) -> b -> a -> c
flip ((NPlies -> NPlies -> NPlies)
-> position
-> NPlies
-> NPositionsByPosition position
-> NPositionsByPosition position
forall k a. Ord k => (a -> a -> a) -> k -> a -> Map k a -> Map k a
Map.insertWith ((NPlies -> NPlies -> NPlies)
 -> position
 -> NPlies
 -> NPositionsByPosition position
 -> NPositionsByPosition position)
-> (NPlies -> NPlies -> NPlies)
-> position
-> NPlies
-> NPositionsByPosition position
-> NPositionsByPosition position
forall a b. (a -> b) -> a -> b
$ (NPlies -> NPlies) -> NPlies -> NPlies -> NPlies
forall a b. a -> b -> a
const NPlies -> NPlies
forall a. Enum a => a -> a
succ) NPlies
1

-- | Wrap the type, so that class-instances can be hung from it.
newtype InstancesByPosition position	= MkInstancesByPosition {
	InstancesByPosition position -> NPositionsByPosition position
getNPositionsByPosition	:: NPositionsByPosition 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 { getNPositionsByPosition :: forall position.
InstancesByPosition position -> NPositionsByPosition position
getNPositionsByPosition = NPositionsByPosition position
m }	= NPositionsByPosition position -> ()
forall a. NFData a => a -> ()
Control.DeepSeq.rnf NPositionsByPosition position
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 -> NPositionsByPosition position
getNPositionsByPosition = NPositionsByPosition position
m }	= NPositionsByPosition position -> InstancesByPosition position
forall position.
NPositionsByPosition position -> InstancesByPosition position
MkInstancesByPosition (NPositionsByPosition position -> InstancesByPosition position)
-> NPositionsByPosition position -> InstancesByPosition position
forall a b. (a -> b) -> a -> b
$ (position -> position)
-> NPositionsByPosition position -> NPositionsByPosition position
forall k2 k1 a. Ord k2 => (k1 -> k2) -> Map k1 a -> Map k2 a
Map.mapKeys position -> position
forall a. ReflectableOnX a => a -> a
Property.Reflectable.reflectOnX NPositionsByPosition position
m

-- | Construct from repeatable data.
mkInstancesByPosition
	:: (Foldable foldable, Ord position)
	=> (a -> position)	-- ^ Position-constructor.
	-> foldable a		-- ^ Data from which to construct positions.
	-> InstancesByPosition position
mkInstancesByPosition :: (a -> position) -> foldable a -> InstancesByPosition position
mkInstancesByPosition a -> position
f	= NPositionsByPosition position -> InstancesByPosition position
forall position.
NPositionsByPosition position -> InstancesByPosition position
MkInstancesByPosition (NPositionsByPosition position -> InstancesByPosition position)
-> (foldable a -> NPositionsByPosition position)
-> foldable a
-> InstancesByPosition position
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a
 -> NPositionsByPosition position -> NPositionsByPosition position)
-> NPositionsByPosition position
-> foldable a
-> NPositionsByPosition position
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
Data.Foldable.foldr (position
-> NPositionsByPosition position -> NPositionsByPosition position
forall position.
Ord position =>
position
-> NPositionsByPosition position -> NPositionsByPosition position
insertPosition' (position
 -> NPositionsByPosition position -> NPositionsByPosition position)
-> (a -> position)
-> a
-> NPositionsByPosition position
-> NPositionsByPosition position
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> position
f) NPositionsByPosition position
forall a. Empty a => a
Property.Empty.empty

-- | Constructor.
mkSingleton :: position -> InstancesByPosition position
mkSingleton :: position -> InstancesByPosition position
mkSingleton	= NPositionsByPosition position -> InstancesByPosition position
forall position.
NPositionsByPosition position -> InstancesByPosition position
MkInstancesByPosition (NPositionsByPosition position -> InstancesByPosition position)
-> (position -> NPositionsByPosition position)
-> position
-> InstancesByPosition position
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (position -> NPlies -> NPositionsByPosition position
forall k a. k -> a -> Map k a
`Map.singleton` 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 -> NPositionsByPosition position
getNPositionsByPosition = NPositionsByPosition position
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 -> NPositionsByPosition position -> NPlies
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
Data.Foldable.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.
 ) NPositionsByPosition position
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 -> NPositionsByPosition position
getNPositionsByPosition = NPositionsByPosition position
m }	= (NPlies -> NPlies -> NPlies)
-> NPlies -> NPositionsByPosition position -> NPlies
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
Data.Foldable.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 NPositionsByPosition position
m

-- | The number of distinct /position/s.
getNDistinctPositions :: InstancesByPosition position -> Type.Count.NPositions
getNDistinctPositions :: InstancesByPosition position -> NPlies
getNDistinctPositions MkInstancesByPosition { getNPositionsByPosition :: forall position.
InstancesByPosition position -> NPositionsByPosition position
getNPositionsByPosition = NPositionsByPosition position
m }	= NPlies -> NPlies
forall a b. (Integral a, Num b) => a -> b
fromIntegral (NPlies -> NPlies) -> NPlies -> NPlies
forall a b. (a -> b) -> a -> b
$ NPositionsByPosition position -> NPlies
forall (t :: * -> *) a. Foldable t => t a -> NPlies
Data.Foldable.length NPositionsByPosition position
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 -> NPositionsByPosition position
getNPositionsByPosition = NPositionsByPosition position
m }	= (NPlies -> Bool) -> NPositionsByPosition position -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
Data.Foldable.any NPlies -> Bool
predicate NPositionsByPosition 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 -> Type.Count.NPositions
findMaximumInstances :: InstancesByPosition position -> NPlies
findMaximumInstances MkInstancesByPosition { getNPositionsByPosition :: forall position.
InstancesByPosition position -> NPositionsByPosition position
getNPositionsByPosition = NPositionsByPosition position
m }
	| NPositionsByPosition position -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
Data.Foldable.null NPositionsByPosition position
m	= NPlies
0	-- CAVEAT: this shouldn't happen.
	| Bool
otherwise		= NPositionsByPosition position -> NPlies
forall (t :: * -> *) a. (Foldable t, Ord a) => t a -> a
Data.Foldable.maximum NPositionsByPosition 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 { getNPositionsByPosition :: forall position.
InstancesByPosition position -> NPositionsByPosition position
getNPositionsByPosition = NPositionsByPosition position
m }
	| Bool
isRepeatable	= NPositionsByPosition position -> InstancesByPosition position
forall position.
NPositionsByPosition position -> InstancesByPosition position
MkInstancesByPosition (NPositionsByPosition position -> InstancesByPosition position)
-> NPositionsByPosition position -> InstancesByPosition position
forall a b. (a -> b) -> a -> b
$ position
-> NPositionsByPosition position -> NPositionsByPosition position
forall position.
Ord position =>
position
-> NPositionsByPosition position -> NPositionsByPosition position
insertPosition' position
position NPositionsByPosition 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 { getNPositionsByPosition :: forall position.
InstancesByPosition position -> NPositionsByPosition position
getNPositionsByPosition = NPositionsByPosition position
m }	= NPositionsByPosition position -> InstancesByPosition position
forall position.
NPositionsByPosition position -> InstancesByPosition position
MkInstancesByPosition (NPositionsByPosition position -> InstancesByPosition position)
-> (NPositionsByPosition position -> NPositionsByPosition position)
-> NPositionsByPosition position
-> InstancesByPosition position
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (NPlies -> Maybe NPlies)
-> position
-> NPositionsByPosition position
-> NPositionsByPosition position
forall k a. Ord k => (a -> Maybe a) -> k -> Map k a -> Map k a
Map.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 (NPositionsByPosition position -> InstancesByPosition position)
-> NPositionsByPosition position -> InstancesByPosition position
forall a b. (a -> b) -> a -> b
$ Bool
-> NPositionsByPosition position -> NPositionsByPosition position
forall a. (?callStack::CallStack) => Bool -> a -> a
Control.Exception.assert (position -> NPositionsByPosition position -> Bool
forall k a. Ord k => k -> Map k a -> Bool
Map.member position
position NPositionsByPosition position
m) NPositionsByPosition position
m