--[[----------------------------------------------------------------------------

WFFiniteStateMachineUtils.lua

--------------------------------------------------------------------------------

ADOBE CONFIDENTIAL
------------------
Copyright 2015 Adobe Systems Incorporated
All Rights Reserved.

NOTICE: All information contained herein is, and remain the property of
Adobe Systems Incorporated and its suppliers, if any. The intellectual and
technical concepts contained herein are proprietary to Adobe Systems
Incorporated and its suppliers and may be covered by U.S. and Foreign
Patents, patents in process, and are protected by trade secret or copyright
law.  Dissemination of this information or reproduction of this material is
strictly forbidden unless prior written permission is obtained from
Adobe Systems Incorporated.

------------------------------------------------------------------------------]]
--
local KSTableUtils = require "KSTableUtils"
local WFArguments = require 'WFArguments'
local WFArguments_check = assert( WFArguments.check, 
										"missing WFArguments.check" )

local WFFunctionUtils = require "WFFunctionUtils"

local WFFiniteStateMachine = require "WFFiniteStateMachine"

--------------------------------------------------------------------------------

local function addValidState( validStates, stateName, allValidStates, errMsg )

	if not allValidStates[ stateName ] then

		error( string.format( "%s: %s", errMsg, stateName ) )

	end

	validStates[ stateName ] = stateName

	return validStates

end

--------------------------------------------------------------------------------

local function wrapInReturnEmptyStrForEmptyArray( f )

	return function( array, ... )

		return #array == 0 and "" or f( array, ... )

	end

end

--------------------------------------------------------------------------------

local function makeColoredRankedNode( stateName, stateColorMap )

	return string.format( [[ 
					node[ peripheries=2  shape = circle style="filled" color=black fillcolor="%s"];
					"%s";]], stateColorMap[ stateName ], 
					stateName )

end

--------------------------------------------------------------------------------

local function makeRankedNodes( stateNames, rankStr, stateColorMap )

	local coloredNodes = WFFunctionUtils.map( makeColoredRankedNode, 
												stateNames, stateColorMap )

	return string.format( [[ 
				{ rank = %s; 
					%s }; ]], rankStr, table.concat( coloredNodes, '\n' ) )

end

--------------------------------------------------------------------------------

makeRankedNodes = wrapInReturnEmptyStrForEmptyArray( makeRankedNodes )

--------------------------------------------------------------------------------

local function makeStartStatesNodesStr( startStates, stateColorMap )

	return makeRankedNodes( startStates, "min", stateColorMap )

end

--------------------------------------------------------------------------------

local function makeEndStatesNodesStr( endStates, stateColorMap )

	return makeRankedNodes( endStates, "max", stateColorMap )

end

--------------------------------------------------------------------------------

local function interpolate( x, y, i, n )

	return x +  ( i - 1 ) * ( y - x ) / ( n - 1 )

end

--------------------------------------------------------------------------------

local function rampUpAndDown( x, y, i, n )

	local mid = math.floor( n / 2 )

	if i <= mid then

		return interpolate( x, y, i, mid )

	end

	return interpolate( y, x, i - mid + 1, n - mid )

end

--------------------------------------------------------------------------------

local function rampUpAndDown2( x, y, i, n )

	local mid = math.floor( n / 2 )

	if i <= mid then

		return rampUpAndDown( x, y, i, mid )

	end

	return rampUpAndDown( y, x, i - mid + 1, n - mid )

end

--------------------------------------------------------------------------------

local function getStateGroupColors( stateGroupNames )

	local startR, startG, startB = 255, 255, 192

	local endR, endG, endB = 192, 192, 255

	local stateGroupColors = {}

	for i, stateGroupName in ipairs( stateGroupNames ) do

		stateGroupColors[ stateGroupName ] = 
			string.format( "#%02x%02x%02x",
							interpolate( startR, endR, i, #stateGroupNames ),
							rampUpAndDown2( startG, endG, i, #stateGroupNames ),
							interpolate( startB, endB, i, #stateGroupNames ) )

	end

	return stateGroupColors

end

--------------------------------------------------------------------------------

local function makeStateGroupNode( stateGroupName, stateGroupColors )

	return string.format( 'node[ style=filled color="%s"];\n\t"%s"',
						stateGroupColors[ stateGroupName ], stateGroupName )

end

--------------------------------------------------------------------------------

local function makeStateGroupColorKey( stateGroupNames )

	return string.format( [[
				subgraph clusterColorKey { 
					"%s";
					label = "state groups";
				};]], table.concat( stateGroupNames, '"; "' ) )

end

--------------------------------------------------------------------------------

local function getNextStateUnlessSeen( transition, fsm, stateName, seenStates )

	local nextStateName = WFFiniteStateMachine.getNextState( fsm, stateName,
																transition )

	if not seenStates[ nextStateName ] then

		return nextStateName

	end
	
end

--------------------------------------------------------------------------------

local function getReachableStates( fsm, startState, endStatesMap,
										reachableStates )

	reachableStates = reachableStates or {}

	local transitions = 
			WFFiniteStateMachine.getStateTransitions( fsm, startState )

	local nextStates = WFFunctionUtils.filter( 
						getNextStateUnlessSeen, 
							transitions, fsm, startState, reachableStates )

	reachableStates[ startState ] = startState

	for _, nextState in ipairs( nextStates ) do

		if not endStatesMap[ nextState ] then

			reachableStates = getReachableStates( fsm, nextState, endStatesMap,
													reachableStates )

		else

			reachableStates[ nextState ] = true

		end

	end

	return reachableStates

end

--------------------------------------------------------------------------------

makeStateGroupColorKey = 
	wrapInReturnEmptyStrForEmptyArray( makeStateGroupColorKey )

--------------------------------------------------------------------------------

local function isMiddleState( stateName, middleStateMap )

	return middleStateMap[ stateName ] and stateName or nil

end

--------------------------------------------------------------------------------

local function getStateGroupMiddleStates( fsm, stateGroupName, middleStateMap )

	local stateGroupStates =
				WFFiniteStateMachine.getStateGroupStates( fsm, stateGroupName )

	return WFFunctionUtils.filter( isMiddleState, stateGroupStates,
										middleStateMap )

end

--------------------------------------------------------------------------------

local function makeStateGroupStateNodesStr( stateGroupColor, 
												stateGroupMiddleStates )

	return string.format( 
				[[node[ style=filled color="%s"];"%s";]],
				stateGroupColor,
				table.concat( stateGroupMiddleStates, '"; "' ) )

end

--------------------------------------------------------------------------------

makeStateGroupStateNodesStr = 
	wrapInReturnEmptyStrForEmptyArray( makeStateGroupStateNodesStr )

--------------------------------------------------------------------------------

local function makeStateGroupStateNodes( stateGroupName, fsm, stateGroupColors,
											middleStateMap )

	local stateGroupMiddleStates =
			getStateGroupMiddleStates( fsm, stateGroupName, middleStateMap )
	
	return #stateGroupMiddleStates > 0 and 
				makeStateGroupStateNodesStr( 
					stateGroupColors[ stateGroupName ],
					stateGroupMiddleStates ) or
				nil

end

--------------------------------------------------------------------------------

local function addStateName( map, stateName )

	map[ stateName ] = stateName

	return map

end

--------------------------------------------------------------------------------

local function addStateGroupStates( statesInStateGroupMap, stateGroupName, fsm )

	return WFFunctionUtils.reduce( 
			statesInStateGroupMap,
			addStateName,
			WFFiniteStateMachine.getStateGroupStates( fsm, stateGroupName ) )

end

--------------------------------------------------------------------------------

local function isStateUndeclared( stateName, statesInStateGroupMap, 
												middleStateMap )

	return not statesInStateGroupMap[ stateName ] and 
			not middleStateMap[ stateName ] and 
				stateName or nil

end

--------------------------------------------------------------------------------

local function stringifyAndConcat( strs )

	return string.format( [["%s";]], table.concat( strs, '"; "' ) )

end

--------------------------------------------------------------------------------

stringifyAndConcat = wrapInReturnEmptyStrForEmptyArray( stringifyAndConcat )

--------------------------------------------------------------------------------

local makeUndeclaredStatesStr = stringifyAndConcat

--------------------------------------------------------------------------------

local function addEdgeForStateTransition( edges, transition, stateName, fsm, 
											omitNextStateMap )

	local nextStateName = WFFiniteStateMachine.getNextState( fsm, stateName,
																transition )

	if stateName == nextStateName or omitNextStateMap[ nextStateName ] then

		return edges

	end

	edges[ #edges + 1 ] = string.format( '"%s" -> "%s"[label = "%s"]', 
											stateName, nextStateName,
											transition )

	return edges

end

--------------------------------------------------------------------------------

local function addEdgesForState( edges, stateName, fsm, omitNextStateMap )

	local stateTransitions = 
			WFFiniteStateMachine.getStateTransitions( fsm, stateName )

	return WFFunctionUtils.reduce( edges,
				addEdgeForStateTransition,
					stateTransitions, stateName, fsm, omitNextStateMap )

end

--------------------------------------------------------------------------------

local function getEdgesStr( fsm, startStatesMap, middleStateMap, 
								reachableEndStatesMap, endStatesMap )

	local edges = {}

	for _, stateMap in pairs( { startStatesMap, middleStateMap, 
									reachableEndStatesMap } ) do

		for stateName in pairs( stateMap ) do

			local omitNextStateMap = 
					stateMap == reachableEndStatesMap and endStatesMap or {}	

			edges = addEdgesForState( edges, stateName, fsm, omitNextStateMap )

		end

	end

	table.sort( edges )

	return #edges == 0 and "" or table.concat( edges, ";\n\t\t" )

end

--------------------------------------------------------------------------------

local function addMiddleStates( middleStateMap, startState, fsm, endStatesMap )

	-- make a map of all reachable states that aren't start or end states
	middleStateMap = 
		getReachableStates( fsm, startState, endStatesMap, middleStateMap )

	middleStateMap[ startState ] = nil

	return middleStateMap

end

--------------------------------------------------------------------------------

local function addStateGroupStateToColorMap( stateColorMap, stateName, color )

	stateColorMap[ stateName ] = color

	return stateColorMap

end

--------------------------------------------------------------------------------

local function addStateGroupStatesToColorMap( stateColorMap, stateGroupName, 
												fsm, stateGroupColors )

	return WFFunctionUtils.reduce( stateColorMap, 
			addStateGroupStateToColorMap, 
				WFFiniteStateMachine.getStateGroupStates( 
					fsm, stateGroupName ), 
				stateGroupColors[ stateGroupName ] )

end

--------------------------------------------------------------------------------

local function getAsDotDiagramStrImp( fsm, wantKey, title, size, startStates,
										endStates )

	local stateMap = WFFiniteStateMachine.getStateMap( fsm )

	-- group states by state groups assigining a unique color to each state
	-- group.
	local stateGroupNames = WFFiniteStateMachine.getStateGroupNames( fsm )

	local stateGroupColors = getStateGroupColors( stateGroupNames )

	local stateColorMap = WFFunctionUtils.reduce( {}, 
							addStateGroupStatesToColorMap, 
								stateGroupNames, fsm, stateGroupColors )

	local startStatesNodesStr = makeStartStatesNodesStr( 
									startStates, stateColorMap )

	local endStatesMap = WFFunctionUtils.reduce( {}, 
								addValidState, 
									endStates, stateMap, 
									"endState not valid" )

	local stateGroupNodes = WFFunctionUtils.map( makeStateGroupNode,
													stateGroupNames,
													stateGroupColors )

	local stateGroupNodesStr = table.concat( stateGroupNodes, "\n" )

	-- create a "key" section of the diagram which explain which colors
	-- correspond to which state group
	local stateGroupColorKey = makeStateGroupColorKey( stateGroupNames )

	local middleStateMap = WFFunctionUtils.reduce( {}, 
								addMiddleStates, 
									startStates, fsm, endStatesMap )

	local startStatesMap = KSTableUtils.mapArrayToSet( startStates )

	local reachableEndStatesMap = {}

	local reachableEndStates = {}

	for endState in pairs( endStatesMap ) do

		if middleStateMap[ endState ] then

			middleStateMap[ endState ] = nil

			reachableEndStatesMap[ endState ] = endState

			reachableEndStates[ #reachableEndStates + 1 ] = endState

		end

	end

	table.sort( reachableEndStates )

	local endStateNodesStr = makeEndStatesNodesStr( 
								reachableEndStates, stateColorMap )

	-- write out all of the states for each state group except if the state
	-- group consists solely of start and end states.
	local stateGroupStateNodes = WFFunctionUtils.filter( 
										makeStateGroupStateNodes, 
											stateGroupNames, 
												fsm, stateGroupColors,
												middleStateMap )

	table.sort( stateGroupStateNodes )

	local stateGroupStateNodesStr = table.concat( stateGroupStateNodes, "\n" )

	-- get a map of all states that are in a state group 
	local statesInStateGroupMap = WFFunctionUtils.reduce( {},
										addStateGroupStates,
											stateGroupNames,
												fsm )

	local undeclaredStates = WFFunctionUtils.filter(
						isStateUndeclared,
						WFFiniteStateMachine.getStates( fsm ),
						statesInStateGroupMap, middleStateMap )

	table.sort( undeclaredStates )

	local undeclaredStatesStr = makeUndeclaredStatesStr( undeclaredStates )

	local edgesStr = getEdgesStr( fsm, startStatesMap, middleStateMap,
									reachableEndStatesMap, endStatesMap )

	return string.format( [[
		digraph finite_state_machine {

			dpi=144;
			label = "%s"; /* (title) */
			size="%s"; /* (size) */
			fontname="Helvetica";
			fontsize=24;
	
			labelloc=t;

			node[fontname="Helvetica"; fontsize=16; sep="+24,24";];

			node [shape = square;];

			/* define state groups (stateGroupNodesStr) */
			%s

			/* define state group color key (stateGroupColorKey) */
			%s

			/* starting nodes (startStatesNodesStr) */
			%s

			/* state group state nodes (stateGroupStateNodesStr) */
			%s

			/* ending nodes (endStateNodesStr) */
			%s
			
			/* other states (undeclaredStatesStr) */
			%s

			/* edges (edgesStr) */
			edge[fontsize = 9.0; fontname="Helvetica";];

			%s;
		}]], 
		title,
		size,
		wantKey and stateGroupNodesStr .. ";" or "",
		wantKey and stateGroupColorKey or "",
		startStatesNodesStr,
		stateGroupStateNodesStr,
		endStateNodesStr,
		undeclaredStatesStr,
		edgesStr )

end

--------------------------------------------------------------------------------
--[[!
-- \brief Serializes a FSM to a string that is in the dot language format.
			See http://graphviz.org for more info.  You can generate a diagram
			from a dot language file, by running it through the dot command
			line program.

			To install that on the mac, use homebrew or Macports

			% # homebrew instructions

			% brew install graphviz

			Once installed, use 

			% dot -Tpng 20150513previewServerThreadGraph.dot > prettyGraph.png

			to generate a png file for the graph

	\param (WFFiniteStateMachine object) An exising FSM object

	\param (string) a title for the graph emitted

	\param (number) a size for the graph emitted

	\param (array) An array of state name strings that are start states. The
					resultant diagram will have these at the top.

	\param (array) An array of state name strings that are end states. The
	resultant diagram will have these at the bottom.
	
	\return (string) A string representing the FSM in dot language format. Save
				it to a file and use the dot program to generate a png.
*/
--]]
local function getAsDotDiagramStr( fsm, title, size, startStates, endStates )

	WFArguments_check( "WFFiniteStateMachine", "string", "number", "table", "table" )

	return getAsDotDiagramStrImp( fsm, false, title, size, startStates,
										endStates )

end

--------------------------------------------------------------------------------

local function getAsDotDiagramStrWithKey( fsm, title, size, startStates, 
											endStates )

	WFArguments_check( "WFFiniteStateMachine", "string", "number", "table", "table" )

	return getAsDotDiagramStrImp( fsm, true, title, size, startStates,
										endStates )

end

--==============================================================================

return {

	getAsDotDiagramStr = getAsDotDiagramStr,

	getAsDotDiagramStrWithKey = getAsDotDiagramStrWithKey,

}
