package com.fasterxml.aalto.dom;

import java.util.*;

import javax.xml.XMLConstants;
import javax.xml.namespace.NamespaceContext;

/* !!! 18-Dec-2008, tatu: Copied from Woodstox almost verbatim, should be
 *   replaced/removed/rewritten soon.
 */
Helper class that implements "bijective map" (Map that allows use of values
as keys and vice versa, bidirectional access), and is specifically
used for storing namespace binding information.
One thing worth noting is that Strings stored are NOT assumed to have
been unified (interned) -- if they were, different implementation would
be more optimal.
/**
 * Helper class that implements "bijective map" (Map that allows use of values
 * as keys and vice versa, bidirectional access), and is specifically
 * used for storing namespace binding information.
 * One thing worth noting is that Strings stored are NOT assumed to have
 * been unified (interned) -- if they were, different implementation would
 * be more optimal.
 */
public final class BijectiveNsMap
{
    /*
    ///////////////////////////////////////////////
    // Constants
    ///////////////////////////////////////////////
     */

    
Let's plan for having up to 14 explicit namespace declarations (2
defaults, for 'xml' and 'xmlns', are pre-populated)
/**
     * Let's plan for having up to 14 explicit namespace declarations (2
     * defaults, for 'xml' and 'xmlns', are pre-populated)
     */
    final static int DEFAULT_ARRAY_SIZE = 2 * 16;

    /*
    ///////////////////////////////////////////////
    // Member vars
    ///////////////////////////////////////////////
     */

    final int _scopeStart;

    
Array that contains { prefix, ns-uri } pairs, up to (but not including) index _scopeEnd. /**
     * Array that contains { prefix, ns-uri } pairs, up to (but not including)
     * index {@link #_scopeEnd}.
     */
    String[] _nsStrings;

    int _scopeEnd;

    /*
    ///////////////////////////////////////////////
    // Life-cycle
    ///////////////////////////////////////////////
     */

    private BijectiveNsMap(int scopeStart, String[] strs)
    {
        _scopeStart = _scopeEnd = scopeStart;
        _nsStrings = strs;
    }

    public static BijectiveNsMap createEmpty()
    {
        String[] strs = new String[DEFAULT_ARRAY_SIZE];

        strs[0] = XMLConstants.XML_NS_PREFIX;
        strs[1] = XMLConstants.XML_NS_URI;
        strs[2] = XMLConstants.XMLNS_ATTRIBUTE;
        strs[3] = XMLConstants.XMLNS_ATTRIBUTE_NS_URI;

        /* Let's consider pre-defined ones to be 'out of scope', i.e.
         * conceptually be part of (missing) parent's mappings.
         */
        return new BijectiveNsMap(4, strs);
    }

    public BijectiveNsMap createChild() {
        return new BijectiveNsMap(_scopeEnd, _nsStrings);
    }

    /*
    ///////////////////////////////////////////////
    // Public API, accessors
    ///////////////////////////////////////////////
     */

    public String findUriByPrefix(String prefix)
    {
        /* This is quite simple: just need to locate the last mapping
         * for the prefix, if any:
         */
        String[] strs = _nsStrings;
        int phash = prefix.hashCode();

        for (int ix = _scopeEnd - 2; ix >= 0; ix -= 2) {
            String thisP = strs[ix];
            if (thisP == prefix ||
                (thisP.hashCode() == phash && thisP.equals(prefix))) {
                return strs[ix+1];
            }
        }
        return null;
    }

    public String findPrefixByUri(String uri)
    {
        /* Finding a valid binding for the given URI is trickier, since
         * mappings can be masked by others... so, we need to first find
         * most recent binding, from the freshest one, and then verify
         * it's still unmasked; if not, continue with the first loop,
         * and so on.
         */

        String[] strs = _nsStrings;
        int uhash = uri.hashCode();

        main_loop:
        for (int ix = _scopeEnd - 1; ix > 0; ix -= 2) {
            String thisU = strs[ix];
            if (thisU == uri ||
                (thisU.hashCode() == uhash && thisU.equals(uri))) {
                // match, but has it been masked?
                String prefix = strs[ix-1];
                /* only need to check, if it wasn't within current scope
                 * (no masking allowed within scopes)
                 */
                if (ix < _scopeStart) {
                    int phash = prefix.hashCode();
                    for (int j = ix-1, end = _scopeEnd; j < end; j += 2) {
                        String thisP = strs[ix];
                        if (thisP == prefix ||
                            (thisP.hashCode() == phash && thisP.equals(prefix))) {
                            // Masking... got to continue the main loop:
                            continue main_loop;
                        }
                    }
                }
                // Ok, unmasked one, can return
                return prefix;
            }
        }
        return null;
    }

    public List<String> getPrefixesBoundToUri(String uri, List<String> l)
    {
        /* Same problems (masking) apply here, as well as with
         * findPrefixByUri...
         */
        String[] strs = _nsStrings;
        int uhash = uri.hashCode();

        main_loop:
        for (int ix = _scopeEnd - 1; ix > 0; ix -= 2) {
            String thisU = strs[ix];
            if (thisU == uri ||
                (thisU.hashCode() == uhash && thisU.equals(uri))) {
                // match, but has it been masked?
                String prefix = strs[ix-1];
                /* only need to check, if it wasn't within current scope
                 * (no masking allowed within scopes)
                 */
                if (ix < _scopeStart) {
                    int phash = prefix.hashCode();
                    for (int j = ix-1, end = _scopeEnd; j < end; j += 2) {
                        String thisP = strs[ix];
                        if (thisP == prefix ||
                            (thisP.hashCode() == phash && thisP.equals(prefix))) {
                            // Masking... got to continue the main loop:
                            continue main_loop;
                        }
                    }
                }
                // Ok, unmasked one, can add
                if (l == null) {
                    l = new ArrayList<String>();
                }
                l.add(prefix);
            }
        }
        return l;
    }

    public int size() {
        return (_scopeEnd >> 1);
    }

    public int localSize() {
        return ((_scopeEnd - _scopeStart) >> 1);
    }

    /*
    ///////////////////////////////////////////////
    // Public API, mutators
    ///////////////////////////////////////////////
     */

    
Method to add a new prefix-to-URI mapping for the current scope.
Note that it should NOT be used for the default namespace
declaration
Params:
prefix – Prefix to bind
uri – URI to bind to the prefix
Returns:
If the prefix was already bound, the URI it was bound to:
  null if it's a new binding for the current scope./**
     * Method to add a new prefix-to-URI mapping for the current scope.
     * Note that it should NOT be used for the default namespace
     * declaration
     *
     * @param prefix Prefix to bind
     * @param uri URI to bind to the prefix
     *
     * @return If the prefix was already bound, the URI it was bound to:
     *   null if it's a new binding for the current scope.
     */
    public String addMapping(String prefix, String uri)
    {
        String[] strs = _nsStrings;
        int phash = prefix.hashCode();

        for (int ix = _scopeStart, end = _scopeEnd; ix < end; ix += 2) {
            String thisP = strs[ix];
            if (thisP == prefix ||
                (thisP.hashCode() == phash && thisP.equals(prefix))) {
                // Overriding an existing mapping
                String old = strs[ix+1];
                strs[ix+1] = uri;
                return old;
            }
        }
        // no previous binding, let's just add it at the end
        if (_scopeEnd >= strs.length) {
            // let's just double the array sizes...
            strs = Arrays.copyOf(strs, (strs.length << 1));
            _nsStrings = strs;
        }
        strs[_scopeEnd++] = prefix;
        strs[_scopeEnd++] = uri;

        return null;
    }

    
Method used to add a dynamic binding, and return the prefix
used to bind the specified namespace URI.
/**
     * Method used to add a dynamic binding, and return the prefix
     * used to bind the specified namespace URI.
     */
    public String addGeneratedMapping(String prefixBase, NamespaceContext ctxt,
                                      String uri, int[] seqArr)
    {
        String[] strs = _nsStrings;
        int seqNr = seqArr[0];
        String prefix;

        main_loop:
        while (true) {
            /* We better intern the resulting prefix? Or not?
             * TODO: maybe soft cache these for other docs?
             */
            prefix = (prefixBase + seqNr).intern();
            ++seqNr;

            /* Ok, let's see if we have a mapping (masked or not) for
             * the prefix. If we do, let's just not use it: we could
             * of course mask it (unless it's in current scope), but
             * it's easier to just get a "virgin" prefix...
             */
            int phash = prefix.hashCode();
            
            for (int ix = _scopeEnd - 2; ix >= 0; ix -= 2) {
                String thisP = strs[ix];
                if (thisP == prefix ||
                    (thisP.hashCode() == phash && thisP.equals(prefix))) {
                    continue main_loop;
                }
            }
            /* So far so good... but do we have a root context that might
             * have something too?
             */

            if (ctxt != null && ctxt.getNamespaceURI(prefix) != null) {
                continue;
            }
            break;
        }
        seqArr[0] = seqNr;

        // Ok, good; then let's just add it in...
        if (_scopeEnd >= strs.length) {
            // let's just double the array sizes...
            strs = Arrays.copyOf(strs, (strs.length << 1));
            _nsStrings = strs;
        }
        strs[_scopeEnd++] = prefix;
        strs[_scopeEnd++] = uri;

        return prefix;
    }
}