Collections Data Structure Java

// Copyright 2007 The Apache Software Foundation
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
import java.io.Serializable;
import java.util.*;
/**
 * An mapped collection where the keys are always strings and access to values is case-insensitive. The case of keys in
 * the map is maintained, but on any access to a key (directly or indirectly), all key comparisons are
 * performed in a case-insensitive manner. The map implementation is intended to support a reasonably finite number
 * (dozens or hundreds, not thousands or millions of key/value pairs. Unlike HashMap, it is based on a sorted list of
 * entries rather than hash bucket. It is also geared towards a largely static map, one that is created and then used
 * without modification.
 *
 * @param  the type of value stored
 */
public class CaseInsensitiveMap extends AbstractMap implements Serializable
{
    private static final long serialVersionUID = 3362718337611953298L;
    private static final int NULL_HASH = Integer.MIN_VALUE;
    private static final int DEFAULT_SIZE = 20;
    private static class CIMEntry implements Map.Entry, Serializable
    {
        private static final long serialVersionUID = 6713986085221148350L;
        private String key;
        private final int hashCode;
        V value;
        public CIMEntry(final String key, final int hashCode, V value)
        {
            this.key = key;
            this.hashCode = hashCode;
            this.value = value;
        }
        public String getKey()
        {
            return key;
        }
        public V getValue()
        {
            return value;
        }
        public V setValue(V value)
        {
            V result = this.value;
            this.value = value;
            return result;
        }
        /**
         * Returns true if both keys are null, or if the provided key is the same as, or case-insensitively equal to,
         * the entrie's key.
         *
         * @param key to compare against
         * @return true if equal
         */
        @SuppressWarnings({ "StringEquality" })
        boolean matches(String key)
        {
            return key == this.key || (key != null && key.equalsIgnoreCase(this.key));
        }
        boolean valueMatches(Object value)
        {
            return value == this.value || (value != null && value.equals(this.value));
        }
    }
    private class EntrySetIterator implements Iterator
    {
        int expectedModCount = modCount;
        int index;
        int current = -1;
        public boolean hasNext()
        {
            return index < size;
        }
        public Object next()
        {
            check();
            if (index >= size) throw new NoSuchElementException();
            current = index++;
            return entries[current];
        }
        public void remove()
        {
            check();
            if (current < 0) throw new NoSuchElementException();
            new Position(current, true).remove();
            expectedModCount = modCount;
        }
        private void check()
        {
            if (expectedModCount != modCount) throw new ConcurrentModificationException();
        }
    }
    @SuppressWarnings("unchecked")
    private class EntrySet extends AbstractSet
    {
        @Override
        public Iterator iterator()
        {
            return new EntrySetIterator();
        }
        @Override
        public int size()
        {
            return size;
        }
        @Override
        public void clear()
        {
            CaseInsensitiveMap.this.clear();
        }
        @Override
        public boolean contains(Object o)
        {
            if (!(o instanceof Map.Entry)) return false;
            Map.Entry e = (Map.Entry) o;
            Position position = select(e.getKey());
            return position.isFound() && position.entry().valueMatches(e.getValue());
        }
        @Override
        public boolean remove(Object o)
        {
            if (!(o instanceof Map.Entry)) return false;
            Map.Entry e = (Map.Entry) o;
            Position position = select(e.getKey());
            if (position.isFound() && position.entry().valueMatches(e.getValue()))
            {
                position.remove();
                return true;
            }
            return false;
        }
    }
    private class Position
    {
        private final int cursor;
        private final boolean found;
        Position(int cursor, boolean found)
        {
            this.cursor = cursor;
            this.found = found;
        }
        boolean isFound()
        {
            return found;
        }
        CIMEntry entry()
        {
            return entries[cursor];
        }
        V get()
        {
            return found ? entries[cursor].value : null;
        }
        V remove()
        {
            if (!found) return null;
            V result = entries[cursor].value;
            // Remove the entry by shifting everything else down.
            System.arraycopy(entries, cursor + 1, entries, cursor, size - cursor - 1);
            // We shifted down, leaving one (now duplicate) entry behind.
            entries[--size] = null;
            // A structural change for sure
            modCount++;
            return result;
        }
        @SuppressWarnings("unchecked")
        V put(String key, int hashCode, V newValue)
        {
            if (found)
            {
                CIMEntry e = entries[cursor];
                V result = e.value;
                // Not a structural change, so no change to modCount
                // Update the key (to maintain case). By definition, the hash code
                // will not change.
                e.key = key;
                e.value = newValue;
                return result;
            }
            // Not found, we're going to add it.
            int newSize = size + 1;
            if (newSize == entries.length)
            {
                // Time to expand!
                int newCapacity = (size * 3) / 2 + 1;
                CIMEntry[] newEntries = new CIMEntry[newCapacity];
                System.arraycopy(entries, 0, newEntries, 0, cursor);
                System.arraycopy(entries, cursor, newEntries, cursor + 1, size - cursor);
                entries = newEntries;
            }
            else
            {
                // Open up a space for the new entry
                System.arraycopy(entries, cursor, entries, cursor + 1, size - cursor);
            }
            CIMEntry newEntry = new CIMEntry(key, hashCode, newValue);
            entries[cursor] = newEntry;
            size++;
            // This is definately a structural change
            modCount++;
            return null;
        }
    }
    // The list of entries. This is kept sorted by hash code. In some cases, there may be different
    // keys with the same hash code in adjacent indexes.
    private CIMEntry[] entries;
    private int size = 0;
    // Used by iterators to check for concurrent modifications
    private transient int modCount = 0;
    private transient Set> entrySet;
    public CaseInsensitiveMap()
    {
        this(DEFAULT_SIZE);
    }
    @SuppressWarnings("unchecked")
    public CaseInsensitiveMap(int size)
    {
        entries = new CIMEntry[Math.max(size, 3)];
    }
    public CaseInsensitiveMap(Map map)
    {
        this(map.size());
        for (Map.Entry entry : map.entrySet())
        {
            put(entry.getKey(), entry.getValue());
        }
    }
    @Override
    public void clear()
    {
        for (int i = 0; i < size; i++)
            entries[i] = null;
        size = 0;
        modCount++;
    }
    @Override
    public boolean isEmpty()
    {
        return size == 0;
    }
    @Override
    public int size()
    {
        return size;
    }
    @SuppressWarnings("unchecked")
    @Override
    public V put(String key, V value)
    {
        int hashCode = caseInsenitiveHashCode(key);
        return select(key, hashCode).put(key, hashCode, value);
    }
    @Override
    public boolean containsKey(Object key)
    {
        return select(key).isFound();
    }
    @Override
    public V get(Object key)
    {
        return select(key).get();
    }
    @Override
    public V remove(Object key)
    {
        return select(key).remove();
    }
    @SuppressWarnings("unchecked")
    @Override
    public Set> entrySet()
    {
        if (entrySet == null) entrySet = new EntrySet();
        return entrySet;
    }
    private Position select(Object key)
    {
        if (key == null || key instanceof String)
        {
            String keyString = (String) key;
            return select(keyString, caseInsenitiveHashCode(keyString));
        }
        return new Position(0, false);
    }
    /**
     * Searches the elements for the index of the indicated key and (case insensitive) hash code. Sets the _cursor and
     * _found attributes.
     */
    private Position select(String key, int hashCode)
    {
        if (size == 0) return new Position(0, false);
        int low = 0;
        int high = size - 1;
        int cursor;
        while (low <= high)
        {
            cursor = (low + high) >> 1;
            CIMEntry e = entries[cursor];
            if (e.hashCode < hashCode)
            {
                low = cursor + 1;
                continue;
            }
            if (e.hashCode > hashCode)
            {
                high = cursor - 1;
                continue;
            }
            return tunePosition(key, hashCode, cursor);
        }
        return new Position(low, false);
    }
    /**
     * select() has located a matching hashCode, but there's an outlying possibility that multiple keys share the same
     * hashCode. Backup the cursor until we get to locate the initial hashCode match, then march forward until the key
     * is located, or the hashCode stops matching.
     *
     * @param key
     * @param hashCode
     */
    private Position tunePosition(String key, int hashCode, int cursor)
    {
        boolean found = false;
        while (cursor > 0)
        {
            if (entries[cursor - 1].hashCode != hashCode) break;
            cursor--;
        }
        while (true)
        {
            if (entries[cursor].matches(key))
            {
                found = true;
                break;
            }
            // Advance to the next entry.
            cursor++;
            // If out of entries,
            if (cursor >= size || entries[cursor].hashCode != hashCode) break;
        }
        return new Position(cursor, found);
    }
    static int caseInsenitiveHashCode(String input)
    {
        if (input == null) return NULL_HASH;
        int length = input.length();
        int hash = 0;
        // This should end up more or less equal to input.toLowerCase().hashCode(), unless String
        // changes its implementation. Let's hope this is reasonably fast.
        for (int i = 0; i < length; i++)
        {
            int ch = input.charAt(i);
            int caselessCh = Character.toLowerCase(ch);
            hash = 31 * hash + caselessCh;
        }
        return hash;
    }
}