Remove protobuf lite for java.

third_party/protobuf/java/src/main/java/com/google/protobuf/SmallSortedMap.java

Index: third_party/protobuf/java/src/main/java/com/google/protobuf/SmallSortedMap.java
diff --git a/third_party/protobuf/java/src/main/java/com/google/protobuf/SmallSortedMap.java b/third_party/protobuf/java/src/main/java/com/google/protobuf/SmallSortedMap.java
deleted file mode 100644
index c6cad6afb0e6bf1ab877c7869cb8d1e61b1aa444..0000000000000000000000000000000000000000
--- a/third_party/protobuf/java/src/main/java/com/google/protobuf/SmallSortedMap.java
+++ /dev/null
@@ -1,618 +0,0 @@
-// Protocol Buffers - Google's data interchange format
-// Copyright 2008 Google Inc.  All rights reserved.
-// http://code.google.com/p/protobuf/
-//
-// 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.TreeMap;
-import java.util.List;
-import java.util.Map;
-import java.util.NoSuchElementException;
-import java.util.Set;
-import java.util.SortedMap;
-
-/**
- * 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;
-
-  /**
-   * @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();
-  }
-
-  /** 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);
-      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();
-  }
-
-  @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}.
-   *
-   * {@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}.
-   *
-   * {@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}.
-   *
-   * {@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.
-   *
-   * {@inheritDoc}
-   */
-  @Override
-  public Set<Map.Entry<K, V>> entrySet() {
-    if (lazyEntrySet == null) {
-      lazyEntrySet = new EntrySet();
-    }
-    return lazyEntrySet;
-  }
-
-  /**
-   * @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>();
-    }
-    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 (Java 1.6 override semantics, but we must support 1.5)
-    public K getKey() {
-      return key;
-    }
-
-    //@Override (Java 1.6 override semantics, but we must support 1.5)
-    public V getValue() {
-      return value;
-    }
-
-    //@Override (Java 1.6 override semantics, but we must support 1.5)
-    public int compareTo(Entry other) {
-      return getKey().compareTo(other.getKey());
-    }
-
-    //@Override (Java 1.6 override semantics, but we must support 1.5)
-    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.
-     *
-     * {@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.
-     *
-     * {@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();
-    }
-  }
-
-  /**
-   * 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 (Java 1.6 override semantics, but we must support 1.5)
-    public boolean hasNext() {
-      return (pos + 1) < entryList.size() ||
-          getOverflowIterator().hasNext();
-    }
-
-    //@Override (Java 1.6 override semantics, but we must support 1.5)
-    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 (Java 1.6 override semantics, but we must support 1.5)
-    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;
-    }
-  }
-
-  /**
-   * 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 (Java 1.6 override semantics, but we must support 1.5)
-      public boolean hasNext() {
-        return false;
-      }
-      //@Override (Java 1.6 override semantics, but we must support 1.5)
-      public Object next() {
-        throw new NoSuchElementException();
-      }
-      //@Override (Java 1.6 override semantics, but we must support 1.5)
-      public void remove() {
-        throw new UnsupportedOperationException();
-      }
-    };
-
-    private static final Iterable<Object> ITERABLE = new Iterable<Object>() {
-      //@Override (Java 1.6 override semantics, but we must support 1.5)
-      public Iterator<Object> iterator() {
-        return ITERATOR;
-      }
-    };
-
-    @SuppressWarnings("unchecked")
-    static <T> Iterable<T> iterable() {
-      return (Iterable<T>) ITERABLE;
-    }
-  }
-}