// TODO(kevinb): this class still needs some design-and-document-for-inheritance love
@ElementTypesAreNonnullByDefault
abstract class AbstractStreamingHasher extends AbstractHasher {
  /** Buffer via which we pass data to the hash algorithm (the implementor) */
  private final ByteBuffer buffer;

  /** Number of bytes to be filled before process() invocation(s). */
  private final int bufferSize;

  /** Number of bytes processed per process() invocation. */

import com.google.common.annotations.VisibleForTesting;

/**
 * Implementation of Geoff Pike's fingerprint2011 hash function. See {@link Hashing#fingerprint2011}
 * for information on the behaviour of the algorithm.
 *
 * <p>On Intel Core2 2.66, on 1000 bytes, fingerprint2011 takes 0.9 microseconds compared to
 * fingerprint at 4.0 microseconds and md5 at 4.5 microseconds.
 *

  }

  // 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.

      default:
        return construct(elements.clone());
    }
  }

  /**
   * Returns an immutable list containing the given elements, sorted according to their natural
   * order. The sorting algorithm used is stable, so elements that compare as equal will stay in the
   * order in which they appear in the input.
   *
   * <p>If your data has no duplicates, or you wish to deduplicate elements, use {@code

  /*
   * One of the key challenges of this class is to prevent lost signals, while trying hard to
   * minimize unnecessary signals. One simple and correct algorithm is to signal some other waiter
   * with a satisfied guard (if one exists) whenever any thread occupying the monitor exits the
   * monitor, either by unlocking all of its held locks, or by starting to wait for a guard. This

        for (int i = 0; i < size; i++) {
          keys[i] = rng.nextInt();
        }
        return createTreap(Ints.asList(keys));
      }

      // See http://en.wikipedia.org/wiki/Treap for details on the algorithm.
      private Optional<BinaryNode> createTreap(List<Integer> keys) {
        if (keys.isEmpty()) {
          return Optional.absent();
        }
        int minIndex = 0;
        for (int i = 1; i < keys.size(); i++) {

 * k). In benchmarks, this implementation performs at least as well as either implementation, and
 * degrades more gracefully for worst-case input.
 *
 * <p>The implementation does not necessarily use a <i>stable</i> sorting algorithm; when multiple
 * equivalent elements are added to it, it is undefined which will come first in the output.
 *
 * @author Louis Wasserman
 */
@GwtCompatible
@ElementTypesAreNonnullByDefault
final class TopKSelector<

  private String algorithm;

  private MessageDigest md;

  @BeforeExperiment
  void setUp() throws Exception {
    md = MessageDigest.getInstance(algorithm);
  }

  @Benchmark
  int getInstance(int reps) throws Exception {
    int retValue = 0;
    for (int i = 0; i < reps; i++) {
      retValue ^= MessageDigest.getInstance(algorithm).getDigestLength();
    }
    return retValue;
  }

     * and the arithmetic mean is always higher than the geometric mean.
     *
     * b) this iteration converges to floor(sqrt(x)). In fact, the number of correct digits doubles
     * with each iteration, so this algorithm takes O(log(digits)) iterations.
     *
     * We start out with a double-precision approximation, which may be higher or lower than the
     * true value. Therefore, we perform at least one Newton iteration to get a guess that's

 * traditional exclusive locks. Although this increases the false positives that the locks detect
 * (i.e. cycles that will not actually result in deadlock), it simplifies the algorithm and
 * implementation considerably. The assumption is that a user of this factory wishes to eliminate
 * any cyclic acquisition ordering.
 *
 * <p><strong>Explicit Lock Acquisition Ordering</strong>
 *