/*	Author: Magdin Stoica
	Supervisor: Dr. Ryan Leduc
	
	Project created in conformity with the requirements for the Degree of Master of Engineering in Software Engineering, 
	Computing and Software Department, 
	McMaster University
	2003 - 2007
*/
#include "CommonDefinitions.h"
#include "DesTransitionFunction.h"
#include "DesEventPool.h"
#include "DesStatePool.h"
#include "DesTransitionIterator.h"
#include "TransitionMapIterator.h"
#include "DesTransitionIterator.h"
#include "DesSelfTransIterator.h"
#include "DesStateTransMapIterator.h"
#include "DesStateTransIterator.h"

namespace DESpot
{

DesTransitionFunction::DesTransitionFunction(StatePool& statePool, EventPool& eventPool, 
											 bool bAllowNonDeterminism /*= false*/): 
			m_transCount(0), m_statePool(statePool), m_eventPool(eventPool), 
			m_nonDetAllowed(bAllowNonDeterminism)
{
	
}

//_________________________________________________________________________________________________

DesTransitionFunction::~DesTransitionFunction(void)
{
}


//_________________________________________________________________________________________________

//Iterates through all the transitions in this function
DesTransitionIterator* DesTransitionFunction::createIterator() const
{
	DesSelfTransIterator* pSelfTransIt = createSelfTransIterator();	
	DesStateIterator* pStateIt = m_statePool.createIterator();
	return new DesTransitionIterator(m_transMap, *pSelfTransIt, *pStateIt);
}

//_________________________________________________________________________________________________

//Iterates through all the inverse transitions in this function
DesTransitionIterator* DesTransitionFunction::createInvIterator() const
{
	DesSelfTransIterator* pSelfTransIt = createSelfTransIterator();	
	DesStateIterator* pStateIt = m_statePool.createIterator();
	return new DesTransitionIterator(m_invTransMap, *pSelfTransIt, *pStateIt);
}

//_________________________________________________________________________________________________

//Iterates only through the transitions in the transition map, ignoring global self-transitions
TransitionMapIterator* DesTransitionFunction::createTransMapIterator() const
{
	return new TransitionMapIterator(m_transMap);	
}

//_________________________________________________________________________________________________

TransitionMapIterator* DesTransitionFunction::createTransMapInvIterator() const
{
	return new TransitionMapIterator(m_invTransMap);
}

//_________________________________________________________________________________________________

DesStateTransMapIterator* DesTransitionFunction::createStateTransMapIterator(const DesState& state) const
{
	return new DesStateTransMapIterator(state, m_transMap);
}

//_________________________________________________________________________________________________

DesStateTransMapIterator* DesTransitionFunction::createStateTransMapInvIterator(const DesState& state) const
{
	return new DesStateTransMapIterator(state, m_invTransMap);
}

//_________________________________________________________________________________________________

DesStateTransIterator* DesTransitionFunction::createStateTransIterator(const DesState& state) const
{
	DesSelfTransIterator* pSelfTransIterator = createSelfTransIterator();		
	return new DesStateTransIterator(state, m_transMap, *pSelfTransIterator);
}

//_________________________________________________________________________________________________

DesStateTransIterator* DesTransitionFunction::createStateTransInvIterator(const DesState& state) const
{
	DesSelfTransIterator* pSelfTransIterator = createSelfTransIterator();		
	return new DesStateTransIterator(state, m_invTransMap, *pSelfTransIterator);
}

//_________________________________________________________________________________________________

DesSelfTransIterator* DesTransitionFunction::createSelfTransIterator() const
{
	return new DesSelfTransIterator(m_globalSelfLoopEventMap);
}

//_________________________________________________________________________________________________

//Return the number of transitions
DesTransition::Count DesTransitionFunction::getTransCount(bool includeSelfTrans /*= true*/) const
{
	DesTransition::Count transCount = m_transCount;

	if (includeSelfTrans)						   
	{
		transCount += (getSelfTransCount() *  m_statePool.getStateCount());	
	}

	return transCount;
}

//_________________________________________________________________________________________________

DesTransition::Count DesTransitionFunction::getSelfTransCount() const
{
	//the number of self-looped events times the number of states
	return m_globalSelfLoopEventMap.size();
}

//_________________________________________________________________________________________________

void DesTransitionFunction::addTransition(const DesTransition& trans)
{
	//First make sure there is no global self-transition with the same event label as the
	//transition being added
	if (isEventSelfLooped(trans.event()))
	{
		throw EX("A global self-loop exist for this event. The local self-loop being added is redundant or non-deterministic.")
	}
	
	//add transition to the regular transition map
	addTransToMap(trans, m_transMap, m_nonDetAllowed);

	//add the inverse transition to the inverse transition map. Note that the inverse transition
	//function is always non-deterministic
	DesTransition invTrans;
	addTransToMap(trans.inverse(invTrans), m_invTransMap, true);

	//A transition with the event label of "trans" has been added so mark the event as used
	markEventUsed(trans.event());

	//update the transition counter
	m_transCount++;
}

//_________________________________________________________________________________________________
//Adds a global self-loop transition to the transition function. If any self-loops are found having the
//the same event label they are removed / replaced by the global one. The local-self loop transitions
//are returned to the caller in the pLocalLoops array if requested. Note that DesTransition objects are
//created for the local self-loops and the caller is responsible for deleting them
void DesTransitionFunction::addGlobalSelfTransition(const DesEvent& selfLoopEvent, 
													std::vector<DesTransition*>* o_pLocalLoops /*= null*/)
{
	//Make sure there is no conflicting transition that would cause a non-determinism or duplication
	if (selfLoopEvent.isUsed())
	{
		//Make sure there is no other self-loop transition with the same event
		if (isEventSelfLooped(selfLoopEvent))
		{
			throw EX("A self-loop transition with the same event label already exists. Cannot add duplicate transitions")
		}
		
		//the global self-loop might conflict with the transition map if a non-loop transition with the same event
		//exists - so both the transition map and the inverse transitin map must be checked. If any local loops are
		//found they will be removed since they are replaced by the global one. The local loops are returned to the
		//caller if requested but ONLY from the regular transition map (callers don't care about the inverse transition map)
		DesTransition::Count localLoopCount = checkAndCleanTransMap(m_transMap, selfLoopEvent, o_pLocalLoops);

		//update the transition counter to subtract the removed local loops
		m_transCount -= localLoopCount;

		//clean the inverse map too
		checkAndCleanTransMap(m_invTransMap, selfLoopEvent);
	}	

	//add the self transition to the transition map and mark the event as used
	m_globalSelfLoopEventMap[selfLoopEvent.getId()] = &selfLoopEvent;
	markEventUsed(selfLoopEvent);
}

//_________________________________________________________________________________________________

void DesTransitionFunction::deleteTransition(const DesTransition& trans)
{
	//Delete the transition from the regular map
	deleteTransFromMap(trans, m_transMap);

	//Delete the transition from inverse transition map
	DesTransition invTrans;
	deleteTransFromMap(trans.inverse(invTrans), m_invTransMap);

	//A transition with the event label of "transToDelete" was removed so the event may have become unused
	//Check to make sure and if no other transition uses this event mark it as unused
	if (notUsed(trans.event()))
	{
		markEventUsed(trans.event(), false);
	}

	//update the transition counter
	m_transCount--;
}

//_________________________________________________________________________________________________

void DesTransitionFunction::deleteGlobalSelfTransition(const DesEvent& selfLoopEvent)
{
	SelfLoopEventIt eventIt = m_globalSelfLoopEventMap.find(selfLoopEvent.getId());
	if (isEventSelfLooped(selfLoopEvent, &eventIt) == false)
	{
		throw EX("Global self-loop not found for this event. Cannot delete global self-loop")
	}
	else
	{
		m_globalSelfLoopEventMap.erase(eventIt);
	}

	//A transition with the event label of "selfLoopEvent" was removed so the event should have become unused
	//as we don't allow local self-loops or non-deterministic transitions. Check to make sure no other transition 
	//uses this event mark it as unused
	if (notUsed(selfLoopEvent) == false)
	{
		assert(false);
		throw EX("Unsupported state. Local transitions and global self-loops coexisted")
	}

	//mark the event as not being used
	markEventUsed(selfLoopEvent, false);
}

//_________________________________________________________________________________________________

void DesTransitionFunction::changeTransition(const DesTransition& trans, const DesTransition& change)
{
	//Change the transition in the regular map
	changeTransInMap(trans, change, m_transMap, m_nonDetAllowed);

	//Change the transition in the inverse transition map
	DesTransition invTrans;
	DesTransition invChange;
	changeTransInMap(trans.inverse(invTrans), change.inverse(invChange), m_invTransMap, true);

	//If the event label has changed the old event might not be used anymore so mark it as such
	if (transEvent(trans) != transEvent(change))
	{
		const DesEvent& originalEvent = trans.event();
		if (notUsed(originalEvent))
		{
			markEventUsed(originalEvent, false);
		}
	}

	//The event label of the changed transition is now in use
	markEventUsed(change.event());	
}

//_________________________________________________________________________________________________

//deletes all the transitions direct and reverse, reverting the transition function back to initial state after construction
void DesTransitionFunction::clear()
{
}

//_________________________________________________________________________________________________

DesTransitionFunction::FindRes DesTransitionFunction::findTransition(const DesTransition& trans)
{
	//This will hold the result until the function is ready to return it
	FindRes findResult = eTransNotFound;

	//Look for "trans" in the transition map see if you can find it or anything similar
	TransMapIt transIt = m_transMap.find(transFromState(trans));
	if (transIt == m_transMap.end())
	{
		//there are no events leaving from the transition's "from state" so the transition cannot be there
		findResult = eTransNotFound;
	}
	else
	{
		//a transition list already exists for this "from state"
		EventMap& eventMap = *transIt->second;

		EventMapIt eventIt = eventMap.find(transEvent(trans));
		if (eventIt == eventMap.end())
		{
			//no transition was found to have the event required by the caller
			findResult = eTransNotFound;
		}
		else
		{
			//if we got here a transition was found. Must check that toState corresponds to what the caller's looking for
			StateMap& stateMap = *(eventIt->second);
			if (stateMap.find(trans.toState().getId()) != stateMap.end())
			{
				findResult = eExactTransFound;
			}
			else
			{
				//The transition found to have the same "from state" and "event" has a different "to state"
				findResult = eOtherTransFound;
			}
		}
	}

	//if the transition was not found in the transition map look in the list of global self-transitions
	if (findResult == eTransNotFound)
	{
		
		if (isEventSelfLooped(trans.event()) == false)
		{
			//there was no global self-transition related to this one so no transition was found
			//ready to return
			findResult = eTransNotFound;
		}
		else
		{
			//a global self-transition was found having the same event label as the given one
			//note that we don't allow local self-loops when a global one is available
			findResult = eOtherSelfTransFound;
		}
	}

	//something was found in the transition map so return the result found there
	return findResult;
}

//_________________________________________________________________________________________________

DesTransitionFunction::FindRes DesTransitionFunction::findGlobalSelfTransition(const DesEvent& selfLoopEvent)
{
	if (isEventSelfLooped(selfLoopEvent))
	{
		//an exact global self-loop transition was found
		return eExactTransFound;
	}
	else
	{
		//a global self-loop was not found. try looking for any transition with this event label
		//to tell the caller if a local-loop is found or a conflicting transition is found
		//NOTE: there is no need to do this search in the inverse transition map as well as they are kept in sync
		for(TransMapIt transIt = m_transMap.begin(); transIt != m_transMap.end(); transIt++)
		{
			EventMap* pEventMap = transIt->second;
			EventMapIt eventIt = pEventMap->find(&selfLoopEvent);			
			if (eventIt != pEventMap->end())
			{
				//Event was found in this map. Check to see if it is just a self-loop or a completely 
				//different transition. If there is only on destination state and is the same as the start state
				//it is a local loop, otherwise a different transition exists
				StateMap& stateMap = *(eventIt->second);
				if ((stateMap.size() == 1) && (transIt->first == stateMap.begin()->second))
				{
					//the source state and the destination state are the same
					return eLocalSelfLoopFound;
				}
				else
				{
					//If the destination state is different than the source 
					//state it means the Des would become non-deterministic 
					return eOtherTransFound;
				}
			}
		}

		//a local self-loop with this event was not found either
		return eTransNotFound;
	}
}

//_________________________________________________________________________________________________

//Checks if a transition with the label "event" leaves "fromState". If there is it returns true
//and returns the destination state in the out parameter o_toState
bool DesTransitionFunction::transExists(const DesState* fromState, const DesEvent* event, const DesState*& o_toState)
{
	if (isEventSelfLooped(*event))
	{
		//thet event is self-looped so toState == fromState
		o_toState = fromState;
		return true;
	}
	else
	{
		TransMapIt transIt = m_transMap.find(fromState);
		if (transIt != m_transMap.end())
		{
			//a transition list already exists for this "from state"
			EventMap& eventMap = *transIt->second;
			
			EventMapIt eventIt = eventMap.find(event);
			if (eventIt != eventMap.end())
			{
				//found a transition
				StateMap& stateMap = *(eventIt->second);
				o_toState = stateMap.begin()->second;
				return true;
			}
		}

		//if we got here it means there is not transition leaving "fromState" with the event label "event"
		return false;
	}
}

//_________________________________________________________________________________________________

//checks if the transition function is non deterministic
bool DesTransitionFunction::isNonDeterministic() const
{
	for(TransMapCIt transIt = m_transMap.begin(); transIt != m_transMap.end(); transIt++)
	{
		EventMap& eventMap = *transIt->second;

		for(EventMapIt eventIt = eventMap.begin(); eventIt != eventMap.end(); eventIt++)
		{
			StateMap& stateMap = *eventIt->second;

			if (stateMap.size() > 1)
			{
				//an event has more than one destination
				return true;
			}
		}
	}

	return false;
}

//_________________________________________________________________________________________________

//Internal function that attempts to find  the event map for the source state of "trans" - the event
//map where the given transition would have to be placed. Returns true if the event map is found. The
//actual event map is returned in the out parameter - eventMap
bool DesTransitionFunction::findEventMapForTrans(TransitionMap& transMap, const DesTransition& trans, EventMap*& o_eventMap)
{
	TransMapIt transIt = transMap.find(transFromState(trans));
	if (transIt == transMap.end())
	{
		return false;
	}
	else
	{
		//return the event map that was found 
		o_eventMap = transIt->second;
		return true;
	}
}

//_________________________________________________________________________________________________

//Internal function that attempts to find the state map for the toState of "trans". It assumes the 
//event map has already been found but we do not know if the event label of "trans" is in it. If 
//it is then we want the list of states associated with that event - the state map
bool DesTransitionFunction::findStateMapForTrans(EventMap& eventMap, const DesTransition& trans, StateMap*& o_stateMap)
{
	EventMapIt eventIt = eventMap.find(transEvent(trans));
	if (eventIt == eventMap.end())
	{
		return false;
	}
	else
	{
		//The event is already there return the state map
		o_stateMap = eventIt->second;
		return true;
	}
}

//_________________________________________________________________________________________________

void DesTransitionFunction::addTransToMap(const DesTransition& trans, TransitionMap& transMap, bool allowNonDet)
{
	EventMap* eventMap = null;
	if (findEventMapForTrans(transMap, trans, eventMap) == false)
	{
		//this is the first transition for this "from state"
		startNewTrans(transMap, trans);
	}
	else
	{	//an event map already exists for this "from state"
				
		//verify that there is no transition having the same ID going to a different state
		//this would create a non-deterministic DES
		StateMap*   toStateMap;
		if (findStateMapForTrans(*eventMap, trans, toStateMap) == false)
		{
			//there is no transition with this event leaving from the fromState of this transition
			//so one can be safely added. Create the state map and put the toState of the transition in it
			startNewStateMap(*eventMap, trans);
		}
		else
		{
			//The event is already there and has states associated with it. We can add this transition to it
			//if non-determinism is allowed (inverse transition functions are always non-deterministic)
			addTransToStateMap(*toStateMap, trans, allowNonDet);
		}
	}
}

//_________________________________________________________________________________________________
//Internal function that deletes the transition "trans" from the given map "transMap". This function is used
//to delete a transition either from the regular map or from the inverse transition map
void DesTransitionFunction::deleteTransFromMap(const DesTransition& trans, TransitionMap& transMap)
{
	TransMapIt fromStateIt;
	EventMapIt eventIt;
	StateMapIt toStateIt;
	
	if (findTransition(transMap, trans, &fromStateIt, &eventIt, &toStateIt))
	{
		StateMap* stateMap = eventIt->second;
		stateMap->erase(toStateIt);

		if (stateMap->size() == 0)
		{
			//the state map is now empty so remove the event completely from this event map
			EventMap* eventMap = fromStateIt->second;
			eventMap->erase(eventIt);

			//clean the memory allocated for the state map			
			delete stateMap; 
			stateMap = null;

			//check to see if we need to delete the event map itself and the root transition entry
			if (eventMap->size() == 0)
			{
				transMap.erase(fromStateIt);

				//the event map is now empty so remove the event map completely for this "from state"
				//as there are no transitions for it anymore
				delete eventMap;   
				eventMap = null;
			}
		}
		
	}
	else
	{
		//transition not found. this should not happen
		throw EX("DesTransition not found. Cannot delete transition")
	}
}

//_________________________________________________________________________________________________
//Internal function that changes "trans" into "change" in the given transition map. It is used to perform the change in both
//the regular transition function and the inverse transition function.
void DesTransitionFunction::changeTransInMap(const DesTransition& trans, const DesTransition& change, 
											 TransitionMap& transMap, bool allowNonDet)
{
	TransMapIt fromStateIt;
	EventMapIt eventIt;
	StateMapIt toStateIt;
	
	if (findTransition(transMap, trans, &fromStateIt, &eventIt, &toStateIt) == false)
	{
		throw EX("DesTransition not found. Cannot change transition")
	}
	else if (isEventSelfLooped(*transEvent(change)))
	{
		//and event label equal to the one to change is globally self-looped so we cannot allow
		//the change. The global self-looped must be removed first
		throw EX("A global self-loop was found having the same event as the changed transition. Cannot change transition")
	}
	else
	{
		//transition found
		if (transFromState(trans) != transFromState(change) )
		{
			//the starting states are different so remove the whole transition and add the changed one
			replaceTransition(transMap, trans, change, allowNonDet);
		}
		else
		{
			//the "from state" was not changed; check for the event being changed
			EventMap& eventMap = *fromStateIt->second;
			if (transEvent(trans) != transEvent(change))
			{
				changeTransitionEvent(transMap, trans, change, eventMap, allowNonDet);
			}
			else
			{
				//only the to state is different so change it
				changeTransitionToState(trans, change, eventMap);				
			}
		}
	}
	
}

//_________________________________________________________________________________________________

//Internal function used to add a transition to the map. No checking is actually done as the function
//assumes there is no transition in the transition map that starts from the fromState of this transition
void DesTransitionFunction::startNewTrans(TransitionMap& transMap, const DesTransition& trans)
{
	//create the state map
	StateMap& toStateMap = *new StateMap;
	toStateMap[transToState(trans)->getId()] = transToState(trans);

	//Create the event map and associate for the event the above state map
	EventMap& eventMap = *new EventMap;
	eventMap[transEvent(trans)] = &toStateMap;
	
	//add the event map to the transition list for this "from state"
	transMap[transFromState(trans)] = &eventMap;

}

//_________________________________________________________________________________________________

//Internal function used to add the toState of a transition to the event map when the event label
//for this transition has not been used yet
void DesTransitionFunction::startNewStateMap(EventMap& eventMap, const DesTransition& trans)
{
	StateMap& toStateMap = *new StateMap;
	toStateMap[transToState(trans)->getId()] = transToState(trans);
	
	eventMap[transEvent(trans)] = &toStateMap;
}

//_________________________________________________________________________________________________

//Internal function that adds a transition to an existing stateMap
void DesTransitionFunction::addTransToStateMap(StateMap& stateMap, const DesTransition& trans, bool nonDetAllowed)
{	
	if (stateMap.empty())
	{
		throw EX("Destination map should not be empty. Unexpected error.")
	}

	if (stateMap.find(trans.toState().getId()) != stateMap.end())
	{
		//The toState of the transition being added is already in the stateMap
		throw EX("This transition is already in the map. Cannot add duplicate transitions")
	}
	else
	{
		if (nonDetAllowed)
		{
			//Non determinism is allowed so add another destination state for this event
			stateMap[transToState(trans)->getId()] = transToState(trans);
		}
		else
		{
			//There is a destination state for this event there but not this state -> nondeterminism
			throw EX("A transition with this <from state> and <event> already exists. Cannot add non-deterministic transitions")
		}
	}
}

//_________________________________________________________________________________________________
//Internal function that makes sure the given transition map does not contain any conflicting transition
//with the selfLoopEvent. The function doesn't consider local loops as conflicts cleaning them and returning
//them to the user
DesTransition::Count DesTransitionFunction::checkAndCleanTransMap(TransitionMap& transMap, const DesEvent& selfLoopEvent,
																  std::vector<DesTransition*>* o_pLocalLoops /*= null*/)
{
	//The two lists are used to keep track of the local self-looped transitions that should be
	//be removed if a global self-loop is added. The first list keeps the iterator pointing to
	//the self-looped state in the transition map while the second list keeps the iterator pointing
	//to the event label of the local self-loop
	std::vector<TransMapIt> localSelfLoopTransList;
	std::vector<EventMapIt> localSelfLoopEventList;

	//go through all transitions looking for local loops with the same event as the one we are globally
	//self-looping. Note that the check will fail (an an exception will be thrown) if a regular transition
	//is found having this event label.If only local loops are found having this event label they are returned
	//in the two list arguments
	checkForLocalLoops(transMap, selfLoopEvent, localSelfLoopTransList, localSelfLoopEventList);

	//clean the transition map of all the local self-loops that have the same event as the global
	//self loop that is being added. The local loops are returned as transition objects in pLocalLoops
	//if it was supplied by the caller
	return cleanLocalLoops(transMap, localSelfLoopTransList, localSelfLoopEventList, o_pLocalLoops);
}

//_________________________________________________________________________________________________

//Internal function that goes through all transitions looking for local loops with the same event as the 
//selfLoopEvent. The check will fail (and an exception will be thrown) if a regular transition
//is found having this event label.If only local loops are found having this event label they are returned
//in the two list arguments
DesTransition::Count DesTransitionFunction::checkForLocalLoops(TransitionMap& transMap, 
															   const DesEvent& selfLoopEvent, 
															   std::vector<TransMapIt>& o_transList,
															   std::vector<EventMapIt>& o_eventList)
{
	//Go through the transition map and search for transition with this event as the label
	for(TransMapIt transIt = transMap.begin(); transIt != transMap.end(); transIt++)
	{
		EventMap* pEventMap = transIt->second;
		EventMapIt eventIt = pEventMap->find(&selfLoopEvent);			
		if (eventIt != pEventMap->end())
		{
			//Event was found in this map. If the destination state is different than the source 
			//state it means the Des would become non-deterministic so we cannot allow the addition
			const DesState* pFromState  = transIt->first;
			StateMap* pToStateMap = eventIt->second;

			if (pToStateMap->empty())
			{
				throw EX("Empty state map found. Unexpected error")
			}
			
			const DesState* pToState = pToStateMap->begin()->second;
			
			if ((pToStateMap->size() == 1) && ( pToState == pFromState))
			{
				//Exactly one regular transition was found which is a self-loop. Remember it in a "found list"
				//If the SelfLoop transition can be added as "global" self-looped event we need to
				//remove the local self-loops
				o_transList.push_back(transIt);
				o_eventList.push_back(eventIt);
			}
			else
			{					
				throw EX("An regular transition exists with this event label. Regular transition not allowed to coexist with global self-loops")
			}				
		}
	}

	return o_transList.size();
}

//_________________________________________________________________________________________________

//Removes all transitions identified by the two given lists. transList identifies the start points
//of the loops, the eventList identifies the event map for the self-loop
DesTransition::Count DesTransitionFunction::cleanLocalLoops(TransitionMap& transMap, 
															std::vector<TransMapIt>& transList, 
															std::vector<EventMapIt>& eventList,
															std::vector<DesTransition*>* o_pLocalLoops)
{
	if (transList.size() != eventList.size())
		throw EX("Transition and event lists must have the same size. Unexpected error")

	//clean the transition map of all the local self-loops that have the same event as the global
	//self loop that is being added
	for(unsigned int iLocalSelfLoop = 0; iLocalSelfLoop < transList.size(); iLocalSelfLoop++)
	{
		TransMapIt& localSelfTransIt     = transList[iLocalSelfLoop];
		EventMapIt& localSelfLoopEventIt = eventList[iLocalSelfLoop];

		const DesState* pFromState  = localSelfTransIt->first;
		EventMap* pEventMap   = localSelfTransIt->second;
		const DesEvent* pEvent	  = localSelfLoopEventIt->first;
		StateMap* pToStateMap = localSelfLoopEventIt->second;

		if (pToStateMap->size() != 1)
			throw EX("The state map must contain exactly one self-loop to be cleaned. Unexpected error;")

		const DesState* pToState   = pToStateMap->begin()->second;

		if (o_pLocalLoops)
		{
			//Return the local self-loop to the caller who is responsible for release the memory for these
			//temporary transition objects. They have to know what their doing (i.e. read the documentation)
			//if they requested them
			DesTransition* pLocalSelfLoop = new DesTransition(*pFromState, 
															  *pEvent, 
															  *pToState);
			o_pLocalLoops->push_back(pLocalSelfLoop);
		}

		//remove the state map and destroy it
		delete pToStateMap;
		pToStateMap = null;
		
		//remove the self-looped event from the event map of the current state
		pEventMap->erase(localSelfLoopEventIt); 

		//check to make sure the state has other transitions beside the one that was just removed
		//if there no more transitions destroy the event map and remove the state from the transition map
		if (pEventMap->size() == 0)
		{
			delete pEventMap;
			pEventMap = null;

			transMap.erase(localSelfTransIt);
		}
	}

	return transList.size();
}

//_________________________________________________________________________________________________

//Completely replaces trans by change by deleting trans and adding change. If adding the "change"
//transition fails the function attempts to put back the original transition
void DesTransitionFunction::replaceTransition(TransitionMap& transMap, const DesTransition& trans, 
											  const DesTransition& change, bool allowNonDet)
{
	deleteTransFromMap(trans, transMap);

	try
	{
		addTransToMap(change, transMap, allowNonDet);
	}
	catch(...)
	{
		//an exception ocurred while adding the changed transition which means it was not added
		//make sure the transition was not added and put back the original transition
		TransMapIt changeIt;
		EventMapIt changeEventIt;
		StateMapIt changeToStateIt;
		if (findTransition(transMap, change, &changeIt, &changeEventIt, &changeToStateIt) == false)			
		{
			//put back the original transition
			addTransition(trans);
		}
		else
		{
			//although an exception ocurred while adding the change the change is there
			assert(false);
		}

		throw; //re-throw the error	- there was an error while trying to change the transition
	}
}


//_________________________________________________________________________________________________

//changes the transition trans to change when the events are different. Their toState is assumed the same
//and the event map corresponds to this to state. If the change cannot be done it throws exception.
void DesTransitionFunction::changeTransitionEvent(TransitionMap& /*transMap*/, 
												  const DesTransition& trans, const DesTransition& change, 
												  EventMap& eventMap, bool allowNonDet)
{
	//remove the toState of the original transition from the state map corresponding to the old event label
	EventMapIt oldEventIt = eventMap.find(transEvent(trans));
	removeToStateFromMap(trans.toState(), eventMap, oldEventIt);

	//the event labels are different; find the new event
	EventMapIt eventIt = eventMap.find(transEvent(change));
	if ( eventIt == eventMap.end())
	{	//change.event() is new event in the map

		//associate the change.toState to the new event
		startNewStateMap(eventMap, change);
	}
	else
	{	//change.event() is already used in the map

		//We can add change.toState ONLY if non-determinism is allowed and if this doesn't cause a duplication		
		StateMap& stateMap = *eventIt->second;
		addTransToStateMap(stateMap, change, allowNonDet);		
	}
}

//_________________________________________________________________________________________________

//change the transition "trans" to "change" when only the destination states are different. Their start state
//and event are assumed to be the same. If the change cannto be done it throws exception.
void DesTransitionFunction::changeTransitionToState(const DesTransition& trans, const DesTransition& change, 
													EventMap& eventMap)
{
	StateMap& stateMap = *eventMap[transEvent(trans)];
	StateMapIt origToStateIt = stateMap.find(trans.toState().getId());

	if (origToStateIt == stateMap.end())
		throw EX("The original transition toState cannot be found. Unexpected error")

	//remove the state map entry for the original transition
	stateMap.erase(origToStateIt);

	//put the new one in
	const DesState* pToStateChange = transToState(change);
	stateMap[pToStateChange->getId()] = pToStateChange;	
}

//_________________________________________________________________________________________________

//Internal functions that removes the toState from the given state map identifid by eventIt. The function
//will properly destroy the state map if empty and remove the event entry from the event map.  The function doesn't
//destroy the event map even if it remained empty. It is up to the caller to do that
void DesTransitionFunction::removeToStateFromMap(const DesState& toState, EventMap& eventMap, EventMapIt& eventIt)
{
	StateMap* pStateMap = eventIt->second;
	StateMapIt toStateIt = pStateMap->find(toState.getId());
	
	if (toStateIt == pStateMap->end())
		throw EX("Destination state not found associated with the given event. Unexpected error")

	//remove the state from the map
	pStateMap->erase(toStateIt);

	//test the map to see if it has become empty
	if (pStateMap->empty())
	{
		//There is no transition associated with the event pointed by eventIt. Thus we need to remove it
		//from the event map and destroy the empty state map
		eventMap.erase(eventIt);
		delete pStateMap;
		pStateMap = null;
	}

	//the event map could be empty if the event was associated with only one "toState" which was just removed
	//the eventMap, even if empty, cannot be removed because it will be used by the caller to add another 
	//"event -> toState" pair to it.  Only the caller can destroy the event map
}

//_________________________________________________________________________________________________
//This internal function attempts to find the exact position of a transition in the transition map. It doesn't check
//for global self-loops
bool DesTransitionFunction::findTransition(TransitionMap& transMap, const DesTransition& trans, 
										   TransMapIt* o_pFromStateIt, 
										   EventMapIt* o_pEventIt /*= null*/,
										   StateMapIt* o_pToStateIt /*= null*/)
{
	TransMapIt transIt = transMap.find(transFromState(trans));
	if (transIt == transMap.end())
	{
		//there are no events leaving from the transition's "from state" so the transition cannot be there
		return false;
	}
	else
	{
		//a transition list exists for this "from state"
		EventMap& eventMap = *transIt->second;
		EventMapIt eventIt = eventMap.find(transEvent(trans));
		if (eventIt == eventMap.end())
		{
			//no transition was found to have the event required by the caller
			return false;
		}

		StateMap& stateMap = *eventIt->second;
		StateMapIt toStateIt = stateMap.find(trans.toState().getId());
		if (toStateIt == stateMap.end())
		{
			//no transition was found having the toState required by the caller
			return false;
		}
				
		//if we got here a transition was found. Return the iterators to the caller
		if (o_pFromStateIt)
		{
			*o_pFromStateIt = transIt;
		}

		if (o_pEventIt)
		{
			*o_pEventIt = eventIt;
		}

		if (o_pToStateIt)
		{
			*o_pToStateIt = toStateIt;
		}

		return true;
	}
}

//_________________________________________________________________________________________________

bool DesTransitionFunction::notUsed(const DesEvent& event) 
{
	//check for the event being globlally self-looped
	if (isEventSelfLooped(event))
	{
		//the event is used as a global self loop
		return false;
	}
	
	//check for the event being used in the local transitions map
	//NOTE: there is no need to check in the inverse transition map. If the event is used, is used in both
	//transition maps or none of them
	for(TransMapCIt transIt = m_transMap.begin(); transIt != m_transMap.end(); transIt++)
	{
		const EventMap* pEventMap = transIt->second;
		
		if (pEventMap->find(&event) != pEventMap->end())
		{
			//Event was found in this map thus it is used by the transition function
			return false;
		}
	}

	//the event was not found throughout the transition function thus it is not used
	return true;
}

//_________________________________________________________________________________________________

//checks to see if an event is self-looped globally and returns the iterator in the 
//map of self loop events if required
bool DesTransitionFunction::isEventSelfLooped(const DesEvent& event, SelfLoopEventIt* pEventIt /*= null*/) 
{
	SelfLoopEventIt eventIt = m_globalSelfLoopEventMap.find(event.getId());
	if (pEventIt != null)
	{
		//an iterator was required
		*pEventIt = eventIt;
	}

	return ( eventIt != m_globalSelfLoopEventMap.end());
}

//_________________________________________________________________________________________________

//Marks the given event as being used or unused depending whether the event is used
//in the transition function either by locals transitions or global self-loops
void DesTransitionFunction::markEventUsed(const DesEvent& event, bool isUsed /*= true*/)
{
	m_eventPool.getEvent(event.getId())->setUsed(isUsed);
}

#ifdef _DEBUG_DESPOT
#include "Windows.h"

void DesTransitionFunction::outputTransitionFunction()
{
	outputTransitionFunction(m_transMap);
	outputTransitionFunction(m_invTransMap);
}
void DesTransitionFunction::outputTransitionFunction(TransitionMap& transMap)
{
	OutputDebugString(L"_______________LOCAL TRANSITIONS__________________\n\n");
	for(TransMapIt transIt = transMap.begin(); transIt != transMap.end(); transIt++)
	{
		const DesState& fromState = *transIt->first;
		OutputDebugString(fromState.getName().c_str());
		OutputDebugString(L": \n");

		EventMap& eventMap = *transIt->second;
		for(EventMapIt eventIt = eventMap.begin(); eventIt != eventMap.end(); eventIt++)
		{
			const DesEvent& eventLabel = *eventIt->first;			
			OutputDebugString(L"\t");
			OutputDebugString(eventLabel.getName().c_str());
			OutputDebugString(L": \n");
			

			StateMap& stateMap = *eventIt->second;
			for(StateMapIt toStateIt = stateMap.begin(); toStateIt != stateMap.end(); toStateIt++)
			{
				const DesState& toState = *toStateIt->second;
				OutputDebugString(L"\t\t");
				OutputDebugString(toState.getName().c_str());
				OutputDebugString(L"\t");
			}
			OutputDebugString(L"\n");
		}
		OutputDebugString(L"_________________________________\n\n");
	}

	OutputDebugString(L"_______________SELF-LOOPED EVENTS__________________\n\n");

	for( SelfLoopEventIt selfLoopIt = m_globalSelfLoopEventMap.begin(); selfLoopIt != m_globalSelfLoopEventMap.end();
		 selfLoopIt++)
	{
		const DesEvent& selfLoop = *selfLoopIt->second;
		OutputDebugString(selfLoop.getName().c_str());
		OutputDebugString(L"\n");
	}

	OutputDebugString(L"_______________End of transition function__________________\n\n");
}
#endif //_DEBUG_DESPOT

} //end of namespace DESpot

