Initial Jack import.

Change-Id: I953cf0a520195a7187d791b2885848ad0d5a9b43

1 files changed, 412 insertions, 0 deletions

diff --git a/guava/src/com/google/common/collect/ForwardingNavigableMap.java b/guava/src/com/google/common/collect/ForwardingNavigableMap.java
new file mode 100644
index 0000000..bf9388b
--- /dev/null
+++ b/guava/src/com/google/common/collect/ForwardingNavigableMap.java
@@ -0,0 +1,412 @@
+/*
+ * Copyright (C) 2012 The Guava Authors
+ *
+ * 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.
+ */
+
+package com.google.common.collect;
+
+import static com.google.common.collect.Maps.keyOrNull;
+
+import com.google.common.annotations.Beta;
+
+import java.util.Iterator;
+import java.util.NavigableMap;
+import java.util.NavigableSet;
+import java.util.NoSuchElementException;
+import java.util.SortedMap;
+
+import javax.annotation.Nullable;
+
+/**
+ * A navigable map which forwards all its method calls to another navigable map. Subclasses should
+ * override one or more methods to modify the behavior of the backing map as desired per the <a
+ * href="http://en.wikipedia.org/wiki/Decorator_pattern">decorator pattern</a>.
+ *
+ * <p><i>Warning:</i> The methods of {@code ForwardingNavigableMap} forward <i>indiscriminately</i>
+ * to the methods of the delegate. For example, overriding {@link #put} alone <i>will not</i>
+ * change the behavior of {@link #putAll}, which can lead to unexpected behavior. In this case, you
+ * should override {@code putAll} as well, either providing your own implementation, or delegating
+ * to the provided {@code standardPutAll} method.
+ *
+ * <p>Each of the {@code standard} methods uses the map's comparator (or the natural ordering of
+ * the elements, if there is no comparator) to test element equality. As a result, if the comparator
+ * is not consistent with equals, some of the standard implementations may violate the {@code Map}
+ * contract.
+ *
+ * <p>The {@code standard} methods and the collection views they return are not guaranteed to be
+ * thread-safe, even when all of the methods that they depend on are thread-safe.
+ *
+ * @author Louis Wasserman
+ * @since 12.0
+ */
+@Beta
+public abstract class ForwardingNavigableMap<K, V>
+    extends ForwardingSortedMap<K, V> implements NavigableMap<K, V> {
+
+  /** Constructor for use by subclasses. */
+  protected ForwardingNavigableMap() {}
+
+  @Override
+  protected abstract NavigableMap<K, V> delegate();
+
+  @Override
+  public Entry<K, V> lowerEntry(K key) {
+    return delegate().lowerEntry(key);
+  }
+
+  /**
+   * A sensible definition of {@link #lowerEntry} in terms of the {@code lastEntry()} of
+   * {@link #headMap(Object, boolean)}. If you override {@code headMap}, you may wish to override
+   * {@code lowerEntry} to forward to this implementation.
+   */
+  protected Entry<K, V> standardLowerEntry(K key) {
+    return headMap(key, false).lastEntry();
+  }
+
+  @Override
+  public K lowerKey(K key) {
+    return delegate().lowerKey(key);
+  }
+
+  /**
+   * A sensible definition of {@link #lowerKey} in terms of {@code lowerEntry}. If you override
+   * {@link #lowerEntry}, you may wish to override {@code lowerKey} to forward to this
+   * implementation.
+   */
+  protected K standardLowerKey(K key) {
+    return keyOrNull(lowerEntry(key));
+  }
+
+  @Override
+  public Entry<K, V> floorEntry(K key) {
+    return delegate().floorEntry(key);
+  }
+
+  /**
+   * A sensible definition of {@link #floorEntry} in terms of the {@code lastEntry()} of
+   * {@link #headMap(Object, boolean)}. If you override {@code headMap}, you may wish to override
+   * {@code floorEntry} to forward to this implementation.
+   */
+  protected Entry<K, V> standardFloorEntry(K key) {
+    return headMap(key, true).lastEntry();
+  }
+
+  @Override
+  public K floorKey(K key) {
+    return delegate().floorKey(key);
+  }
+
+  /**
+   * A sensible definition of {@link #floorKey} in terms of {@code floorEntry}. If you override
+   * {@code floorEntry}, you may wish to override {@code floorKey} to forward to this
+   * implementation.
+   */
+  protected K standardFloorKey(K key) {
+    return keyOrNull(floorEntry(key));
+  }
+
+  @Override
+  public Entry<K, V> ceilingEntry(K key) {
+    return delegate().ceilingEntry(key);
+  }
+
+  /**
+   * A sensible definition of {@link #ceilingEntry} in terms of the {@code firstEntry()} of
+   * {@link #tailMap(Object, boolean)}. If you override {@code tailMap}, you may wish to override
+   * {@code ceilingEntry} to forward to this implementation.
+   */
+  protected Entry<K, V> standardCeilingEntry(K key) {
+    return tailMap(key, true).firstEntry();
+  }
+
+  @Override
+  public K ceilingKey(K key) {
+    return delegate().ceilingKey(key);
+  }
+
+  /**
+   * A sensible definition of {@link #ceilingKey} in terms of {@code ceilingEntry}. If you override
+   * {@code ceilingEntry}, you may wish to override {@code ceilingKey} to forward to this
+   * implementation.
+   */
+  protected K standardCeilingKey(K key) {
+    return keyOrNull(ceilingEntry(key));
+  }
+
+  @Override
+  public Entry<K, V> higherEntry(K key) {
+    return delegate().higherEntry(key);
+  }
+
+  /**
+   * A sensible definition of {@link #higherEntry} in terms of the {@code firstEntry()} of
+   * {@link #tailMap(Object, boolean)}. If you override {@code tailMap}, you may wish to override
+   * {@code higherEntry} to forward to this implementation.
+   */
+  protected Entry<K, V> standardHigherEntry(K key) {
+    return tailMap(key, false).firstEntry();
+  }
+
+  @Override
+  public K higherKey(K key) {
+    return delegate().higherKey(key);
+  }
+
+  /**
+   * A sensible definition of {@link #higherKey} in terms of {@code higherEntry}. If you override
+   * {@code higherEntry}, you may wish to override {@code higherKey} to forward to this
+   * implementation.
+   */
+  protected K standardHigherKey(K key) {
+    return keyOrNull(higherEntry(key));
+  }
+
+  @Override
+  public Entry<K, V> firstEntry() {
+    return delegate().firstEntry();
+  }
+
+  /**
+   * A sensible definition of {@link #firstEntry} in terms of the {@code iterator()} of
+   * {@link #entrySet}. If you override {@code entrySet}, you may wish to override
+   * {@code firstEntry} to forward to this implementation.
+   */
+  protected Entry<K, V> standardFirstEntry() {
+    return Iterables.getFirst(entrySet(), null);
+  }
+
+  /**
+   * A sensible definition of {@link #firstKey} in terms of {@code firstEntry}. If you override
+   * {@code firstEntry}, you may wish to override {@code firstKey} to forward to this
+   * implementation.
+   */
+  protected K standardFirstKey() {
+    Entry<K, V> entry = firstEntry();
+    if (entry == null) {
+      throw new NoSuchElementException();
+    } else {
+      return entry.getKey();
+    }
+  }
+
+  @Override
+  public Entry<K, V> lastEntry() {
+    return delegate().lastEntry();
+  }
+
+  /**
+   * A sensible definition of {@link #lastEntry} in terms of the {@code iterator()} of the
+   * {@link #entrySet} of {@link #descendingMap}. If you override {@code descendingMap}, you may
+   * wish to override {@code lastEntry} to forward to this implementation.
+   */
+  protected Entry<K, V> standardLastEntry() {
+    return Iterables.getFirst(descendingMap().entrySet(), null);
+  }
+
+  /**
+   * A sensible definition of {@link #lastKey} in terms of {@code lastEntry}. If you override
+   * {@code lastEntry}, you may wish to override {@code lastKey} to forward to this implementation.
+   */
+  protected K standardLastKey() {
+    Entry<K, V> entry = lastEntry();
+    if (entry == null) {
+      throw new NoSuchElementException();
+    } else {
+      return entry.getKey();
+    }
+  }
+
+  @Override
+  public Entry<K, V> pollFirstEntry() {
+    return delegate().pollFirstEntry();
+  }
+
+  /**
+   * A sensible definition of {@link #pollFirstEntry} in terms of the {@code iterator} of
+   * {@code entrySet}. If you override {@code entrySet}, you may wish to override
+   * {@code pollFirstEntry} to forward to this implementation.
+   */
+  protected Entry<K, V> standardPollFirstEntry() {
+    return poll(entrySet().iterator());
+  }
+
+  @Override
+  public Entry<K, V> pollLastEntry() {
+    return delegate().pollLastEntry();
+  }
+
+  /**
+   * A sensible definition of {@link #pollFirstEntry} in terms of the {@code iterator} of the
+   * {@code entrySet} of {@code descendingMap}. If you override {@code descendingMap}, you may wish
+   * to override {@code pollFirstEntry} to forward to this implementation.
+   */
+  protected Entry<K, V> standardPollLastEntry() {
+    return poll(descendingMap().entrySet().iterator());
+  }
+
+  @Override
+  public NavigableMap<K, V> descendingMap() {
+    return delegate().descendingMap();
+  }
+
+  /**
+   * A sensible implementation of {@link NavigableMap#descendingMap} in terms of the methods of
+   * this {@code NavigableMap}. In many cases, you may wish to override
+   * {@link ForwardingNavigableMap#descendingMap} to forward to this implementation or a subclass
+   * thereof.
+   *
+   * <p>In particular, this map iterates over entries with repeated calls to
+   * {@link NavigableMap#lowerEntry}. If a more efficient means of iteration is available, you may
+   * wish to override the {@code entryIterator()} method of this class.
+   *
+   * @since 12.0
+   */
+  @Beta
+  protected class StandardDescendingMap extends Maps.DescendingMap<K, V> {
+    /** Constructor for use by subclasses. */
+    public StandardDescendingMap() {}
+
+    @Override
+    NavigableMap<K, V> forward() {
+      return ForwardingNavigableMap.this;
+    }
+
+    @Override
+    protected Iterator<Entry<K, V>> entryIterator() {
+      return new Iterator<Entry<K, V>>() {
+        private Entry<K, V> toRemove = null;
+        private Entry<K, V> nextOrNull = forward().lastEntry();
+
+        @Override
+        public boolean hasNext() {
+          return nextOrNull != null;
+        }
+
+        @Override
+        public java.util.Map.Entry<K, V> next() {
+          if (!hasNext()) {
+            throw new NoSuchElementException();
+          }
+          try {
+            return nextOrNull;
+          } finally {
+            toRemove = nextOrNull;
+            nextOrNull = forward().lowerEntry(nextOrNull.getKey());
+          }
+        }
+
+        @Override
+        public void remove() {
+          Iterators.checkRemove(toRemove != null);
+          forward().remove(toRemove.getKey());
+          toRemove = null;
+        }
+      };
+    }
+  }
+
+  @Override
+  public NavigableSet<K> navigableKeySet() {
+    return delegate().navigableKeySet();
+  }
+
+  /**
+   * A sensible implementation of {@link NavigableMap#navigableKeySet} in terms of the methods of
+   * this {@code NavigableMap}. In many cases, you may wish to override
+   * {@link ForwardingNavigableMap#navigableKeySet} to forward to this implementation or a subclass
+   * thereof.
+   *
+   * @since 12.0
+   */
+  @Beta
+  protected class StandardNavigableKeySet extends Maps.NavigableKeySet<K, V> {
+    /** Constructor for use by subclasses. */
+    public StandardNavigableKeySet() {}
+
+    @Override
+    NavigableMap<K, V> map() {
+      return ForwardingNavigableMap.this;
+    }
+  }
+
+  @Override
+  public NavigableSet<K> descendingKeySet() {
+    return delegate().descendingKeySet();
+  }
+
+  /**
+   * A sensible definition of {@link #descendingKeySet} as the {@code navigableKeySet} of
+   * {@link #descendingMap}. (The {@link StandardDescendingMap} implementation implements
+   * {@code navigableKeySet} on its own, so as not to cause an infinite loop.) If you override
+   * {@code descendingMap}, you may wish to override {@code descendingKeySet} to forward to this
+   * implementation.
+   */
+  protected NavigableSet<K> standardDescendingKeySet() {
+    return descendingMap().navigableKeySet();
+  }
+
+  /**
+   * A sensible definition of {@link #subMap(Object, Object)} in terms of
+   * {@link #subMap(Object, boolean, Object, boolean)}. If you override
+   * {@code subMap(K, boolean, K, boolean)}, you may wish to override {@code subMap} to forward to
+   * this implementation.
+   */
+  @Override
+  protected SortedMap<K, V> standardSubMap(K fromKey, K toKey) {
+    return subMap(fromKey, true, toKey, false);
+  }
+
+  @Override
+  public NavigableMap<K, V> subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) {
+    return delegate().subMap(fromKey, fromInclusive, toKey, toInclusive);
+  }
+
+  @Override
+  public NavigableMap<K, V> headMap(K toKey, boolean inclusive) {
+    return delegate().headMap(toKey, inclusive);
+  }
+
+  @Override
+  public NavigableMap<K, V> tailMap(K fromKey, boolean inclusive) {
+    return delegate().tailMap(fromKey, inclusive);
+  }
+
+  /**
+   * A sensible definition of {@link #headMap(Object)} in terms of
+   * {@link #headMap(Object, boolean)}. If you override {@code headMap(K, boolean)}, you may wish
+   * to override {@code headMap} to forward to this implementation.
+   */
+  protected SortedMap<K, V> standardHeadMap(K toKey) {
+    return headMap(toKey, false);
+  }
+
+  /**
+   * A sensible definition of {@link #tailMap(Object)} in terms of
+   * {@link #tailMap(Object, boolean)}. If you override {@code tailMap(K, boolean)}, you may wish
+   * to override {@code tailMap} to forward to this implementation.
+   */
+  protected SortedMap<K, V> standardTailMap(K fromKey) {
+    return tailMap(fromKey, true);
+  }
+
+  @Nullable
+  private static <T> T poll(Iterator<T> iterator) {
+    if (iterator.hasNext()) {
+      T result = iterator.next();
+      iterator.remove();
+      return result;
+    }
+    return null;
+  }
+}