/*
 * Scanner.java
 */
package Gramaticas;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Observable;

public class Scanner extends Observable {
	/**
	 * La cola contiene nodos que pueden estar formados por varios simbolos
	 * (terminales y no terminales)
	 */
	public LinkedList<ArrayList<Simbolo>> Q;
	/** */
	public ArrayList<Simbolo> u;
	/** */
	public ArrayList<Simbolo> v;
	/** */
	public ArrayList<Simbolo> w;
	/** */
	public ArrayList<Simbolo> uwv;
	/** */
    public ArrayList<Simbolo> q;
	/** */
    public No_terminal A;
	/** */
    public ReglaGIC[] reglasArray;
	/** */
    public boolean done;
	/** */
    public int index;
	/** */
    public int i;
	/** */
    public int j;
	/** Contador de nodos */
    public int cont;
    /**	Contador de nodos */
    public int contNodos;
    /** hijo uwv -> padre q */
    public HashMap<ArrayList<Simbolo>, ArrayList<Simbolo>> T;
    /** */
    public boolean stopondone = true;
    
    
    /**
     * @param s simbolo inical
     * @param w cadena
     * @param G gramatica
     * @return true/false dependiendo si w se puede derivar de G
     */
    public boolean scanAnchura(Simbolo S, Cadena p, GIC G) throws G_Exception {

        Q = new LinkedList<ArrayList<Simbolo>>();
        u = new ArrayList<Simbolo>();
        v = new ArrayList<Simbolo>();
        w = new ArrayList<Simbolo>();
        uwv = new ArrayList<Simbolo>();
        A = null;
        reglasArray = (ReglaGIC[]) G.reglas.toArray(new ReglaGIC[] {});

        cont = 0;
        contNodos = 1;
        
        ArrayList<Simbolo> simIni = new ArrayList<Simbolo>();
        simIni.add(S);
        Q.addFirst(simIni);
        
        do {
            q = Q.getFirst();
            Q.removeFirst();
            i = 0;
            System.out.println("////");
            done = false;
            /*Obtenemos q=uAv*/
            index = obtenerPrimeroNoTerminal(q);
            A = new No_terminal(q.get(index).get_id());
            
            u = new ArrayList<Simbolo>();
            v = new ArrayList<Simbolo>();
            
            for (int j=0; j<q.size(); j++) { 
                if (j<index)
                    u.add(q.get(j));
                else if (j>index)
                    v.add(q.get(j));
            }
            /*Solo consideramos las reglas que se derivan de el simbolo no terminal mas a la izq de q*/
            do { // Para cada nodo
                if (i >= reglasArray.length)
                    /*Si no hay mas reglas*/
                    done = true;
                if (!done) {
                    if (reglasArray[i].izqda.toString().equals(A.toString())) {
                        w = new ArrayList<Simbolo>();
                        w= cloneList(reglasArray[i].drcha);
                        uwv = new ArrayList<Simbolo>();
                        uwv.addAll(u);
                        uwv.addAll(w);
                        uwv.addAll(v);
                        if (containsNoTerminal(uwv) && coincidePrefijo(uwv, p, obtenerPrimeroNoTerminal(uwv))) {
                            contNodos++;
                            Q.addLast(uwv);
                            this.notifyObservers();
                            T.put(uwv,q);
                        }
                    }
                }
                cont++;
                i++;
            } while (!done && !coincideCadena(uwv, p));
        } while  (stopondone && !Q.isEmpty() && !coincideCadena(uwv, p));

        if (coincideCadena(uwv, p))
            return true;
        else
            return false;
    }
    
    /**
     * 
     * @param array_s
     * @return
     */
    public static int obtenerPrimeroNoTerminal(ArrayList<Simbolo> array_s) {
        
        for (Simbolo s: array_s) {
            if (s instanceof No_terminal) 
                return(array_s.indexOf(s));
        }
        return(-1);
    }
	
    /**
     * 
     * @param array_s
     * @return
     */
    public static boolean containsNoTerminal(ArrayList<Simbolo> array_s) {
        if (array_s.isEmpty())
            return(true);
        for (Simbolo s: array_s) {
            if (s instanceof No_terminal)
                return true;
        }
        return false;
    }
    
    /**
     * 
     * @param uwv
     * @param p
     * @param index
     * @return
     */
    public static boolean coincidePrefijo(ArrayList<Simbolo> uwv, Cadena p, int index) {
        int i=0;
        for (Simbolo s: uwv) {
            if (i< index) {
                if (s.id != p.get(i).id)
                    return(false);
                i++;
            }
        }
        return(true);
    }
    
    /**
     * 
     * @param uwv
     * @param p
     * @return
     */
    public static boolean coincideCadena(ArrayList<Simbolo> uwv, Cadena p) {
        if (uwv.size() != p.size())
            return false;
        return(coincidePrefijo(uwv, p, uwv.size()));
    }
  
    /**
     * 
     * @param list
     * @return
     */
    public static ArrayList<Simbolo> cloneList(ArrayList<Simbolo> list){
    	ArrayList<Simbolo> newlist = new ArrayList<Simbolo>();
    	for (Simbolo obj : list)
    	{
    		//if (obj is ICloneable)
    			newlist.add((Simbolo) obj.clone());
    	}
    	return newlist;
    }
}