/*

 * 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 com.sun.xml.internal.bind.v2.util;

import java.util.AbstractSet;

import java.util.Iterator;

import java.util.NoSuchElementException;

import java.util.Set;

import java.util.Map;

import java.util.Collection;

import java.util.HashSet;

import javax.xml.namespace.QName;

import com.sun.xml.internal.bind.v2.runtime.Name;

/**

 * Map keyed by {@link QName}.

 *

 * This specialized map allows a look up operation without constructing

 * a new QName instance, for a performance reason. This {@link Map} assumes

 * that both namespace URI and local name are {@link String#intern() intern}ed.

 *

 * @since JAXB 2.0

 */

public final class QNameMap<V> {

    /**

     * The default initial capacity - MUST be a power of two.

     */

    private static final int DEFAULT_INITIAL_CAPACITY = 16;

    /**

     * The maximum capacity, used if a higher value is implicitly specified

     * by either of the constructors with arguments.

     * MUST be a power of two <= 1<<30.

     */

    private static final int MAXIMUM_CAPACITY = 1 << 30;

    /**

     * The table, resized as necessary. Length MUST Always be a power of two.

     */

    transient Entry<V>[] table = new Entry[DEFAULT_INITIAL_CAPACITY];

    /**

     * The number of key-value mappings contained in this identity hash map.

     */

    transient int size;

    /**

     * The next size value at which to resize . Taking it as

     * MAXIMUM_CAPACITY

     * @serial

     */

    private int threshold;

    /**

     * The load factor used when none specified in constructor.

     **/

    private static final float DEFAULT_LOAD_FACTOR = 0.75f;

    /**

     * Gives an entrySet view of this map

     */

    private Set<Entry<V>> entrySet = null;

    public QNameMap() {

        threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);

        table = new Entry[DEFAULT_INITIAL_CAPACITY];

    }

    /**

     * Associates the specified value with the specified keys in this map.

     * If the map previously contained a mapping for this key, the old

     * value is replaced.

     *

     * @param namespaceUri First key with which the specified value is to be associated.

     * @param localname Second key with which the specified value is to be associated.

     * @param value value to be associated with the specified key.

     *

     */

    public void put(String namespaceUri,String localname, V value ) {

        //keys cannot be null

        assert localname !=null;

        assert namespaceUri !=null;

        // keys must be interned

        assert localname == localname.intern();

        assert namespaceUri == namespaceUri.intern();

        int hash = hash(localname);

        int i = indexFor(hash, table.length);

        for (Entry<V> e = table[i]; e != null; e = e.next) {

            if (e.hash == hash && localname == e.localName && namespaceUri==e.nsUri) {

                e.value = value;

                return;

            }

        }

        addEntry(hash, namespaceUri,localname, value, i);

    }

    public void put(QName name, V value ) {

        put(name.getNamespaceURI(),name.getLocalPart(),value);

    }

    public void put(Name name, V value ) {

        put(name.nsUri,name.localName,value);

    }

    /**

     * Returns the value to which the specified keys are mapped in this QNameMap,

     * or <tt>null</tt> if the map contains no mapping for this key.

     *

     * @param   nsUri the namespaceUri key whose associated value is to be returned.

     * @param   localPart the localPart key whose associated value is to be returned.

     * @return  the value to which this map maps the specified set of keya, or

     *          <tt>null</tt> if the map contains no mapping for this set of keys.

     * @see #put(String,String, Object)

     */

    public V get( String nsUri, String localPart ) {

        Entry<V> e = getEntry(nsUri,localPart);

        if(e==null) return null;

        else        return e.value;

        }

    public V get( QName name ) {

        return get(name.getNamespaceURI(),name.getLocalPart());

    }

    /**

     * Returns the number of keys-value mappings in this map.

     *

     * @return the number of keys-value mappings in this map.

     */

    public int size() {

        return size;

    }

    /**

     * Copies all of the mappings from the specified map to this map

     * These mappings will replace any mappings that

     * this map had for any of the keys currently in the specified map.

     *

     * @param map mappings to be stored in this map.

     *

     */

    public QNameMap<V> putAll(QNameMap<? extends V> map) {

        int numKeysToBeAdded = map.size();

        if (numKeysToBeAdded == 0)

            return this;

        if (numKeysToBeAdded > threshold) {

            int targetCapacity = numKeysToBeAdded;

            if (targetCapacity > MAXIMUM_CAPACITY)

                targetCapacity = MAXIMUM_CAPACITY;

            int newCapacity = table.length;

            while (newCapacity < targetCapacity)

                newCapacity <<= 1;

            if (newCapacity > table.length)

                resize(newCapacity);

        }

        for( Entry<? extends V> e : map.entrySet() )

            put(e.nsUri,e.localName,e.getValue());

        return this;

    }

    /**

     * Returns a hash value for the specified object.The hash value is computed

     * for the localName.

     */

    private static int hash(String x) {

        int h = x.hashCode();

        h += ~(h << 9);

        h ^=  (h >>> 14);

        h +=  (h << 4);

        h ^=  (h >>> 10);

        return h;

    }

    /**

     * Returns index for hash code h.

     */

    private static int indexFor(int h, int length) {

        return h & (length-1);

    }

    /**

     * Add a new entry with the specified keys, value and hash code to

     * the specified bucket.  It is the responsibility of this

     * method to resize the table if appropriate.

     *

     */

    private void addEntry(int hash, String nsUri, String localName, V value, int bucketIndex) {

        Entry<V> e = table[bucketIndex];

        table[bucketIndex] = new Entry<V>(hash, nsUri, localName, value, e);

        if (size++ >= threshold)

            resize(2 * table.length);

    }

    /**

     * Rehashes the contents of this map into a new array with a

     * larger capacity.  This method is called automatically when the

     * number of keys in this map reaches its threshold.

     */

    private void resize(int newCapacity) {

        Entry[] oldTable = table;

        int oldCapacity = oldTable.length;

        if (oldCapacity == MAXIMUM_CAPACITY) {

            threshold = Integer.MAX_VALUE;

            return;

        }

        Entry[] newTable = new Entry[newCapacity];

        transfer(newTable);

        table = newTable;

        threshold = newCapacity;

    }

    /**

     * Transfer all entries from current table to newTable.

     */

    private void transfer(Entry<V>[] newTable) {

        Entry<V>[] src = table;

        int newCapacity = newTable.length;

        for (int j = 0; j < src.length; j++) {

            Entry<V> e = src[j];

            if (e != null) {

                src[j] = null;

                do {

                    Entry<V> next = e.next;

                    int i = indexFor(e.hash, newCapacity);

                    e.next = newTable[i];

                    newTable[i] = e;

                    e = next;

                } while (e != null);

            }

        }

    }

    /**

     * Returns one random item in the map.

     * If this map is empty, return null.

     *

     * <p>

     * This method is useful to obtain the value from a map that only contains one element.

     */

    public Entry<V> getOne() {

        for( Entry<V> e : table ) {

            if(e!=null)

                return e;

        }

        return null;

    }

    public Collection<QName> keySet() {

        Set<QName> r = new HashSet<QName>();

        for (Entry<V> e : entrySet()) {

            r.add(e.createQName());

        }

        return r;

    }

    private abstract class HashIterator<E> implements Iterator<E> {

        Entry<V> next;  // next entry to return

        int index;              // current slot

        HashIterator() {

            Entry<V>[] t = table;

            int i = t.length;

            Entry<V> n = null;

            if (size != 0) { // advance to first entry

                while (i > 0 && (n = t[--i]) == null) {}

            }

            next = n;

            index = i;

        }

        public boolean hasNext() {

            return next != null;

        }

        Entry<V> nextEntry() {

            Entry<V> e = next;

            if (e == null)

                throw new NoSuchElementException();

            Entry<V> n = e.next;

            Entry<V>[] t = table;

            int i = index;

            while (n == null && i > 0)

                n = t[--i];

            index = i;

            next = n;

            return e;

        }

        public void remove() {

            throw new UnsupportedOperationException();

        }

    }

    public boolean containsKey(String nsUri,String localName) {

        return getEntry(nsUri,localName)!=null;

    }

    /**

     * Returns true if this map is empty.

     */

    public boolean isEmpty() {

        return size == 0;

    }

    public static final class Entry<V>  {

        /** The namespace URI. */

        public final String nsUri;

        /** The localPart. */

        public final String localName;

        V value;

        final int hash;

        Entry<V> next;

        /**

         * Create new entry.

         */

        Entry(int h, String nsUri, String localName, V v, Entry<V> n) {

            value = v;

            next = n;

            this.nsUri = nsUri;

            this.localName = localName;

            hash = h;

        }

        /**

         * Creates a new QName object from {@link #nsUri} and {@link #localName}.

         */

        public QName createQName() {

            return new QName(nsUri,localName);

        }

        public V getValue() {

            return value;

        }

        public V setValue(V newValue) {

            V oldValue = value;

            value = newValue;

            return oldValue;

        }

        @Override

        public boolean equals(Object o) {

            if (!(o instanceof Entry))

                return false;

            Entry e = (Entry)o;

            String k1 = nsUri;

            String k2 = e.nsUri;

            String k3 = localName;

            String k4 = e.localName;

            if (k1 == k2 || (k1 != null && k1.equals(k2)) &&

                    (k3 == k4 ||(k3 !=null && k3.equals(k4)))) {

                Object v1 = getValue();

                Object v2 = e.getValue();

                if (v1 == v2 || (v1 != null && v1.equals(v2)))

                    return true;

            }

            return false;

        }

        @Override

        public int hashCode() {

            return ( localName.hashCode()) ^

                    (value==null   ? 0 : value.hashCode());

        }

        @Override

        public String toString() {

            return '"'+nsUri +"\",\"" +localName + "\"=" + getValue();

        }

    }

    public Set<Entry<V>> entrySet() {

        Set<Entry<V>> es = entrySet;

        return es != null ? es : (entrySet = new EntrySet());

    }

    private Iterator<Entry<V>> newEntryIterator() {

        return new EntryIterator();

    }

    private class EntryIterator extends HashIterator<Entry<V>> {

        public Entry<V> next() {

            return nextEntry();

        }

    }

    private class EntrySet extends AbstractSet<Entry<V>> {

        public Iterator<Entry<V>> iterator() {

            return newEntryIterator();

        }

        @Override

        public boolean contains(Object o) {

            if (!(o instanceof Entry))

                return false;

            Entry<V> e = (Entry<V>) o;

            Entry<V> candidate = getEntry(e.nsUri,e.localName);

            return candidate != null && candidate.equals(e);

        }

        @Override

        public boolean remove(Object o) {

            throw new UnsupportedOperationException();

        }

        public int size() {

            return size;

        }

    }

    private Entry<V> getEntry(String nsUri,String localName) {

        // strings must be interned

        assert nsUri==nsUri.intern();

        assert localName==localName.intern();

        int hash = hash(localName);

        int i = indexFor(hash, table.length);

        Entry<V> e = table[i];

        while (e != null && !(localName == e.localName && nsUri == e.nsUri))

            e = e.next;

        return e;

    }

    @Override

    public String toString() {

        StringBuilder buf = new StringBuilder();

        buf.append('{');

        for( Entry<V> e : entrySet() ) {

            if(buf.length()>1)

                buf.append(',');

            buf.append('[');

            buf.append(e);

            buf.append(']');

        }

        buf.append('}');

        return buf.toString();

    }

}