/*
 * Javolution - Java(TM) Solution for Real-Time and Embedded Systems
 * Copyright (C) 2005 - Javolution (http://javolution.org/)
 * All rights reserved.
 * 
 * Permission to use, copy, modify, and distribute this software is
 * freely granted, provided that this notice is preserved.
 */
package javolution37.javolution.xml.pull;

import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.Reader;
import java.io.UnsupportedEncodingException;

import java.lang.CharSequence;
import java.lang.IllegalStateException;
import java.nio.ByteBuffer;
import javax.realtime.MemoryArea;

import javolution37.javolution.io.Utf8ByteBufferReader;
import javolution37.javolution.io.Utf8StreamReader;
import javolution37.javolution.lang.Reusable;
import javolution37.javolution.lang.Text;
import javolution37.javolution.lang.TypeFormat;
import javolution37.javolution.util.FastTable;
import javolution37.javolution.xml.sax.Attributes;

/**
 * 
 This class provides a real-time XPP-like XML parser; this parser is
 *     extremely fast (around 2-5x times faster than conventional 
 *     SAX/XPP parsers).
 *     
 * 
 This parser does not create temporary objects
 *     (e.g. no String instance allocated on the heap) and
 *     has no adverse effect on memory footprint and garbage collection.
 *     
 * 
 The parser input source can be either a {@link #setInput(Reader) Reader},
 *     an {@link #setInput(InputStream) InputStream} or even a {@link 
 *     #setInput(ByteBuffer) ByteBuffer} (e.g. MappedByteBuffer).
 *     Here is an example parsing a resource as input stream:[code]
 *     InputStream in = Configuration.class.getResourceAsStream("configuration.xml");
 *     XmlPullParserImpl xpp = new XmlPullParserImpl();
 *     xpp.setInput(in);
 *     for (int e = xpp.getEventType(); e != XmlPullParserImpl.END_DOCUMENT; e = xpp.next()) {
 *         if (e == XmlPullParserImpl.START_TAG) { // Reads value
 *             CharSequence key = xpp.getName();
 *             if (xpp.next() == XmlPullParserImpl.TEXT) {
 *                 CharSequence value = xpp.getText();
 *                 Configuration.set(key, value);
 *             }
 *         }
 *     }[/code]
 *     
 * 
 This parser is light (less than 15Kbytes compressed) and maintains
 *     a very small memory footprint while parsing (e.g. less than 10Kbytes
 *     while parsing 32Mbytes files). Typical applications include SOAP
 *     messaging, embedded/realtime systems (J2ME), web servers 
 *     (possibly thousands instances running concurrently), etc.
 *     
 * 
 The {@link CharSequence CharSequence} generated by this parser have
 *     the following characteristics:
 *     

 *         
 They are immutable within their definition scope. The 
 *              CharSequence created while parsing an XML element are
 *              reused only after the element is out-of-scope (end tag).
 *         
 They support equality or lexical comparison with any
 *              CharSequence (e.g. String).
 *         
 They have the same hashcode than String and can be
 *              used to retrieve data from maps (e.g.
 *              {@link javolution37.javolution.util.FastMap FastMap}) for which 
 *              the keys are String instances.
 *         
 Like any CharSequence, they can quickly be 
 *              converted to primitive types (e.g. int, double) using the 
 *              {@link TypeFormat} utility class.
 *     

 *     
 * 
 Finally, this parser does not break up character data during call back
 *     (the whole character data between markups is always being returned).
 *     
 * 
  Note: If a SAX2 parser is required, applications may also use the 
 *    {@link javolution37.javolution.xml.sax.XmlSaxParserImpl SAX2 wrapper} 
 *    (3-5x faster than conventional SAX2 parsers).
 *    
 * @author  Gregory Arakelian
 * @author  Jean-Marie Dautelle
 * @version 3.4, September 20, 2005
 */
public final class XmlPullParserImpl implements XmlPullParser, Reusable {

    /**
     * If this feature is activated, whitespaces are ignored. 
     * In other words, there will be no {@link #TEXT} event with 
     * {@link #isWhitespace()} returning true.
     */
    public static final String 
          FEATURE_IGNORE_WHITESPACE = "http://javolution.org/xml/pull/ignore-whitespace";

    /**
     * Holds the internal event when text is being merged (ref. next())
     */
    private static final int MERGED_TEXT = 16;

    /**
     * Holds the reader buffer capacity.
     */
    private static final int READER_BUFFER_CAPACITY = 2048;

    /**
     * Holds the parsing line.
     */
    private int _lineNumber;

    /**
     * Holds the column offset (column = _columnOffset + _index).
     */
    private int _columnOffset;

    /**
     * Holds the line length when line break occurs.
     */
    private int _lineLength;

    /**
     * Holds the current index in the character buffer.
     */
    private int _index;

    /**
     * Indicates if whitespace is ignored 
     * (see {@link #FEATURE_IGNORE_WHITESPACE}).
     */
    private boolean _ignoreWhitespace;

    /**
     * Holds the data buffer for CharSequence produced by this parser.
     */
    private char[] _data = new char[READER_BUFFER_CAPACITY * 2];

    /**
     * Holds the current length of the data buffer (_data).
     */
    private int _length;

    /**
     * Holds the current depth.
     */
    private int _depth;

    /**
     * Holds the namespace  stack.
     */
    private final Namespaces _namespaces = new Namespaces();

    /**
     * Holds the current attributes.
     */
    private final AttributesImpl _attributes = new AttributesImpl(_namespaces);

    /**
     * Holds working stack.
     */
    private final FastTable _elemStack = new FastTable();

    /**
     * Holds the character buffer used for reading.
     */
    private final char[] _chars = new char[READER_BUFFER_CAPACITY];

    /**
     * Holds the default stream reader (UTF-8).
     */
    private final Utf8StreamReader _inputStreamReader = new Utf8StreamReader(
            READER_BUFFER_CAPACITY);

    /**
     * Holds the default ByteBuffer reader (UTF-8).
     */
    private final Utf8ByteBufferReader _byteBufferReader = new Utf8ByteBufferReader();

    /**
     * Number of characters read from reader
     */
    private int _charsRead;

    /**
     * Holds local name (i.e. does not include prefix, if any).
     */
    private CharSequenceImpl _elemLocalName;

    /**
     * Holds element namespace (lookup performed using prefix and namespace stack).
     */
    private CharSequenceImpl _elemNamespace;

    /**
     * Holds qualified name (include prefix).
     */
    private CharSequenceImpl _elemQName;

    /**
     * Holds prefix.
     */
    private CharSequenceImpl _elemPrefix;

    /**
     * Holds attribute qualified name.
     */
    private CharSequenceImpl _attrQName;

    /**
     * Holds attribute prefix.
     */
    private CharSequenceImpl _attrPrefix;

    /**
     * Holds attribute value.
     */
    private CharSequenceImpl _attrValue;

    /**
     * Holds character sequence when parsing numeric literal.
     */
    private final CharSequenceImpl _num = new CharSequenceImpl();

    /**
     * Holds current event type
     */
    private int _eventType = END_DOCUMENT;

    /**
     * Input encoding, if known
     */
    private String _inputEncoding;

    /**
     * Indicates if event type is START_TAG, and tag is empty, i.e. 
     */
    private boolean _isEmpty;

    /**
     * Holds reader used to get data
     */
    private Reader _reader;

    /**
     * Holds start of escape sequence
     */
    private int _escStart;

    /**
     * Holds saved parser state when escape sequence encountered.
     */
    private int _savedState;

    /**
     * Holds the start of text withing _data array.
     */
    private int _start;

    /**
     * Holds the parser state.
     */
    private int _state = CHAR_DATA;

    /**
     * Holds the text associated with current event.
     */
    private CharSequenceImpl _text;

    /**
     * Holds the text merged together.
     */
    private CharSequenceImpl _mergedText;

    /**
     * Indicates if text contains non whitespace characters (characters 
     * others than space, cr, lf, tab).
     */
    private boolean _hasNonWhitespace;

    /**
     * Holds character sequences instances.
     */
    private CharSequenceImpl[] _seqs = new CharSequenceImpl[256];

    /**
     * Holds character sequence index. 
     */
    private int _seqsIndex;

    /**
     * Holds number of character sequence instances allocated. 
     */
    private int _seqsCapacity;

    /**
     * Default constructor.
     */
    public XmlPullParserImpl() {
    }

    /**
     * Sets the byte buffer this parser is going to process
     * (UTF-8 encoding).
     *
     * @param  byteBuffer the byte buffer with UTF-8 encoding.
     * @see    Utf8ByteBufferReader
     */
    public void setInput(ByteBuffer byteBuffer) {
        if (_reader != null)
            throw new IllegalStateException("Parser not reset.");
        _byteBufferReader.setByteBuffer(byteBuffer);
        _inputEncoding = "UTF-8";
        setInput(_byteBufferReader);
    }

    /**
     * Sets the input stream this parser is going to process
     * (UTF-8 encoding).
     *
     * @param in the input stream with UTF-8 encoding.
     * @see    Utf8StreamReader
     */
    public void setInput(InputStream in) {
        if (_reader != null)
            throw new IllegalStateException("Parser not reset.");
        _inputStreamReader.setInputStream(in);
        _inputEncoding = "UTF-8";
        setInput(_inputStreamReader);
    }

    // Implements XmlPullParser interface.
    public void setInput(InputStream inputStream, String inputEncoding)
            throws XmlPullParserException {
        if ((inputEncoding == null) || inputEncoding.equals("utf-8")
                || inputEncoding.equals("UTF-8")) {
            setInput(inputStream);
            return;
        }
        try {
            _inputEncoding = inputEncoding;
            setInput(new InputStreamReader(inputStream, inputEncoding));
        } catch (UnsupportedEncodingException e) {
            throw new XmlPullParserException(e.getMessage());
        }
    }

    // Implements XmlPullParser interface.
    public void setInput(Reader in) {
        if (_reader != null)
            throw new IllegalStateException("Parser not reset.");
        _reader = in;
        _eventType = START_DOCUMENT;
    }

    // Implements XmlPullParser interface.
    public void defineEntityReplacementText(String entityName,
            String replacementText) throws XmlPullParserException {
    }

    /**
     * Returns SAX-2 like attributes for the current element.
     * 
     * @return the attributes of the current element.
     */
    public Attributes getSaxAttributes() {
        return _attributes;
    }

    // Implements XmlPullParser interface.
    public int getAttributeCount() {
        if (_eventType != START_TAG)
            return -1;
        return _attributes.getLength();
    }

    // Implements XmlPullParser interface.
    public CharSequence getAttributeName(int index) {
        return _attributes.getLocalName(index);
    }

    // Implements XmlPullParser interface.
    public CharSequence getAttributeNamespace(int index) {
        return _attributes.getURI(index);
    }

    // Implements XmlPullParser interface.
    public CharSequence getAttributePrefix(int index) {
        return _attributes.getPrefix(index);
    }

    // Implements XmlPullParser interface.
    public String getAttributeType(int index) {
        return _attributes.getType(index);
    }

    // Implements XmlPullParser interface.
    public CharSequence getAttributeValue(String namespace, String name) {
        return namespace == null ? _attributes.getValue("", name) : _attributes
                .getValue(namespace, name);
    }

    // Implements XmlPullParser interface.
    public CharSequence getAttributeValue(int index) {
        return _attributes.getValue(index);
    }

    // Implements XmlPullParser interface.
    public int getDepth() {
        return _depth;
    }

    // Implements XmlPullParser interface.
    public int getEventType() throws XmlPullParserException {
        return _eventType;
    }

    // Implements XmlPullParser interface.
    public String getInputEncoding() {
        return _inputEncoding;
    }

    // Implements XmlPullParser interface.
    public int getLineNumber() {
        int column = _columnOffset + _index;
        return (column != 0) ? _lineNumber : _lineNumber - 1;
    }

    // Implements XmlPullParser interface.
    public int getColumnNumber() {
        int column = _columnOffset + _index;
        return (column != 0) ? column : _lineLength;
    }

    // Implements XmlPullParser interface.
    public CharSequence getName() {
        return _elemLocalName;
    }

    // Implements XmlPullParser interface.
    public CharSequence getNamespace() {
        return _elemNamespace;
    }

    // Implements XmlPullParser interface.
    public CharSequence getPrefix() {
        return _elemPrefix;
    }

    /**
     * Returns the current element qualified name.
     *
     * @return the qualified name of the current element (prefix:localName).
     */
    public CharSequence getQName() {
        return _elemQName;
    }

    // Implements XmlPullParser interface.
    public CharSequence getNamespace(String prefix) {
        return _namespaces.getNamespaceUri(prefix);
    }

    // Implements XmlPullParser interface.
    public int getNamespaceCount(int depth) {
        return _namespaces.getNamespaceCount(depth);
    }

    // Implements XmlPullParser interface.
    public CharSequence getNamespacePrefix(int pos) {
        return _namespaces.getNamespacePrefix(pos);
    }

    // Implements XmlPullParser interface.
    public CharSequence getNamespaceUri(int pos) {
        return _namespaces.getNamespaceUri(pos);
    }

    // Implements XmlPullParser interface.
    public CharSequence getPositionDescription() {
        return Text.valueOf("line ").concat(Text.valueOf(getLineNumber()))
                .concat(Text.valueOf(", column ")).concat(
                        Text.valueOf(getColumnNumber()));
    }

    // Implements XmlPullParser interface.
    public CharSequence getText() {
        return _text;
    }

    // Implements XmlPullParser interface.
    public char[] getTextCharacters(int[] holderForStartAndLength) {
        if (_text != null) {
            holderForStartAndLength[0] = _text.offset;
            holderForStartAndLength[1] = _text.length;
            return _text.data;
        }
        holderForStartAndLength[0] = holderForStartAndLength[1] = -1;
        return null;
    }

    // Implements XmlPullParser interface.
    public boolean isAttributeDefault(int index) {
        return false;
    }

    // Implements XmlPullParser interface.
    public boolean isEmptyElementTag() throws XmlPullParserException {
        return _isEmpty;
    }

    // Implements XmlPullParser interface.
    public boolean isWhitespace() throws XmlPullParserException {
        if (_eventType == TEXT || _eventType == CDSECT)
            return !_hasNonWhitespace;
        throw new IllegalStateException();
    }

    // Implements XmlPullParser interface.
    public int next() throws XmlPullParserException, IOException {
        // Coalesces text events.
        while (true) {
            switch (nextToken()) {
            case XmlPullParser.TEXT:
            case XmlPullParser.CDSECT:
                // Coalesces text events.
                if (_mergedText == null) {
                    _mergedText = _text;
                } else {
                    _mergedText.data = _text.data;
                    _mergedText.length += _text.length;
                }
                _length = _text.offset + _text.length;
                _start = _length;
                break;
            case XmlPullParser.COMMENT:
            case XmlPullParser.PROCESSING_INSTRUCTION:
                // Ignores comments and processing instructions.
                break;
            case MERGED_TEXT: // Not visible outside (replaced with TEXT)
                _text = _mergedText;
                _mergedText = null;
                return _eventType = TEXT;
            default:
                return _eventType;
            }
        }
    }

    // Implements XmlPullParser interface.
    public int nextTag() throws XmlPullParserException, IOException {
        int eventType = next();
        if (eventType == TEXT && isWhitespace()) { // skip whitespace
            eventType = next();
        }
        if (eventType != START_TAG && eventType != END_TAG) {
            throw error("expected start or end tag");
        }
        return eventType;
    }

    // Implements XmlPullParser interface.
    public CharSequence nextText() throws XmlPullParserException, IOException {
        if (getEventType() != START_TAG)
            throw error("parser must be on START_TAG to read next text");
        int eventType = next();
        if (eventType == TEXT) {
            CharSequence result = getText();
            eventType = next();
            if (eventType != END_TAG)
                throw error("event TEXT must be immediately followed by END_TAG");

            return result;
        } else if (eventType == END_TAG) {
            return CharSequenceImpl.EMPTY;
        } else {
            throw error("parser must be on START_TAG or TEXT to read text");
        }
    }

    // Implements XmlPullParser interface.
    public void setFeature(String name, boolean state)
            throws XmlPullParserException {
        if (name.equals(FEATURE_IGNORE_WHITESPACE)) {
            _ignoreWhitespace = state;
        }
    }

    // Implements XmlPullParser interface.
    public boolean getFeature(String name) {
        if (name.equals(FEATURE_IGNORE_WHITESPACE)) {
            return _ignoreWhitespace;
        }
        return false;
    }

    // Implements XmlPullParser interface.
    public void setProperty(String name, Object value)
            throws XmlPullParserException {
    }

    // Implements XmlPullParser interface.
    public Object getProperty(String name) {
        return null;
    }

    // Implements XmlPullParser interface.
    public void require(int type, String namespace, String name)
            throws XmlPullParserException, IOException {
        if (type != getEventType()
                || (namespace != null && !getNamespace().equals(namespace))
                || (name != null && getName().equals(name)))
            throw error("Require " + TYPES[type] + " failed");
    }

    // Implements XmlPullParser interface.
    public int nextToken() throws XmlPullParserException, IOException {
        switch (_eventType) { // Previous event.
        case XmlPullParser.START_DOCUMENT:
            _charsRead = _reader.read(_chars, 0, _chars.length);
            break;
        case XmlPullParser.END_DOCUMENT:
            throw error("End of document reached.");
        case XmlPullParser.START_TAG:
            _attributes.reset();
            if (_isEmpty) { // Previous empty tag, generates END_TAG automatically.
                _isEmpty = false;
                return _eventType = END_TAG;
            }
            _elemPrefix = null;
            _elemLocalName = null;
            _elemNamespace = null;
            _elemQName = null;
            break;
        case XmlPullParser.END_TAG:
            _depth--;
            _length = _elemQName.offset;
            _start = _length;
            while (_seqs[--_seqsIndex] != _elemQName) {
            }
            _elemPrefix = null;
            _elemLocalName = null;
            _elemNamespace = null;
            _elemQName = null;
            break;
        case XmlPullParser.TEXT:
        case XmlPullParser.CDSECT:
        case XmlPullParser.COMMENT:
        case XmlPullParser.PROCESSING_INSTRUCTION:
            _text = null;
            _hasNonWhitespace = false;
            break;
        }

        while (_index < _charsRead) {

            // Preprocessing.
            //
            char c = _chars[_index];
            if (++_index == _charsRead) { // Reloads buffer.
                _columnOffset += _index;
                _index = 0;
                _charsRead = _reader.read(_chars, 0, _chars.length);
                while ((_length + _charsRead) >= _data.length) {
                    // Potential overflow, resizes.
                    increaseDataBuffer();
                }
            }
            // Replaces #xD and #xD#xA with #xA as per XML 1.0
            // recommendations (&2.11).
            if (c < 0x20) {
                if (c == 0xD) { // Replaces #xD with #xA
                    if ((_index < _charsRead) && (_chars[_index] == 0xA)) {
                        // Unless next char is #xA, then continue,
                        // #xD#xA will be replaced by #xA
                        continue;
                    }
                    c = 0xA;
                }
                if (c == 0xA) {
                    _lineNumber++; // Do it now, locator will readjust.
                    _lineLength = _columnOffset + _index;
                    _columnOffset = -_index; // column = 0
                } else if (c != 0x9) { // Not a tab.
                    throw error("Illegal XML character U+"
                            + Integer.toHexString(c));
                }
            }
            // Appends to buffer.
            _data[_length++] = c;
            // Detects escape sequence (e.g. character reference).
            if ((c == '&') && (_state != STATE_COMMENT) && (_state != PI)
                    && (_state != CDATA) && (_state != ESCAPE)) { // (&2.4)
                _savedState = _state;
                _escStart = _length;
                _state = ESCAPE;
            }

            // Main processing.
            //
            switch (_state) {
            case CHAR_DATA:
                if (c == '<') {
                    _state = MARKUP;
                    int nbrChar = _length - _start - 1;
                    _length = _start; // Do not keep.
                    if (_hasNonWhitespace
                            || (!_ignoreWhitespace && (nbrChar > 0))) {
                        setText(_start, nbrChar);
                        return _eventType = TEXT;
                    }
                } else if (!_hasNonWhitespace && c > ' ') {
                    _hasNonWhitespace = true;
                }
                break;

            case MARKUP:
                if (_length - _start == 1) {
                    if (c == '/') {
                        _state = CLOSE_TAG + READ_ELEM_NAME;
                        _length = _start;
                        _elemQName = newSeq();
                        _elemQName.offset = _start;
                        if (_mergedText != null)
                            return _eventType = MERGED_TEXT; // Flushes.
                    } else if (c == '?') {
                        _state = PI;
                        _length = _start;
                    } else if (c != '!') {
                        _state = OPEN_TAG + READ_ELEM_NAME;
                        _elemQName = newSeq();
                        _elemQName.offset = _start;
                        if (_mergedText != null)
                            return _eventType = MERGED_TEXT; // Flushes.
                    }
                } else if ((_length - _start == 3) && (_data[_start] == '!')
                        && (_data[_start + 1] == '-')
                        && (_data[_start + 2] == '-')) {
                    _state = STATE_COMMENT;
                    _length = _start;
                } else if ((_length - _start == 8) && (_data[_start] == '!')
                        && (_data[_start + 1] == '[')
                        && (_data[_start + 2] == 'C')
                        && (_data[_start + 3] == 'D')
                        && (_data[_start + 4] == 'A')
                        && (_data[_start + 5] == 'T')
                        && (_data[_start + 6] == 'A')
                        && (_data[_start + 7] == '[')) {
                    _state = CDATA;
                    _length = _start;
                } else if (c == '>') {
                    _state = CHAR_DATA;
                    _length = _start;
                }
                break;

            case STATE_COMMENT:
                if ((c == '>') && (_length - _start >= 3)
                        && (_data[_length - 2] == '-')
                        && (_data[_length - 3] == '-')) {
                    _state = CHAR_DATA;
                    int nbrChar = _length - _start - 3;
                    _length = _start; // Do not keep.
                    if (nbrChar > 0) {
                        setText(_start, nbrChar);
                        return _eventType = COMMENT;
                    }
                }
                break;

            case PI: // Ignores Processing Instructions.
                if ((c == '>') && (_length - _start >= 2)
                        && (_data[_length - 2] == '?')) {
                    _state = CHAR_DATA;
                    int nbrChar = _length - _start - 2;
                    _length = _start; // Do not keep.
                    if (nbrChar > 0) {
                        setText(_start, nbrChar);
                        return _eventType = PROCESSING_INSTRUCTION;
                    }
                }
                break;

            case CDATA:
                if ((c == '>') && (_length - _start >= 3)
                        && (_data[_length - 2] == ']')
                        && (_data[_length - 3] == ']')) {
                    _state = CHAR_DATA;
                    int nbrChar = _length - _start - 3;
                    _length = _start; // Do not keep.
                    if (nbrChar > 0) {
                        setText(_start, nbrChar);
                        return _eventType = CDSECT;
                    }
                }
                if (!_hasNonWhitespace && c > ' ') {
                    _hasNonWhitespace = true;
                }
                break;

            // OPEN_TAG:
            case OPEN_TAG + READ_ELEM_NAME:
                if (c == '>') {
                    _elemQName.length = _length - _elemQName.offset - 1;
                    _elemQName.data = _data;
                    _state = CHAR_DATA;
                    _start = _length;
                    return _eventType = processElement(OPEN_TAG);
                } else if (c == '/') {
                    _elemQName.length = _length - _elemQName.offset - 1;
                    _elemQName.data = _data;
                    _state = OPEN_TAG + EMPTY_TAG;
                } else if ((c == ':') && (_elemPrefix == null)) {
                    _elemPrefix = newSeq();
                    _elemPrefix.offset = _elemQName.offset;
                    _elemPrefix.length = _length - _elemQName.offset - 1;
                    _elemPrefix.data = _data;
                } else if (c <= ' ') {
                    _elemQName.length = _length - _elemQName.offset - 1;
                    _elemQName.data = _data;
                    _state = OPEN_TAG + ELEM_NAME_READ;
                }
                break;
            case OPEN_TAG + ELEM_NAME_READ:
                if (c == '>') {
                    _state = CHAR_DATA;
                    _start = _length;
                    return _eventType = processElement(OPEN_TAG);
                } else if (c == '/') {
                    _state = OPEN_TAG + EMPTY_TAG;
                } else if (c > ' ') {
                    _attrQName = newSeq();
                    _attrQName.offset = _length - 1;
                    _state = OPEN_TAG + READ_ATTR_NAME;
                }
                break;
            case OPEN_TAG + READ_ATTR_NAME:
                if (c <= ' ') {
                    _attrQName.length = _length - _attrQName.offset - 1;
                    _attrQName.data = _data;
                    _state = OPEN_TAG + ATTR_NAME_READ;
                } else if (c == '=') {
                    _attrQName.length = _length - _attrQName.offset - 1;
                    _attrQName.data = _data;
                    _state = OPEN_TAG + EQUAL_READ;
                } else if ((c == ':') && (_attrPrefix == null)) {
                    _attrPrefix = newSeq();
                    _attrPrefix.offset = _attrQName.offset;
                    _attrPrefix.length = _length - _attrQName.offset - 1;
                    _attrPrefix.data = _data;
                }
                break;
            case OPEN_TAG + ATTR_NAME_READ:
                if (c == '=') {
                    _state = OPEN_TAG + EQUAL_READ;
                } else if (c > ' ') {
                    throw error("'=' expected");
                }
                break;
            case OPEN_TAG + EQUAL_READ:
                if (c == '\'') {
                    _attrValue = newSeq();
                    _attrValue.offset = _length;
                    _state = OPEN_TAG + READ_ATTR_VALUE_SIMPLE_QUOTE;
                } else if (c == '\"') {
                    _attrValue = newSeq();
                    _attrValue.offset = _length;
                    _state = OPEN_TAG + READ_ATTR_VALUE_DOUBLE_QUOTE;
                } else if (c > ' ') {
                    throw error("Quotes expected");
                }
                break;
            case OPEN_TAG + READ_ATTR_VALUE_SIMPLE_QUOTE:
                if (c == '\'') {
                    _attrValue.length = _length - _attrValue.offset - 1;
                    _attrValue.data = _data;
                    processAttribute();
                    _state = OPEN_TAG + ELEM_NAME_READ;
                }
                break;
            case OPEN_TAG + READ_ATTR_VALUE_DOUBLE_QUOTE:
                if (c == '\"') {
                    _attrValue.length = _length - _attrValue.offset - 1;
                    _attrValue.data = _data;
                    processAttribute();
                    _state = OPEN_TAG + ELEM_NAME_READ;
                }
                break;
            case OPEN_TAG + EMPTY_TAG:
                if (c == '>') {
                    _state = CHAR_DATA;
                    _start = _length;
                    return _eventType = processElement(OPEN_TAG + EMPTY_TAG);
                } else {
                    throw error("'>' expected");
                }

            // CLOSE_TAG:
            case CLOSE_TAG + READ_ELEM_NAME:
                if (c == '>') {
                    _elemQName.length = _length - _elemQName.offset - 1;
                    _elemQName.data = _data;
                    _state = CHAR_DATA;
                    _start = _length;
                    return _eventType = processElement(CLOSE_TAG);
                } else if ((c == ':') && (_elemPrefix == null)) {
                    _elemPrefix = newSeq();
                    _elemPrefix.offset = _elemQName.offset;
                    _elemPrefix.length = _length - _elemQName.offset - 1;
                    _elemPrefix.data = _data;
                } else if (c <= ' ') {
                    _elemQName.length = _length - _elemQName.offset - 1;
                    _elemQName.data = _data;
                    _state = CLOSE_TAG + ELEM_NAME_READ;
                }
                break;
            case CLOSE_TAG + ELEM_NAME_READ:
                if (c == '>') {
                    _state = CHAR_DATA;
                    _start = _length;
                    return _eventType = processElement(CLOSE_TAG);
                } else if (c > ' ') {
                    throw error("'>' expected");
                }
                break;

            case ESCAPE:
                if (c == ';') { // Escape terminator.
                    if ((_length - _escStart == 3)
                            && (_data[_length - 3] == 'l')
                            && (_data[_length - 2] == 't')) {
                        _data[_escStart - 1] = '<';
                    } else if ((_length - _escStart == 3)
                            && (_data[_length - 3] == 'g')
                            && (_data[_length - 2] == 't')) {
                        _data[_escStart - 1] = '>';
                    } else if ((_length - _escStart == 5)
                            && (_data[_length - 5] == 'a')
                            && (_data[_length - 4] == 'p')
                            && (_data[_length - 3] == 'o')
                            && (_data[_length - 2] == 's')) {
                        _data[_escStart - 1] = '\'';
                    } else if ((_length - _escStart == 5)
                            && (_data[_length - 5] == 'q')
                            && (_data[_length - 4] == 'u')
                            && (_data[_length - 3] == 'o')
                            && (_data[_length - 2] == 't')) {
                        _data[_escStart - 1] = '\"';
                    } else if ((_length - _escStart == 4)
                            && (_data[_length - 4] == 'a')
                            && (_data[_length - 3] == 'm')
                            && (_data[_length - 2] == 'p')) {
                        _data[_escStart - 1] = '&';
                    } else { // Character reference (&4.1)
                        if ((_length - _escStart > 1)
                                && (_data[_escStart] == '#')) {
                            try {
                                if (_data[_escStart + 1] == 'x') { // Hexadecimal.
                                    _num.offset = _escStart + 2;
                                    _num.length = _length - _escStart - 3;
                                    _num.data = _data;
                                    _data[_escStart - 1] = (char) TypeFormat
                                            .parseInt(_num, 16);
                                } else { // Decimal.
                                    _num.offset = _escStart + 1;
                                    _num.length = _length - _escStart - 2;
                                    _num.data = _data;
                                    _data[_escStart - 1] = (char) TypeFormat
                                            .parseInt(_num);
                                }
                            } catch (NumberFormatException e) {
                                throw error("Ill-formed character reference");
                            }
                        } else {
                            throw error("'#' expected");
                        }
                    }
                    _state = _savedState;
                    _length = _escStart;
                } else if (c <= ' ') {
                    throw error("';' expected");
                }
                break;

            default:
                throw error("State unknown: " + _state);
            }
        }

        if (_depth != 0)
            throw error("Unexpected end of file");
        reset();
        return END_DOCUMENT;
    }

    // Defines parsing states.
    private static final int CHAR_DATA = 0x10;

    private static final int MARKUP = 0x20;

    private static final int STATE_COMMENT = 0x30;

    private static final int PI = 0x40;

    private static final int CDATA = 0x50;

    private static final int OPEN_TAG = 0x60;

    private static final int CLOSE_TAG = 0x70;

    private static final int ESCAPE = 0x90;

    // Defines element parsing sub-states.
    private static final int READ_ELEM_NAME = 0x01;

    private static final int ELEM_NAME_READ = 0x02;

    private static final int READ_ATTR_NAME = 0x03;

    private static final int ATTR_NAME_READ = 0x04;

    private static final int EQUAL_READ = 0x05;

    private static final int READ_ATTR_VALUE_SIMPLE_QUOTE = 0x06;

    private static final int READ_ATTR_VALUE_DOUBLE_QUOTE = 0x07;

    private static final int EMPTY_TAG = 0x08;

    /**
     * Processes the attribute just read.
     *
     * @throws XmlPullParserException any SAX exception, possibly wrapping another
     *         exception.
     */
    private void processAttribute() throws XmlPullParserException {
        if (_attrPrefix == null) { // No prefix.
            if (isXmlns(_attrQName)) { // Sets default namespace.
                _namespaces.map(null, _attrValue);
            } else {
                _attributes.addAttribute(_attrQName, CharSequenceImpl.EMPTY,
                        _attrQName, _attrValue);
            }
        } else { // Prefix.
            CharSequenceImpl localName = newSeq();
            localName.offset = _attrQName.offset + _attrPrefix.length + 1;
            localName.length = _attrQName.length - _attrPrefix.length - 1;
            localName.data = _attrQName.data;

            if (isXmlns(_attrPrefix)) { // Namespace association.
                _namespaces.map(localName, _attrValue);
            } else {
                _attributes.addAttribute(localName, _attrPrefix, _attrQName,
                        _attrValue);
            }
            _attrPrefix = null; // Resets.
        }
    }

    /**
     * Processes the element just read.
     *
     * @param  state the current parser state.
     * @throws XmlPullParserException any SAX exception, possibly wrapping another
     *         exception.
     */
    private int processElement(int state) throws XmlPullParserException {
        if (_elemPrefix != null) { // Prefix, sets uri.
            _elemLocalName = newSeq();
            _elemLocalName.offset = _elemQName.offset + _elemPrefix.length + 1;
            _elemLocalName.length = _elemQName.length - _elemPrefix.length - 1;
            _elemLocalName.data = _elemQName.data;
            _elemNamespace = _namespaces.getNamespaceUri(_elemPrefix);
            if (_elemNamespace == null)
                throw error("Namespace " + _elemPrefix + " undefined");
        } else { // No prefix.
            _elemLocalName = _elemQName;
            _elemNamespace = _namespaces.getDefault();
        }
        if (state == OPEN_TAG + EMPTY_TAG) {
            _isEmpty = true;
            _depth++;
            _namespaces.flush();
            return START_TAG;

        } else if (state == OPEN_TAG) {
            _depth++;
            _elemStack.addLast(_elemQName);
            _elemStack.addLast(_elemNamespace);
            _elemStack.addLast(_elemLocalName);
            _elemStack.addLast(_elemPrefix);
            _namespaces.push();
            return START_TAG;

        } else if (state == CLOSE_TAG) {
            _elemPrefix = (CharSequenceImpl) _elemStack.removeLast();
            _elemLocalName = (CharSequenceImpl) _elemStack.removeLast();
            _elemNamespace = (CharSequenceImpl) _elemStack.removeLast();
            CharSequenceImpl qName = _elemQName; // Current.
            _elemQName = (CharSequenceImpl) _elemStack.removeLast();
            if (!_elemQName.equals(qName))
                throw error("Unexpected end tag for " + _elemQName);
            _namespaces.pop();
            return END_TAG;

        } else {
            throw error("Unexpected state: " + state);
        }
    }

    // Implements Reusable.
    public void reset() {
        try {
            if (_reader != null)
                _reader.close();
        } catch (IOException e) {
            // Ignores exceptions.
        }

        // Resets all members (alphabetically ordered).
        _attributes.reset();
        _attrPrefix = null;
        _attrQName = null;
        _attrValue = null;
        _attrQName = null;
        _charsRead = 0;
        _columnOffset = 0;
        _depth = 0;
        _elemLocalName = null;
        _elemNamespace = null;
        _elemPrefix = null;
        _elemQName = null;
        _elemStack.reset();
        _escStart = 0;
        _eventType = END_DOCUMENT;
        _hasNonWhitespace = false;
        _ignoreWhitespace = false;
        _index = 0;
        _inputEncoding = null;
        _isEmpty = false;
        _length = 0;
        _lineLength = 0;
        _lineNumber = 0;
        _mergedText = null;
        _namespaces.reset();
        _reader = null;
        _savedState = 0;
        _seqsIndex = 0;
        _start = 0;
        _state = CHAR_DATA;
        _text = null;
    }

    /**
     * Sets current text.
     *
     * @param  start the start index.
     * @param  end the end index.
     */
    private void setText(int start, int length) {
        _text = newSeq();
        _text.data = _data;
        _text.offset = start;
        _text.length = length;
    }

    /**
     * Indicates if the specified character sequence is xmlns.
     *
     * @param  chars the characters sequence to be tested.
     * @return chars.equals("xmlns")
     */
    private static boolean isXmlns(CharSequenceImpl chars) {
        return (chars.length == 5) && (chars.data[chars.offset] == 'x')
                && (chars.data[chars.offset + 1] == 'm')
                && (chars.data[chars.offset + 2] == 'l')
                && (chars.data[chars.offset + 3] == 'n')
                && (chars.data[chars.offset + 4] == 's');
    }

    private XmlPullParserException error(String message) {
        XmlPullParserException e = new XmlPullParserException(message, this,
                null);
        return e;
    }

    // Returns a new character sequence from the pool.
    private CharSequenceImpl newSeq() {
        return (_seqsIndex < _seqsCapacity) ? _seqs[_seqsIndex++] : newSeq2();
    }

    private CharSequenceImpl newSeq2() {
        MemoryArea.getMemoryArea(this).executeInArea(new Runnable() {
            public void run() {
                if (_seqsCapacity++ >= _seqs.length) { // Resizes.
                    CharSequenceImpl[] tmp = new CharSequenceImpl[_seqs.length * 2];
                    System.arraycopy(_seqs, 0, tmp, 0, _seqs.length);
                    _seqs = tmp;
                }
                _seqs[_seqsIndex] = new CharSequenceImpl();
            }
        });
        return _seqs[_seqsIndex++];
    }

    private void increaseDataBuffer() {
        MemoryArea.getMemoryArea(this).executeInArea(new Runnable() {
            public void run() {
                char[] tmp = new char[_data.length * 2];
                System.arraycopy(_data, 0, tmp, 0, _data.length);
                _data = tmp;
            }
        });
    }
}