this.height = 1 + Math.max(height(left), height(right));
    }

    private void recompute() {
      recomputeMultiset();
      recomputeHeight();
    }

    private AvlNode<E> rebalance() {
      switch (balanceFactor()) {
        case -2:
          // requireNonNull is safe because right must exist in order to get a negative factor.
          requireNonNull(right);
          if (right.balanceFactor() > 0) {

 * comparator utilities, see either {@code Comparator} itself (for Java 8+), or {@code
 * com.google.common.collect.Ordering} (otherwise).
 *
 * <h3>Relationship to {@code Ordering}</h3>
 *
 * <p>In light of the significant enhancements to {@code Comparator} in Java 8, the overwhelming
 * majority of usages of {@code Ordering} can be written using only built-in JDK APIs. This class is

   * Written by Doug Lea with assistance from members of JCP JSR-166 Expert Group and released to
   * the public domain, as explained at http://creativecommons.org/publicdomain/zero/1.0/
   *
   * Other contributors include Andrew Wright, Jeffrey Hayes, Pat Fisher, Mike Judd.
   */

  /**
   * An implementation of {@link ExecutorService#invokeAny} for {@link ListeningExecutorService}
   * implementations.
   */
  @SuppressWarnings({

 *
 * <p>A non-null {@code Optional<T>} reference can be used as a replacement for a nullable {@code T}
 * reference. It allows you to represent "a {@code T} that must be present" and a "a {@code T} that
 * might be absent" as two distinct types in your program, which can aid clarity.
 *
 * <p>Some uses of this class include
 *
 * <ul>
 *   <li>As a method return type, as an alternative to returning {@code null} to indicate that no

    int left = 0;
    int right = 2 * k - 1;

    int minThresholdPosition = 0;
    // The leftmost position at which the greatest of the k lower elements
    // -- the new value of threshold -- might be found.

    int iterations = 0;
    int maxIterations = IntMath.log2(right - left, RoundingMode.CEILING) * 3;
    while (left < right) {
      int pivotIndex = (left + right + 1) >>> 1;

    return new SingletonImmutableSet<>(element);
  }

  /*
   * TODO: b/315526394 - Skip the Builder entirely for the of(...) methods, since we don't need to
   * worry that we might trigger the fallback to the JDK-backed implementation? (The varargs one
   * _could_, so we could keep it as it is. Or we could convince ourselves that hash flooding is
   * unlikely in practice there, too.)
   */

  /**

    // then we know it must have given a pending toString value earlier. If not, then the future
    // completed after the timeout expired, and the message might be success.
    if (isDone()) {
      throw new TimeoutException(message + " but future completed as timeout expired");
    }
    throw new TimeoutException(message + " for " + futureToString);
  }

  /**

     * Even though it's weird to pass a defaultValue that is null, some callers do so. Those who
     * pass a literal "null" should probably just use `get`, but I would expect other callers to
     * pass an expression that *might* be null. This could happen with:
     *
     * - a `getFooOrDefault(@CheckForNull Foo defaultValue)` method that returns
     *   `map.getOrDefault(FOO_KEY, defaultValue)`
     *

    @Override
    public int compare(@CheckForNull Object left, @CheckForNull 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) {
        return leftCode < rightCode ? -1 : 1;

  }

  private static final class NullFriendlyComparator<T> implements Comparator<T>, Serializable {
    @Override
    public int compare(T left, T right) {
      return String.valueOf(left).compareTo(String.valueOf(right));
    }
  }