/*************************************************************************/
/*                                                                       */
/*                Centre for Speech Technology Research                  */
/*                     University of Edinburgh, UK                       */
/*                      Copyright (c) 1995,1996                          */
/*                        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 :  Simon King                               */
/*                    Date   :  November 1996                            */
/*-----------------------------------------------------------------------*/
/*                   Lattice/Finite State Network                        */
/*                                                                       */
/*=======================================================================*/

#include "EST_lattice.h"
#include <fstream>
#include <cstdlib>

Lattice::Lattice()
{
    tf=NULL;
}


Lattice::~Lattice()
{

}

Lattice::Node*
Lattice::start_node()
{
    if(nodes.head() != NULL )
	return nodes(nodes.head()); 
    else{
	cerr << "LAttice has no nodes !" << endl;
	return NULL;
    }

}

#if 0
bool Lattice::build_qmap(Bigram &g, float error_margin)
{

    // very crude VQ (not vectors though)
    // works best on log bigrams ?

    // to do : automatically determine error_margin

    int i,j;
    EST_Litem *l_ptr;
    bool flag;

    // first, build a list, then transfer to array
    Tlist<float> list_qmap;

    qmap_error_margin = error_margin;

    for (i = 0; i < g.size(); ++i){
	for (j = 0; j < g.size(); ++j){
		
	    flag = false;
	    for(l_ptr=list_qmap.head();l_ptr != 0; l_ptr=l_ptr->next())
		if(fabs(list_qmap(l_ptr) - g.p(i,j)) <= error_margin){
		    flag = true;
		    break;
		}

	    if(!flag)
		list_qmap.append(g.p(i,j));
	    
	}
    }

    // special zero (within error_margin) entry, if not already there
    flag = false;
    for(l_ptr=list_qmap.head();l_ptr != 0; l_ptr=l_ptr->next())
	if(fabs(list_qmap(l_ptr)) <= error_margin){
	    flag = true;
	    break;
	}
    
    if(!flag)
	list_qmap.append(0);
    
    qsort(list_qmap);

    i=0;
    for(l_ptr=list_qmap.head();l_ptr != 0; l_ptr=l_ptr->next())
	i++;

    // transfer to array
    qmap.resize(i);
    i=0;
    for(l_ptr=list_qmap.head();l_ptr != 0; l_ptr=l_ptr->next())
	qmap(i++) = list_qmap(l_ptr);

    list_qmap.clear();


    cerr << "Built qmap with " << i << " entries" << endl;

    return true;
}


bool
Lattice::build_nmap(Bigram &g)
{


    int j;
    //name_map_entry_t entry;
    EST_Litem *l_ptr;

    // first, build a list, then transfer to array
    Tlist<EST_String> list_nmap;

    // wordlist must not have !ENTER of !EXIT in it
    for (j = 0; j < g.size() - 2; ++j){
	if(g.words(j) == "!ENTER"){
	    cerr << "Wordlist contains special word !ENTER" << endl;
	    return false;
	}
	if(g.words(j) == "!EXIT"){
	    cerr << "Wordlist contains special word !EXIT" << endl;
	    return false;
	}
    }




    // add all words
    for (j = 0; j < g.size() - 2; ++j)
	list_nmap.append(g.words(j));

    // special enter and exit
    list_nmap.append("!ENTER");
    list_nmap.append("!EXIT");

    qsort(list_nmap);

    cerr << list_nmap << endl;

    j=0;
    for(l_ptr=list_nmap.head();l_ptr != 0; l_ptr=l_ptr->next())
	j++;

    // transfer to array
    nmap.resize(j);
    j=0;
    for(l_ptr=list_nmap.head();l_ptr != 0; l_ptr=l_ptr->next())
	nmap(j++) = list_nmap(l_ptr);

    list_nmap.clear();
    cerr << "Built nmap with " << j << " entries" << endl;

    return true;
}


bool
Lattice::construct_alphabet(Bigram &g)
{

    int i,j,enteri,exiti,aindex,qindex,nindex,count;
    symbol_t *sym;
    EST_Litem *a_ptr;
    bool flag;

    if(!build_qmap(g,1.0e-02) || !build_nmap(g)) // to do : fix
	return false;


    // temporary list
    Tlist<symbol_t*> list_alphabet;

    // alphabet consists of all occurring combinations of
    // nmap and qmap entries

    enteri = g.size() - 2;
    exiti  = g.size() - 1;

    aindex=0;

    // order is this way for speed
    for (j = 0; j < g.size(); ++j){
	
	cerr << "constructing alphabet " << (int)((float)j*100/(float)g.size()) << "%     \r";
	
	if(j == enteri)
	    nindex = nmap_name_to_index("!ENTER");
	else if(j == exiti)
	    nindex = nmap_name_to_index("!EXIT");
	else
	    nindex = nmap_name_to_index(g.words(j)); // check !!
	
	for (i = 0; i < g.size(); ++i){
	    
	    qindex = qmap_value_to_index(g.p(i,j));
		  
	    // have we got sym already ?
	    flag=false;
	    for(a_ptr=list_alphabet.tail();a_ptr!=NULL;a_ptr=a_ptr->prev()){
		if( (list_alphabet(a_ptr)->nmap_index == nindex) &&
		    (list_alphabet(a_ptr)->qmap_index == qindex) ){
		    flag=true;
		    break;
		}
		
		// since words are added in order, stop
		// when we get to previous word
		if(list_alphabet(a_ptr)->nmap_index != nindex)
		    break;
	    }

	    
	    if(!flag){
		sym = new symbol_t;
		sym->qmap_index=qindex;
		sym->nmap_index=nindex;
		list_alphabet.append(sym);
	    }
	}
    }

    // special ENTER with prob of 1 symbol
    nindex = nmap_name_to_index("!ENTER");
    qindex = qmap_value_to_index(0); // log prob
    flag=false;
    for(a_ptr=list_alphabet.tail();a_ptr!=NULL;a_ptr=a_ptr->prev())
	if( (list_alphabet(a_ptr)->nmap_index == nindex) &&
	    (list_alphabet(a_ptr)->qmap_index == qindex) ){
	    flag=true;
	    break;
	}
    
    if(!flag){
	sym = new symbol_t;
	sym->qmap_index=qindex;
	sym->nmap_index=nindex;
	list_alphabet.append(sym);
    }

    // and special no-label label (e-move)
    sym = new symbol_t;
    sym->qmap_index=-1;
    sym->nmap_index=-1;
    list_alphabet.append(sym);

    ptr_qsort(list_alphabet);

    count=0;
    for(a_ptr=list_alphabet.head();a_ptr != NULL; a_ptr=a_ptr->next())
	count++;


    alphabet.resize(count);
    count=0;
    for(a_ptr=list_alphabet.head();a_ptr != NULL; a_ptr=a_ptr->next())
	alphabet(count++) = *(list_alphabet(a_ptr));
    
    // .. to do - delete syms
    list_alphabet.clear();

    e_move_symbol_index = alphabet_index_lookup(-1,-1);

    cerr << "Alphabet has " << count << " symbols                   " << endl;
    
    return true;
}


bool
Lattice::construct(Bigram &g)
{

    // every word becomes a node, every non-zero transition becomes an arc
    // eliminate any transitions into ENTER and out of EXIT
    int i,j,k;
    EST_Litem *n_ptr,*a_ptr;
    Node *n;
    Arc *a;
    Node *from,*to;
    int symbol;
    // unfortunate, but fixed in Bigram class
    int enteri = g.size() - 2;
    int exiti  = g.size() - 1;
    int from_name,to_name;
    
    // single entry node, no name since no arcs in
    // single arc out to node called "!ENTER"

    Node *enter_node = new Node;
    enter_node->name.append(-1); // no name !
    nodes.append(enter_node);

    // make nodes - one for every entry in nmap
    for(i=0; i<nmap.n(); i++){

	n = new Node;
	n->name.append(i); // index into nmap
	nodes.append(n);

	if(nmap(i) == "!ENTER"){ // temporary hack

	    symbol = alphabet_index_lookup(i,qmap_value_to_index(0)); // for log probs !!!
	    a = new Arc;
	    a->label = symbol;
	    a->to = n;
	    enter_node->arcs_out.append(a);

	}


	// keep note of final node
	if(nmap(i) == "!EXIT") // temporary hack
	    final_nodes.append(n);

    }

    // make arcs
    k=0;
    for (i = 0; i < g.size(); ++i){
	cerr << "building lattice " << (int)((float)i*100/(float)g.size()) << "%    \r";
	for (j = 0; j < g.size(); ++j){

	    // ignore any transitions into ENTER or out of EXIT
	    //if((g.p(i, j) > 0) &&  - for probs only, can't do for log probs
	    if((j != enteri) && (i != exiti)){

		// find from and to nodes
		from=NULL;
		to=NULL;

		if(i == enteri)
		    from_name = nmap_name_to_index("!ENTER");
		else
		    from_name = nmap_name_to_index(g.words(i));

		if(j == exiti)
		    to_name = nmap_name_to_index("!EXIT");
		else
		    to_name= nmap_name_to_index(g.words(j));

		for (n_ptr = nodes.head(); n_ptr != 0; n_ptr = n_ptr->next()){
		    int name = nodes(n_ptr)->name(nodes(n_ptr)->name.head());
		    if(name == from_name)
			from = nodes(n_ptr);
		    if(name == to_name)
			to = nodes(n_ptr);
		}

		if(from==NULL){
		    cerr << "Couldn't find 'from' node " << nmap_index_to_name(from_name) << endl;
		    return false;
		}
		    
		if(to==NULL){
		    cerr << "Couldn't find 'to' node " << nmap_index_to_name(to_name) << endl;
		    return false;
		}

		// get arc symbol - speed up this fn !
		symbol = alphabet_index_lookup(to_name,qmap_value_to_index(g.p(i,j)));
		if(symbol < 0){
		    cerr << "Couldn't lookup symbol in alphabet !" << endl;
		    return false;
		}
 	
		a = new Arc;
		a->label = symbol;
		a->to = to;
		
		from->arcs_out.append(a);
		

	    }
	}
    }
    cerr << "                                    \r";

    int c1=0,c2=0,c3=0;
    for(n_ptr=nodes.head();n_ptr!=NULL;n_ptr=n_ptr->next()){
	c1++;
	for(a_ptr=nodes(n_ptr)->arcs_out.head();a_ptr!=NULL; a_ptr=a_ptr->next())
	    c2++;
    }
    
    for (n_ptr = final_nodes.head(); n_ptr != 0; n_ptr = n_ptr->next())
	c3++;

    cerr << "NFA has " << c1 
	 << " nodes (" << c3 << " final)"
	 << " and " << c2 << " arcs" << endl;
    
    return true;
}
#endif

bool Lattice::determinise()
{
    // very simple, but potentially time/memory consuming

    // make a new lattice whose nodes are all permutations
    // of the nodes in the old lattice
    // BUT : only make the nodes which are actually required
    // (otherwise number of new nodes = 2^(number of old nodes)

    // we will call the old lattice NFA and the new one DFA

    EST_Litem *n_ptr,*n2_ptr,*a_ptr,*l_ptr;
    Node *new_node;
    EST_TList<Node*> new_nodes;
    EST_TList<Node*> new_final_nodes;
    EST_TList<Arc*> new_arcs;
    EST_TList<Arc*> arc_list;
    EST_TList<int> new_name;
    int c,count,current_label,new_arcs_made;
    bool is_final;

    // first, sort nodes' lists of arcs by label to make 
    // it easier
    cerr << "sorting arc lists" << endl;
    sort_arc_lists();

    cerr << "making new nodes" << endl;

    // - for every node in the NFA, look at the outgoing arcs with
    //   the same label
    // - make a DFA node which is a combination of the NFA nodes
    //   which are the destinations of those arcs

    // there are more DFA nodes made later

    // enter node is special case, it has no in-going arcs
    // so will not be made in the following loop

    // for now, assume one enter node at head of list ... hmmmmm
    new_node = new Node;
    if(new_node == NULL){
	cerr << "Could not allocate any more memory";
	return false;
    }
    new_node->name = nodes(nodes.head())->name;
    new_nodes.append(new_node);



    for (n_ptr = nodes.head(); n_ptr != 0; n_ptr = n_ptr->next()){

	for (a_ptr = nodes(n_ptr)->arcs_out.head(); a_ptr != 0; a_ptr = a_ptr->next()){

	    current_label = nodes(n_ptr)->arcs_out(a_ptr)->label;

	    // make list of arc destinations along arcs with this label
	    is_final=false;
	    new_name.clear();
	    new_name = nodes(n_ptr)->arcs_out(a_ptr)->to->name;
	    if(final(nodes(n_ptr)->arcs_out(a_ptr)->to) )
		is_final=true;
	    while((a_ptr != NULL) &&
		  (a_ptr->next() != NULL) &&
		  (nodes(n_ptr)->arcs_out(a_ptr->next())->label == current_label)){
		merge_sort_unique(new_name,nodes(n_ptr)->arcs_out(a_ptr->next())->to->name);

		if( !is_final && final(nodes(n_ptr)->arcs_out(a_ptr->next())->to) )
		    is_final=true;

		a_ptr=a_ptr->next();

	    }

	    // make new node with this name, unless we already have one
	    bool flag=false;
	    for (n2_ptr = new_nodes.head(); n2_ptr != 0; n2_ptr = n2_ptr->next())
		if( new_nodes(n2_ptr)->name == new_name ){
		    flag=true;
		    break;
		}
	    
	    if(!flag){ // need to make new node

		new_node = new Node;
		if(new_node == NULL){
		    cerr << "Could not allocate any more memory";
		    count=0;
		    for (n2_ptr = new_nodes.head(); n2_ptr != 0; n2_ptr = n2_ptr->next())
			count++;
		    cerr << " after making " << count << " nodes" << endl;
		    return false;
		}

		new_node->name = new_name;
		new_nodes.append(new_node);

		if(is_final)
		    new_final_nodes.append(new_node);
	    }

	}  // loop round outgoing arcs for this node
	
    } // loop round NFA nodes
    

    // now, for every node in the DFA, its 'transition function' (i.e. outgoing arcs)
    // is the sum of the transition functions of its constituent nodes from
    // the NFA

    c=0;
    new_arcs_made=0;
    for (n_ptr = new_nodes.head(); n_ptr != 0; n_ptr = n_ptr->next()){

	c++;
	cerr << "Processing node " << c
	     << "  arcs=" << new_arcs_made << "       \r";

	// find constituent nodes in NFA (only works if NFA names are single ints !)
	arc_list.clear();
	for(l_ptr=new_nodes(n_ptr)->name.head(); l_ptr != 0; l_ptr = l_ptr->next()){

	    for(n2_ptr = nodes.head(); n2_ptr != 0; n2_ptr = n2_ptr->next()){
		
		if(nodes(n2_ptr)->name(nodes(n2_ptr)->name.head()) ==
		   new_nodes(n_ptr)->name(l_ptr))
 		    arc_list += nodes(n2_ptr)->arcs_out;


	    }
	}

	// now we have a list of all the NFA nodes we can 'get to'
	// from this DFA node, sort by label and find the
	// DFA node for each label

	// or rather, take the arc list from above, and collapse
	// all arcs with the same label into one arc to the DFA
	// node which is the equivalent of the NFA nodes at the
	// end of those arcs

	sort_by_label(arc_list);

	for(a_ptr=arc_list.head();a_ptr!=NULL;a_ptr=a_ptr->next()){

	    current_label=arc_list(a_ptr)->label;
	    //cerr << " label " << current_label;

	    is_final=false;
	    EST_TList<int> new_name2;
	    new_name2 = arc_list(a_ptr)->to->name;
	    if(final(arc_list(a_ptr)->to) )
		is_final=true;
	    while((a_ptr != NULL) &&
		  (a_ptr->next() != NULL) &&
		  (arc_list(a_ptr->next())->label == current_label)){
		merge_sort_unique(new_name2,arc_list(a_ptr)->to->name);
		if( !is_final && final(arc_list(a_ptr)->to) )
		    is_final=true;
		a_ptr=a_ptr->next();
	    }

	    //cerr << " -> " << new_name2;

	    // find DFA node with that name
	    bool flag=false;
	    for (n2_ptr = new_nodes.head(); n2_ptr != 0; n2_ptr = n2_ptr->next())
		if( new_nodes(n2_ptr)->name == new_name2 ){
		    flag=true;
		    break;
		}
	    
	    if(!flag){ // failed to make node previously, do it now
		new_node = new Node;
		if(new_node == NULL){
		    cerr << "Could not allocate any more memory";
		    count=0;
		    for (n2_ptr = new_nodes.head(); n2_ptr != 0; n2_ptr = n2_ptr->next())
			count++;
		    cerr << " after making " << count << " nodes" << endl;
		    return false;
		}

		new_node->name = new_name2;
		new_nodes.append(new_node);
		link(new_nodes(n_ptr),new_node,current_label);

		if(is_final)
		    new_final_nodes.append(new_node);

	    }else{

		link(new_nodes(n_ptr),new_nodes(n2_ptr),current_label);

	    }

		new_arcs_made++;
	}


    } // loop round DFA nodes

    cerr << endl;

    // delete old nodes, and replace with new nodes
    for (n_ptr = nodes.head(); n_ptr != 0; n_ptr = n_ptr->next())
	delete nodes(n_ptr);
    nodes.clear();
    nodes=new_nodes;
    new_nodes.clear();

    final_nodes.clear();
    final_nodes=new_final_nodes;
    new_final_nodes.clear();

    int c1=0,c2=0,c3=0;
    for(n_ptr=nodes.head();n_ptr!=NULL;n_ptr=n_ptr->next()){
	c1++;
	for(a_ptr=nodes(n_ptr)->arcs_out.head();a_ptr!=NULL; a_ptr=a_ptr->next())
	    c2++;
    }
    
    for (n_ptr = final_nodes.head(); n_ptr != 0; n_ptr = n_ptr->next())
	c3++;

    cerr << "DFA has " << c1 
	 << " nodes (" << c3 << " final)"
	<< " and " << c2 << " arcs" << endl;


    return true;
}

bool
Lattice::link(Node *n1, Node *n2, int label)
{

    //if(l==NULL)
    //l=&arcs;

    // create arc between two nodes
    // in direction n1,n2 
    Arc *new_arc;

    if( (n1==NULL) || (n2==NULL) ){
	cerr << "Can't link null nodes" << endl;
	return false;
    }
	


    new_arc = new Arc;
    //new_arc->from = n1;
    new_arc->to = n2;
    new_arc->label = label;

    n1->arcs_out.append(new_arc);
    //n2->arcs_in.append(new_arc);
    //l->append(new_arc);

    return true;
}

void
Lattice::sort_arc_lists()
{
    EST_Litem *n_ptr;

    for (n_ptr = nodes.head(); n_ptr != 0; n_ptr = n_ptr->next()){
	
	// can't sort nodes(n_ptr)->arcs_out directly
	// since it is a list of pointers

	sort_by_label(nodes(n_ptr)->arcs_out);

    }

}

void
sort_by_label(EST_TList<Lattice::Arc*> &l){
    ptr_qsort(l);
}


bool
Lattice::build_distinguished_state_table(bool ** &dst)
{

    int i,j;
    EST_Litem *n_ptr,*n2_ptr;

    int num_nodes = nodes.length();
    // not every element will be used
    dst = new bool*[num_nodes];
    if(dst==NULL){
	cerr << "Not enough memory" << endl;
	return false;
    }
    for(i=0;i<num_nodes;i++){
	dst[i] = new bool[num_nodes];
	if(dst[i]==NULL){
	    cerr << "Not enough memory" << endl;
	    return false;
	}
	for(j=0;j<num_nodes;j++)
	    dst[i][j] = false;

    }

    cerr << "final/non-final scan";
    // any final/non-final (or non-final/final) pairs are distinguished immediately
    for(i=0,n_ptr=nodes.head();n_ptr->next()!=NULL;n_ptr=n_ptr->next(),i++){
	for(j=i+1,n2_ptr=n_ptr->next();n2_ptr!=NULL;n2_ptr=n2_ptr->next(),j++){
	    
	    if(final(nodes(n_ptr)) && !final(nodes(n2_ptr)))
		dst[i][j] = true;
	    else if(!final(nodes(n_ptr)) && final(nodes(n2_ptr)))
		dst[i][j] = true;
	    
	}
    }
    cerr << "\r                        \r";

    // two possible methods, depending on network representation
    // for sparse networks, use actual nodes and their lists of arcs
    //build_distinguished_state_table_direct(dst);
    
    // for dense networks, use a transition function matrix
    // which will be faster but more memory consuming

    if(!build_transition_function()){
	cerr << "Couldn't build transition function" << endl;
	return false;
    }

    if(!build_distinguished_state_table_from_transition_function(dst)){
	cerr << "Couldn't build dst from transition function" << endl;
	return false;
    }

    // delete tf, since it will be wrong for minimised net
    for(i=0;i<num_nodes;i++)
	delete [] tf[i];
    delete [] tf;
    tf=NULL;

    return true;
}

bool
Lattice::build_distinguished_state_table_direct(bool ** &dst)
{

    int i,j,i1,j1,scan_count,this_symbol;
    EST_Litem *n_ptr,*n2_ptr,*a_ptr,*s_ptr;
    bool flag,flag2;

    // carry out repeated scans of the distinguished state table until no more
    // cells are set true

    flag=true;
    scan_count=0;
    while(flag){
	flag=false;

	scan_count++;

	for(i=0,n_ptr=nodes.head();n_ptr->next()!=NULL;n_ptr=n_ptr->next(),i++){
	    
	    for(j=i+1,n2_ptr=n_ptr->next();n2_ptr!=NULL;n2_ptr=n2_ptr->next(),j++){
		
		cerr << "scan " << scan_count << " : " << i << "," << j << "     \r";

		if(!dst[i][j]){

		    // go through alphabet, or rather just those symbols
		    // occurring on the arcs out of this pair of nodes
		    
		    flag2=true;
		    s_ptr=nodes(n_ptr)->arcs_out.head();
		    while(s_ptr != NULL){


			if(flag2){ // we are going through symbols on arcs out of 'nodes(n_ptr)'
			    this_symbol=nodes(n_ptr)->arcs_out(s_ptr)->label;
			    i1 = node_index(nodes(n_ptr)->arcs_out(s_ptr)->to);

			    j1=-1;
			    for(a_ptr=nodes(n2_ptr)->arcs_out.head();
				a_ptr!=NULL; a_ptr=a_ptr->next())
				if(nodes(n2_ptr)->arcs_out(a_ptr)->label == this_symbol)
				    j1 = node_index(nodes(n2_ptr)->arcs_out(a_ptr)->to);

			}else{ // we are going through symbols on arcs out of 'nodes(n2_ptr)'
			    this_symbol=nodes(n2_ptr)->arcs_out(s_ptr)->label;
			    j1 = node_index(nodes(n2_ptr)->arcs_out(s_ptr)->to);

			    i1=-1;
			    for(a_ptr=nodes(n_ptr)->arcs_out.head();
				a_ptr!=NULL; a_ptr=a_ptr->next())
				if(nodes(n_ptr)->arcs_out(a_ptr)->label == this_symbol)
				    i1 = node_index(nodes(n_ptr)->arcs_out(a_ptr)->to);
			}


			// States (nodes) are distinguished if, for any symbol, they
			// have transitions (arcs) to a pair of distinguished states.
			// This includes the case where, for any symbol, one state
			// has a transition and the other does not

			if(   ( (i1>=0) && (j1>=0) && dst[i1][j1]) ||
			      ( (i1>=0) && (j1<0) ) ||
			      ( (j1>=0) && (i1<0) )     )
			    {
				dst[i][j] = true;
				flag=true;
				break; // out of s_ptr loop
				
			    }

			s_ptr=s_ptr->next();
			if( (s_ptr==NULL) && (flag2) ){ // now go down second list
			    s_ptr=nodes(n2_ptr)->arcs_out.head();
			    flag2=false;
			}
			
		    }
		}
	    }
	}
    }

    return true;
}

bool
Lattice::build_distinguished_state_table_from_transition_function(bool ** &dst)
{
    int i,j,i2,j2,k,scan_count;
    int num_nodes = nodes.length();
    int num_symbols = alphabet.n();
    bool flag;

    flag=true;
    scan_count=0;
    while(flag){
	flag=false;
	
	scan_count++;
	
	for(i=0;i<num_nodes-1;i++){

	    cerr << "scan " << scan_count << " : row "
		 << i << "   \r";
	    
	    for(j=i+1;j<num_nodes;j++){
		
		if( !dst[i][j] ){
		    
		    for(k=0;k<num_symbols;k++){
			
			i2 = tf[i][k];
			j2 = tf[j][k];
			
			if((i2<0) && (j2>=0)){
			    dst[i][j] = true;
			    flag=true;
			    break;

			}else if((j2<0) && (i2>=0)){
			    dst[i][j] = true;
			    flag=true;
			    break;
			    
			}else if( (i2>0) && (j2>0) && dst[i2][j2] ){
			    dst[i][j] = true;
			    flag=true;
			    break;
			}
			
		    }
		}
	    }
	}	    
    }

    return true;
}

bool
Lattice::minimise()
{

    // method, make distinguished state table
    // scan all pairs of states (a.k.a. nodes)


    int i,j;
    EST_Litem *n_ptr,*n2_ptr,*n3_ptr,*a_ptr;
    int num_nodes = nodes.length();
    bool **dst = NULL; // distinguished state table
    bool flag;

    if(!build_distinguished_state_table(dst)){
	cerr << "Couldn't build distinguished state table" << endl;
	return false;
    }

    int count=0,count2=0;
    for(i=0;i<num_nodes-1;i++)
	for(j=i+1;j<num_nodes;j++)
	    if(!dst[i][j])
		count++;
	    else
		count2++;
    
    cerr << "There are " << count << " undistinguished pairs of nodes and "
	 << count2 << " distinguished pairs" << endl;


    // make lists of nodes to be merged
    EST_TList<Node *> merge_list;
	


    flag=true;
    while(flag){
	flag=false;

	merge_list.clear();
	for(i=0,n_ptr=nodes.head();n_ptr->next()!=NULL;n_ptr=n_ptr->next(),i++){
	    
	    cerr << "merge, processing row " << i << "        \r";
	    
	    for(j=i+1,n2_ptr=n_ptr->next();n2_ptr!=NULL;n2_ptr=n2_ptr->next(),j++){
		
		if(!dst[i][j]){

		    // is the merge list empty ?
		    if(merge_list.head() == NULL){
			// put this pair of nodes on merge list
			merge_list.append(nodes(n_ptr));
			merge_list.append(nodes(n2_ptr));
			dst[i][j] = true;

		    }else{ // merge list already has some items on it

			// see if either of this pair of nodes is on the merge list,
			// and if so add the other node in the pair
			bool add1=false,add2=false;
			for(n3_ptr=merge_list.head();n3_ptr!=NULL;n3_ptr=n3_ptr->next()){
			    if(merge_list(n3_ptr) == nodes(n_ptr))
				add2=true;
			    if(merge_list(n3_ptr) == nodes(n2_ptr))
				add1=true;
			}
			

			if(add1 && !add2){
			    merge_list.append(nodes(n_ptr));
			    dst[i][j] = true;
			}else if(add2 && !add1){
			    merge_list.append(nodes(n2_ptr));
			    dst[i][j] = true;
			}
			

		    }
		}
	    }
	}

	// anything on the merge list ?
	if(merge_list.head() != NULL){

	    // so merge them
	    count=0;
	    for(n_ptr=merge_list.head();n_ptr!=NULL;n_ptr=n_ptr->next())
		count++;
	    cerr << "merging " << count << " nodes out of ";
	    
	    count=0;
	    for(n_ptr=nodes.head();n_ptr!=NULL;n_ptr=n_ptr->next())
		count++;
	    cerr << count;
	    
	    merge_nodes(merge_list);
	    flag=true;

	    count=0;
	    for(n_ptr=nodes.head();n_ptr!=NULL;n_ptr=n_ptr->next())
		count++;
	    cerr << " leaving " << count << endl;
	    
	    
	}


    }

    int c1=0,c2=0;
    for(n_ptr=nodes.head();n_ptr!=NULL;n_ptr=n_ptr->next()){
	c1++;
	for(a_ptr=nodes(n_ptr)->arcs_out.head();a_ptr!=NULL; a_ptr=a_ptr->next())
	    c2++;
    }
    
    cerr << "Minimum state DFA has " << c1 
	 << " nodes and " << c2 << " arcs         " << endl;

    merge_arcs();

    c1=0,c2=0;
    for(n_ptr=nodes.head();n_ptr!=NULL;n_ptr=n_ptr->next()){
	c1++;
	for(a_ptr=nodes(n_ptr)->arcs_out.head();a_ptr!=NULL; a_ptr=a_ptr->next())
	    c2++;
    }
    
    cerr << "Pruned minimum state DFA has " << c1 
	 << " nodes and " << c2 << " arcs" << endl;

    for(i=0;i<num_nodes;i++)
	delete [] dst[i];
    delete [] dst;
    
    return true;
}


void
Lattice::merge_nodes(EST_TList<Node*> &l)
{

    if(l.head() == NULL)
	return;

    // make a new node with all node labels of old nodes
    // and all arcs of old nodes

    EST_Litem *n_ptr,*n2_ptr,*a_ptr,*a2_ptr;
    Node *new_node;
    new_node = new Node;


    // to do .. deal with final_nodes list too ....



    for(n_ptr=l.head();n_ptr!=NULL;n_ptr=n_ptr->next()){

	// get arcs
	for(a_ptr=l(n_ptr)->arcs_out.head();a_ptr!=NULL;a_ptr=a_ptr->next())
	    new_node->arcs_out.append(l(n_ptr)->arcs_out(a_ptr));

	// get name
	merge_sort_unique(new_node->name,l(n_ptr)->name);

	// find arcs into old nodes and make them go into new node
	for(n2_ptr=nodes.head();n2_ptr!=NULL;n2_ptr=n2_ptr->next()){
	    for(a2_ptr=nodes(n2_ptr)->arcs_out.head();a2_ptr!=NULL;a2_ptr=a2_ptr->next()){
		if(nodes(n2_ptr)->arcs_out(a2_ptr)->to == l(n_ptr))
		    nodes(n2_ptr)->arcs_out(a2_ptr)->to = new_node;
	    }
	}

    }


    // delete old nodes, but not arcs
    for(n_ptr=l.head();n_ptr!=NULL;n_ptr=n_ptr->next()){
	for(n2_ptr=nodes.head();n2_ptr!=NULL;n2_ptr=n2_ptr->next())
	    if(nodes(n2_ptr) == l(n_ptr)){
		nodes(n2_ptr)->name.clear();
		nodes(n2_ptr)->arcs_out.clear();
		delete nodes(n2_ptr);
		nodes.remove(n2_ptr);
	    }
    }
    
    nodes.append(new_node);

}

void
Lattice::merge_arcs()
{

    EST_Litem *n_ptr,*a_ptr,*a2_ptr;
    EST_TList<Arc*> merge_list;
    int count=0,count2;

    // find repeated arcs with the same label between two nodes
    for(n_ptr=nodes.head();n_ptr!=NULL;n_ptr=n_ptr->next()){

	count2=0;
	for(a_ptr=nodes(n_ptr)->arcs_out.head();a_ptr!=NULL; a_ptr=a_ptr->next())
	    count2++;

	cerr << "merging arcs from node " << ++count 
	     << ", before:" << count2;

	for(a_ptr=nodes(n_ptr)->arcs_out.head();a_ptr->next()!=NULL; a_ptr=a_ptr->next()){
	    
	    merge_list.clear();
	    for(a2_ptr=a_ptr->next();a2_ptr!=NULL; a2_ptr=a2_ptr->next())

		if((nodes(n_ptr)->arcs_out(a_ptr)->label ==
		   nodes(n_ptr)->arcs_out(a2_ptr)->label) &&

		    (nodes(n_ptr)->arcs_out(a_ptr)->to ==
		     nodes(n_ptr)->arcs_out(a2_ptr)->to) ){

		    delete nodes(n_ptr)->arcs_out(a2_ptr);
		    a2_ptr=nodes(n_ptr)->arcs_out.remove(a2_ptr);
		    
		}

	}

	count2=0;
	for(a_ptr=nodes(n_ptr)->arcs_out.head();a_ptr!=NULL; a_ptr=a_ptr->next())
	    count2++;

	cerr<< ", after:" << count2 << endl;

    }

    cerr << "                                                    \r" << endl;
    
}


void
Lattice::prune_arcs(Node *node, EST_TList<Arc*> arcs)
{

    int count=0;
    EST_Litem *a_ptr;
    for(a_ptr=arcs.head(); a_ptr != 0; a_ptr=a_ptr->next() ){
	prune_arc(node, arcs(a_ptr));
	count++;
    }
    //cerr << "pruned " << count << " arcs" << endl;
}


void
Lattice::prune_arc(Node *node, Arc *arc)
{
    remove_arc_from_nodes_out_list(node,arc);
    delete arc;
}

/*
void
Lattice::remove_arc_from_nodes_in_list(Node *n, Arc *a)
{
    EST_Litem *a_ptr;
    for (a_ptr = n->arcs_in.head(); a_ptr != 0; a_ptr = a_ptr->next())
	if(n->arcs_in(a_ptr) == a)
	    n->arcs_in.remove(a_ptr);
}
*/

void
Lattice::remove_arc_from_nodes_out_list(Node *n, Arc *a)
{
    EST_Litem *a_ptr;
    for (a_ptr = n->arcs_out.head(); a_ptr != 0; a_ptr = a_ptr->next())
	if(n->arcs_out(a_ptr) == a)
	    n->arcs_out.remove(a_ptr);
}

/* not used
bool
Lattice::is_enter_node(Node *n)
{
    // contains "!ENTER" in its list of names
    EST_Litem *l_ptr;
    for(l_ptr=n->name.head(); l_ptr != 0; l_ptr=l_ptr->next())
	if(n->name(l_ptr) == nmap_name_to_index("!ENTER")) // temporary !!
	    return true;
    return false;
}
*/

/* Superseded now we have list of final nodes
bool
Lattice::is_exit_node(Node *n)
{
    EST_Litem *l_ptr;
    for(l_ptr=n->name.head(); l_ptr != 0; l_ptr=l_ptr->next())
	if(n->name(l_ptr) == nmap_name_to_index("!EXIT")) // temporary !!
	    return true;
    return false;
}
*/

EST_String 
Lattice::nmap_index_to_name(int index)
{
    if(index < nmap.n())
	return nmap(index);
    else{
	cerr << "Warning : nmap index " << index << " out of range" << endl;
	return EST_String("!error!");
    }

}

int 
Lattice::nmap_name_to_index(const EST_String &name)
{
    int i,j,mid;

    // binary search
    i=0;
    j=nmap.n()-1;
    
    while(true){
	
	mid = (i+j)/2;

	if(name > nmap(mid))
	   i = mid;
	
	else if(name < nmap(mid))
	    j = mid;
	
	else{ // name == nmap(mid)
	    return mid; // lucky strike
	}

	if(i==j){
	    if(name == nmap(i))
		return i;
	    else{
		cerr << "Lattice::nmap_name_to_index failed for '"
		     << name << "'" << endl;
		return -1;
	    }
	
	}else if(j==i+1){
	    
	    if(name == nmap(i))
		return i;
	    else if(name == nmap(j))
		return j;
	    else{
		cerr << "Lattice::nmap_name_to_index failed for '"
		     << name << "'" << endl;
		return -1;
	    }
	    
	}
	
    }

    return -1;
}


float 
Lattice::qmap_index_to_value(int index)
{
    if(index < qmap.n())
	return qmap(index);
    else{
	cerr << "Warning : qmap index " << index << " out of range" << endl;
	return 1;
    }
}


int
Lattice::qmap_value_to_index(float value)
{
    int i,j,mid;

    // binary search
    i=0;
    j=qmap.n()-1;
    
    while(true){
	
	mid = (i+j)/2;

	if(value > qmap(mid))
	   i = mid;
	
	else if(value < qmap(mid))
	    j = mid;
	
	else
	    return mid; // lucky strike

	if(i==j)
	    return i;

	else if(j==i+1){
	    
	    if( fabs(qmap(i) - value) < fabs(qmap(j) - value) )
		return i;
	    else
		return j;
	}
	
    }
    return 0;
}

int
Lattice::node_index(Node *n)
{
    EST_Litem *n_ptr;
    for (n_ptr = nodes.head(); n_ptr != 0; n_ptr = n_ptr->next()){
	if(nodes(n_ptr) == n)
	    return nodes.index(n_ptr);
	
    }

    //cerr << "Lattice::node_index(Node *n) couldn't find index of node " << n->name;

    return -1;
}




bool
Lattice::expand()
{

    // keep HTK happy - it can't handle multiple arcs into a node
    // with different word labels


    EST_Litem *n_ptr,*n2_ptr,*a_ptr,*w_ptr;
    int word;
    EST_TList<int> word_list;
    Node *new_node;
    Arc *new_arc;
    for (n_ptr = nodes.head(); n_ptr != 0; n_ptr = n_ptr->next()){

	// find all arcs into this node
	word_list.clear();
	for (n2_ptr = nodes.head(); n2_ptr != 0; n2_ptr = n2_ptr->next()){

	    for (a_ptr = nodes(n2_ptr)->arcs_out.head(); a_ptr != 0; a_ptr = a_ptr->next())
		if(nodes(n2_ptr)->arcs_out(a_ptr)->to == nodes(n_ptr)){
		    
		    if(nodes(n2_ptr)->arcs_out(a_ptr)->label != e_move_symbol_index){
			word = alphabet_index_to_symbol(nodes(n2_ptr)->arcs_out(a_ptr)->label)->nmap_index;
			word_list.append(word);
			sort_unique(word_list);
			
		    }
		}
	}
	
	
	// if word_list.head() is NULL we should be worried
	if((word_list.head() != NULL) && word_list.head()->next() != NULL){

	    // for each word make a null node, change all offending arcs to point
	    // to it, and make another link from null node to nodes(n_ptr)

	    for(w_ptr=word_list.head();w_ptr!=NULL;w_ptr=w_ptr->next()){

		// make null node
		new_node = new Node;
		new_arc = new Arc;
		new_arc->label = e_move_symbol_index; // no label
		new_arc->to = nodes(n_ptr);
		new_node->arcs_out.append(new_arc);

		// for every arc into nodes(n_ptr) with this word label, change its arcs
		for (n2_ptr = nodes.head(); n2_ptr != 0; n2_ptr = n2_ptr->next()){
		    
		    for (a_ptr = nodes(n2_ptr)->arcs_out.head(); a_ptr != 0; a_ptr = a_ptr->next()){
			if(nodes(n2_ptr)->arcs_out(a_ptr)->to == nodes(n_ptr)){
			    
			    word = alphabet_index_to_symbol(nodes(n2_ptr)->arcs_out(a_ptr)->label)->nmap_index;
			    if(word == word_list(w_ptr)){
				
				// change the arc
				nodes(n2_ptr)->arcs_out(a_ptr)->to = new_node;
			    }
			    
			}
		    }
		}
		nodes.append(new_node);
	    }
	}
    }

    // need to make sure ENTER node has no arcs in - if so add a dummy ENTER node

    //Node *enter_node = nodes(nodes.head());
    bool flag=false;
    for(n_ptr=nodes.head();n_ptr!=NULL;n_ptr=n_ptr->next()){
	for(a_ptr=nodes(n_ptr)->arcs_out.head();a_ptr!=NULL; a_ptr=a_ptr->next()){
	    flag=true;
	    break;
	}
    }

/*
    if(flag){
	cerr << " fixing ENTER node" << endl;
	new_node = new Node;
	new_arc = new Arc;
	new_arc->label = enter_node->label; 
	new_arc->to = enter_node;
	new_node->arcs_out.append(new_arc);
	nodes.append(new_node);
    }	
    */

    // also need to make sure there is only one EXIT node
    if(final_nodes.length() > 1){
	cerr << " making single EXIT node" << endl;
	
	// make null node
	new_node = new Node;

	for(n_ptr=final_nodes.head();n_ptr!=NULL;n_ptr=n_ptr->next()){

	    new_arc = new Arc;
	    new_arc->label = e_move_symbol_index; // no label
	    new_arc->to = final_nodes(n_ptr);
	    final_nodes(n_ptr)->arcs_out.append(new_arc);


	}

	// empty final node list (nodes themselves remain on nodes list)
	final_nodes.clear();

	// now a single final node
	nodes.append(new_node);
	final_nodes.append(new_node);
    }


    int c1=0,c2=0;
    for(n_ptr=nodes.head();n_ptr!=NULL;n_ptr=n_ptr->next()){
	c1++;
	for(a_ptr=nodes(n_ptr)->arcs_out.head();a_ptr!=NULL; a_ptr=a_ptr->next())
	    c2++;
    }
    
    cerr << "HTKified DFA has " << c1 
	 << " nodes and " << c2 << " arcs" << endl;

    return true;
}

bool
Lattice::final(Node *n)
{
    EST_Litem *n_ptr;
    for (n_ptr = final_nodes.head(); n_ptr != 0; n_ptr = n_ptr->next())
	if(final_nodes(n_ptr) == n)
	    return true;

    return false;
}



EST_String Lattice::name_as_string(EST_IList &l)
{
    EST_String name;
    EST_Litem *l_ptr;
    for(l_ptr=l.head();l_ptr!=NULL;l_ptr=l_ptr->next())
	name+=nmap_index_to_name(l(l_ptr)) + ",";

    return name;
}



int
Lattice::alphabet_index_lookup(int nmap_index, int qmap_index)
{
    symbol_t sym;
    sym.nmap_index = nmap_index;
    sym.qmap_index = qmap_index;

    return alphabet_symbol_to_index(&sym);
}


Lattice::symbol_t* 
Lattice::alphabet_index_to_symbol(int index)
{
    if(index < alphabet.n())
	return &(alphabet[index]);
    else{
	cerr << "Warning : alphabet index " << index << " out of range" << endl;
	return NULL;
    }

}

int
Lattice::alphabet_symbol_to_index(Lattice::symbol_t *sym)
{

    int i,j,mid;

    // binary search
    i=0;
    j=alphabet.n()-1;
    
    while(true){
	
	mid = (i+j)/2;

	if(*sym > alphabet(mid))
	   i = mid;
	
	else if(*sym < alphabet(mid))
	    j = mid;
	
	else // *sym == alphabet(mid)
	    return mid; // lucky strike

	if(i==j){
	    if(*sym == alphabet(i))
		return i;
	    else{
		cerr << "Lattice::alphabet_symbol_to_index failed for '"
		     << *sym << "' 1" << endl;
		return -1;
	    }
	
	}else if(j==i+1){
	    
	    if(*sym == alphabet(i))
		return i;
	    else if(*sym == alphabet(j))
		return j;
	    else{
		cerr << "Lattice::alphabet_symbol_to_index failed for '"
		     << *sym << "' 2" << endl;

		cerr << i << " " << alphabet(i) << endl;
		cerr << j << " " << alphabet(j) << endl;

		return -1;
	    }
	    
	}
	
    }

    return -1;

}


bool
Lattice::build_transition_function()
{

    // different representation of the network , currently only for DFAs
    // since for a NFA each tf cell would be a list

    int i,j;
    EST_Litem *n_ptr,*a_ptr;
    int num_nodes = nodes.length();
    int num_symbols = alphabet.n();

    if(tf != NULL)
	cerr << "Warning : discarding existing transition function" << endl;


    tf = new int*[num_nodes];
    for(i=0;i<num_nodes;i++)
	tf[i] = new int[num_symbols];

    if(tf == NULL){
	cerr << "Not enough memory to build transition function"
	     << "(needed " << num_nodes*num_symbols*sizeof(int) << " bytes)" << endl;
	return false;
    }

    for(i=0,n_ptr=nodes.head();n_ptr!=NULL;n_ptr=n_ptr->next(),i++){

	cerr << "building transition function " << (int)((float)(i+1)*100/(float)num_nodes) << "%    \r";

	for(j=0;j<alphabet.n();j++){

	    tf[i][j]=-1; // means no transition
	    for(a_ptr=nodes(n_ptr)->arcs_out.head();a_ptr!=NULL;a_ptr=a_ptr->next()){

		if(j == nodes(n_ptr)->arcs_out(a_ptr)->label){
		    tf[i][j] = node_index(nodes(n_ptr)->arcs_out(a_ptr)->to);
		    break;
		}
	    }
	}
    }

    cerr << endl;
    return true;
}



bool
Lattice::accepts(EST_TList<symbol_t*> &string)
{
    (void) string;
    return false;
}


float
Lattice::viterbi_transduce(EST_TList<EST_String> &input,
			   EST_TList<Arc*> &path,
			   EST_Litem *current_symbol,
			   Node *start_node)
{

    // finds maximum sum-of-probs path
    EST_Litem *a_ptr,*best;

    if(start_node == NULL){
	start_node = nodes(nodes.head());
	current_symbol = input.head();
	path.clear();
    }

    if(current_symbol == NULL){ // consumed all input
	if( final(start_node) )
	    return 0; // log prob 1
	
	else
	    return -10000000; // hack for now
	
    }

    best=NULL;
    float max=-10000000; // hack for now
    for (a_ptr = start_node->arcs_out.head(); a_ptr != 0; a_ptr = a_ptr->next()){

	if( alphabet_index_to_symbol(start_node->arcs_out(a_ptr)->label)->nmap_index
	    == nmap_name_to_index(input(current_symbol)) ){
	    
	    float x = viterbi_transduce(input,
					path,
					current_symbol->next(),
					start_node->arcs_out(a_ptr)->to)
		+ qmap_index_to_value(alphabet_index_to_symbol(start_node->arcs_out(a_ptr)->label)->qmap_index);
	
	    if(x > max){
		max = x;
		best = a_ptr;
	    }
	}
    }

    if(best != NULL)
	path.append(start_node->arcs_out(best));
    
    return max;

}


float Lattice::viterbi_transduce(EST_Track &observations,
			   EST_TList<Arc*> &path,
			   float &score,
			   int current_frame,
			   Node *start_node)
{
    // finds maximum sum-of-probs path
    EST_Litem *a_ptr,*best;

    if(start_node == NULL){
	start_node = nodes(nodes.head());
	current_frame = 0;
	path.clear();
	score = 0.0;
    }
    
    if(current_frame == observations.num_frames()){ // consumed all input
	if( final(start_node) )
	    return 0; // log prob 1
	
	else
	    return -10000000; // hack for now
	
    }
    

    if(score < -100000){ // hack !
	return -10000000;
    }
    
    best=NULL;
    float max=-10000000; // hack for now
    for (a_ptr = start_node->arcs_out.head(); a_ptr != 0; a_ptr = a_ptr->next()){

	int observation_element =
	    alphabet_index_to_symbol(start_node->arcs_out(a_ptr)->label)->nmap_index
	    - 2; // HACK !!@!!!! to skip ENTER/EXIT
	
	float this_observation = observations.a(current_frame,observation_element);
	    
	//cerr << "frame " << current_frame << "," << observation_element
	//<< " : " << this_observation << endl;

	float x = viterbi_transduce(observations,
				    path,
				    score,
				    current_frame+1,
				    start_node->arcs_out(a_ptr)->to)

	    + qmap_index_to_value(alphabet_index_to_symbol(start_node->arcs_out(a_ptr)->label)->qmap_index)
	
	    + this_observation;
	
	if(x > max){
	    max = x;
	    best = a_ptr;
	}

    }

    if(best != NULL){
	path.append(start_node->arcs_out(best));

	int observation_element =
	    alphabet_index_to_symbol(start_node->arcs_out(best)->label)->nmap_index;
	
	float this_observation = observations.a(current_frame,observation_element);

	score += qmap_index_to_value(alphabet_index_to_symbol(start_node->arcs_out(best)->label)->qmap_index) + this_observation;
;

    }

    cerr << max << endl;

    return max;

}

// hack for now (required for SHARED=2)
bool Lattice::symbol_t::operator!=(Lattice::symbol_t const &) const {
return false;
}