gt:         return leftCode < rightCode ? -1 : 1;
context: /*
   * Copyright (C) 2007 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_voltpatches.common.collect;
  
  import static com.google_voltpatches.common.base.Preconditions.checkNotNull;
  import static com.google_voltpatches.common.collect.CollectPreconditions.checkNonnegative;
  
  import com.google_voltpatches.common.annotations.GwtCompatible;
  import com.google_voltpatches.common.annotations.VisibleForTesting;
  import com.google_voltpatches.common.base.Function;
  import com.google_voltpatches.errorprone.annotations.CanIgnoreReturnValue;
  import java.util.ArrayList;
  import java.util.Arrays;
  import java.util.Collection;
  import java.util.Collections;
  import java.util.Comparator;
  import java.util.HashSet;
  import java.util.Iterator;
  import java.util.List;
  import java.util.Map;
  import java.util.NoSuchElementException;
  import java.util.SortedMap;
  import java.util.SortedSet;
  import java.util.TreeSet;
  import java.util.concurrent.ConcurrentMap;
  import java.util.concurrent.atomic.AtomicInteger;
  import javax.annotation_voltpatches.Nullable;
  
  /**
   * A comparator, with additional methods to support common operations. This is an "enriched" version
   * of {@code Comparator} for pre-Java-8 users, in the same sense that {@link FluentIterable} is an
   * enriched {@link Iterable} for pre-Java-8 users.
   *
   * <h3>Three types of methods</h3>
   *
   * Like other fluent types, there are three types of methods present: methods for <i>acquiring</i>,
   * <i>chaining</i>, and <i>using</i>.
   *
   * <h4>Acquiring</h4>
   *
   * <p>The common ways to get an instance of {@code Ordering} are:
   *
   * <ul>
   * <li>Subclass it and implement {@link #compare} instead of implementing {@link Comparator}
   *     directly
   * <li>Pass a <i>pre-existing</i> {@link Comparator} instance to {@link #from(Comparator)}
   * <li>Use the natural ordering, {@link Ordering#natural}
   * </ul>
   *
   * <h4>Chaining</h4>
   *
   * <p>Then you can use the <i>chaining</i> methods to get an altered version of that {@code
   * Ordering}, including:
   *
   * <ul>
   * <li>{@link #reverse}
   * <li>{@link #compound(Comparator)}
   * <li>{@link #onResultOf(Function)}
   * <li>{@link #nullsFirst} / {@link #nullsLast}
   * </ul>
   *
   * <h4>Using</h4>
   *
   * <p>Finally, use the resulting {@code Ordering} anywhere a {@link Comparator} is required, or use
   * any of its special operations, such as:
   *
   * <ul>
   * <li>{@link #immutableSortedCopy}
   * <li>{@link #isOrdered} / {@link #isStrictlyOrdered}
   * <li>{@link #min} / {@link #max}
   * </ul>
   *
   * <h3>Understanding complex orderings</h3>
   *
   * <p>Complex chained orderings like the following example can be challenging to understand.
   *
   * <pre>{@code
   * Ordering<Foo> ordering =
   *     Ordering.natural()
   *         .nullsFirst()
   *         .onResultOf(getBarFunction)
   *         .nullsLast();
   * }</pre>
   *
   * Note that each chaining method returns a new ordering instance which is backed by the previous
   * instance, but has the chance to act on values <i>before</i> handing off to that backing instance.
   * As a result, it usually helps to read chained ordering expressions <i>backwards</i>. For example,
   * when {@code compare} is called on the above ordering:
   *
   * <ol>
   * <li>First, if only one {@code Foo} is null, that null value is treated as <i>greater</i>
   * <li>Next, non-null {@code Foo} values are passed to {@code getBarFunction} (we will be comparing
   *     {@code Bar} values from now on)
   * <li>Next, if only one {@code Bar} is null, that null value is treated as <i>lesser</i>
   * <li>Finally, natural ordering is used (i.e. the result of {@code Bar.compareTo(Bar)} is returned)
   * </ol>
   *
   * <p>Alas, {@link #reverse} is a little different. As you read backwards through a chain and
   * encounter a call to {@code reverse}, continue working backwards until a result is determined, and
   * then reverse that result.
   *
   * <h3>Additional notes</h3>
   *
   * <p>Except as noted, the orderings returned by the factory methods of this class are serializable
   * if and only if the provided instances that back them are. For example, if {@code ordering} and
   * {@code function} can themselves be serialized, then {@code ordering.onResultOf(function)} can as
   * well.
   *
   * <h3>For Java 8 users</h3>
   *
   * <p>If you are using Java 8, this class is now obsolete <i>(pending a few August 2016
   * updates)</i>. Most of its functionality is now provided by {@link Stream} and by {@link
   * Comparator} itself, and the rest can now be found as static methods in our new {@link
   * Comparators} class. See each method below for further instructions. Whenever possible, you should
   * change any references of type {@code Ordering} to be of type {@code Comparator} instead. However,
   * at this time we have no plan to <i>deprecate</i> this class.
   *
   * <p>Many replacements involve adopting {@code Stream}, and these changes can sometimes make your
   * code verbose. Whenever following this advice, you should check whether {@code Stream} could be
   * adopted more comprehensively in your code; the end result may be quite a bit simpler.
   *
   * <h3>See also</h3>
   *
   * <p>See the Guava User Guide article on <a href=
   * "https://github.com/google/guava/wiki/OrderingExplained">{@code Ordering}</a>.
   *
   * @author Jesse Wilson
   * @author Kevin Bourrillion
   * @since 2.0
   */
  @GwtCompatible
  public abstract class Ordering<T> implements Comparator<T> {
    // Natural order
  
    /**
     * Returns a serializable ordering that uses the natural order of the values. The ordering throws
     * a {@link NullPointerException} when passed a null parameter.
     *
     * <p>The type specification is {@code <C extends Comparable>}, instead of the technically correct
     * {@code <C extends Comparable<? super C>>}, to support legacy types from before Java 5.
     *
     * <p><b>Java 8 users:</b> use {@link Comparator#naturalOrder} instead.
     */
    @GwtCompatible(serializable = true)
    @SuppressWarnings("unchecked") // TODO(kevinb): right way to explain this??
    public static <C extends Comparable> Ordering<C> natural() {
      return (Ordering<C>) NaturalOrdering.INSTANCE;
    }
  
    // Static factories
  
    /**
     * Returns an ordering based on an <i>existing</i> comparator instance. Note that it is
     * unnecessary to create a <i>new</i> anonymous inner class implementing {@code Comparator} just
     * to pass it in here. Instead, simply subclass {@code Ordering} and implement its {@code compare}
     * method directly.
     *
     * <p><b>Java 8 users:</b> this class is now obsolete as explained in the class documentation, so
     * there is no need to use this method.
     *
     * @param comparator the comparator that defines the order
     * @return comparator itself if it is already an {@code Ordering}; otherwise an ordering that
     *     wraps that comparator
     */
    @GwtCompatible(serializable = true)
    public static <T> Ordering<T> from(Comparator<T> comparator) {
      return (comparator instanceof Ordering)
          ? (Ordering<T>) comparator
          : new ComparatorOrdering<T>(comparator);
    }
  
    /**
     * Simply returns its argument.
     *
     * @deprecated no need to use this
     */
    @GwtCompatible(serializable = true)
    @Deprecated
    public static <T> Ordering<T> from(Ordering<T> ordering) {
      return checkNotNull(ordering);
    }
  
    /**
     * Returns an ordering that compares objects according to the order in which they appear in the
     * given list. Only objects present in the list (according to {@link Object#equals}) may be
     * compared. This comparator imposes a "partial ordering" over the type {@code T}. Subsequent
     * changes to the {@code valuesInOrder} list will have no effect on the returned comparator. Null
     * values in the list are not supported.
     *
     * <p>The returned comparator throws a {@link ClassCastException} when it receives an input
     * parameter that isn't among the provided values.
     *
     * <p>The generated comparator is serializable if all the provided values are serializable.
     *
     * @param valuesInOrder the values that the returned comparator will be able to compare, in the
     *     order the comparator should induce
     * @return the comparator described above
     * @throws NullPointerException if any of the provided values is null
     * @throws IllegalArgumentException if {@code valuesInOrder} contains any duplicate values
     *     (according to {@link Object#equals})
     */
    // TODO(kevinb): provide replacement
    @GwtCompatible(serializable = true)
    public static <T> Ordering<T> explicit(List<T> valuesInOrder) {
      return new ExplicitOrdering<T>(valuesInOrder);
    }
  
    /**
     * Returns an ordering that compares objects according to the order in which they are given to
     * this method. Only objects present in the argument list (according to {@link Object#equals}) may
     * be compared. This comparator imposes a "partial ordering" over the type {@code T}. Null values
     * in the argument list are not supported.
     *
     * <p>The returned comparator throws a {@link ClassCastException} when it receives an input
     * parameter that isn't among the provided values.
     *
     * <p>The generated comparator is serializable if all the provided values are serializable.
     *
     * @param leastValue the value which the returned comparator should consider the "least" of all
     *     values
     * @param remainingValuesInOrder the rest of the values that the returned comparator will be able
     *     to compare, in the order the comparator should follow
     * @return the comparator described above
     * @throws NullPointerException if any of the provided values is null
     * @throws IllegalArgumentException if any duplicate values (according to {@link
     *     Object#equals(Object)}) are present among the method arguments
     */
    // TODO(kevinb): provide replacement
    @GwtCompatible(serializable = true)
    public static <T> Ordering<T> explicit(T leastValue, T... remainingValuesInOrder) {
      return explicit(Lists.asList(leastValue, remainingValuesInOrder));
    }
  
    // Ordering<Object> singletons
  
    /**
     * Returns an ordering which treats all values as equal, indicating "no ordering." Passing this
     * ordering to any <i>stable</i> sort algorithm results in no change to the order of elements.
     * Note especially that {@link #sortedCopy} and {@link #immutableSortedCopy} are stable, and in
     * the returned instance these are implemented by simply copying the source list.
     *
     * <p>Example:
     *
     * <pre>{@code
     * Ordering.allEqual().nullsLast().sortedCopy(
     *     asList(t, null, e, s, null, t, null))
     * }</pre>
     *
     * <p>Assuming {@code t}, {@code e} and {@code s} are non-null, this returns {@code [t, e, s, t,
     * null, null, null]} regardless of the true comparison order of those three values (which might
     * not even implement {@link Comparable} at all).
     *
     * <p><b>Warning:</b> by definition, this comparator is not <i>consistent with equals</i> (as
     * defined {@linkplain Comparator here}). Avoid its use in APIs, such as {@link
     * TreeSet#TreeSet(Comparator)}, where such consistency is expected.
     *
     * <p>The returned comparator is serializable.
     *
     * <p><b>Java 8 users:</b> Use the lambda expression {@code (a, b) -> 0} instead (in certain cases
     * you may need to cast that to {@code Comparator<YourType>}).
     *
     * @since 13.0
     */
    @GwtCompatible(serializable = true)
    @SuppressWarnings("unchecked")
    public static Ordering<Object> allEqual() {
      return AllEqualOrdering.INSTANCE;
    }
  
    /**
     * Returns an ordering that compares objects by the natural ordering of their string
     * representations as returned by {@code toString()}. It does not support null values.
     *
     * <p>The comparator is serializable.
     *
     * <p><b>Java 8 users:</b> Use {@code Comparator.comparing(Object::toString)} instead.
     */
    @GwtCompatible(serializable = true)
    public static Ordering<Object> usingToString() {
      return UsingToStringOrdering.INSTANCE;
    }
  
    /**
     * Returns an arbitrary ordering over all objects, for which {@code compare(a, b) == 0} implies
     * {@code a == b} (identity equality). There is no meaning whatsoever to the order imposed, but it
     * is constant for the life of the VM.
     *
     * <p>Because the ordering is identity-based, it is not "consistent with {@link
     * Object#equals(Object)}" as defined by {@link Comparator}. Use caution when building a {@link
     * SortedSet} or {@link SortedMap} from it, as the resulting collection will not behave exactly
     * according to spec.
     *
     * <p>This ordering is not serializable, as its implementation relies on {@link
     * System#identityHashCode(Object)}, so its behavior cannot be preserved across serialization.
     *
     * @since 2.0
     */
    // TODO(kevinb): copy to Comparators, etc.
    public static Ordering<Object> arbitrary() {
      return ArbitraryOrderingHolder.ARBITRARY_ORDERING;
    }
  
    private static class ArbitraryOrderingHolder {
      static final Ordering<Object> ARBITRARY_ORDERING = new ArbitraryOrdering();
    }
  
    @VisibleForTesting
    static class ArbitraryOrdering extends Ordering<Object> {
  
      private final AtomicInteger counter = new AtomicInteger(0);
      private final ConcurrentMap<Object, Integer> uids =
          Platform.tryWeakKeys(new MapMaker()).makeMap();
  
      private Integer getUid(Object obj) {
        Integer uid = uids.get(obj);
        if (uid == null) {
          // One or more integer values could be skipped in the event of a race
          // to generate a UID for the same object from multiple threads, but
          // that shouldn't be a problem.
          uid = counter.getAndIncrement();
          Integer alreadySet = uids.putIfAbsent(obj, uid);
          if (alreadySet != null) {
            uid = alreadySet;
          }
        }
        return uid;
      }
  
      @Override
      public int compare(Object left, Object right) {
        if (left == right) {
          return 0;
        } else if (left == null) {
          return -1;
        } else if (right == null) {
          return 1;
        }
        int leftCode = identityHashCode(left);
        int rightCode = identityHashCode(right);
        if (leftCode != rightCode) {
  