/**
 * @(#)Grammar.java	18.03.2004
 * 
 * @author kst
 */
package commons.chartparser;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
/**
 * Implementierung eines vereinfachten Earley-Chart-Parsers. Analysiert S�tze und erzeugt einen
 * Syntax-Baum. Die Chart ist als Liste von Items realisiert. Items (eine innere Klasse des
 * ChartParsers) bestehen aus + start: Anfang des geparsten Abschnitts + end: Ende des geparsten
 * Abschnitts + dotpos: Position trennt inaktiven und aktiven Abschnitt + rule: Die
 * Transformationsregeln (S->NP VP). Regeln k�nnen grammatische Merkmale enthalten, s.
 * Bsp.-Grammatik.
 */
@SuppressWarnings("unchecked")
public class ChartParser extends commons.chartparser.Parser
{

ArrayList  items   = null; // Die 'Chart': Eine Liste mit Items.
STree      synTree = null; // Das Ergebnis des Parsings als Baum.
// z�hlt die Eintragungen in die Chart, nur f�r Debug-Ausgabe.
static int counter = 0;

public ChartParser()
{
   super(); // pro forma: die abstrakte Superklasse hat keinen Konstruktor
   // Main.debug("Parser : ChartParser");
}

/**
 * Konstruktor des Parsers
 * @param grm - Die verwendete Gramatik
 * @param lex - Das verwendete Lexikon Hinweis: stree und items werden bei jedem Aufruf der Methode
 * 'STree parse(ArrayList satz)' neu erzeugt.
 */
public ChartParser(Grammar grm, Lex lex)
{
   this();
   super.setGrammar(grm);
   super.setLexicon(lex);
   Main.debug("Lexicon, size : " + super.getLexicon().size());
   Main.debug("Start element : " + super.getStartElement());
   Main.debug("Grammar/rules : " + super.getGrammar().size());
}

/**
 * Startet und steuert das das Parsing, der
 * @param satz ist eine Liste von Woerten. Vor dem Start wird der Parser initialisiert und geprueft.
 * In dieser Implementierung spielen Satzzeichen keine Rolle.
 */
public STree parse (List satz)
{
   // Main.debug("Satzlaenge : " + (satz == null ? -1 : satz.size()));
   if (initChartParser(satz))
   {
      { // Initialisiere die Chart --------------------------------->
         // fuege alle Regeln, die das Startelement erweitern, der Chart
         // hinzu:
         for (Iterator I = super.getGrammar().expand(super.getStartElement()); I.hasNext();)
         {
            addItem(new Item(0, (Rule) I.next()), "INIT");
         }
         // epandiere alle Regeln, die jetzt in der Chart sind:
         expand(0, 0);
      } // Initialisiere die Chart ---------------------------------|
      // ----------------------------------------------------------->
      // verarbeitet die Chart, Regeln und Lexikon
      // fuer den ganzen Satz indem es die Chart von links
      // nach rechts abschnittweise entfaltet:
      for (int j = 0; j < satz.size(); j++) // endpos des abschnitts
      {
         for (int i = 0; i <= j; i++) // startpos des abschnitts
         {
            // Main.debug("[" + i + ":" + j + "]");
            scan(i, j);
            complete();
            expand(i, j);
         }
      }
      // -----------------------------------------------------------|
   }
   // Syntaxbaum aufraeumen
   compile();
   return synTree;
}

/**
 * Initialisiert den Parser fuer die Verarbeitung eines neuen Satzes: Leere Chart erzeugen, leeren
 * Syntaxbaum erzeugen, Counter ruecksetzen. Lexicon und Grammatik bleiben nach dem
 * Konstruktoraufruf unveraendert. Der Rueckgabewert ist true, wenn weder Satz noch Grammatik noch
 * Lexikon leer sind und es ein Startelement gibt.
 */
public boolean initChartParser (List satz)
{
   counter = 0;
   items = new ArrayList();
   super.setSentence(satz);
   return super.getStartElement() != null && super.getSentence().size() > 0 && super.getGrammar().size() > 0
      && super.getLexicon().size() > 0;
}

/**
 * Fuegt ein neues Item der Chart genau dann hinzu, wenn das Item nicht schon in der Chart ist.
 * Ausserdem: Ausgabe einer Meldung auf der Konsole.
 */
private boolean addItem (Item I, String m)
{
   boolean add = !containsItem(I);
   if (add)
   {
      items.add(I);
      if (!super.quiet)
      {
         Object[] o = (Object[]) Array.newInstance(Object.class, 3);
         o[0] = new Integer(++counter);
         o[1] = m.substring(0, 1);
         o[2] = I.toString();
         Main.debug(Main.format("%1$3d.) %2$1s %3$s", o));
      }
   }
   return add;
}

/*
 * pr�ft, ob die chart ein item mit einem aktiven symbol hat, das zu dem wort an wordpos passt
 * (lex-zugriff). wenn ja, wird ein neues item erzeugt mit dem erkannten wort auf der inaktiven
 * seite.
 */
public void scan (int start, int end)
{
   String word = ((String) super.getSentence().get(end));
   for (int i = 0; i < items.size(); i++)
   {
      Item testitem = (Item) items.get(i);
      if (testitem.start == start && testitem.end == end)
      {
         String[] ai = activeItems(testitem);
         if (ai.length > 0)
         {
            if (ai[0].equals(word))
            {
               addItem(new Item(start, end + 1, testitem.rule, testitem.dotpos + 1), "SCAN");
            }
         }
      }
   }
}

/**
 * suche alle aktiven items in der chart: f�r jedes nicht-terminal: suche die zu dem aktiven item
 * passenden regeln in der grammatik und f�ge die expansion des aktiven items gem�� der regel der
 * chart hinzu und markierte diesen eintrag als passiv.
 */
public void expand (int start, int end)
{
   while (doexpandRules(start, end));
}

private boolean doexpandRules (int start, int end)
{
   boolean repeat = false;
   for (int i = 0; i < items.size(); i++)
   {
      Item item = (Item) items.get(i);
      String ai[] = activeItems(item);
      for (int j = 0; j < ai.length; j++)
      {
         Iterator regeln = super.getGrammar().expand(ai[j]);
         if (regeln != null)
         {
            while (regeln.hasNext())
            {
               Rule regel = (Rule) regeln.next();
               if (addItem(new Item(end, end, regel, 0), "EXPD") && !repeat)
               {
                  repeat = true;
               }
            }
         }
         else
         // vielleicht ist es ein Terminalsymbol?
         {
            String cat = Lex.getCat(ai[j]);
            String kgr = Lex.getKgr(ai[j]);
            Iterator lexentries = super.getLexicon().expand(cat, kgr);
            if (lexentries != null)
            {
               while (lexentries.hasNext())
               {
                  Word word = (Word) lexentries.next();
                  Rule rule = new Rule(cat, kgr, word.getForm(), word);
                  if (addItem(new Item(end, end, rule, 0), "EXPD") && !repeat)
                  {
                     repeat = true;
                  }
               }
            }
         }
      }
   }
   return repeat;
}

/**
 * vorhandene chart eintraege zu gr��eren einheiten zusammenfassen. suche in der chart regeln, die
 * aktive items aufl�sen und erzeugt jeweils ein neues item mit der aufl�sung im inaktiven teil.
 */
public void complete ()
{
   while (doComplete());
}

private boolean doComplete ()
{
   boolean repeat = false;
   for (int i = 0; i < items.size(); i++)
   {
      Item item1 = (Item) items.get(i);
      String[] ai = activeItems(item1);
      if (!item1.completed() && ai.length > 0)
      {
         String actItem = ai[0];
         for (int j = 0; j < items.size(); j++)
         {
            if (i == j)
            {
               continue;
            }
            Item item2 = (Item) items.get(j);
            Rule rule = item2.rule;
            if (Unify.rules(rule.lexpr(), actItem))
            {
               if (item2.completed())
               {
                  if (item1.end == item2.start)
                  {
                     if (addItem(new Item(item1.start, item2.end, item1.rule, item1.dotpos + 1), "COMP") && !repeat)
                     {
                        repeat = true;
                     }
                  }
               }
            }
         }
      }
   }
   return repeat;
}

/**
 * Pruefen, ob ein Item bereits in der Chart ist
 */
public boolean containsItem (Item item)
{
   for (Iterator I = items.iterator(); I.hasNext();)
   {
      if (((Item) I.next()).equals(item)) { return true; }
   }
   return false;
}

/**
 * Extrahiert nur die aktiven Items aus einem Item.
 */
public static String[] activeItems (Item item)
{
   String[] rexpr = item.rule.rexpr();
   ArrayList ai = new ArrayList();
   for (int i = item.dotpos; i < rexpr.length; i++)
   {
      ai.add(rexpr[i]);
   }
   String[] s = (String[]) Array.newInstance(String.class, ai.size());
   for (int i = 0; i < ai.size(); i++)
   {
      s[i] = (String) ai.get(i);
   }
   return s;
}

/**
 * Extrahiert nur die inaktiven Items aus einem Item.
 */
public static String[] passiveItems (Item item)
{
   String[] rexpr = item.rule.rexpr();
   ArrayList ai = new ArrayList();
   for (int i = 0; i < item.dotpos; i++)
   {
      ai.add(rexpr[i]);
   }
   String[] s = (String[]) Array.newInstance(String.class, ai.size());
   for (int i = 0; i < ai.size(); i++)
   {
      s[i] = (String) ai.get(i);
   }
   return s;
}

/**
 * loescht alle sinnlosen eintraege aus der chart und baut den syntax-baum auf.
 */
void compile ()
{
   synTree = null;
   for (int x = items.size() - 1; x >= 0; x--)
   {
      Item i = (Item) items.get(x);
      if (!i.completed())
      {
         items.remove(x);
         continue;
      }
      if (i.rule.lexpr().equals(super.getStartElement()))
      {
         synTree = new STree();
      }
   }
   if (synTree != null)
   {
      expandSynTree(synTree, super.getStartElement(), null);
   }
}

void expandSynTree (STree pnode, String lexpr, Rule prule)
{
   pnode = pnode.addChild(lexpr, prule); // parent node bekommt ein kind
   Item currentItem = getItemFromChart(lexpr);
   if (currentItem == null) { return; }
   for (int i = 0; i < currentItem.rule.rexpr().length; i++)
   {
      String nextSymbol = currentItem.rule.rexpr()[i];
      expandSynTree(pnode, nextSymbol, currentItem.rule);
   }
}

Item getItemFromChart (String lexpr)
{
   for (Iterator I = items.iterator(); I.hasNext();)
   {
      Item i = ((Item) I.next());
      if (i.rule.lexpr().equals(lexpr)) { return i; }
   }
   return null;
}

public String toString ()
{
   StringBuilder sb = new StringBuilder();
   Iterator I = items.iterator();
   if (I != null)
   {
      while (I.hasNext())
      {
         sb.append(" ");
         sb.append(((Item) I.next()).toString());
         if (I.hasNext())
         {
            sb.append("\n");
         }
      }
   }
   return sb.toString();
}

public static String toString (String[] as)
{
   StringBuilder sb = new StringBuilder();
   for (int i = 0; i < as.length; i++)
   {
      sb.append(as[i]);
      sb.append(i < as.length ? " " : "");
   }
   return sb.toString().trim();
}

public String checkResult ()
{
   StringBuilder result = new StringBuilder();
   if (synTree == null)
   {
      boolean firstError = true;
      // check if word occurs in passive items part of one of the items in
      // the chart
      for (Iterator words = super.getSentence().iterator(); words.hasNext();)
      {
         String w = (String) words.next();
         boolean found = false;
         for (Iterator I = items.iterator(); I.hasNext();)
         {
            String[] pi = passiveItems((Item) I.next());
            if (pi != null)
            {
               for (int x = 0; x < pi.length; x++)
               {
                  if (pi[x].equals(w))
                  {
                     found = true;
                     break;
                  }
               }
            }
            if (found)
            {
               break;
            }
         }
         // not found? word has not been recognized!
         if (!found)
         {
            if (firstError)
            {
               result.append("Nicht im Lexikon: ");
               firstError = false;
            }
            result.append("'");
            result.append(w);
            result.append("' ");
         }
      }
      if (result.toString().trim().length() != 0)
      {
         result.append(". ");
      }
      firstError = true;
      for (Iterator I = items.iterator(); I.hasNext();)
      {
         String lexpr = ((Item) I.next()).rule.lexpr();
         boolean found = false;
         for (Iterator II = items.iterator(); II.hasNext();)
         {
            String[] pi = passiveItems((Item) II.next());
            if (pi != null)
            {
               for (int x = 0; x < pi.length; x++)
               {
                  if (pi[x].equals(lexpr))
                  {
                     found = true;
                     break;
                  }
               }
            }
            if (found)
            {
               break;
            }
         }
         if (!found)
         {
            if (firstError)
            {
               result.append("Nicht komplettierte Regeln: ");
               firstError = false;
            }
            result.append("'");
            result.append(lexpr);
            result.append("' ");
         }
      }
   }
   result.append(". Erkannte Satzteile:\n" + toString());
   return result.toString();
}

public static class Item
{

int  start  = -1;
int  end    = -1;
Rule rule   = null;
int  dotpos = -1;

public Item(int start, Rule rule)
{
   this.start = start;
   this.end = start;
   this.rule = rule;
   dotpos = 0;
}

public Item(int start, int end, Rule rule, int dot)
{
   this.start = start;
   this.end = end;
   this.rule = rule;
   dotpos = dot;
}

public boolean completed ()
{
   return dotpos == rule.elements();
}

public void setDot (int pos)
{
   dotpos = pos;
}

public String toString ()
{
   StringBuilder sb = new StringBuilder();
   sb.append(start);
   sb.append("-");
   sb.append(end);
   sb.append(" ");
   Object[] o = (Object[]) Array.newInstance(Object.class, 1);
   o[0] = rule.lexpr();
   sb.append(Main.format("%1$-4s", o));
   sb.append(" -> ");
   sb.append(ChartParser.toString(passiveItems(this)));
   sb.append(".");
   sb.append(ChartParser.toString(activeItems(this)));
   return sb.toString();
}

public boolean equals (Item i)
{
   if (i == null) return false;
   if (i.start != start) return false;
   if (i.end != end) return false;
   if (i.dotpos != dotpos) // ???
   return false;
   return (i.rule.toString().equals(rule.toString()));
}
}
}