/*
 * (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.xpointer;

import com.ibm.xml.parser.AttDef;
import com.ibm.xml.parser.Child;
import com.ibm.xml.parser.DTD;
import com.ibm.xml.parser.LibraryException;
import com.ibm.xml.parser.Parent;
import com.ibm.xml.parser.TXDocument;
import com.ibm.xml.parser.TXElement;
import com.ibm.xml.parser.XMLChar;
import java.util.Enumeration;
import java.util.Hashtable;
import java.util.Vector;
import org.w3c.dom.Attribute;
import org.w3c.dom.CDATASection;
import org.w3c.dom.Document;
import org.w3c.dom.Element;
import org.w3c.dom.Node;
import org.w3c.dom.NodeIterator;

/**
 * XPointer.
 * (Based on <a href="http://www.w3.org/TR/1998/WD-xptr-19980303">WD-xptr-19980303</a>)
 *
 * @version 1.1
 * @author TAMURA Kent &lt;kent@trl.ibm.co.jp&gt;
 */
public class XPointer implements java.io.Serializable {
    public final static String S_ALL = "all";   // InstanceOrAll
    public final static String S_END = "end";   // Position

    public final static int NT_NONE = 0;
    public final static int NT_NAME = 1;
    public final static int NT_ELEMENT = 2;
    public final static int NT_PI = 3;
    public final static int NT_COMMENT = 4;
    public final static int NT_TEXT = 5;
    public final static int NT_CDATA = 6;
    public final static int NT_ALL = 7;
    public final static String nodetypes[] = {
        null, null, "#element", "#pi", "#comment",
        "#text", "#cdata", "#all",
    };
    public final static String S_ELEMENT = "element";
    public final static String S_PI = "pi";
    public final static String S_COMMENT = "comment";
    public final static String S_TEXT = "text";
    public final static String S_CDATA = "cdata";
    public final static String S_NIMPLIED = "#IMPLIED";
    public final static String S_IMPLIED = "IMPLIED";

    public final static String literals[] = {
        null, "root", "origin", "id", "html",
        "child", "descendant", "ancestor", "preceding",
        "psibling", "following", "fsibling",
        "span", "attr", "string",
    };
    public final static int ST_NONE = -1;
    public final static int ST_ROOT = 1;
    public final static int ST_ORIGIN = ST_ROOT+1;
    public final static int ST_ID = ST_ORIGIN+1;
    public final static int ST_HTML = ST_ID+1;
    public final static int ST_CHILD = ST_HTML+1;
    public final static int ST_DESCENDANT = ST_CHILD+1;
    public final static int ST_ANCESTOR = ST_DESCENDANT+1;
    public final static int ST_PRECEDING = ST_ANCESTOR+1;
    public final static int ST_PSIBLING = ST_PRECEDING+1;
    public final static int ST_FOLLOWING = ST_PSIBLING+1;
    public final static int ST_FSIBLING = ST_FOLLOWING+1;
    public final static int ST_SPAN = ST_FSIBLING+1;
    public final static int ST_ATTR = ST_SPAN+1;
    public final static int ST_STRING = ST_ATTR+1;

    public static final int T_IMPLIED = 0;
    public static final int T_ANY = T_IMPLIED+1;
    public static final int T_NAME = T_ANY+1;
    public static final int T_EXACT = T_NAME+1;


    AbsTerm absTerm;
    Vector otherTerms;
    String string = null;

    /**
     *
     * @param abs null is ok.
     * @param otherterms null is ok.
     */
    public XPointer(AbsTerm abs, Vector otherterms) {
        this.absTerm = abs;
        this.otherTerms = otherterms == null ? new Vector() : otherterms;
    }

    /**
     *
     */
    public AbsTerm getAbsTerm() {
        return this.absTerm;
    }
    /**
     *
     */
    public void setAbsTerm(AbsTerm abs) {
        this.absTerm = abs;
        this.string = null;
    }

    /**
     * Return a Vecotr consisted of <code>RelTerm / SpanTerm / AttrTerm / StringTerm</code>.
     */
    public Vector getOtherTermsVector() {
        return this.otherTerms;
    }

    /**
     *
     */
    public void appendOtherTerm(OtherTerm ot) {
        if (null == this.otherTerms)
            this.otherTerms = new Vector();
        this.otherTerms.addElement(ot);
        this.string = null;
    }

    /**
     *
     */
    public void insertOtherTerm(OtherTerm ot) {
        if (null == this.otherTerms)
            this.otherTerms = new Vector();
        this.otherTerms.insertElementAt(ot, 0);
        this.string = null;
    }

    /**
     *
     * @return Removed object; <code>null</code> when this has no OtherTerm.
     */
    public OtherTerm removeLastOtherTerm() {
        OtherTerm ret = null;
        synchronized (this.otherTerms) {
            int len = this.otherTerms.size();
            if (len > 0) {
                ret = (OtherTerm)this.otherTerms.elementAt(len-1);
                this.otherTerms.removeElementAt(len-1);
            }
        }
        this.string = null;
        return ret;
    }

    /**
     * Return a String representation of this instance.
     */
    public String toString() {
        if (null != this.string) {
            return this.string;
        }
        StringBuffer sb = new StringBuffer(100);
        if (null != this.absTerm) {
            sb.append(this.absTerm.toString());
            if (0 < this.otherTerms.size())
                sb.append(".");
        }
        int i = 0;
        for (Enumeration en = this.otherTerms.elements();  en.hasMoreElements();  ) {
            if (i > 0)  sb.append(".");
            i ++;
            sb.append(en.nextElement().toString());
        }
        return this.string = sb.toString();
    }

    /**
     * Returns a node pointed by this <CODE>XPointer</CODE> instance.
     *
     * <DL>  
     *   <DT>The following terms aren't supported in this method:</DT>
     *   <DD><KBD>origin()</KBD></DD>
     *   <DD><KBD>html()</KBD></DD>
     *   <DD><KBD>span()</KBD></DD>
     *   <DD><KBD>string()</KBD></DD>
     * </DL>
     *
     * @return Matched nodes. Never returns null.
     */
    public synchronized Pointed point(TXDocument doc) {
        Node origin = doc.getDocumentElement();
        if (this.absTerm == null || this.absTerm.getType() == XPointer.ST_ROOT) {
        } else if (this.absTerm.getType() == XPointer.ST_ORIGIN
                   || this.absTerm.getType() == XPointer.ST_HTML) {
            return new Pointed();               // Not supported.
        } else {                                // ID
            DTD dtd = doc.getDTD();
            if (dtd == null)  return new Pointed(); // No ID information.
            origin = dtd.checkID(this.absTerm.getParameter());
            if (origin == null)  return new Pointed(); // No such an ID.
        }
        return point(origin);
    }

    /**
     *
     */
    public synchronized Pointed point(Node origin) {
        Pointed pointed = new Pointed();
        pointed.add(origin);
        this.previous = XPointer.ST_NONE;
        Enumeration en = this.otherTerms.elements();
        while (en.hasMoreElements()) {
            Object obj = en.nextElement();
            Pointed result = new Pointed();
            Enumeration en2 = pointed.elements();
            while (en2.hasMoreElements()) {
                Pointed.Item it = (Pointed.Item)en2.nextElement();
                if (it.node != null)
                    point(result, obj, it.node);
            }
            pointed = result;
        }
        return pointed;
    }
    private transient int previous;
    private void point(Pointed result, Object obj, Node origin) {
        if (obj instanceof RelTerm) {
            RelTerm rel = (RelTerm)obj;

            int type = rel.getType();
            if (type == XPointer.ST_NONE) {
                if (this.previous == XPointer.ST_NONE) // This XPointer has an error.
                    return;
                type = this.previous;
            }

            int instance = rel.getInstance();
            if (instance == 0)  return;         // Invalid XPointer.
            Vector v;
            NodeIterator ni;
            Node n;
            switch (type) {
              case XPointer.ST_CHILD:
                ni = origin.getChildNodes();
                if (rel.isAll()) {
                    while ((n = ni.toNextNode()) != null) {
                        if (rel.match(n))
                            result.add(n);
                    }
                } else if (instance > 0) {
                    while ((n = ni.toNextNode()) != null) {
                        if (rel.match(n) && --instance == 0) {
                            result.add(n);
                            break;
                        }
                    }
                } else {
                    ni.toLastNode();
                    while ((n = ni.toPrevNode()) != null) {
                        if (rel.match(n) && ++instance == 0) {
                            result.add(n);
                            break;
                        }
                    }
                }
                break;

              case XPointer.ST_DESCENDANT:
                if (!(origin instanceof Element))
                    return;
                v = new Vector();
                addMatchingNodes(v, (Element)origin, rel);
                if (rel.isAll()) {
                    for (int i = 0;  i < v.size();  i ++)
                        result.add((Node)v.elementAt(i));
                } else if (instance > 0) {
                    if (instance <= v.size())
                        result.add((Node)v.elementAt(instance-1));
                } else {
                    if (instance+v.size() >= 0)
                        result.add((Node)v.elementAt(instance+v.size()));
                }
                break;

              case XPointer.ST_ANCESTOR:
                v = new Vector();
                while (origin.getParentNode() instanceof Element) {
                    origin = origin.getParentNode();
                    if (rel.match(origin))
                        v.addElement(origin);
                }
                if (rel.isAll()) {
                    for (int i = 0;  i < v.size();  i ++)
                        result.add((Node)v.elementAt(i));
                } else if (instance > 0) {
                    if (instance <= v.size())
                        result.add((Node)v.elementAt(instance-1));
                } else {
                    if (instance+v.size() >= 0)
                        result.add((Node)v.elementAt(instance+v.size()));
                }
                break;

              case XPointer.ST_PRECEDING:
                v = new Vector();
                while (origin.getPreviousSibling() != null
                       || origin.getParentNode() instanceof Element) {
                    if (origin.getPreviousSibling() == null)
                        origin = origin.getParentNode();
                    else
                        origin = origin.getPreviousSibling();
                    if (rel.match(origin))
                        v.addElement(origin);
                }
                if (rel.isAll()) {
                    for (int i = 0;  i < v.size();  i ++)
                        result.add((Node)v.elementAt(i));
                } else if (instance > 0) {
                    if (instance <= v.size())
                        result.add((Node)v.elementAt(instance-1));
                } else {
                    if (instance+v.size() >= 0)
                        result.add((Node)v.elementAt(instance+v.size()));
                }
                break;

              case XPointer.ST_FOLLOWING:
                v = new Vector();
                while (origin.getNextSibling() != null
                       || origin.getParentNode() instanceof Element) {
                    if (origin.getNextSibling() == null)
                        origin = origin.getParentNode();
                    else
                        origin = origin.getNextSibling();
                    if (rel.match(origin))
                        v.addElement(origin);
                }
                if (rel.isAll()) {
                    for (int i = 0;  i < v.size();  i ++)
                        result.add((Node)v.elementAt(i));
                } else if (instance > 0) {
                    if (instance <= v.size())
                        result.add((Node)v.elementAt(instance-1));
                } else {
                    if (instance+v.size() >= 0)
                        result.add((Node)v.elementAt(instance+v.size()));
                }
                break;

              case XPointer.ST_PSIBLING:
                if (rel.isAll()) {
                    while ((origin = origin.getPreviousSibling()) != null) {
                        if (rel.match(origin))
                            result.add(origin);
                    }
                } else if (instance > 0) {
                    while ((origin = origin.getPreviousSibling()) != null) {
                        if (rel.match(origin) && --instance == 0) {
                            result.add(origin);
                            break;
                        }
                    }
                } else {
                    instance = Math.abs(instance);
                    ni = origin.getParentNode().getChildNodes();
                    while ((n = ni.toNextNode()) != null) {
                        if (rel.match(n) && ++instance == 0) {
                            result.add(n);
                            break;
                        }
                    }
                }
                break;

              case XPointer.ST_FSIBLING:
                if (rel.isAll()) {
                    while ((origin = origin.getNextSibling()) != null) {
                        if (rel.match(origin))
                            result.add(origin);
                    }
                } else if (instance > 0) {
                    while ((origin = origin.getNextSibling()) != null) {
                        if (rel.match(origin) && --instance == 0) {
                            result.add(origin);
                            break;
                        }
                    }
                } else {
                    instance = Math.abs(instance);
                    ni = origin.getParentNode().getChildNodes();
                    ni.toLastNode();
                    while ((n = ni.toPrevNode()) != null) {
                        if (rel.match(n) && ++instance == 0) {
                            result.add(n);
                            break;
                        }
                    }
                }
                break;
            }

            this.previous = type;

        } else if (obj instanceof StringTerm) {
            this.previous = XPointer.ST_NONE;
                                                // Not supported yet.

        } else if (obj instanceof SpanTerm) {
            this.previous = XPointer.ST_NONE;
                                                // Not supported.
        } else if (obj instanceof AttrTerm) {
            this.previous = XPointer.ST_NONE;
            if (origin instanceof Element) {
                String value = ((Element)origin).getAttribute(((AttrTerm)obj).getName());
                if (value != null)
                    result.add(value);
            }

        } else {
            throw new LibraryException("com.ibm.xml.xpointer.XPointer#point(): Internal Error: unknown OtherTerm.");
        }
    }

    static private void addMatchingNodes(Vector v, Element el, RelTerm rel) {
        NodeIterator ni = el.getChildNodes();
        Node n;
        while ((n = ni.toNextNode()) != null) {
            if (rel.match(n)) {
                v.addElement(n);
            }
            if (n instanceof Element)
                addMatchingNodes(v, (Element)n, rel);
        }
    }

    /**
     * @return an XPointer instance, or <var>null</var>
     * @see com.ibm.xml.parser.Child#makeXPointer
     */
    public static XPointer makeXPointer(Child target) {
        if (target.getNodeType() == Node.DOCUMENT)
            return null;                        // XPointer can't point the whole of a document.

                                                // Search for root Document
        Child ch = target;
        while (ch.getNodeType() != Node.DOCUMENT) {
            ch = (Child)ch.getParentNode();
            if (ch == null)
                return null;                    // No document
        }
        TXDocument tdoc = (TXDocument)ch;
        if (target.getParentNode() == tdoc) {   // target is the root element
            return new XPointer(new AbsTerm(XPointer.ST_ROOT, null), null);
        }

        DTD dtd = tdoc.getDTD();
        if (dtd != null) {                      // Examine ID
            Node parent = target.getNodeType() != Node.ELEMENT
                ? target.getParentNode() : target;
            do {
                TXElement el = (TXElement)parent;
                Enumeration attrs = el.attributeElements();
                while (attrs.hasMoreElements()) {
                    Attribute a = (Attribute)attrs.nextElement();
                    AttDef ad = dtd.getAttributeDeclaration(el.getName(), a.getName());
                    if (ad != null && ad.getDeclaredType() == AttDef.ID) {
                        XPointer xp = new XPointer(new AbsTerm(XPointer.ST_ID, a.getValue()), null);
                        if (el != target) {
                            ch = target;
                            RelTerm lastrelterm = null;
                            do {
                                xp.insertOtherTerm(lastrelterm = makeRelTerm(ch));
                                ch = (Child)ch.getParentNode();
                            } while (ch != el);
                            lastrelterm.setType(XPointer.ST_CHILD);
                        }
                        return xp;
                    }
                }
                parent = parent.getParentNode();
            } while (!(parent instanceof TXDocument));
                                                // No ID attribute in parent elements
        }

        TXElement root = (TXElement)tdoc.getDocumentElement();
        XPointer xp = new XPointer(new AbsTerm(XPointer.ST_ROOT, null), null);
        ch = target;
        RelTerm lastrelterm = null;
        do {
            xp.insertOtherTerm(lastrelterm = makeRelTerm(ch));
            ch = (Child)ch.getParentNode();
        } while (ch != root);
        lastrelterm.setType(XPointer.ST_CHILD);
        
        return xp;
    }

    /**
     *
     * @param ch A child of el; TXElement or TXText or TXCDATASection or TXComment or TXPI
     * @return A type of this RelTem is always ST_NONE.
     */
    private static RelTerm makeRelTerm(Child ch)
        throws LibraryException, IllegalArgumentException {
        Enumeration en = ((TXElement)ch.getParentNode()).elements();
        int type = ch.getNodeType();
        int count = 1;
        switch (type) {
          case Node.ELEMENT:
            String name = ((TXElement)ch).getName();
            while (en.hasMoreElements()) {
                Child child = (Child)en.nextElement();
                if (child.getNodeType() == type && ((TXElement)child).getName().equals(name)) {
                    if (child == ch) {
                        return new RelTerm(XPointer.ST_NONE, false, count, name);
                    } else
                        count ++;
                }
            }
            break;

          case Node.TEXT:                       // and CDATA
            if (ch instanceof CDATASection) {
                while (en.hasMoreElements()) {
                    Child child = (Child)en.nextElement();
                    if (child.getNodeType() == type && child instanceof CDATASection) {
                        if (child == ch) {
                            return new RelTerm(XPointer.ST_NONE, false, count, XPointer.NT_CDATA);
                        } else
                            count ++;
                    }
                }
            } else {
                while (en.hasMoreElements()) {
                    Child child = (Child)en.nextElement();
                    if (child.getNodeType() == type && !(child instanceof CDATASection)) {
                        if (child == ch) {
                            return new RelTerm(XPointer.ST_NONE, false, count, XPointer.NT_TEXT);
                        } else
                            count ++;
                    }
                }
            }
            break;

          case Node.COMMENT:
          case Node.PI:
            while (en.hasMoreElements()) {
                Child child = (Child)en.nextElement();
                if (child.getNodeType() == type) {
                    if (child == ch) {
                        return new RelTerm(XPointer.ST_NONE, false, count,
                                           type == Node.COMMENT
                                           ? XPointer.NT_COMMENT
                                           : XPointer.NT_PI);
                    } else
                        count ++;
                }
            }
            break;

          default:
            throw new IllegalArgumentException("com.ibm.xml.xpointer.XPointer#makeRelTerm():");
        }
        throw new LibraryException("com.ibm.xml.xpointer.XPointer#makeRelTerm(): Specified child isn't a child of specified element.");
    }
}

