OOPSGen Code

#include <OOLS/dfa.h>

namespace OOLS
{

void DFA::PartialState::expand()
{
	std::set<NFAState*> completed;
	std::set<NFAState*> worklist;
	std::set<NFAState*>::iterator it_wl;

	std::set<NFAState*> search;
	std::set<NFAState*>::iterator it_search;
	
	worklist.insert(nfaset.begin(), nfaset.end());
	NFAState* from;

	while(!worklist.empty())
	{
		from = *worklist.begin();
		search = from->getLambdaNextStateSet();
		completed.insert(*worklist.begin());
		worklist.erase(worklist.begin());

		for(it_search = search.begin(); it_search != search.end(); it_search++)
			if(worklist.find(*it_search) == worklist.end() &&
					completed.find(*it_search) == completed.end()
				)
				{
					worklist.insert(*it_search);
					nfaset.insert(*it_search);
					//if((*it_search)->getYieldSymbol() != OOPG::NullSymbolId)
				}
	}
}

DFA::PartialState* DFA::PartialState::ptr()
{
	return this;
}

bool DFA::PartialState::operator<(const PartialState &them) const
{
	std::set<NFAState*>::iterator it_this;
	std::set<NFAState*>::iterator it_them;

	if(nfaset.size() < them.nfaset.size()) return true;
	if(nfaset.size() > them.nfaset.size()) return false;
	
	it_them = them.nfaset.begin();

	for(it_this = nfaset.begin(); it_this != nfaset.end(); it_this++, it_them++)
	{
		if(**it_this < **it_them)
			return true;
		if(**it_this > **it_them)
			return false;
	}

	return false;
}

DFA::State::State(SymbolId yieldSymbol)
{
	this->yieldSymbol = yieldSymbol;
}

std::string DFA::getStateName(DFA::DFA::State* s)
{
	std::stringstream ret("");
	ret << s;

	if(s->getYieldSymbol() != OOPG::NullSymbolId)
		ret << "_" << alpha_out->lookupName(s->getYieldSymbol());

	return ret.str();
}

DFA::DFA(NFA* nfa, OOPG::Alphabet* alpha_in, OOPG::Alphabet* alpha_out)
{
	std::set<PartialState*, ptr_compare<PartialState> > all_states;
	std::set<PartialState*>::iterator it_all;
	std::pair<std::set<PartialState*>::iterator, bool> it_all_ins;
	std::set<PartialState*, ptr_compare<PartialState> > completed;
	std::set<PartialState*, ptr_compare<PartialState> > worklist;
	std::set<PartialState*, ptr_compare<PartialState> >::iterator it_wl;
	PartialState* npartial;

	std::set<NFAState*>::iterator it_partial;
	NFAState::TransitList::const_iterator it_nfajmp;

	JumpPart parts(256);
	JumpPart::PartMap::iterator it_parts;

	typedef std::pair<PartialState*, PartialState*> PStatePair;
	PStatePair searchPair;
	std::map<PStatePair, BitField> state_transits;
	std::map<PStatePair, BitField>::iterator it_found_transit;
	std::map<PStatePair, BitField>::iterator it_transits;

	std::map<PartialState*, State*> machineMap;
	SymbolId yieldSymbol = OOPG::NullSymbolId;
	SymbolId tmpYieldSymbol;

	this->alpha_in = alpha_in;
	this->alpha_out = alpha_out;

	PartialState entry;
	entry.nfaset.insert(nfa->getEntry());
	entry.expand();
	worklist.insert(entry.ptr());
	this->entry = NULL;

	while(!worklist.empty())
	{
		it_wl = completed.insert(*worklist.begin()).first;
		worklist.erase(worklist.begin());

		parts.jumps.clear();
		yieldSymbol = OOPG::NullSymbolId;

		for(it_partial = (*it_wl)->nfaset.begin(); it_partial != (*it_wl)->nfaset.end(); it_partial++)
		{
			for(it_nfajmp = (*it_partial)->begin(); it_nfajmp != (*it_partial)->end(); it_nfajmp++)
				parts.associate(it_nfajmp->symbols.begin(), it_nfajmp->symbols.end(), it_nfajmp->target);

			tmpYieldSymbol = (*it_partial)->getYieldSymbol();
			if(tmpYieldSymbol > yieldSymbol)
				yieldSymbol = tmpYieldSymbol;
		}

		for(it_parts = parts.jumps.begin(); it_parts != parts.jumps.end(); it_parts++)
		{
			//Build a partial state from the list of outgoing transits
			npartial = new PartialState();
			npartial->nfaset.insert(it_parts->second.begin(), it_parts->second.end());
			npartial->expand();

			//Check to see if the "new" partial state is really new or not
			//Select the old element if the partial state already existed, or insert it into worklist
			it_all_ins = all_states.insert(npartial);
			if(it_all_ins.second) worklist.insert(*(it_all_ins.first));
			else delete npartial;

			//
			searchPair = PStatePair(*it_wl, *it_all_ins.first);
			if((it_found_transit = state_transits.find(searchPair)) != state_transits.end())
				it_found_transit->second |= it_parts->first;
			else state_transits.insert(std::make_pair(searchPair,it_parts->first));
		}
		
		State* tmp = new State(yieldSymbol);
		machine_map[*it_wl] = tmp;
		statemachine.push_back(tmp);
		state_set.insert(tmp);
		if(!this->entry) this->entry = tmp;
	}

	for(it_transits = state_transits.begin(); it_transits != state_transits.end(); it_transits++)
	{
		searchPair = it_transits->first;
		machineMap[searchPair.first]->jumps.insert(std::make_pair(machineMap[searchPair.second],it_transits->second));
	}
}

void DFA::output(std::ostream &s_out)
{
	typedef std::set<State*> StateSet;
	typedef std::map<State*, BitField> JMap;
	
	StateSet complete, worklist, degenerate;
	StateSet::iterator it;
	OOPG::Alphabet::iterator it_alpha;

	JMap::iterator it_jmp;

	std::stringstream label;

	s_out << "digraph Regex {" << std::endl;

	worklist.clear();
	complete.clear();
	worklist.insert(entry);

	while(!worklist.empty())
	{
		it = worklist.begin();
		complete.insert(*it);

		s_out << "\t\"" << getStateName(*it) << "\" ";

		if((*it)->getYieldSymbol() != OOPG::NullSymbolId) s_out << "[shape=doublecircle]" << std::endl;
		else s_out << "[shape=circle]" << std::endl;

		for(it_jmp = (*it)->jumps.begin(); it_jmp != (*it)->jumps.end(); it_jmp++)
		{
			if(complete.find(it_jmp->first) == complete.end())
				worklist.insert(it_jmp->first);

			s_out << "\t\"" << getStateName(*it) << "\" -> \"" << getStateName(it_jmp->first) << "\" [label=\"[";

			for(it_alpha = alpha_in->begin(); it_alpha != alpha_in->end(); it_alpha++)
				if(it_jmp->second.isset(it_alpha->getId()))
					s_out << it_alpha->getName();

			s_out << "]\"];" << std::endl;
		}

		s_out << std::endl;

		worklist.erase(*it);
	}

	s_out << "}" << std::endl;

}

}