/*
 * (C) Copyright IBM Corp. 1997-1998  All rights reserved.
 *
 * US Government Users Restricted Rights Use, duplication or
 * disclosure restricted by GSA ADP Schedule Contract with IBM Corp.
 *
 * The program is provided "as is" without any warranty express or
 * implied, including the warranty of non-infringement and the implied
 * warranties of merchantibility and fitness for a particular purpose.
 * IBM will not be liable for any damages suffered by you as a result
 * of using the Program. In no event will IBM be liable for any
 * special, indirect or consequential damages or lost profits even if
 * IBM has been advised of the possibility of their occurrence. IBM
 * will not be liable for any third party claims against you.
 */

package com.ibm.xml.parser;

import java.util.*;

/**
 * ContentModel provides content model support for element declarations.  Refer to ElementDecl
 * for an overview of content models.
 *
 * @version 1.1
 * @author TAMURA Kent &lt;kent@trl.ibm.co.jp&gt;
 * @see com.ibm.xml.parser.ElementDecl
 */
public class ContentModel implements Cloneable, java.io.Serializable {
    
            ElementFactory      factory             =   null;
            int                 type                =   ElementDecl.MODEL_GROUP;
            CMNode              modelGroupNode      =   null;
            transient CMNode    rootContentModelNode=   null;
            transient Hashtable symbolHashTable     =   null;
            transient Object[]  symbolNextStateTable=   null;   // array of int[]
            transient boolean[] terminalFlag        =   null; 
            String              pseudo              =   null;

    /**
     * Constructor for content models NOT of type <var>MODEL_GROUP</var>.
     * @param   type    The type for this content model. 
     *                  Must be one of org.w3c.dom.ElementDefinition#ContentType.
     *                  Note that the XML4J parser will never set <code>#PCDATA</code> as the
     *                  content type; <code>MODEL_GROUP</code> will be set instead.
     */
    public ContentModel(int type) {
        this.type = type;
    }
    
    /**
     * Constructor for content models of <var>type</var> <code>MODEL_GROUP</code>.
     * @param   modelGroupNode    The content model associated with the model group.
     */
    public ContentModel(CMNode modelGroupNode) {
        this.type = ElementDecl.MODEL_GROUP;
        this.modelGroupNode = modelGroupNode;
    }

    /**
     * Clone this content model using the appropriate factory.  
     * @return          Cloned content model.
     */
    public synchronized Object clone() {
        ContentModel cs = null == this.factory ? new ContentModel(this.type)
            : this.factory.createContentModel(this.type);
        cs.setFactory(getFactory());
        if (null != this.modelGroupNode) {
            cs.modelGroupNode = this.modelGroupNode.cloneNode();
        }
        return cs;
    }
    
    /**
     * Returns the factory used for creating this content model. 
     * @return          The factory used for creating this content model, or <var>null</var> 
     *                  if no factory.
     * @see #setFactory
     */
    public ElementFactory getFactory() {
        return this.factory;
    }

    /**
     * Sets the factory to be used in creating this content model.
     * @param factory   The factory to be used in creating this content model.
     * @see #getFactory
     */
    public void setFactory(ElementFactory factory) {
        this.factory = factory;
    }

    /**
     * Returns the content model associated with this model group content model.
     * @return          The content model associated with this model group, or <var>null</var>
     *                  if this content model's <var>type</var> is anything other than
     *                  <code>MODEL_GROUP</code>.
     * @see #setContentModelNode
     */
    public CMNode getContentModelNode() {
        return this.modelGroupNode;
    }
    
    /**
     * Sets the content model associated with this model group content model.  This method
     * has no meaning for content models NOT of <var>type</var> <code>MODEL_GROUP</code>.
     * @return          The content model associated with this model group.
     * @see #getContentModelNode
     */
    public void setContentModelNode(CMNode modelGroupNode) {
        this.modelGroupNode = modelGroupNode;
        this.rootContentModelNode = null;
    }

    /**
     * Returns this content model in XML format.  For example:
     * &quot;<code>EMPTY</code>&quot;,  &quot;<code>ANY</code>&quot;, and 
     * &quot;<code>(HEAD,BODY)</code>&quot;.
     * @return  The string represenation of the content model or pseudo content model.
     * @see #setPseudoContentModel
     */
    public String toString() {
        if (null != this.pseudo)  return this.pseudo;
        String ret = "com.ibm.xml.parser.ContentModel#toString(): Internal error";
        switch (this.type) {
          case ElementDecl.EMPTY:
            ret = "EMPTY";
            break;
          case ElementDecl.ANY:
            ret = "ANY";
            break;

          case ElementDecl.MODEL_GROUP:
          case ElementDecl.PCDATA:
            if (this.modelGroupNode instanceof CM1op && ((CM1op)this.modelGroupNode).getNode() instanceof CMLeaf) {
                CM1op cs1 = (CM1op)this.modelGroupNode;
                ret = "("+cs1.getNode()+")"+(char)cs1.getType();
            } else if (this.modelGroupNode instanceof CMLeaf) {
                ret = "("+this.modelGroupNode+")";
            } else
                ret = this.modelGroupNode.toString();
            break;

        }
        return ret;
    }
    
    /**
     * Returns the pseudo content model being used in place of an actual content model.
     * <p>Pseudo content models are useful when the application does not care about
     * the validity of a document's structure, and wishes to quickly specify a literal
     * string to represent the content model in use.  For example, instead of specifying
     * an element declaration as:
     * <pre>
     *
     * CMNode model = new CM1op('*', new CM2op('|', new CM2op('|', new CMLeaf("#PCDATA"), new CMLeaf("FOO")), new CMLeaf("BAR")));
     * ContentModel cm = factory.createContentModel(model);
     * ElementDecl ed = fatory.createElementDecl("ROOT", cm); 
     * </pre>
     * <p>..the same element declaration could be more directly specified as:
     * <pre>
     *
     * ContentModel cm = factory.createContentModel(ElementDecl.MODEL_GROUP);
     * cm.setPseudoContentModel("(#PCDATA|FOO|BAR)*");
     * ElementDecl ed = factory.createElementDecl("ROOT", cm); 
     *
     * </pre>
     * @return  A literal string representing this content model.  Note that this value
     *          is not calculated from an actual content model specification; rather, 
     *          it simply returns the value set by <code>setPseudoContentModel</code>.
     * @see #setPseudoContentModel
     */
    public String getPseudoContentModel() {
        return this.pseudo;
    }

    /**
     * Sets the pseudo content model being used in place of an actual content model.
     * <p>Refer to <code>getPseudoContentModel</code> for a descripion of pseudo content
     * models.
     * @param   literal The literal string to be used in place of an actual content model.
     * @see #getPseudoContentModel
     */
    public void setPseudoContentModel(String literal) {
        this.pseudo = literal;
    }

    int getType() {
        return this.type;
    }

    void setType(int arg) {
        this.type = arg;
        if (ElementDecl.EMPTY == arg || ElementDecl.ANY == arg)
            this.modelGroupNode = null;
    }

    static class Symbol {
        String m_sym;
        int m_id;
        Symbol(String s, int i) {
            m_sym = s;
            m_id = i;
        }
    }
    
    void toDFA() {
        if (null == this.modelGroupNode)  return;
        if (null != this.rootContentModelNode)  return;
        CMLeaf terminalleaf = new CMLeaf(DTD.CM_EOC);
        this.rootContentModelNode = new CM2op(',', checkPlus(this.modelGroupNode), terminalleaf);
                                                // Numbering leafs
        Vector leafs = new Vector();
        countLeaf(leafs, this.rootContentModelNode);
        int nleafs = leafs.size();
        this.rootContentModelNode.prepare(nleafs);
                                                // Make symbol table
        this.symbolHashTable = new Hashtable();            // symbol-symbolnumber table
        int nofsymbols = 0;
        for (int i = 0;  i < nleafs;  i ++) {
            String n = ((CMLeaf)leafs.elementAt(i)).getName();
            if (null != n) {
                if (!this.symbolHashTable.containsKey(n))
                    this.symbolHashTable.put(n, new Symbol(n, nofsymbols++));
            }
        }
                                                // Setup followpos
        BitSet[] followposs = new BitSet[nleafs];
        for (int i = 0;  i < nleafs;  i ++)  followposs[i] = new BitSet(nleafs);
        this.rootContentModelNode.setFollowpos(followposs);

        Vector Dstates = new Vector();          // Vector of state(BitSet)
        Vector Dtranv = new Vector();           // Vector of symbol-nextstate table.
        Hashtable stable = new Hashtable();     // state(BitSet)-state(int) table.

        BitSet T = this.rootContentModelNode.firstpos();
        int newstatenumber = 0;                 // == Dstates.size()
        int firstunmarkedstate = 0;
        int terminalleafposition = terminalleaf.getPosition();
        Vector terminalstate = new Vector();    // Boolean
        stable.put(T, new Integer(newstatenumber++));
        Dstates.addElement(T);
        Dtranv.addElement(makeArrayFilledMinus1(nofsymbols));
        BitSet empty = new BitSet(nleafs);

        while (firstunmarkedstate < newstatenumber) {
            T = (BitSet)Dstates.elementAt(firstunmarkedstate++);
            int[] Dtran1 = (int[])Dtranv.elementAt(((Integer)stable.get(T)).intValue());
            terminalstate.addElement(new Boolean(T.get(terminalleafposition)));
            for (Enumeration en = this.symbolHashTable.elements();  en.hasMoreElements();  ) {
                Symbol sym = (Symbol)en.nextElement();
                BitSet U = new BitSet(nleafs);
                for (int p = 0;  p < nleafs;  p ++) {
                    if (T.get(p)) {
                        CMLeaf nl = (CMLeaf)leafs.elementAt(p);
                        if (nl.getName().equals(sym.m_sym))
                            U.or(followposs[p]);
                    }
                }
                if (!empty.equals(U)) {
                    if (!stable.containsKey(U)) {
                        Dstates.addElement(U);
                        Dtranv.addElement(makeArrayFilledMinus1(nofsymbols));
                        stable.put(U, new Integer(newstatenumber++));
                    } 
                                                // Dtran[T, a] := U
                    Dtran1[sym.m_id] = ((Integer)stable.get(U)).intValue();
                }
            }
        }
        this.symbolNextStateTable = new Object[Dtranv.size()];
        Dtranv.copyInto(this.symbolNextStateTable);
        this.terminalFlag = new boolean[Dtranv.size()];
        for (int i = 0;  i < terminalstate.size();  i ++)
            this.terminalFlag[i] = ((Boolean)terminalstate.elementAt(i)).booleanValue();
    }
    
    boolean check(TXElement t) throws LibraryException {
        if (ElementDecl.EMPTY == this.type) {
            return t.isEmpty();
        } else if (ElementDecl.ANY == this.type) {
            return true;
        } else if (ElementDecl.MODEL_GROUP == this.type) {
            toDFA();
            int length = t.size();
            int state = 0;
            for (int i = 0;  i < length;  i ++) {
                Child ae = t.elementAt(i);
                if ((ae instanceof TXText && !((TXText)ae).getIsIgnorableWhitespace())
                    || ae instanceof TXElement) {
                    String sym = (ae instanceof TXText)
                        ? DTD.CM_PCDATA : ((TXElement)ae).getName();
                    int symid = getSymbolID(sym);
                    if (symid < 0)  return false;
                    state = ((int[])this.symbolNextStateTable[state])[symid];
                    if (0 > state)  return false;
                }
            }
            return this.terminalFlag[state]; 
        }
        throw new LibraryException("com.ibm.xml.parser.ContentModel#check("+t+"): Unsupported element declaration type detected. "+toString());
    }

    Hashtable prepareTable() {
        Hashtable hash = new Hashtable();
        toDFA();
        if (ElementDecl.MODEL_GROUP == this.type) {
            Enumeration en = this.symbolHashTable.elements();
            while (en.hasMoreElements()) {
                Symbol sym = (Symbol)en.nextElement();
                hash.put(sym.m_sym, new InsertableElement(sym.m_sym, false));
            }
        }
        hash.put(DTD.CM_PCDATA, new InsertableElement(DTD.CM_PCDATA, false));
        hash.put(DTD.CM_EOC, new InsertableElement(DTD.CM_EOC, false));
        hash.put(DTD.CM_ERROR, new InsertableElement(DTD.CM_ERROR, false));
        return hash;
    }
    
    static void cleanTable(Hashtable hash) {
        Enumeration en = hash.elements();
        while (en.hasMoreElements()) {
            InsertableElement ie = (InsertableElement)en.nextElement();
            ie.status = false;
            ie.index = -1;
        }
        if (null == hash.get(DTD.CM_PCDATA))
            hash.put(DTD.CM_PCDATA, new InsertableElement(DTD.CM_PCDATA, false));
        if (null == hash.get(DTD.CM_EOC))
            hash.put(DTD.CM_EOC, new InsertableElement(DTD.CM_EOC, false));
        if (null == hash.get(DTD.CM_ERROR))
            hash.put(DTD.CM_ERROR, new InsertableElement(DTD.CM_ERROR, false));
    }

    Hashtable getInsertableElements(TXElement el, int ind, Hashtable hash, boolean validInsertion) {
        // This method is not used by parser.
        int clen = el.size();
        if (0 > ind)  ind = 0;
        else if (clen < ind)  ind = clen;

        cleanTable(hash);
        if (ElementDecl.EMPTY == this.type) {
            ((InsertableElement)hash.get(DTD.CM_PCDATA)).status = false;
            ((InsertableElement)hash.get(DTD.CM_EOC)).status = true;
            InsertableElement ie = ((InsertableElement)hash.get(DTD.CM_ERROR));
            if (el.isEmpty()) {
                ie.status = false;
            } else {
                ie.status = true;
                ie.index = 0;
            }

        } else if (ElementDecl.ANY == this.type) {
            Enumeration en = hash.elements();
            while (en.hasMoreElements()) {
                InsertableElement ie = (InsertableElement)en.nextElement();
                ie.status = true;
            }
            ((InsertableElement)hash.get(DTD.CM_ERROR)).status = false;

        } else if (ElementDecl.MODEL_GROUP == this.type) {
            toDFA();
            int state = 0;
            boolean error = false;
            int i;
            for (i = 0;  i < ind;  i ++) {
                Child ae = el.elementAt(i);
                if ((ae instanceof TXText && !((TXText)ae).getIsIgnorableWhitespace())
                    || ae instanceof TXElement) {
                    String sym = (ae instanceof TXText)
                        ? DTD.CM_PCDATA : ((TXElement)ae).getName();
                    int symid = getSymbolID(sym);
                    if (symid < 0) {
                        error = true;
                        break;
                    }
                    state = ((int[])this.symbolNextStateTable[state])[symid];
                    if (0 > state) {
                        error = true;
                        break;
                    }
                }
            }
            if (!error) {
                Enumeration en = this.symbolHashTable.elements();
                while (en.hasMoreElements()) {
                    Symbol sym = (Symbol)en.nextElement();
                    InsertableElement ie = (InsertableElement)hash.get(sym.m_sym);
                    if (null == ie)
                        hash.put(sym.m_sym, ie = new InsertableElement(sym.m_sym));
                    int newstate = ((int[])this.symbolNextStateTable[state])[sym.m_id];
                    ie.status = (validInsertion ? checkAfterTargetPosition(el, ind, newstate)
                                 : 0 <= newstate);
                }
                ((InsertableElement)hash.get(DTD.CM_EOC)).status = this.terminalFlag[state];
            } else {
                InsertableElement ie = (InsertableElement)hash.get(DTD.CM_ERROR);
                ie.status = true;
                ie.index = i;
            }
        }
        return hash;
    }

    boolean checkAfterTargetPosition(TXElement el, int start, int state) {
        if (0 >= state)  return false;
        for (int i = start;  i < el.size();  i ++) {
            Child ae = el.elementAt(i);
            if ((ae instanceof TXText && !((TXText)ae).getIsIgnorableWhitespace())
                || ae instanceof TXElement) {
                String sym = (ae instanceof TXText)
                    ? DTD.CM_PCDATA : ((TXElement)ae).getName();
                int symid = getSymbolID(sym);
                if (symid < 0)  return false;
                state = ((int[])this.symbolNextStateTable[state])[symid];
                if (0 > state)  return false;
            }
        }
        return this.terminalFlag[state]; 
    }

    /**
     *
     * @return null if EMPTY or ANY
     */
    Vector getChildrenOrder() {
        Vector v = new Vector();
        appendNode(v, this.modelGroupNode);
        return v;
    }
    
    private void appendNode(Vector v, CMNode n) throws LibraryException {
        if (n instanceof CM1op) {
            appendNode(v, ((CM1op)n).getNode());
        } else if (n instanceof CM2op) {
            appendNode(v, ((CM2op)n).getLeft());
            appendNode(v, ((CM2op)n).getRight());
        } else if (n instanceof CMLeaf) {
            v.addElement(((CMLeaf)n).getName());
        } else {
            throw new LibraryException("com.ibm.xml.parser.ContentModel#appendNode(): Invalid CMNode detected.");
        }
    }

    private void countLeaf(Vector leafs, CMNode cs) {
        if (cs instanceof CMLeaf) {
            ((CMLeaf)cs).setPosition(leafs.size());
            leafs.addElement(cs);
        } else if (cs instanceof CM1op) {
            countLeaf(leafs, ((CM1op)cs).getNode());
        } else if (cs instanceof CM2op) {
            countLeaf(leafs, ((CM2op)cs).getLeft());
            countLeaf(leafs, ((CM2op)cs).getRight());
        }
    }

    /**
     *  r+ -> rr* and #PCDATA -> #PCDATA*  conversion
     */
    private CMNode checkPlus(CMNode c) {
        CMNode ret = null;
        if (c instanceof CM1op) {
            CM1op c1 = (CM1op)c;
            if ('+' == c1.getType()) {
                CMNode cc = checkPlus(c1.getNode());
                ret = new CM2op(',', cc, new CM1op('*', cc.cloneNode()));
            } else
                ret = new CM1op(c1.getType(), checkPlus(c1.getNode()));
        } else if (c instanceof CM2op) {
            CM2op c2 = (CM2op)c;
            ret = new CM2op(c2.getType(), checkPlus(c2.getLeft()), checkPlus(c2.getRight()));
        } else if (c instanceof CMLeaf) {
            if (((CMLeaf)c).getName().equals(DTD.CM_PCDATA)) {
                ret = new CM1op('*', c);
            } else
                ret = c;
        }
        return ret;
    }
    
    private int getSymbolID(String s) {
        Symbol sym = (Symbol)this.symbolHashTable.get(s);
        return null == sym ? -1 : sym.m_id;
    }

    private int[] makeArrayFilledMinus1(int s) {
        int[] ai = new int[s];
        for (int i = 0;  i < s;  i ++)
            ai[i] = -1;
        return ai;
    }
}
