notifyStopped();
    }
  }

  /*
   * A NoOp service that will delay the startup and shutdown notification for a configurable amount
   * of time.
   */
  private static class NoOpDelayedService extends NoOpService {
    private long delay;

    public NoOpDelayedService(long delay) {
      this.delay = delay;
    }

    @Override
    protected void doStart() {
      new Thread() {

        (expectedOutcome == Outcome.HANG)
            ? EXPECTED_HANG_DELAY_MILLIS
            : UNEXPECTED_HANG_DELAY_MILLIS;
    boolean hung =
        !awaitUninterruptibly(callCompletedLatch, hangDelayMillis, TimeUnit.MILLISECONDS);
    if (hung) {
      assertEquals(expectedOutcome, Outcome.HANG);
    } else {
      assertNull(task.get(UNEXPECTED_HANG_DELAY_MILLIS, TimeUnit.MILLISECONDS));
    }
  }

  @Override

    }

    @Override
    public ListenableScheduledFuture<?> schedule(Runnable command, long delay, TimeUnit unit) {
      TrustedListenableFutureTask<@Nullable Void> task =
          TrustedListenableFutureTask.create(command, null);
      ScheduledFuture<?> scheduled = delegate.schedule(task, delay, unit);
      return new ListenableScheduledTask<@Nullable Void>(task, scheduled);
    }

    @Override

      // http://graphics.stanford.edu/~seander/bithacks.html#IntegerMinOrMax

      int delta = a - b; // can't overflow, since a and b are nonnegative

      int minDeltaOrZero = delta & (delta >> (Integer.SIZE - 1));
      // equivalent to Math.min(delta, 0)

      a = delta - minDeltaOrZero - minDeltaOrZero; // sets a to Math.abs(a - b)
      // a is now nonnegative and even

            } else if (behavior == 1) { // return null
              computeNullCount.incrementAndGet();
              return null;
            } else if (behavior == 2) { // slight delay before returning
              Thread.sleep(5);
              computeCount.incrementAndGet();
              return key;
            } else {
              computeCount.incrementAndGet();
              return key;

  private void assertEvents(String... events) {
    assertEquals(Arrays.toString(events), stopwatch.readEventsAndClear());
  }

  /**
   * The stopwatch gathers events and presents them as strings. R0.6 means a delay of 0.6 seconds
   * caused by the (R)ateLimiter U1.0 means the (U)ser caused the stopwatch to sleep for a second.
   */
  static class FakeStopwatch extends SleepingStopwatch {
    long instant = 0L;

 * than {@code size()}. Furthermore, this structure only depends on a fixed number of arrays; {@code
 * add(x)} operations <i>do not</i> create objects for the garbage collector to deal with, and for
 * every element added, the garbage collector will have to traverse {@code 1.5} references on
 * average, in the marking phase, not {@code 5.0} as in {@code java.util.HashSet}.
 *

    List<T> list = Arrays.asList(strictlyOrderedElements);

    // for use calling Collection.toArray later
    T[] emptyArray = Platform.newArray(strictlyOrderedElements, 0);

    // shoot me, but I didn't want to deal with wildcards through the whole test
    @SuppressWarnings("unchecked")
    Scenario<T> starter = new Scenario<>((Ordering<T>) ordering, list, emptyArray);
    verifyScenario(starter, 0);
  }

    List<T> list = Arrays.asList(strictlyOrderedElements);

    // for use calling Collection.toArray later
    T[] emptyArray = Platform.newArray(strictlyOrderedElements, 0);

    // shoot me, but I didn't want to deal with wildcards through the whole test
    @SuppressWarnings("unchecked")
    Scenario<T> starter = new Scenario<>((Ordering<T>) ordering, list, emptyArray);
    verifyScenario(starter, 0);
  }

    SMALL_DELAY_MS = SHORT_DELAY_MS * 5;
    MEDIUM_DELAY_MS = SHORT_DELAY_MS * 10;
    LONG_DELAY_MS = SHORT_DELAY_MS * 200;
  }

  /**
   * Returns a timeout in milliseconds to be used in tests that verify that operations block or time
   * out.
   */
  long timeoutMillis() {
    return SHORT_DELAY_MS / 4;
  }