content: // Protocol Buffers - Google's data interchange format
  // Copyright 2008 Google Inc.  All rights reserved.
  // https://developers.google.com/protocol-buffers/
  //
  // Redistribution and use in source and binary forms, with or without
  // modification, are permitted provided that the following conditions are
  // met:
  //
  //     * Redistributions of source code must retain the above copyright
  // notice, this list of conditions and the following disclaimer.
  //     * Redistributions in binary form must reproduce the above
  // copyright notice, this list of conditions and the following disclaimer
  // in the documentation and/or other materials provided with the
  // distribution.
  //     * Neither the name of Google Inc. nor the names of its
  // contributors may be used to endorse or promote products derived from
  // this software without specific prior written permission.
  //
  // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  
  package com.google.protobuf;
  
  import java.util.AbstractMap;
  import java.util.AbstractSet;
  import java.util.ArrayList;
  import java.util.Collections;
  import java.util.Iterator;
  import java.util.List;
  import java.util.Map;
  import java.util.NoSuchElementException;
  import java.util.Set;
  import java.util.SortedMap;
  import java.util.TreeMap;
  
  /**
   * A custom map implementation from FieldDescriptor to Object optimized to minimize the number of
   * memory allocations for instances with a small number of mappings. The implementation stores the
   * first {@code k} mappings in an array for a configurable value of {@code k}, allowing direct
   * access to the corresponding {@code Entry}s without the need to create an Iterator. The remaining
   * entries are stored in an overflow map. Iteration over the entries in the map should be done as
   * follows:
   *
   * <pre>{@code
   * for (int i = 0; i < fieldMap.getNumArrayEntries(); i++) {
   *   process(fieldMap.getArrayEntryAt(i));
   * }
   * for (Map.Entry<K, V> entry : fieldMap.getOverflowEntries()) {
   *   process(entry);
   * }
   * }</pre>
   *
   * The resulting iteration is in order of ascending field tag number. The object returned by {@link
   * #entrySet()} adheres to the same contract but is less efficient as it necessarily involves
   * creating an object for iteration.
   *
   * <p>The tradeoff for this memory efficiency is that the worst case running time of the {@code
   * put()} operation is {@code O(k + lg n)}, which happens when entries are added in descending
   * order. {@code k} should be chosen such that it covers enough common cases without adversely
   * affecting larger maps. In practice, the worst case scenario does not happen for extensions
   * because extension fields are serialized and deserialized in order of ascending tag number, but
   * the worst case scenario can happen for DynamicMessages.
   *
   * <p>The running time for all other operations is similar to that of {@code TreeMap}.
   *
   * <p>Instances are not thread-safe until {@link #makeImmutable()} is called, after which any
   * modifying operation will result in an {@link UnsupportedOperationException}.
   *
   * @author darick@google.com Darick Tong
   */
  // This class is final for all intents and purposes because the constructor is
  // private. However, the FieldDescriptor-specific logic is encapsulated in
  // a subclass to aid testability of the core logic.
  class SmallSortedMap<K extends Comparable<K>, V> extends AbstractMap<K, V> {
  
    /**
     * Creates a new instance for mapping FieldDescriptors to their values. The {@link
     * #makeImmutable()} implementation will convert the List values of any repeated fields to
     * unmodifiable lists.
     *
     * @param arraySize The size of the entry array containing the lexicographically smallest
     *     mappings.
     */
    static <FieldDescriptorType extends FieldSet.FieldDescriptorLite<FieldDescriptorType>>
        SmallSortedMap<FieldDescriptorType, Object> newFieldMap(int arraySize) {
      return new SmallSortedMap<FieldDescriptorType, Object>(arraySize) {
        @Override
        @SuppressWarnings("unchecked")
        public void makeImmutable() {
          if (!isImmutable()) {
            for (int i = 0; i < getNumArrayEntries(); i++) {
              final Map.Entry<FieldDescriptorType, Object> entry = getArrayEntryAt(i);
              if (entry.getKey().isRepeated()) {
                final List value = (List) entry.getValue();
                entry.setValue(Collections.unmodifiableList(value));
              }
            }
            for (Map.Entry<FieldDescriptorType, Object> entry : getOverflowEntries()) {
              if (entry.getKey().isRepeated()) {
                final List value = (List) entry.getValue();
                entry.setValue(Collections.unmodifiableList(value));
              }
            }
          }
          super.makeImmutable();
        }
      };
    }
  
    /**
     * Creates a new instance for testing.
     *
     * @param arraySize The size of the entry array containing the lexicographically smallest
     *     mappings.
     */
    static <K extends Comparable<K>, V> SmallSortedMap<K, V> newInstanceForTest(int arraySize) {
      return new SmallSortedMap<K, V>(arraySize);
    }
  
    private final int maxArraySize;
    // The "entry array" is actually a List because generic arrays are not
    // allowed. ArrayList also nicely handles the entry shifting on inserts and
    // removes.
    private List<Entry> entryList;
    private Map<K, V> overflowEntries;
    private boolean isImmutable;
    // The EntrySet is a stateless view of the Map. It's initialized the first
    // time it is requested and reused henceforth.
    private volatile EntrySet lazyEntrySet;
    private Map<K, V> overflowEntriesDescending;
    private volatile DescendingEntrySet lazyDescendingEntrySet;
  
    /**
     * @code arraySize Size of the array in which the lexicographically smallest mappings are stored.
     *     (i.e. the {@code k} referred to in the class documentation).
     */
    private SmallSortedMap(int arraySize) {
      this.maxArraySize = arraySize;
      this.entryList = Collections.emptyList();
      this.overflowEntries = Collections.emptyMap();
      this.overflowEntriesDescending = Collections.emptyMap();
    }
  
    /** Make this map immutable from this point forward. */
    public void makeImmutable() {
      if (!isImmutable) {
        // Note: There's no need to wrap the entryList in an unmodifiableList
        // because none of the list's accessors are exposed. The iterator() of
        // overflowEntries, on the other hand, is exposed so it must be made
        // unmodifiable.
        overflowEntries =
            overflowEntries.isEmpty()
                ? Collections.<K, V>emptyMap()
                : Collections.unmodifiableMap(overflowEntries);
        overflowEntriesDescending =
            overflowEntriesDescending.isEmpty()
                ? Collections.<K, V>emptyMap()
                : Collections.unmodifiableMap(overflowEntriesDescending);
        isImmutable = true;
      }
    }
  
    /** @return Whether {@link #makeImmutable()} has been called. */
    public boolean isImmutable() {
      return isImmutable;
    }
  
    /** @return The number of entries in the entry array. */
    public int getNumArrayEntries() {
      return entryList.size();
    }
  
    /** @return The array entry at the given {@code index}. */
    public Map.Entry<K, V> getArrayEntryAt(int index) {
      return entryList.get(index);
    }
  
    /** @return There number of overflow entries. */
    public int getNumOverflowEntries() {
      return overflowEntries.size();
    }
  
    /** @return An iterable over the overflow entries. */
    public Iterable<Map.Entry<K, V>> getOverflowEntries() {
      return overflowEntries.isEmpty()
          ? EmptySet.<Map.Entry<K, V>>iterable()
          : overflowEntries.entrySet();
    }
  
    Iterable<Map.Entry<K, V>> getOverflowEntriesDescending() {
      return overflowEntriesDescending.isEmpty()
          ? EmptySet.<Map.Entry<K, V>>iterable()
          : overflowEntriesDescending.entrySet();
    }
  
    @Override
    public int size() {
      return entryList.size() + overflowEntries.size();
    }
  
    /**
     * The implementation throws a {@code ClassCastException} if o is not an object of type {@code K}.
     *
     * <p>{@inheritDoc}
     */
    @Override
    public boolean containsKey(Object o) {
      @SuppressWarnings("unchecked")
      final K key = (K) o;
      return binarySearchInArray(key) >= 0 || overflowEntries.containsKey(key);
    }
  
    /**
     * The implementation throws a {@code ClassCastException} if o is not an object of type {@code K}.
     *
     * <p>{@inheritDoc}
     */
    @Override
    public V get(Object o) {
      @SuppressWarnings("unchecked")
      final K key = (K) o;
      final int index = binarySearchInArray(key);
      if (index >= 0) {
        return entryList.get(index).getValue();
      }
      return overflowEntries.get(key);
    }
  
    @Override
    public V put(K key, V value) {
      checkMutable();
      final int index = binarySearchInArray(key);
      if (index >= 0) {
        // Replace existing array entry.
        return entryList.get(index).setValue(value);
      }
      ensureEntryArrayMutable();
      final int insertionPoint = -(index + 1);
      if (insertionPoint >= maxArraySize) {
        // Put directly in overflow.
        return getOverflowEntriesMutable().put(key, value);
      }
      // Insert new Entry in array.
      if (entryList.size() == maxArraySize) {
        // Shift the last array entry into overflow.
        final Entry lastEntryInArray = entryList.remove(maxArraySize - 1);
        getOverflowEntriesMutable().put(lastEntryInArray.getKey(), lastEntryInArray.getValue());
      }
      entryList.add(insertionPoint, new Entry(key, value));
      return null;
    }
  
    @Override
    public void clear() {
      checkMutable();
      if (!entryList.isEmpty()) {
        entryList.clear();
      }
      if (!overflowEntries.isEmpty()) {
        overflowEntries.clear();
      }
    }
  
    /**
     * The implementation throws a {@code ClassCastException} if o is not an object of type {@code K}.
     *
     * <p>{@inheritDoc}
     */
    @Override
    public V remove(Object o) {
      checkMutable();
      @SuppressWarnings("unchecked")
      final K key = (K) o;
      final int index = binarySearchInArray(key);
      if (index >= 0) {
        return removeArrayEntryAt(index);
      }
      // overflowEntries might be Collections.unmodifiableMap(), so only
      // call remove() if it is non-empty.
      if (overflowEntries.isEmpty()) {
        return null;
      } else {
        return overflowEntries.remove(key);
      }
    }
  
    private V removeArrayEntryAt(int index) {
      checkMutable();
      final V removed = entryList.remove(index).getValue();
      if (!overflowEntries.isEmpty()) {
        // Shift the first entry in the overflow to be the last entry in the
        // array.
        final Iterator<Map.Entry<K, V>> iterator = getOverflowEntriesMutable().entrySet().iterator();
        entryList.add(new Entry(iterator.next()));
        iterator.remove();
      }
      return removed;
    }
  
    /**
     * @param key The key to find in the entry array.
     * @return The returned integer position follows the same semantics as the value returned by
     *     {@link java.util.Arrays#binarySearch()}.
     */
    private int binarySearchInArray(K key) {
      int left = 0;
      int right = entryList.size() - 1;
  
      // Optimization: For the common case in which entries are added in
      // ascending tag order, check the largest element in the array before
      // doing a full binary search.
      if (right >= 0) {
        int cmp = key.compareTo(entryList.get(right).getKey());
        if (cmp > 0) {
          return -(right + 2); // Insert point is after "right".
        } else if (cmp == 0) {
          return right;
        }
      }
  
      while (left <= right) {
        int mid = (left + right) / 2;
        int cmp = key.compareTo(entryList.get(mid).getKey());
        if (cmp < 0) {
          right = mid - 1;
        } else if (cmp > 0) {
          left = mid + 1;
        } else {
          return mid;
        }
      }
      return -(left + 1);
    }
  
    /**
     * Similar to the AbstractMap implementation of {@code keySet()} and {@code values()}, the entry
     * set is created the first time this method is called, and returned in response to all subsequent
     * calls.
     *
     * <p>{@inheritDoc}
     */
    @Override
    public Set<Map.Entry<K, V>> entrySet() {
      if (lazyEntrySet == null) {
        lazyEntrySet = new EntrySet();
      }
      return lazyEntrySet;
    }
  
    Set<Map.Entry<K, V>> descendingEntrySet() {
      if (lazyDescendingEntrySet == null) {
        lazyDescendingEntrySet = new DescendingEntrySet();
      }
      return lazyDescendingEntrySet;
    }
  
    /** @throws UnsupportedOperationException if {@link #makeImmutable()} has has been called. */
    private void checkMutable() {
      if (isImmutable) {
        throw new UnsupportedOperationException();
      }
    }
  
    /**
     * @return a {@link SortedMap} to which overflow entries mappings can be added or removed.
     * @throws UnsupportedOperationException if {@link #makeImmutable()} has been called.
     */
    @SuppressWarnings("unchecked")
    private SortedMap<K, V> getOverflowEntriesMutable() {
      checkMutable();
      if (overflowEntries.isEmpty() && !(overflowEntries instanceof TreeMap)) {
        overflowEntries = new TreeMap<K, V>();
        overflowEntriesDescending = ((TreeMap<K, V>) overflowEntries).descendingMap();
      }
      return (SortedMap<K, V>) overflowEntries;
    }
  
    /** Lazily creates the entry list. Any code that adds to the list must first call this method. */
    private void ensureEntryArrayMutable() {
      checkMutable();
      if (entryList.isEmpty() && !(entryList instanceof ArrayList)) {
        entryList = new ArrayList<Entry>(maxArraySize);
      }
    }
  
    /**
     * Entry implementation that implements Comparable in order to support binary search within the
     * entry array. Also checks mutability in {@link #setValue()}.
     */
    private class Entry implements Map.Entry<K, V>, Comparable<Entry> {
  
      private final K key;
      private V value;
  
      Entry(Map.Entry<K, V> copy) {
        this(copy.getKey(), copy.getValue());
      }
  
      Entry(K key, V value) {
        this.key = key;
        this.value = value;
      }
  
      @Override
      public K getKey() {
        return key;
      }
  
      @Override
      public V getValue() {
        return value;
      }
  
      @Override
      public int compareTo(Entry other) {
        return getKey().compareTo(other.getKey());
      }
  
      @Override
      public V setValue(V newValue) {
        checkMutable();
        final V oldValue = this.value;
        this.value = newValue;
        return oldValue;
      }
  
      @Override
      public boolean equals(Object o) {
        if (o == this) {
          return true;
        }
        if (!(o instanceof Map.Entry)) {
          return false;
        }
        @SuppressWarnings("unchecked")
        Map.Entry<?, ?> other = (Map.Entry<?, ?>) o;
        return equals(key, other.getKey()) && equals(value, other.getValue());
      }
  
      @Override
      public int hashCode() {
        return (key == null ? 0 : key.hashCode()) ^ (value == null ? 0 : value.hashCode());
      }
  
      @Override
      public String toString() {
        return key + "=" + value;
      }
  
      /** equals() that handles null values. */
      private boolean equals(Object o1, Object o2) {
        return o1 == null ? o2 == null : o1.equals(o2);
      }
    }
  
    /** Stateless view of the entries in the field map. */
    private class EntrySet extends AbstractSet<Map.Entry<K, V>> {
  
      @Override
      public Iterator<Map.Entry<K, V>> iterator() {
        return new EntryIterator();
      }
  
      @Override
      public int size() {
        return SmallSortedMap.this.size();
      }
  
      /**
       * Throws a {@link ClassCastException} if o is not of the expected type.
       *
       * <p>{@inheritDoc}
       */
      @Override
      public boolean contains(Object o) {
        @SuppressWarnings("unchecked")
        final Map.Entry<K, V> entry = (Map.Entry<K, V>) o;
        final V existing = get(entry.getKey());
        final V value = entry.getValue();
        return existing == value || (existing != null && existing.equals(value));
      }
  
      @Override
      public boolean add(Map.Entry<K, V> entry) {
        if (!contains(entry)) {
          put(entry.getKey(), entry.getValue());
          return true;
        }
        return false;
      }
  
      /**
       * Throws a {@link ClassCastException} if o is not of the expected type.
       *
       * <p>{@inheritDoc}
       */
      @Override
      public boolean remove(Object o) {
        @SuppressWarnings("unchecked")
        final Map.Entry<K, V> entry = (Map.Entry<K, V>) o;
        if (contains(entry)) {
          SmallSortedMap.this.remove(entry.getKey());
          return true;
        }
        return false;
      }
  
      @Override
      public void clear() {
        SmallSortedMap.this.clear();
      }
    }
  
    private class DescendingEntrySet extends EntrySet {
      @Override
      public Iterator<java.util.Map.Entry<K, V>> iterator() {
        return new DescendingEntryIterator();
      }
    }
  
    /**
     * Iterator implementation that switches from the entry array to the overflow entries
     * appropriately.
     */
    private class EntryIterator implements Iterator<Map.Entry<K, V>> {
  
      private int pos = -1;
      private boolean nextCalledBeforeRemove;
      private Iterator<Map.Entry<K, V>> lazyOverflowIterator;
  
      @Override
      public boolean hasNext() {
        return (pos + 1) < entryList.size()
            || (!overflowEntries.isEmpty() && getOverflowIterator().hasNext());
      }
  
      @Override
      public Map.Entry<K, V> next() {
        nextCalledBeforeRemove = true;
        // Always increment pos so that we know whether the last returned value
        // was from the array or from overflow.
        if (++pos < entryList.size()) {
          return entryList.get(pos);
        }
        return getOverflowIterator().next();
      }
  
      @Override
      public void remove() {
        if (!nextCalledBeforeRemove) {
          throw new IllegalStateException("remove() was called before next()");
        }
        nextCalledBeforeRemove = false;
        checkMutable();
  
        if (pos < entryList.size()) {
          removeArrayEntryAt(pos--);
        } else {
          getOverflowIterator().remove();
        }
      }
  
      /**
       * It is important to create the overflow iterator only after the array entries have been
       * iterated over because the overflow entry set changes when the client calls remove() on the
       * array entries, which invalidates any existing iterators.
       */
      private Iterator<Map.Entry<K, V>> getOverflowIterator() {
        if (lazyOverflowIterator == null) {
          lazyOverflowIterator = overflowEntries.entrySet().iterator();
        }
        return lazyOverflowIterator;
      }
    }
  
    /**
     * Reverse Iterator implementation that switches from the entry array to the overflow entries
     * appropriately.
     */
    private class DescendingEntryIterator implements Iterator<Map.Entry<K, V>> {
  
      private int pos = entryList.size();
      private Iterator<Map.Entry<K, V>> lazyOverflowIterator;
  
      @Override
      public boolean hasNext() {
        return (pos > 0 && pos <= entryList.size()) || getOverflowIterator().hasNext();
      }
  
      @Override
      public Map.Entry<K, V> next() {
        if (getOverflowIterator().hasNext()) {
          return getOverflowIterator().next();
        }
        return entryList.get(--pos);
      }
  
      @Override
      public void remove() {
        throw new UnsupportedOperationException();
      }
  
      /**
       * It is important to create the overflow iterator only after the array entries have been
       * iterated over because the overflow entry set changes when the client calls remove() on the
       * array entries, which invalidates any existing iterators.
       */
      private Iterator<Map.Entry<K, V>> getOverflowIterator() {
        if (lazyOverflowIterator == null) {
          lazyOverflowIterator = overflowEntriesDescending.entrySet().iterator();
        }
        return lazyOverflowIterator;
      }
    }
  
    /**
     * Helper class that holds immutable instances of an Iterable/Iterator that we return when the
     * overflow entries is empty. This eliminates the creation of an Iterator object when there is
     * nothing to iterate over.
     */
    private static class EmptySet {
  
      private static final Iterator<Object> ITERATOR =
          new Iterator<Object>() {
            @Override
            public boolean hasNext() {
              return false;
            }
  
            @Override
            public Object next() {
              throw new NoSuchElementException();
            }
  
            @Override
            public void remove() {
              throw new UnsupportedOperationException();
            }
          };
  
      private static final Iterable<Object> ITERABLE =
          new Iterable<Object>() {
            @Override
            public Iterator<Object> iterator() {
              return ITERATOR;
            }
          };
  
      @SuppressWarnings("unchecked")
      static <T> Iterable<T> iterable() {
        return (Iterable<T>) ITERABLE;
      }
    }
  
    @Override
    public boolean equals(Object o) {
      if (this == o) {
        return true;
      }
  
      if (!(o instanceof SmallSortedMap)) {
        return super.equals(o);
      }
  
      SmallSortedMap<?, ?> other = (SmallSortedMap<?, ?>) o;
      final int size = size();
      if (size != other.size()) {
        return false;
      }
  
      // Best effort try to avoid allocating an entry set.
      final int numArrayEntries = getNumArrayEntries();
      if (numArrayEntries != other.getNumArrayEntries()) {
        return entrySet().equals(other.entrySet());
      }
  
      for (int i = 0; i < numArrayEntries; i++) {
        if (!getArrayEntryAt(i).equals(other.getArrayEntryAt(i))) {
          return false;
        }
      }
  
      if (numArrayEntries != size) {
        return overflowEntries.equals(other.overflowEntries);
      }
  
      return true;
    }
  
    @Override
    public int hashCode() {
      int h = 0;
      final int listSize = getNumArrayEntries();
      for (int i = 0; i < listSize; i++) {
        h += entryList.get(i).hashCode();
      }
      // Avoid the iterator allocation if possible.
      if (getNumOverflowEntries() > 0) {
        h += overflowEntries.hashCode();
      }
      return h;
    }
  }
  