/*

 * Copyright (c) 2010, Oracle and/or its affiliates. All rights reserved.

 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

 *

 * This code is free software; you can redistribute it and/or modify it

 * under the terms of the GNU General Public License version 2 only, as

 * published by the Free Software Foundation.  Oracle designates this

 * particular file as subject to the "Classpath" exception as provided

 * by Oracle in the LICENSE file that accompanied this code.

 *

 * This code is distributed in the hope that it will be useful, but WITHOUT

 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

 * version 2 for more details (a copy is included in the LICENSE file that

 * accompanied this code).

 *

 * You should have received a copy of the GNU General Public License version

 * 2 along with this work; if not, write to the Free Software Foundation,

 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

 *

 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

 * or visit www.oracle.com if you need additional information or have any

 * questions.

 */

package xmlkit; // -*- mode: java; indent-tabs-mode: nil -*-

// XML Implementation packages:

import java.util.*;

import java.io.Reader;

import java.io.Writer;

import java.io.OutputStream;

import java.io.InputStreamReader;

import java.io.OutputStreamWriter;

import java.io.BufferedReader;

import java.io.PrintWriter;

import java.io.StringWriter;

import java.io.StringReader;

import java.io.IOException;

import org.xml.sax.XMLReader;

import org.xml.sax.InputSource;

import org.xml.sax.ContentHandler;

import org.xml.sax.SAXException;

import org.xml.sax.SAXParseException;

import org.xml.sax.Attributes;

import org.xml.sax.ext.LexicalHandler;

import org.xml.sax.helpers.AttributesImpl;

/**

 * A kit of methods and classes useful for manipulating XML trees in

 * memory. They are very compact and easy to use. An XML element

 * occupies six pointers of overhead (like two arrays) plus a pointer

 * for its name, each attribute name and value, and each sub-element.

 * Many useful XML operations (or Lisp-like calls) can be accomplished

 * with a single method call on an element itself.

 * <p>

 * There is strong integration with the Java collection classes.

 * There are viewing and conversion operators to and from various

 * collection types. Elements directly support list iterators.

 * Most <tt>List</tt> methods work analogously on elements.

 * <p>

 * Because of implementation compromises, these XML trees are less

 * functional than many standard XML classes.

 * <ul>

 * <li>There are no parent or sibling pointers in the tree.</li>

 * <li>Attribute names are simple strings, with no namespaces.</li>

 * <li>There is no internal support for schemas or validation.</li>

 * </ul>

 * <p>

 * Here is a summary of functionality in <tt>XMLKit</tt>.

 * (Overloaded groups of methods are summarized by marking some

 * arguments optional with their default values. Some overloaded

 * arguments are marked with their alternative types separated by

 * a bar "|". Arguments or return values for which a null is

 * specially significant are marked by an alternative "|null".

 * Accessors which have corresponding setters are marked

 * by "/set". Removers which have corresponding retainers are marked

 * by "/retain".)

 * <pre>

 * --- element construction

 * new Element(int elemCapacity=4), String name=""

 * new Element(String name, String[] attrs={}, Element[] elems={}, int elemCapacity=4)

 * new Element(String name, String[] attrs, Object[] elems, int elemCapacity=4)

 * new Element(Element original) // shallow copy

 * new Element(String name="", Collection elems) // coercion

 *

 * Element shallowCopy()

 * Element shallowFreeze() // side-effecting

 * Element deepCopy()

 * Element deepFreeze() // not side-effecting

 *

 * EMPTY // frozen empty anonymous element

 * void ensureExtraCapacity(int)

 * void trimToSize()

 * void sortAttrs() // sort by key

 *

 * --- field accessors

 * String getName()/set

 * int size()

 * boolean isEmpty()

 * boolean isFrozen()

 * boolean isAnonymous()

 * int getExtraCapacity()/set

 * int attrSize()

 *

 * --- attribute accessors

 * String getAttr(int i)/set

 * String getAttrName(int i)

 *

 * String getAttr(String key)/set

 * List getAttrList(String key)/set

 * Number getAttrNumber(String key)/set

 * long getAttrLong(String key)/set

 * double getAttrDouble(String key)/set

 *

 * String getAttr(String key, String dflt=null)

 * long getAttrLong(String key, long dflt=0)

 * double getAttrDouble(String key, double dflt=0)

 *

 * Element copyAttrsOnly()

 * Element getAttrs()/set =&gt; <em>&lt;&gt;&lt;key&gt;value&lt;/key&gt;...&lt;/&gt;</em>

 * void addAttrs(Element attrs)

 *

 * void removeAttr(int i)

 * void clearAttrs()

 *

 * --- element accessors

 * Object get(int i)/set

 * Object getLast() | null

 * Object[] toArray()

 * Element copyContentOnly()

 *

 * void add(int i=0, Object subElem)

 * int addAll(int i=0, Collection | Element elems)

 * int addContent(int i=0, TokenList|Element|Object|null)

 * void XMLKit.addContent(TokenList|Element|Object|null, Collection sink|null)

 *

 * void clear(int beg=0, int end=size)

 * void sort(Comparator=contentOrder())

 * void reverse()

 * void shuffle(Random rnd=(anonymous))

 * void rotate(int distance)

 * Object min/max(Comparator=contentOrder())

 *

 * --- text accessors

 * CharSequence getText()/set

 * CharSequence getUnmarkedText()

 * int addText(int i=size, CharSequence)

 * void trimText();

 *

 * --- views

 * List asList() // element view

 * ListIterator iterator()

 * PrintWriter asWriter()

 * Map asAttrMap()

 * Iterable<CharSequence> texts()

 * Iterable<Element> elements()

 * Iterable<T> partsOnly(Class<T>)

 * String[] toStrings()

 *

 * --- queries

 * boolean equals(Element | Object)

 * int compareTo(Element | Object)

 * boolean equalAttrs(Element)

 * int hashCode()

 * boolean isText() // every sub-elem is CharSequence

 * boolean hasText() // some sub-elem is CharSequence

 *

 * boolean contains(Object)

 * boolean containsAttr(String)

 *

 * int indexOf(Object)

 * int indexOf(Filter, int fromIndex=0)

 * int lastIndexOf(Object)

 * int lastIndexOf(Filter, int fromIndex=size-1)

 *

 * int indexOfAttr(String)

 *

 * // finders, removers, and replacers do addContent of each filtered value

 * // (i.e., TokenLists and anonymous Elements are broken out into their parts)

 * boolean matches(Filter)

 *

 * Object find(Filter, int fromIndex=0)

 * Object findLast(Filter, int fromIndex=size-1)

 * Element findAll(Filter, int fromIndex=0 & int toIndex=size)

 * int findAll(Filter, Collection sink | null, int fromIndex=0 & int toIndex=size)

 *

 * Element removeAllInTree(Filter)/retain

 * int findAllInTree(Filter, Collection sink | null)

 * int countAllInTree(Filter)

 * Element removeAllInTree(Filter)/retain

 * int removeAllInTree(Filter, Collection sink | null)/retain

 * void replaceAllInTree(Filter)

 *

 * Element findElement(String name=any)

 * Element findAllElements(String name=any)

 *

 * Element findWithAttr(String key, String value=any)

 * Element findAllWithAttr(String key, String value=any)

 *

 * Element removeElement(String name=any)

 * Element removeAllElements(String name=any)/retain

 *

 * Element removeWithAttr(String key, String value=any)

 * Element removeAllWithAttr(String key, String value=any)/retain

 *

 * //countAll is the same as findAll but with null sink

 * int countAll(Filter)

 * int countAllElements(String name=any)

 * int countAllWithAttr(String key, String value=any)

 *

 * void replaceAll(Filter, int fromIndex=0 & int toIndex=size)

 * void replaceAllInTree(Filter)

 * void XMLKit.replaceAll(Filter, List target) //if(fx){remove x;addContent fx}

 *

 * --- element mutators

 * boolean remove(Object)

 * Object remove(int)

 * Object removeLast() | null

 *

 * Object remove(Filter, int fromIndex=0)

 * Object removeLast(Filter, int fromIndex=size-1)

 * Element sink = removeAll(Filter, int fromIndex=0 & int toIndex=size)/retain

 * int count = removeAll(Filter, int fromIndex=0 & int toIndex=size, Collection sink | null)/retain

 *

 * Element removeAllElements(String name=any)

 *

 * --- attribute mutators

 * ??int addAllAttrsFrom(Element attrSource)

 *

 * --- parsing and printing

 * void tokenize(String delims=whitespace, returnDelims=false)

 * void writeTo(Writer)

 * void writePrettyTo(Writer)

 * String prettyString()

 * String toString()

 *

 * ContentHandler XMLKit.makeBuilder(Collection sink, tokenizing=false, makeFrozen=false) // for standard XML parser

 * Element XMLKit.readFrom(Reader, tokenizing=false, makeFrozen=false)

 * void XMLKit.prettyPrintTo(Writer | OutputStream, Element)

 * class XMLKit.Printer(Writer) { void print/Recursive(Element) }

 * void XMLKit.output(Object elem, ContentHandler, LexicalHandler=null)

 * void XMLKit.writeToken(String, char quote, Writer)

 * void XMLKit.writeCData(String, Writer)

 * Number XMLKit.convertToNumber(String, Number dflt=null)

 * long XMLKit.convertToLong(String, long dflt=0)

 * double XMLKit.convertToDouble(String, double dflt=0)

 *

 * --- filters

 * XMLKit.ElementFilter { Element filter(Element) }

 * XMLKit.elementFilter(String name=any | Collection nameSet)

 * XMLKit.AttrFilter(String key) { boolean test(String value) }

 * XMLKit.attrFilter(String key, String value=any)

 * XMLKit.attrFilter(Element matchThis, String key)

 * XMLKit.classFilter(Class)

 * XMLKit.textFilter() // matches any CharSequence

 * XMLKit.specialFilter() // matches any Special element

 * XMLKit.methodFilter(Method m, Object[] args=null, falseResult=null)

 * XMLKit.testMethodFilter(Method m, Object[] args=null)

 * XMLKit.not(Filter) // inverts sense of Filter

 * XMLKit.and(Filter&Filter | Filter[])

 * XMLKit.or(Filter&Filter | Filter[])

 * XMLKit.stack(Filter&Filter | Filter[]) // result is (fx && g(fx))

 * XMLKit.content(Filter, Collection sink) // copies content to sink

 * XMLKit.replaceInTree(Filter pre, Filter post=null) // pre-replace else recur

 * XMLKit.findInTree(Filter pre, Collection sink=null) // pre-find else recur

 * XMLKit.nullFilter() // ignores input, always returns null (i.e., false)

 * XMLKit.selfFilter( ) // always returns input (i.e., true)

 * XMLKit.emptyFilter() // ignores input, always returns EMPTY

 * XMLKit.constantFilter(Object) // ignores input, always returns constant

 *

 * --- misc

 * Comparator XMLKit.contentOrder() // for comparing/sorting mixed content

 * Method XMLKit.Element.method(String name) // returns Element method

 * </pre>

 *

 * @author jrose

 */

public abstract class XMLKit {

    private XMLKit() {

    }

    // We need at least this much slop if the element is to stay unfrozen.

    static final int NEED_SLOP = 1;

    static final Object[] noPartsFrozen = {};

    static final Object[] noPartsNotFrozen = new Object[NEED_SLOP];

    static final String WHITESPACE_CHARS = " \t\n\r\f";

    static final String ANON_NAME = new String("*");  // unique copy of "*"

    public static final class Element implements Comparable<Element>, Iterable<Object> {

        // Note:  Does not implement List, because it has more

        // significant parts besides its sub-elements.  Therefore,

        // hashCode and equals must be more distinctive than Lists.

        // <name> of element

        String name;

        // number of child elements, in parts[0..size-1]

        int size;

        // The parts start with child elements::  {e0, e1, e2, ...}.

        // Following that are optional filler elements, all null.

        // Following that are attributes as key/value pairs.

        // They are in reverse: {...key2, val2, key1, val1, key0, val0}.

        // Child elements and attr keys and values are never null.

        Object[] parts;

        // Build a partially-constructed node.

        // Caller is responsible for initializing promised attributes.

        Element(String name, int size, int capacity) {

            this.name = name.toString();

            this.size = size;

            assert (size <= capacity);

            this.parts = capacity > 0 ? new Object[capacity] : noPartsFrozen;

        }

        /** An anonymous, empty element.

         *  Optional elemCapacity argument is expected number of sub-elements.

         */

        public Element() {

            this(ANON_NAME, 0, NEED_SLOP + 4);

        }

        public Element(int extraCapacity) {

            this(ANON_NAME, 0, NEED_SLOP + Math.max(0, extraCapacity));

        }

        /** An empty element with the given name.

         *  Optional extraCapacity argument is expected number of sub-elements.

         */

        public Element(String name) {

            this(name, 0, NEED_SLOP + 4);

        }

        public Element(String name, int extraCapacity) {

            this(name, 0, NEED_SLOP + Math.max(0, extraCapacity));

        }

        /** An empty element with the given name and attributes.

         *  Optional extraCapacity argument is expected number of sub-elements.

         */

        public Element(String name, String... attrs) {

            this(name, attrs, (Element[]) null, 0);

        }

        public Element(String name, String[] attrs, int extraCapacity) {

            this(name, attrs, (Element[]) null, extraCapacity);

        }

        /** An empty element with the given name and sub-elements.

         *  Optional extraCapacity argument is expected extra sub-elements.

         */

        public Element(String name, Element... elems) {

            this(name, (String[]) null, elems, 0);

        }

        public Element(String name, Element[] elems, int extraCapacity) {

            this(name, (String[]) null, elems, extraCapacity);

        }

        /** An empty element with the given name, attributes, and sub-elements.

         *  Optional extraCapacity argument is expected extra sub-elements.

         */

        public Element(String name, String[] attrs, Object... elems) {

            this(name, attrs, elems, 0);

        }

        public Element(String name, String[] attrs, Object[] elems, int extraCapacity) {

            this(name, 0,

                    ((elems == null) ? 0 : elems.length)

                    + Math.max(0, extraCapacity)

                    + NEED_SLOP

                    + ((attrs == null) ? 0 : attrs.length));

            int ne = ((elems == null) ? 0 : elems.length);

            int na = ((attrs == null) ? 0 : attrs.length);

            int fillp = 0;

            for (int i = 0; i < ne; i++) {

                if (elems[i] != null) {

                    parts[fillp++] = elems[i];

                }

            }

            size = fillp;

            for (int i = 0; i < na; i += 2) {

                setAttr(attrs[i + 0], attrs[i + 1]);

            }

        }

        public Element(Collection c) {

            this(c.size());

            addAll(c);

        }

        public Element(String name, Collection c) {

            this(name, c.size());

            addAll(c);

        }

        /** Shallow copy.  Same as old.shallowCopy().

         *  Optional extraCapacity argument is expected extra sub-elements.

         */

        public Element(Element old) {

            this(old, 0);

        }

        public Element(Element old, int extraCapacity) {

            this(old.name, old.size,

                    old.size

                    + Math.max(0, extraCapacity) + NEED_SLOP

                    + old.attrLength());

            // copy sub-elements

            System.arraycopy(old.parts, 0, parts, 0, size);

            int alen = parts.length

                    - (size + Math.max(0, extraCapacity) + NEED_SLOP);

            // copy attributes

            System.arraycopy(old.parts, old.parts.length - alen,

                    parts, parts.length - alen,

                    alen);

            assert (!isFrozen());

        }

        /** Shallow copy.  Same as new Element(this). */

        public Element shallowCopy() {

            return new Element(this);

        }

        static public final Element EMPTY = new Element(ANON_NAME, 0, 0);

        Element deepFreezeOrCopy(boolean makeFrozen) {

            if (makeFrozen && isFrozen()) {

                return this;  // no need to copy it

            }

            int alen = attrLength();

            int plen = size + (makeFrozen ? 0 : NEED_SLOP) + alen;

            Element copy = new Element(name, size, plen);

            // copy attributes

            System.arraycopy(parts, parts.length - alen, copy.parts, plen - alen, alen);

            // copy sub-elements

            for (int i = 0; i < size; i++) {

                Object e = parts[i];

                String str;

                if (e instanceof Element) {  // recursion is common case

                    e = ((Element) e).deepFreezeOrCopy(makeFrozen);

                } else if (makeFrozen) {

                    // Freeze StringBuffers, etc.

                    e = fixupString(e);

                }

                copy.setRaw(i, e);

            }

            return copy;

        }

        /** Returns new Element(this), and also recursively copies sub-elements. */

        public Element deepCopy() {

            return deepFreezeOrCopy(false);

        }

        /** Returns frozen version of deepCopy. */

        public Element deepFreeze() {

            return deepFreezeOrCopy(true);

        }

        /** Freeze this element.

         *  Throw an IllegalArgumentException if any sub-element is not already frozen.

         *  (Use deepFreeze() to make a frozen copy of an entire element tree.)

         */

        public void shallowFreeze() {

            if (isFrozen()) {

                return;

            }

            int alen = attrLength();

            Object[] nparts = new Object[size + alen];

            // copy attributes

            System.arraycopy(parts, parts.length - alen, nparts, size, alen);

            // copy sub-elements

            for (int i = 0; i < size; i++) {

                Object e = parts[i];

                String str;

                if (e instanceof Element) {  // recursion is common case

                    if (!((Element) e).isFrozen()) {

                        throw new IllegalArgumentException("Sub-element must be frozen.");

                    }

                } else {

                    // Freeze StringBuffers, etc.

                    e = fixupString(e);

                }

                nparts[i] = e;

            }

            parts = nparts;

            assert (isFrozen());

        }

        /** Return the name of this element. */

        public String getName() {

            return name;

        }

        /** Change the name of this element. */

        public void setName(String name) {

            checkNotFrozen();

            this.name = name.toString();

        }

        /** Reports if the element's name is a particular string (spelled "*").

         *  Such elements are created by the nullary Element constructor,

         *  and by query functions which return multiple values,

         *  such as <tt>findAll</tt>.

         */

        public boolean isAnonymous() {

            return name == ANON_NAME;

        }

        /** Return number of elements.  (Does not include attributes.) */

        public int size() {

            return size;

        }

        /** True if no elements.  (Does not consider attributes.) */

        public boolean isEmpty() {

            return size == 0;

        }

        /** True if this element does not allow modification. */

        public boolean isFrozen() {

            // It is frozen iff there is no slop space.

            return !hasNulls(NEED_SLOP);

        }

        void checkNotFrozen() {

            if (isFrozen()) {

                throw new UnsupportedOperationException("cannot modify frozen element");