// Assert that the dataset contains the same elements after the in-place computation (although
    // they may be reordered). We only do this for one index rather than for all indexes, as it is
    // quite expensive (quadratic in the size of PSEUDORANDOM_DATASET).
    double[] dataset = Doubles.toArray(PSEUDORANDOM_DATASET);
    @SuppressWarnings("unused")
    double actual = percentiles().index(33).computeInPlace(dataset);

 * @since 2.0
 */
@GwtCompatible(emulated = true)
@ElementTypesAreNonnullByDefault
public final class Sets {
  private Sets() {}

  /**
   * {@link AbstractSet} substitute without the potentially-quadratic {@code removeAll}
   * implementation.
   */
  abstract static class ImprovedAbstractSet<E extends @Nullable Object> extends AbstractSet<E> {
    @Override
    public boolean removeAll(Collection<?> c) {

 *
 * <h3>Performance</h3>
 *
 * <p>The average time complexity of the computation is O(N) in the size of the dataset. There is a
 * worst case time complexity of O(N^2). You are extremely unlikely to hit this quadratic case on
 * randomly ordered data (the probability decreases faster than exponentially in N), but if you are
 * passing in unsanitized user data then a malicious user could force it. A light shuffle of the

    }
    for (int j = 0; j < 1000; j++) {
      builder.add(9);
    }
    ImmutableSortedSet<Integer> unused = builder.build();
    assertThat(compares[0]).isAtMost(10000);
    // hopefully something quadratic would have more digits
  }

  public static <E extends @Nullable Object> CopyOnWriteArrayList<E> newCopyOnWriteArrayList(
      Iterable<? extends E> elements) {
    // We copy elements to an ArrayList first, rather than incurring the
    // quadratic cost of adding them to the COWAL directly.
    Collection<? extends E> elementsCollection =
        (elements instanceof Collection)
            ? (Collection<? extends E>) elements
            : newArrayList(elements);

      InCompletionOrderState<T> localState = state;
      if (localState != null) {
        // Don't print the actual array! We don't want inCompletionOrder(list).toString() to have
        // quadratic output.
        return "inputCount=["
            + localState.inputFutures.length
            + "], remaining=["
            + localState.incompleteOutputCount.get()
            + "]";
      }

      InCompletionOrderState<T> localState = state;
      if (localState != null) {
        // Don't print the actual array! We don't want inCompletionOrder(list).toString() to have
        // quadratic output.
        return "inputCount=["
            + localState.inputFutures.length
            + "], remaining=["
            + localState.incompleteOutputCount.get()
            + "]";
      }