!!! This file is used for PIRE benchmarking
!!! Don't change its contents so that results can be compared to the previous runs


(Cdbg << "State " << ns << " carries tag " << ti->second << " because of old state " << *j << Endl);
	letters = LettersTbl(LettersEquality(m_transitions));
	for (TSet<size_t>::iterator i = dead.begin(), ie = dead.end(); i != ie; ++i) {
				s << " ";
		PIRE_IFDEBUG(Cdbg << "New terminals = [" << Join(mNewTerminals.begin(), mNewTerminals.end(), ",") << "]" << Endl);

			for (TransitionRow::iterator k = j->begin(), ke = j->end(); k != ke; ++k)
	TransitionTable::iterator dest = m_transitions.begin() + oldsize;
	Tags oldTags;
{
		}
	determined = fallude <iostream>

	ClearFinal();
				Y_ASSERT(false);
	}
		m_final.insert(state);
				std::bind2nd(std::plus<size_t>(), oldsize));
	for (Tags::const_iterator it = rhs.tags.begin(), ie = rhs.tags.end(); it != ie; ++it)
	if (toOit != outputs.end()) {
	DoSwap(m_final, fsm.m_final);
			outIt->second[*toi] |= (fromThruOut | Output(thru, *toi));

}
    for (ystring::const_iterator i = str.begin(), ie = str.end(); i != ie; ++i)
	}
	for (unsigned letter = 0; letter < MaxChar; ++letter)
	if (i == outputs.end())
	for (Fsm::TransitionTable::const_iterator outer = m_tbl->begin(), outerEnd = m_tbl->end(); outer != outerEnd; ++outer) {
			Y_ASSERT(letter->second.size() == 1 || !"FSM::minimize(): FSM not deterministic");
					mNewTerminals.insert(ns);
	// Invert outputs
	ClearFinal();

		}
private:
	ClearFinal();
	// criteria to test whether a transition has been created or not.
typedef TVector<size_t> DeterminedTransitions;
		PIRE_IFDEBUG(Cdbg << "Returning transition [" << Join(state.begin(), state.end(), ", ") << "] --" << letter
	else if (c == EndMark)
		m_final.insert(*it + lhsSize);	
Fsm& Fsm::Append(char c)
	TVector<bool> unchecked(Size(), true);
		return ystring("<Epsilon>");
				size_t& newState = ltr[ymake_pair(state, *cit)];
#include <algorithm>
	return *this;
						break;
}
		ConnectFinal(Size() - 1, letter);
			Disconnect(rhs.initial + lhsSize, *to + lhsSize, Epsilon);

	}

	return true;
	TSet<size_t> mNewTerminals;
	TSet<size_t> res;
	// Minimization algorithm is only applicable to a determined FSM.
		}
	for (size_t i = 0; i < Size(); ++i)
	// Apply
		for (TransitionRow::const_iterator k = j->begin(), ke = j->end(); k != ke; ++k) {
		}
}
	ConnectFinal(Size() - 1, c);
	// Assign the transition
{
	TVector<Char> distinctLetters;

	}
		last.Split(MinimizeEquality(detTran, distinctLetters, &stateClassMap));
		Tags::iterator ti = oldTags.find(fromIdx);
				if (from != old2new.end() && to != old2new.end()) {
		m_transitions[*i].clear();
// Assuming the epsilon transitions is possible from 'from' to 'thru',
					outer->insert(ymake_pair(*cit, targets->second));
	Outputs::iterator oi = outputs.find(from);
namespace Impl {
		return next;
}
}
			oi->second.erase(oi2);
	Fsm inverted;
	Fsm rhs2(rhs);

		return ystring("<Begin>");
	if (out != rhs.outputs.end())
		const StatesSet& to = Destinations(from, Epsilon);
	else if (c == '\r')
		, mTerminals(fsm.TerminalStates())
Fsm& Fsm::operator += (const Fsm& rhs)
	}
			return false;
}
	TVector< ybitset<MaxChar> > row(Size());
	}
		// Append tags
	size_t end = Size() - 1;
	// state #0 cannot appear in LTRs. Thus we can use this
			for (StatesSet::iterator j = i->second.begin(), je = i->second.end(); j != je; ++j)
	PIRE_IFDEBUG(Cdbg << "=== After all epsilons removed" << Endl << *this << Endl);
	ConnectFinal(end);
	ClearFinal();
//     PIRE_IFDEBUG(LOG_DEBUG("fsm") << "=== Left-hand side ===\n" << *this);
	// Import outputs
			// Enqueue the state for further traversal if it hasnt been already checked
}
#include <numeric>
			useless[i] = false;
	Import(rhs);
		size_t cl = stPartition.Representative(st);
	SetFinal(end, true);
public:
	ClearHints();
 * along with Pire.  If not, see <http://www.gnu.org/licenses>.
			empty = false;
	else if (c == '\n')
Fsm& Fsm::operator &= (const Fsm& rhs)
}
#include <functional>
	SetFinal(end, 1);
	ClearHints();
// from which a transition to themselves on any letter is possible.
	typedef ypair<size_t, char> Transition;
	while (count--)
	for (TransitionTable::iterator i = m_transitions.begin(), ie = m_transitions.end(); i != ie; ++i)
	return false;
	outputs.swap(oldOutputs);
			empty = false;
	{
	Connect(Size() - 2, Size() - 1);
}
				std::cerr << "WTF?! Transition from " << state << " on letter " << rit->first << " leads to non-existing state " << *sit << "\n";
		Outputs::value_type::second_type& dest = outputs[oit->first + oldsize];
			for (State::const_iterator j = states[ns].begin(), je = states[ns].end(); j != je; ++j)
				state = newState;
				}
};
}
	Outputs::const_iterator out = rhs.outputs.find(rhs.initial);
	
    return *this;
	State Next(const State& state, Char letter) const
	*this |= rhs2;
	for (LettersTbl::ConstIterator lit = letters.Begin(), lie = letters.End(); lit != lie; ++lit)
	Complement();
	m_transitions(1),
			if (targets == dest->end())
Fsm& Fsm::AppendStrings(const TVector<ystring>& strings)
			tags[dest] |= ti->second;

				Old2New::iterator from = old2new.find(i->first);
{

	
	TSet<size_t> mTerminals;
				if (!newState) {
				Outputs::value_type::second_type::const_iterator oit2 = oit->second.find(std::distance(row.begin(), rit));
	else
		if (ia == outer->end() && ib == outer->end())
	ClearFinal();
						mNewFsm.Connect(ns, ns, letterIt->first);
 * Pire is free software: you can redistribute it and/or modify

Empty spaces
what are we living for
Abandoned places
I guess we know the score
}
		}
		// new connections that were merged from 'to' state
		State next;
		throw Error("Regexp pattern too complicated");
    return *this;
	Complement();
	m_sparsed(false),
		}
			s << "<Epsilon> ";
	
		return ystring("<End>");
			i->second.insert(dest);
ystring CharDump(Char c)
		for (StatesSet::const_iterator fr = connections.begin(), fre = connections.end(); fr != fre; ++fr) {
				// If any state containing in our one is marked final, mark the new state final as well
			oi->second.insert(ymake_pair(dest, output));
		const StatesSet& connections = (inverted.m_transitions[to])[0];
	TMap<Transition, size_t> ltr;

	SetFinal(Size() - 1, true);
	ClearHints();
		PIRE_IFDEBUG(Cdbg << "=== Determined ===" << Endl << *this << Endl);
			out.SetOutput(j->first, i->first, j->second);

	Fsm mNewFsm;
{
	// Invert transitions
	for (FinalTable::const_iterator it = rhs.m_final.begin(), ie = rhs.m_final.end(); it != ie; ++it)
 * Regular Expressions library.
		PIRE_IFDEBUG(Cdbg << "Stage " << cnt++ << ": state classes = " << last << Endl);
{
	while (!queue.empty()) {

{
	return ret;
		}
	PIRE_IFDEBUG(Cdbg << "=== After epsilons shortcut\n" << *this << Endl);
		Connect(*it, to, c);
	size_t fromIdx = 0;
	unsigned long fromThruOut = Output(from, thru);
}
	for (FinalTable::iterator it = m_final.begin(), ie = m_final.end(); it != ie; ++it)
	out.tags = tags;
	for (TransitionTable::const_iterator outer = rhs.m_transitions.begin(), outerEnd = rhs.m_transitions.end(); outer != outerEnd; ++outer, ++dest) {

			detTran[(j - m_transitions.begin()) * MaxChar + k->first] = *(k->second.begin());
	//      outputs[from][i] |= (outputs[from][to] | outputs[to][i])
	if (!IsDetermined()) {
	if (i != m_transitions[from].end())

	}
	PIRE_IFDEBUG(Cdbg << "Removing dead ends on:" << Endl << *this << Endl);
 *
namespace Pire {
	else if (c < 256) {
void Fsm::Minimize()
{
						if (oit2->second & (1ul << i))
			ConnectFinal(end, static_cast<unsigned char>(str[0]));
	if (outputs.find(from) != outputs.end() && outputs[from].find(to) != outputs[from].end()) {
	Connect(begin, initial);
		}
	if (ti != tags.end())
	m_final.insert(0);
	TSet<Transition> usedTransitions;

		
	// a that transition already points somewhere (either to end
	PIRE_IFDEBUG(Cdbg << "Initial finals: { " << Join(m_final.begin(), m_final.end(), ", ") << " }" << Endl);
	for (size_t i = 0; i < Size(); ++i)
			throw Error("regexp pattern too complicated");
		return ystring("\\n");
			}
// It merges transitions, tags, and outputs of 'to' state into 'from' state
		tags[from] |= ti->second;
}
			s << "<Begin> ";

		m_final.erase(state);

{
	typedef Fsm::LettersTbl LettersTbl;
	for (size_t from = 0; from != Size(); ++from) {
	out.letters = Letters();
}
	return *this;
{
			std::copy(part.begin(), part.end(), std::back_inserter(next));
			i->second.erase(di);
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
				empty = false;
				
		}
	Tags::iterator ti = tags.find(to);

				inverted.Connect(*toSt, j - m_transitions.begin(), 0);


		}
    
		unchecked[to] = false;


			Connect(dest, last.Index(*letter->second.begin()), letter->first);
Fsm& Fsm::AppendSpecial(Char c)
			}
	DoSwap(isAlternative, fsm.isAlternative);
	for (TransitionRow::iterator i = m_transitions[from].begin(), ie = m_transitions[from].end(); i != ie; ++i) {
		if (m_prev) {
					;
	for (size_t st = 0; st < clMap.size(); st++) {
		mNewFsm.Resize(states.size());
/*
				return false;

	// Resize FSM
			for (TVector<Char>::const_iterator cit = lit->second.second.begin(), cie = lit->second.second.end(); cit != cie; ++cit)
			if ((*m_prev)[a] != (*m_prev)[b])
		initial = rhs.initial + lhsSize;
	for (TransitionTable::const_iterator j = m_transitions.begin(), je = m_transitions.end(); j != je; ++j) {

	for (size_t from = 0; from != Size(); ++from) {
	m_final.swap(oldFinal);




	const TransitionRow& row = m_transitions[lhsSize + rhs.initial];
	for (TransitionRow::const_iterator i = m_transitions[from].begin(), ie = m_transitions[from].end(); i != ie; ++i)
		const StatesSet& tos = rhs.Destinations(rhs.initial, Epsilon);
		}
	Resize(last.Size());
}
	Outputs::mapped_type::const_iterator j = i->second.find(to);
	}
#include <utility>
	for (size_t i = 0; i < Size(); ++i)
	FinalTable oldFinal;
	Outputs::iterator outIt = outputs.find(from);
	StateClassMap stateClassMap(Size());
{
		if (di != i->second.end()) {
bool Fsm::Connected(size_t from, size_t to, Char c) const
	while (UpdateStateClassMap(stateClassMap, last)) {
	size_t Next(size_t state, Char letter) const
 * 
	for (TransitionRow::iterator i = m_transitions[from].begin(), ie = m_transitions[from].end(); i != ie; ++i)
{
	for (size_t letter = 0; letter < MaxChar; ++letter) {
		}
			m_final.insert(i);
void Fsm::DumpState(yostream& s, size_t state) const
Fsm& Fsm::Append(const ystring& str)
{
			// The single letter: connect all the previously final states to end
		snprintf(buf, sizeof(buf)-1, "\\%03o", static_cast<int>(c));
        Append(*i);
	{
Fsm& Fsm::AppendDot()
			// All other letters except last one
void Fsm::RemoveEpsilons()
}
	s << "    ";
					PIRE_IFDEBUG(Cdbg << "State " << ns << " becomes final because of old state " << *j << Endl);
			throw Error("None of strings passed to appendStrings() can be empty");
		                  << "--> [" << Join(next.begin(), next.end(), ", ") << "]" << Endl);
	letters = LettersTbl(LettersEquality(m_transitions));

		}
// Faster transition table representation for determined FSM
	
				return false;
	for (size_t letter = 0; letter != (1 << (sizeof(char)*8)); ++letter)
	for (TransitionTable::iterator from = oldTransitions.begin(), fromEnd = oldTransitions.end(); from != fromEnd; ++from, ++fromIdx) {
	void AcceptStates(const TVector<State>& states)
	typedef TVector<size_t> State;
		PIRE_IFDEBUG(Cdbg << "Connecting " << from << " --" << letter << "--> " << to << Endl);
			Y_ASSERT(k->second.size() == 1);
	determined = false;
		}
				if (mFsm.IsFinal(*j)) {
		out.Connect(Size(), *i, Epsilon);
 * fsm.cpp -- the implementation of the FSM class.
		for (TransitionRow::iterator i = m_transitions[from].begin(), ie = m_transitions[from].end(); i != ie; ++i)
	SetFinal(Size() - 1, true);
	Resize(Size() + 1);
	for (size_t from = 0; from < Size(); ++from)
				outputs[from][*newConnSt] |= frEpsOutput;
	PIRE_IFDEBUG(Cdbg << "=== Minimized (" << Size() << " states) ===" << Endl << *this << Endl);
	{
				Old2New::iterator to   = old2new.find(j->first);
			if (!firstJump) {
			}
void Fsm::Disconnect(size_t from, size_t to, Char c)
			// First letter: all previously final states are connected to the new state
	RemoveDeadEnds();
	return *this;
			inveps[*to].insert(from);
	for (TVector<ystring>::const_iterator i = strings.begin(), ie = strings.end(); i != ie; ++i)
	// Merge transitions from 'to' state into transitions from 'from' state
		}
	}
	PIRE_IFDEBUG(unsigned cnt = 0);
	static const unsigned MaxSize = 200000;
			for (TVector<Char>::const_iterator cit = lit->second.second.begin(), cie = lit->second.second.end(); cit != cie; ++cit)
unsigned long Fsm::Output(size_t from, size_t to) const
	m_sparsed = true;
	out.Resize(Size() + 1);
{
	// Make a transitive closure of all epsilon transitions (Floyd-Warshall algorithm)
}
			if (mTerminals.find(*i) != mTerminals.end())
		if (fsEpsOutputExists) {
{


	

	}
			TransitionRow::const_iterator targets = dest->find(lit->first);
	}
	TDeque<size_t> queue;

			s << "<End> ";
{
	ClearHints();
Char Fsm::Translate(Char c) const
		}

	typedef TMap<State, size_t> InvStates;
			if (*from != thru)
 * You should have received a copy of the GNU Lesser Public License


	if (Pire::Impl::Determine(task, maxsize ? maxsize : MaxSize)) {
{
	if (Initial() == state)
	for (StatesSet::const_iterator toi = to.begin(), toe = to.end(); toi != toe; ++toi) {
	
			}
	for (TransitionTable::const_iterator j = m_transitions.begin(), je = m_transitions.end(); j != je; ++j) {
	

	Resize(Size() + 1);
					mNewFsm.SetFinal(ns, true);
			s << "\n    ";
{
Fsm& Fsm::Complement()
	ClearFinal();
	{
		DumpState(s, state);
class FsmDetermineTask {
		else if (ia == outer->end() || ib == outer->end() || ia->second != ib->second) {
			determined = determined && (usedFirsts.find(str[0]) != usedFirsts.end());
	size_t begin = Size(), end = Size() + 1;
	return *this;
		for (StatesSet::iterator from = inveps[thru].begin(); from != inveps[thru].end(); ++from)
				// We only care if the states are connected or not regerdless through what letter

	DoSwap(outputs, fsm.outputs);
	typedef Partition<size_t, MinimizeEquality> StateClasses;
	Sparse();
				old2new[*j].push_back(ns);
				Fsm::Tags::const_iterator ti = mFsm.tags.find(*j);
void Fsm::ConnectFinal(size_t to, Char c /* = Epsilon */)
	// Valid for all letters in given strings except final ones,
			std::transform(inner->second.begin(), inner->second.end(), std::inserter(targets, targets.begin()),
	}
			for (TSet<size_t>::const_iterator newConnSt = connStates.begin(), ncse = connStates.end(); newConnSt != ncse; ++newConnSt) {
 * it under the terms of the GNU Lesser Public License as published by
	ClearHints();
			s << " => " << std::distance(row.begin(), rit);

{
	for (size_t thru = 0; thru != Size(); ++thru)


	unsigned long frEpsOutput = 0;
				}
	if (final)

{
	rhs2.Complement();
	} else if (isAlternative && !rhs.isAlternative) {

					newState = Resize(Size() + 1);

			} else

{
		}
#include <stdio.h>
	letters(m_transitions),
	}
				
}
	return ret;
		for (TransitionRow::iterator letter = from->begin(), letterEnd = from->end(); letter != letterEnd; ++letter) {
	for (Outputs::iterator oit = oldOutputs.begin(), oie = oldOutputs.end(); oit != oie; ++oit)
	void Connect(size_t from, size_t to, Char letter)
	FsmDetermineTask(const Fsm& fsm)
	}	
}
		if (outIt != outputs.end())
		if (!Determine(maxSize)) 
		if (ok)
{
	else
// Removes all Epsilon-connections by iterating though states and merging each Epsilon-connection
	// Preserve tags (although thier semantics are usually heavily broken at this point)
			}
	const DeterminedTransitions* m_tbl;
	Outputs::iterator toOit = outputs.find(to);
	// Combine tags
		Connect(end, end, letter);
				determined = determined && (usedFirsts.find(str[0]) != usedFirsts.end());


			if (unchecked[*fr] && useless[*fr]) {
Fsm Fsm::operator *(size_t count)
		if (i != initial)
}
// TODO: Think how to update only changed states
typedef TVector<size_t> StateClassMap;
bool Fsm::Determine(size_t maxsize /* = 0 */)
	}

			outputs[last.Index(oit->first)].insert(ymake_pair(last.Index(oit2->first), oit2->second));
}

		if (letter != Epsilon)
void Fsm::Divert(size_t from, size_t to, size_t dest)
	// or somewhere else). Another attempt to create such transition
		bool empty = true;
void Fsm::DumpTo(yostream& s) const
	determined = false;
Fsm Fsm::MakeFalse()
		if (oi2 != oi->second.end()) {
		if (rit->test(EndMark)) {
		}
			size_t& firstJump = startLtr[str[0]];
	ClearHints();
}
	{
//     PIRE_IFDEBUG(LOG_DEBUG("fsm") << "Importing");
		for (StatesSet::const_iterator inner = outer->second.begin(), innerEnd = outer->second.end(); inner != innerEnd; ++inner)
	if (IsFinal(state))
				const TVector<Char>& letters = Letters().Klass(Letters().Representative(rit->first));
			// The last letter: connect the current state to end
	const Fsm::FinalTable* m_final;
				if (ti != mFsm.tags.end()) {

	inline bool operator()(size_t a, size_t b) const
	
	Resize(Size() + 1);
{
	initial = begin;
	} else if (c == Epsilon)
	// Precompute letter classes
		for (Outputs::value_type::second_type::iterator oit2 = oit->second.begin(), oie2 = oit->second.end(); oit2 != oie2; ++oit2)
	}
	TransitionRow::const_iterator it = m_transitions[from].find(Translate(c));
		


					for (LettersTbl::ConstIterator letterIt = Letters().Begin(), letterEnd = Letters().End(); letterIt != letterEnd; ++letterIt)
			if (*toi != from)
}
	for (TransitionRow::const_iterator rit = m_transitions[state].begin(), rie = m_transitions[state].end(); rit != rie; ++rit)
		}
					TVector<int> payload;
			}
// Updates the mapping of states to partitions.
    return *this;
			for (StatesSet::const_iterator toSt = k->second.begin(), toSte = k->second.end(); toSt != toSte; ++toSt) {
const Fsm::StatesSet& Fsm::Destinations(size_t from, Char c) const
//     PIRE_IFDEBUG(LOG_DEBUG("fsm") << "=== Right-hand side ===\n" << rhs);
		mNewFsm.m_final.clear();
		Fsm::TransitionRow::const_iterator ib = outer->find(b);
{
{
	else if (c == BeginMark)
	Y_ASSERT(clMap.size() != 0);
		m_tbl(&tbl), m_letters(&letters), m_prev(clMap), m_final(0) {}

		}
	for (Outputs::const_iterator oit = rhs.outputs.begin(), oie = rhs.outputs.end(); oit != oie; ++oit) {
	return *this;
							payload.push_back(i);

}


		if (IsFinal(i)) {
			// Compute the set of states that are reachable from 'to' state
	};
	TSet<char> usedFirsts;
			PIRE_IFDEBUG(Cdbg << "State " << ns << " = [" << Join(states[ns].begin(), states[ns].end(), ", ") << "]" << Endl);
#include <queue>
	// Merge all 'to' into 'from' outputs:
	} else if (!isAlternative && rhs.isAlternative) {
	determined = false;
 *
				if (*cit != lit->first)
}
		}
			for (State::const_iterator j = states[ns].begin(), je = states[ns].end(); j != je; ++j) {

	for (TransitionRow::const_iterator outer = row.begin(), outerEnd = row.end(); outer != outerEnd; ++outer)
	// Erase all useless states

			for (end = begin; end < 256 && rit->test(end); ++end)

 * the Free Software Foundation, either version 3 of the License, or
		if (rit->test(BeginMark)) {

{
	Swap(out);
	PIRE_IFDEBUG(Cdbg << "=== After epsilons merged\n" << *this << Endl);


	}
		}
	return (i != m_transitions[from].end()) ? i->second : DefaultValue<StatesSet>();
}
};
	char buf[8];
	}
 */
	State Initial() const { return State(1, mFsm.initial); }
			letters.Append(letter);
	DoSwap(determined, fsm.determined);
{
		return ystring("\\r");
	Result Failure() { return false; }
	for (TransitionTable::iterator outer = m_transitions.begin(), outerEnd = m_transitions.end(); outer != outerEnd; ++outer) {
	// Do the breadth-first search, marking all states
{
			dest->insert(ymake_pair(inner->first, targets));
	

			TSet<size_t> targets;
				s << CharDump(begin) << ".." << (CharDump(end-1));
	
	Resize(Size() + 1);
Fsm& Fsm::Surround()
	if (ti != tags.end())

			}
		i->erase(Epsilon);
	
	for (TVector<ystring>::const_iterator sit = strings.begin(), sie = strings.end(); sit != sie; ++sit) {
	PIRE_IFDEBUG(Cdbg << "=== Initial ===" << Endl << *this << Endl);
		Connect(begin, begin, letter);
	ConnectFinal(Size() - 1);

		return true;
	return changed;
		Connect(Size() - 1, lhsSize + rhs.initial);
	tags.swap(oldTags);
	SetFinal(Size() - 1, true);
			ConnectFinal(*inner, outer->first);
		if (!m_transitions[i].empty())
}

				<< last.Index(*letter->second.begin()) << Endl);


						// Weve got no tags and already know that the state is final,

	
{
		// If there is an output of the 'from'->'to' connection it has to be set to all
				continue;
	ConnectFinal(Size() - 1, sta
