/*************************************************************************/
/*                                                                       */
/*                Centre for Speech Technology Research                  */
/*                     University of Edinburgh, UK                       */
/*                         Copyright (c) 1997                            */
/*                        All Rights Reserved.                           */
/*                                                                       */
/*  Permission is hereby granted, free of charge, to use and distribute  */
/*  this software and its documentation without restriction, including   */
/*  without limitation the rights to use, copy, modify, merge, publish,  */
/*  distribute, sublicense, and/or sell copies of this work, and to      */
/*  permit persons to whom this work is furnished to do so, subject to   */
/*  the following conditions:                                            */
/*   1. The code must retain the above copyright notice, this list of    */
/*      conditions and the following disclaimer.                         */
/*   2. Any modifications must be clearly marked as such.                */
/*   3. Original authors' names are not deleted.                         */
/*   4. The authors' names are not used to endorse or promote products   */
/*      derived from this software without specific prior written        */
/*      permission.                                                      */
/*                                                                       */
/*  THE UNIVERSITY OF EDINBURGH AND THE CONTRIBUTORS TO THIS WORK        */
/*  DISCLAIM ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING      */
/*  ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT   */
/*  SHALL THE UNIVERSITY OF EDINBURGH NOR THE CONTRIBUTORS BE LIABLE     */
/*  FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES    */
/*  WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN   */
/*  AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,          */
/*  ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF       */
/*  THIS SOFTWARE.                                                       */
/*                                                                       */
/*************************************************************************/
/*                     Author :  Alan W Black                            */
/*                     Date   :  November 1997                           */
/*-----------------------------------------------------------------------*/
/*                                                                       */
/* Basic WFST operations: minimization, determinization, intersection,   */
/*   union, composition                                                  */
/*                                                                       */
/*=======================================================================*/
#include <iostream>
#include <cstdlib>
#include "EST_WFST.h"
#include "wfst_aux.h"
#include "EST_String.h"
#include "EST_TList.h"
#include "EST_TKVL.h"
#include "EST_THash.h"

Declare_TList_T(EST_WFST_MultiState *,EST_WFST_MultiStateP)

  // Declare_KVL(int, EST_IList)

	typedef EST_TKVI<int, EST_IList> KVI_int_EST_IList_t; 
	typedef EST_TKVL<int, EST_IList> KVL_int_EST_IList_t; 
	
	static EST_IList int_EST_IList_kv_def_EST_IList_s; 
	static int int_EST_IList_kv_def_int_s; 
	
	template <> EST_IList *EST_TKVL< int, EST_IList >::default_val=&int_EST_IList_kv_def_EST_IList_s; 
	template <> int *EST_TKVL< int, EST_IList >::default_key=&int_EST_IList_kv_def_int_s; 
	
	Declare_TList_N(KVI_int_EST_IList_t, 0)


#if defined(INSTANTIATE_TEMPLATES)
#include "../base_class/EST_TList.cc"

  Instantiate_TList_T_MIN(EST_WFST_MultiState *,EST_WFST_MultiStateP)

#include "../base_class/EST_TKVL.cc"

	  //  Instantiate_KVL(int, EST_IList)

        template class EST_TKVL<int, EST_IList>; 
        template class EST_TKVI<int, EST_IList>; 
// ostream &operator<<(ostream &s, EST_TKVI< int , EST_IList > const &i){  return s << i.k << "\t" << i.v << "\n"; } 
//	ostream& operator << (ostream& s,  EST_TKVL< int , EST_IList > const &l) {EST_Litem *p; for (p = l.list.head(); p ; p = p->next()) s << l.list(p).k << "\t" << l.list(p).v << endl; return s;} 
        Instantiate_TIterator_T(KVL_int_EST_IList_t, KVL_int_EST_IList_t::IPointer_k, int, KVL_int_EST_IList_kitt) 
        Instantiate_TStructIterator_T(KVL_int_EST_IList_t, KVL_int_EST_IList_t::IPointer, KVI_int_EST_IList_t, KVL_int_EST_IList_itt) 
        Instantiate_TIterator_T(KVL_int_EST_IList_t, KVL_int_EST_IList_t::IPointer, KVI_int_EST_IList_t, KVL_int_EST_IList_itt) 

	  // Instantiate_TList(KVI_int_EST_IList_t)

	template class EST_TList< TLIST_KVI_int_EST_IList_t_VAL >; 
	template class EST_TItem< TLIST_KVI_int_EST_IList_t_VAL >; 
	template const char *error_name(EST_TList< KVI_int_EST_IList_t > val); 

        Instantiate_TIterator_T( EST_TList<KVI_int_EST_IList_t>, EST_TList<KVI_int_EST_IList_t>::IPointer, KVI_int_EST_IList_t, TList_KVI_int_EST_IList_t_itt);


#endif

typedef EST_TList<EST_WFST_MultiState *> Agenda;

static enum wfst_state_type intersect_state_type(wfst_list &wl,
						 EST_WFST_MultiState *ms);
static int check_distinguished(const EST_WFST &nmwfst,
			       int p, int q,
			       wfst_marks &marks,
			       wfst_assumes &assumptions);

void EST_WFST_MultiState::add(int i)
{
    // If of set type only add it if its not already there
    EST_Litem *p;

    if (p_type == wfst_ms_set)
	for (p=head(); p != 0; p=p->next())
	{
	    if ((*this)(p) == i)
		return;
	    else if (i < (*this)(p))  // keep the list ordered 
	    {
		insert_before(p,i);
		return;
	    }
	}

    append(i);
}

int multistate_index(EST_WFST_MultiStateIndex &index,
		     EST_WFST_MultiState *ms,int proposed) 
{
    // Returns proposed if ms is not already in index, otherwise
    // returns the value that was proposed when it was first new.

    // I'll have to make this more efficient in future.
    EST_String istring("");
    EST_Litem *p;
    int ns,found;

    for (p=ms->head(); p != 0; p = p->next())
	istring += itoString((*ms)(p)) + " ";

    ns = index.val(istring,found);
    if (found)
	return ns;
    else
    {
        index.add_item(istring,proposed);
	return proposed;
    }
}

static int pair_check(EST_THash<int,int> &pairs_done, int i, int o, int odim)
{
    int p;
    int found;

    p = (i*odim)+o;  // unique number representing i/o pair

    pairs_done.val(p,found);
    if (!found)
    {   // first time seeing this pair
	pairs_done.add_item(p,1);
	return 0;
    }
    return 1;

}

void EST_WFST::determinize(const EST_WFST &ndwfst)
{
    // Determinise a non-deterministic WFST
    EST_WFST_MultiState *start_state,*nms,*current;
    int ns;
    Agenda multistate_agenda;
    EST_WFST_MultiStateIndex index(100);
    int i,o, new_name;
    int c=0;
    EST_Litem *sp, *tp;

    clear();
    p_in_symbols.copy(ndwfst.p_in_symbols);
    p_out_symbols.copy(ndwfst.p_out_symbols);

    // Create a starting state and add it to this WFST
    start_state = new EST_WFST_MultiState(wfst_ms_set);
    start_state->add(ndwfst.start_state());
    ndwfst.add_epsilon_reachable(start_state);
    
    p_start_state = add_state(ndwfst.ms_type(start_state));
    start_state->set_name(p_start_state);

    multistate_agenda.append(start_state);  // initialize agenda

    while (multistate_agenda.length() > 0)
    {
	EST_THash<int,int> pairs_done(100);
	current = multistate_agenda.first();
	multistate_agenda.remove(multistate_agenda.head());
	if ((c % 100) == 99)
	    cout << "Determinizing " << summary() << " Agenda " 
		<< multistate_agenda.length() << endl;
	c++;

	for (sp=current->head(); sp != 0; sp=sp->next())
	{
	    const EST_WFST_State *s = ndwfst.state((*current)(sp));
	    for (tp=s->transitions.head(); tp != 0; tp = tp->next())
	    {
		i = s->transitions(tp)->in_symbol();
		o = s->transitions(tp)->out_symbol();
		// Need to check if i/o has already been proposed
		if (pair_check(pairs_done,i,o,p_out_symbols.length()) == 1)
		    continue;  // already prosed those
//	for (i=0; i < p_in_symbols.length(); i++)
//	{   // start at 2 to skip any and epsilon characters -- hmm bad
//	    for (o=0; o < p_out_symbols.length(); o++)
//	    {
		if ((i==o) && (i==0)) 
		    continue;  // don't deal here with epsilon transitions
		nms = apply_multistate(ndwfst,current,i,o);
		if ((nms->length() == 0) ||
		    (ndwfst.ms_type(nms) == wfst_error))
		{
		    delete nms;
		    continue;    // no state to go to
		}
		new_name = multistate_index(index,nms,p_num_states);
		if (new_name == p_num_states)  // genuinely new
		{   // create a real state and add it to the agenda
		    ns = add_state(ndwfst.ms_type(nms));
		    nms->set_name(ns);
		    multistate_agenda.append(nms);  
		}
		else
		{
		    nms->set_name(new_name);
		    delete nms;
		}

		// Add new transition to current state
		p_states[current->name()]
		    ->add_transition(nms->weight(),
				     nms->name(),
				     i,o);
		
	    }
	}
	delete current;

	// Probably want some progress summary
    }

}

EST_WFST_MultiState *EST_WFST::apply_multistate(const EST_WFST &wfst,
						EST_WFST_MultiState *ms,
						int in, int out) const
{
    // Apply in and out to ms and find all new states it becomes
    EST_Litem *p;
    EST_WFST_MultiState *new_ms = new EST_WFST_MultiState(wfst_ms_set);
    
    new_ms->clear();
    
    for (p=ms->head(); p != 0; p=p->next())
	// Add all new possible states from ms(p) given in/out
	wfst.transition_all((*ms)(p),in,out,new_ms);

    // Add epsilon reachable states from any states in multistates
    wfst.add_epsilon_reachable(new_ms);

    return new_ms;

}

enum wfst_state_type EST_WFST::ms_type(EST_WFST_MultiState *ms) const
{
    // Returns wfst_error if ms contains an error state, wfst_final
    // if there is at least one final and wfst_non_final
    EST_Litem *p;
    enum wfst_state_type r = wfst_nonfinal;

    for (p=ms->head(); p != 0; p = p->next())
	if (p_states((*ms)(p))->type() == wfst_error)
	    return wfst_error;
	else if (p_states((*ms)(p))->type() == wfst_licence)
	    // wfst_licence states are generated in KK compilation
	    r = wfst_licence;
	else if ((p_states((*ms)(p))->type() == wfst_final) &&
		 (r != wfst_licence))
	    r = wfst_final;

    if (r == wfst_licence)
	return wfst_nonfinal;
    else 
	return r;
}

void EST_WFST::transition_all(int state,
			      int in,
			      int out,
			      EST_WFST_MultiState *ms) const
{
    // Find all possible new states from state given in/out
    const EST_WFST_State *s = p_states(state);
    EST_Litem *i;

    for (i=s->transitions.head(); i != 0; i=i->next())
    {
	if ((in == s->transitions(i)->in_symbol()) &&
	    (out == s->transitions(i)->out_symbol()))
	    ms->add(s->transitions(i)->state());
    }
}

static int is_a_member(const EST_IList &ii, int i)
{
    for (EST_Litem *p=ii.head(); p != 0; p=p->next())
	if (ii(p) == i)
	    return TRUE;
    return FALSE;
}

void EST_WFST::add_epsilon_reachable(EST_WFST_MultiState *ms) const
{
    // As ms->add() adds in order we need to copy to a new list and append
    // to it any new epsilon accessible states
    EST_Litem *p;
    EST_IList ii;
    int ie = p_in_symbols.name(get_c_string(epsilon_label()));
    int oe = p_out_symbols.name(get_c_string(epsilon_label()));

    for (p=ms->head(); p != 0; p=p->next())
	ii.append((*ms)(p));

    for (p=ii.head(); p != 0; p=p->next())
    {
	const EST_WFST_State *s = p_states(ii(p));
	EST_Litem *i;

	for (i=s->transitions.head(); i != 0; i=i->next())
	{
	    if ((ie == s->transitions(i)->in_symbol()) &&
		(oe == s->transitions(i)->out_symbol()))
	    {
		// Add to end of ii if not already there
		int nstate = s->transitions(i)->state();
		if (!is_a_member(ii,nstate));
		{
		    ii.append(nstate);
		    ms->add(nstate); // gets added in order
		}
	    }
	}
    }
}

/************************************************************************/
/*  Intersection of a list of transducers, i.e. what is accepted by all */
/************************************************************************/
void EST_WFST::intersection(wfst_list &wl)
{
    // This is very similar to determinisation, similar complexity too
    EST_WFST_MultiState *start_state = new EST_WFST_MultiState(wfst_ms_list);
    EST_WFST_MultiState *nms,*current;
    int ns;
    Agenda multistate_agenda;
    EST_WFST_MultiStateIndex index(100);
    int i,o, new_name, n;
    EST_Litem *p,*q;
    int c=0;

    // Initialize this WFST from the given ones
    clear();
    p_in_symbols.copy(wl.first().p_in_symbols);
    p_out_symbols.copy(wl.first().p_out_symbols);

    // Determinize each input WFST and make a new start state consisting of 
    // the start states of each of the input WFSTs
    for (p=wl.tail(); p != 0; p=p->prev())
    {
	if (!wl(p).deterministic())
	{
	    cout << "...intersection deterministing" << endl;
	    EST_WFST tt = wl(p);
	    wl(p).determinize(tt);
	}
	start_state->add(wl(p).start_state());
    }
    
    p_start_state = add_state(intersect_state_type(wl,start_state));
    // Label multistate start start with single-state name
    start_state->set_name(p_start_state);

    multistate_agenda.append(start_state);  // initialize agenda

    while (multistate_agenda.length() > 0)
    {
	current = multistate_agenda.first();
	multistate_agenda.remove(multistate_agenda.head());
	if ((c % 100) == 99)
	    cout << "Intersection " << summary() << " Agenda " 
		<< multistate_agenda.length() << endl;
	c++;

	// For all possible in/out pairs
	for (i=0; i < p_in_symbols.length(); i++)
	{   // start at 2 to skip any and epsilon characters -- hmm bad
	    for (o=0; o < p_out_symbols.length(); o++)
	    {
		if ((i==o) && (i==0)) // shouldn't be epsilon/epsilon here 
		    continue;
		nms = new EST_WFST_MultiState(wfst_ms_list);
		// Increment multistate to new multistate for each individual
		// state using each WFST
		for (n=0,p=wl.head(),q=current->head(); 
		     (p != 0) && (q != 0);
		     p=p->next(),q=q->next(),n++)
		    nms->add(wl(p).transition((*current)(q),i,o));
		if (intersect_state_type(wl,nms) == wfst_error)
		{
		    delete nms;
		    continue;    // no state to go to
		}
		new_name = multistate_index(index,nms,p_num_states);
		if (new_name == p_num_states)  // genuinely new and unseen
		{   // create a real state and add it to the agenda
		    ns = add_state(intersect_state_type(wl,nms));
		    nms->set_name(ns);
		    multistate_agenda.append(nms);  
		}
		else  // already seen this state, and is already named
		{
		    nms->set_name(new_name);
		    delete nms;
		}

		// Add new transition to current state
		p_states[current->name()]
		    ->add_transition(nms->weight(),nms->name(),i,o);
	    }
	}
	delete current;
	// Probably want some progress summary
    }

}

static enum wfst_state_type intersect_state_type(wfst_list &wl,
						 EST_WFST_MultiState *ms)
{
    // Find the state type of the combined states
    // If any are error, return error, if one is nonfinal return nonfinal
    // otherwise its final
    EST_Litem *p,*q;
    enum wfst_state_type r = wfst_final;

    for (p=wl.head(),q=ms->head(); 
	 (p != 0) && (q != 0); 
	 p=p->next(),q=q->next())
    {
	if ((*ms)(q) == WFST_ERROR_STATE)
	    return wfst_error;

	enum wfst_state_type dd = wl(p).state((*ms)(q))->type();

	if (dd == wfst_error)
	    return wfst_error;
	else if (dd == wfst_nonfinal)
	    r = wfst_nonfinal;
    }
    return r;
}

void EST_WFST::intersection(const EST_WFST &a, const EST_WFST &b)
{
    // Intersect two WFSTs
    wfst_list wl;

    wl.append(a);
    wl.append(b);
    
    intersection(wl);
}

/*******************************************************************/
/*  Minimization is of complexity of O(n^2)                        */
/*******************************************************************/
void EST_WFST::minimize(const EST_WFST &nmwfst)
{
    // Minimize a WFST
    int p,q;
    wfst_marks marks(nmwfst.num_states());
    wfst_assumes assumptions;

    //  For each combination of states
    for (p=0; p < nmwfst.num_states()-1; p++)
	for (q=p+1; q < nmwfst.num_states(); q++)
	    check_distinguished(nmwfst,p,q,marks,assumptions);

    // The marked array now has all different and lists to equivalent states
    // Build an array mapping old name to new name.
    int num_new_states;
    int i;
    EST_IVector state_map;

    marks.find_state_map(state_map,num_new_states);

    // Build the new minimized WFST mapping existing transitions
    clear();
    p_in_symbols.copy(nmwfst.p_in_symbols);
    p_out_symbols.copy(nmwfst.p_out_symbols);

    init(num_new_states);
    p_start_state = state_map(nmwfst.p_start_state);

    for (i=0; i < nmwfst.num_states(); i++)
    {
	if (p_states[state_map(i)] == 0)
	    p_states[state_map(i)] = 
		copy_and_map_states(state_map,nmwfst.state(i),nmwfst);
    }

}

static int check_distinguished(const EST_WFST &nmwfst,
			       int p, int q,
			       wfst_marks &marks,
			       wfst_assumes &assumptions)
{
    // Check to see if these two are equivalent
    EST_Litem *t;
    EST_IList from_p,from_q;
    
    if (marks.distinguished(p,q))   // been here, done that
	return TRUE;
    else if (marks.undistinguished(p,q)) // been here too
	return FALSE;
    // Not been here yet so do some work to try to find out if
    // these states can be distinguished
    else if ((nmwfst.state(p)->type() != nmwfst.state(q)->type()) ||
	     (nmwfst.state(p)->num_transitions() != 
	      nmwfst.state(q)->num_transitions()))
    {	// Different final/non-final type or different number
	// of transitions so obviously different states
	marks.distinguish(p,q);
	return TRUE;
    }
    else 
    {   // Have to check their transitions individually
	for (t=nmwfst.state(p)->transitions.head(); t != 0; t=t->next())
	{
	    int in = nmwfst.state(p)->transitions(t)->in_symbol();
	    int out = nmwfst.state(p)->transitions(t)->out_symbol();
	    int y = nmwfst.state(p)->transitions(t)->state();
	    int z = nmwfst.transition(q,in,out);
	    if ((z == WFST_ERROR_STATE) || 
		(marks.distinguished(y,z)))
	    {   // no equiv transition or obviously different states
		marks.distinguish(p,q);
		return TRUE;
	    }
	    else if (equivalent_to(y,z,assumptions))
		continue;
	    else   // Potential equivalence, record y,z for later
	    {
		from_p.append(y);
		from_q.append(z);
	    }
	}
	// All transitions had potential match so only now
	// actually check their follow sets
	EST_Litem *yp, *zp;
	int tl = FALSE;
	if (assumptions.length() == 0)
	    tl = TRUE;
	// assume they are undistinguished
	add_assumption(p,q,assumptions);
	for (yp=from_p.head(),zp=from_q.head(); 
	     yp != 0; yp=yp->next(),zp=zp->next())
	    if (check_distinguished(nmwfst,from_p(yp),from_q(zp),
				    marks,
				    assumptions))
	    {
		marks.distinguish(p,q);  // set the distinguished
		assumptions.clear();
		return TRUE;
	    }
	// ok I give up, they are the same
	if (tl)
	{   // This is equivalent given the assumptions (and no
	    // higher level assumptions) so we can mark these states
	    // as undistinguished (and all the assumptions)
	    mark_undistinguished(marks,assumptions);
	    assumptions.clear();
	}
	return FALSE;
    }
}

void EST_WFST::extend_alphabets(const EST_WFST &b)
{
    // Extend current in/out alphabets to accommodate anything in b's
    // that are not in a's
    // This guarantees that the number in this will still be valid
    EST_StrList ivocab, ovocab;
    int i;
    
    for (i=0; i<p_in_symbols.length(); i++)
 	ivocab.append(in_symbol(i));
    for (i=0; i<b.p_in_symbols.length(); i++)
	if (!strlist_member(ivocab,b.in_symbol(i)))
	    ivocab.append(b.in_symbol(i));
    for (i=0; i<p_out_symbols.length(); i++)
	ovocab.append(out_symbol(i));
    for (i=0; i<b.p_out_symbols.length(); i++)
	if (!strlist_member(ovocab,b.out_symbol(i)))
	    ovocab.append(b.out_symbol(i));

    p_in_symbols.init(ivocab);
    p_out_symbols.init(ovocab);
}

EST_WFST_State *EST_WFST::copy_and_map_states(const EST_IVector &state_map,
					      const EST_WFST_State *s,
					      const EST_WFST &b) const
{
    // Copy s into new state mapping new states to those in state map
    EST_WFST_State *ns = new EST_WFST_State(state_map(s->name()));
    EST_Litem *i;

    ns->set_type(s->type());

    for (i=s->transitions.head(); i != 0; i=i->next())
    {
	int mapped_state= state_map(s->transitions(i)->state());
	if (mapped_state != WFST_ERROR_STATE)
	    ns->add_transition(s->transitions(i)->weight(),
		    mapped_state,
		    in_symbol(b.in_symbol(s->transitions(i)->in_symbol())),
		    out_symbol(b.out_symbol(s->transitions(i)->out_symbol())));
    }

    return ns;
}

/***********************************************************************/
/* Build a WFST which doesn't accept any of the strings that a accepts */
/* This keeps the same in/out alphabet                                 */
/***********************************************************************/
void EST_WFST::complement(const EST_WFST &a)
{
    int i;

    copy(a);  

    for (i=0; i < num_states(); i++)
    {
	if (p_states[i]->type() == wfst_final)
	    p_states[i]->set_type(wfst_nonfinal);
	else if (p_states[i]->type() == wfst_nonfinal)
	    p_states[i]->set_type(wfst_final);
	// errors remain errors
    }
}

static int noloopstostart(const EST_WFST &a)
{
    // TRUE if there are no transitions leading to the start state
    // when this is true there is a union operation which preserves
    // deterministicness
    int i;

    for (i=0; i < a.num_states(); i++)
    {
	const EST_WFST_State *s = a.state(i);
	EST_Litem *p;
	for (p=s->transitions.head(); p != 0; p=p->next())
	{
	    if (s->transitions(p)->state() == a.start_state())
		return FALSE;
	}
    }
    return TRUE;
}

int EST_WFST::deterministiconstartstates(const EST_WFST &a, const EST_WFST &b) const
{
    // TRUE if there are no common transition labels from a and b's
    // start state
    EST_IMatrix tab;
    int in,out;

    tab.resize(a.p_in_symbols.length(),a.p_out_symbols.length());
    tab.fill(0);

    for (EST_Litem *t=a.state(a.start_state())->transitions.head();
	 t != 0; t=t->next())
    {
	tab(a.state(a.start_state())->transitions(t)->in_symbol(),
	    a.state(a.start_state())->transitions(t)->out_symbol()) = 1;
    }

    for (EST_Litem *tt=b.state(b.start_state())->transitions.head();
	 tt != 0; tt=tt->next())
    {
	in = a.in_symbol(b.in_symbol(b.state(b.start_state())->transitions(tt)->in_symbol()));
	out = a.out_symbol(b.out_symbol(b.state(b.start_state())->transitions(tt)->out_symbol()));
	if (in == -1) 
	    continue;  // obviously not a clash
	else if (out == -1) 
	    continue;  // obviously not a clash
	else if (tab(in,out) == 1)
	    return FALSE;
    }
    return TRUE;
}

/***********************************************************************/
/* Build a WFST which accepts both strings of a and of b               */
/***********************************************************************/
void EST_WFST::uunion(const EST_WFST &a,const EST_WFST &b)
{
    EST_IVector smap;
    int i;

    copy(a);
    extend_alphabets(b);

    if (a.deterministic() && b.deterministic() &&
	noloopstostart(a) && noloopstostart(b) &&
	deterministiconstartstates(a,b))
    {
	// This does the union without the epsilon and will preserve
	// deterministic wfsts in this special case
	smap.resize(b.num_states());
	smap[0] = start_state();
	for (i=1; i < b.num_states(); ++i)
	    smap[i] = i+a.num_states()-1;

	more_states(a.num_states()+b.num_states()-1);
	p_num_states += b.num_states()-1;
	for (i=1; i < b.num_states(); i++)
	    p_states[smap(i)] = copy_and_map_states(smap,b.state(i),b);

	const EST_WFST_State *s = b.state(b.start_state());
	EST_Litem *p;
	for (p=s->transitions.head(); p != 0; p=p->next())
	{
	    int mapped_state= smap(s->transitions(p)->state());
	    if (mapped_state != WFST_ERROR_STATE)
		p_states[start_state()]->
		 add_transition(s->transitions(p)->weight(),
		   mapped_state,
		   in_symbol(b.in_symbol(s->transitions(p)->in_symbol())),
		   out_symbol(b.out_symbol(s->transitions(p)->out_symbol())));
	}
    }
    else
    {   // do it the hard way
	smap.resize(b.num_states());
	for (i=0; i < b.num_states(); ++i)
	    smap[i] = i+a.num_states();

	more_states(a.num_states()+b.num_states());
	p_num_states += b.num_states();
	for (i=0; i < b.num_states(); i++)
	    p_states[smap(i)] = copy_and_map_states(smap,b.state(i),b);

	// Actually do the union bit by adding an epsilon transition from
	// the start of a to start state of b
	p_states[start_state()]->add_transition(0.0,smap[b.start_state()],
						in_epsilon(), out_epsilon());
    }

}

/***********************************************************************/
/* Build a WFST which a followed by b                                  */
/***********************************************************************/
void EST_WFST::concat(const EST_WFST &a,const EST_WFST &b)
{
    EST_IVector smap;
    int i;

    copy(a);  
    extend_alphabets(b);

    smap.resize(b.num_states());
    for (i=0; i < b.num_states(); ++i)
	smap[i] = i+a.num_states();

    more_states(a.num_states()+b.num_states());

    // everything final in a becomes non final and an epsilon transition
    // goes from them to the start of b
    for (i=0; i < num_states(); i++)
    {
	if (p_states[i]->type() == wfst_final)
	{
	    p_states[i]->set_type(wfst_nonfinal);
	    p_states[i]->add_transition(0.0,smap[b.start_state()],
					in_epsilon(), out_epsilon());
	}
    }

    p_num_states += b.num_states();
    for (i=0; i < b.num_states(); i++)
	p_states[smap(i)] = copy_and_map_states(smap,b.state(i),b);

}

/***********************************************************************/
/* Build a WFST from composing a and b (feeding output of a to         */
/* input of b)                                                         */
/***********************************************************************/
void EST_WFST::compose(const EST_WFST &a,const EST_WFST &b)
{
    EST_WFST_MultiState *start_state = new EST_WFST_MultiState(wfst_ms_list);
    EST_WFST_MultiState *nms,*current;
    Agenda multistate_agenda;
    EST_WFST_MultiStateIndex index(100);
    wfst_list wl;
    EST_WFST t;
    int i,new_name;
    EST_Litem *p,*q;

    clear();
    p_in_symbols.copy(a.p_in_symbols);
    p_out_symbols.copy(b.p_out_symbols);

    // Unfortunately need to needlessly copy a and b here
    wl.append(a);
    start_state->add(a.start_state());
    wl.append(b);
    start_state->add(b.start_state());

    p_start_state = add_state(intersect_state_type(wl,start_state));
    // Label multistate start start with single-state name
    start_state->set_name(p_start_state);

    multistate_agenda.append(start_state);  // initialize agenda

    while (multistate_agenda.length() > 0)
    {
	current = multistate_agenda.first();
	multistate_agenda.remove(multistate_agenda.head());

	// For all possible in/out pairs
	for (i=0; i < p_in_symbols.length(); i++)
	{   // start at 2 to skip any and epsilon characters -- hmm bad
	    // find transitions
	    wfst_translist transa;

	    wl.first().transduce(current->first(),i,transa);
	    for (p=transa.head(); p != 0; p=p->next())
	    {
		wfst_translist transb;
		// feed a's out to b'is in
		wl.last().transduce(
                          current->last(),
			  b.in_symbol(a.out_symbol(transa(p)->out_symbol())),
			  transb);
		for (q = transb.head(); q != 0; q=q->next())
		{
		    nms = new EST_WFST_MultiState(wfst_ms_list);
		    nms->add(transa(p)->state());
		    nms->add(transb(q)->state());
		    
		    if (intersect_state_type(wl,nms) == wfst_error)
		    {
			delete nms;
			continue;    // no state to go to
		    }
		    new_name = multistate_index(index,nms,p_num_states);
		    if (new_name == p_num_states)  // genuinely new and unseen
		    {   // create a real state and add it to the agenda
			int ns = add_state(intersect_state_type(wl,nms));
			nms->set_name(ns);
			multistate_agenda.append(nms);  
		    }
		    else  // already seen this state, and is already named
			nms->set_name(new_name);

		    // Add new transition to current state
		    p_states[current->name()]
			->add_transition(nms->weight(),nms->name(),
					 i,transb(q)->out_symbol());
		    
		}
		
	    }
	}
	delete current;
	// Probably want some progress summary
    }

}

/***********************************************************************/
/* Build a WFST which accepts strings in a but not in b                */
/***********************************************************************/
void EST_WFST::difference(const EST_WFST &a,const EST_WFST &b)
{
    EST_WFST compb;

    // This is sort of a complement, but not quite
    // But what would the name of this operation be?
    compb.copy(b);
    for (int i=0; i < compb.num_states(); i++)
    {
	if (compb.p_states[i]->type() == wfst_final)
	    compb.p_states[i]->set_type(wfst_error);
    }

    uunion(a,compb);
}

/***********************************************************************/
/* Remove states from which a final state can't be reached             */
/***********************************************************************/
void EST_WFST::remove_error_states(const EST_WFST &a)
{
    // Find all states which are reachable from the start state, and
    // can reach a final state.  Mark all others as error states
    wfst_list wl;

    wl.append(a);
    EST_WFST &ab = wl.first();

    ab.current_tag = ++traverse_tag;
    for (int i=0; i < ab.p_num_states; i++)
	ab.can_reach_final(i);
    // This will copy only the non-error states
    intersection(wl);

}

int EST_WFST::can_reach_final(int state)
{
    // Return TRUE iff this state is final or can reach a final state

    if (p_states[state]->type() == wfst_final)
	return TRUE;
    else if (p_states[state]->type() == wfst_error)
	return FALSE;
    else if (p_states[state]->tag() == current_tag)  
	// Been here and it is reachable
	return TRUE;
    else
    {
	EST_Litem *i;
	enum wfst_state_type current_val = p_states[state]->type();
	enum wfst_state_type r = wfst_error;
	// temporarily set this to error to stop infinite recursion
	p_states[state]->set_type(wfst_error);

	for (i=p_states[state]->transitions.head(); i != 0; i=i->next())
	    // if any transition goes to something that reaches a final state
	    // set the value back to its original
	    if (can_reach_final(p_states[state]->transitions(i)->state()))
		r = current_val;

	// Will be set back to original value iff a final state
	// is reachable from here
	p_states[state]->set_type(r);
	if (r == wfst_error)
	    return FALSE;
	else
	{
	    p_states[state]->set_tag(current_tag);
	    return TRUE;
	}
    }
}

/***********************************************************************/
/* True is wfst is deterministic                                       */
/***********************************************************************/
int EST_WFST::deterministic() const
{
    // True if all states contains no multiple arcs with the same symbol
    EST_IMatrix tab;

    tab.resize(p_in_symbols.length(),p_out_symbols.length());

    for (int i=0; i < p_num_states; i++)
    {
	tab.fill(0);
	for (EST_Litem *t=state(i)->transitions.head(); t != 0; t=t->next())
	{
	    if (tab(state(i)->transitions(t)->in_symbol(),
		    state(i)->transitions(t)->out_symbol()) == 1)
		return FALSE;
	    else
		tab(state(i)->transitions(t)->in_symbol(),
		    state(i)->transitions(t)->out_symbol()) = 1;
	}
    }
    return TRUE;
}