Have Extrema support non-Comparable types, so that it can potentially be used in more places in the codebase. Also clean up javadoc and document the performance characteristics.

RELNOTES: None
PiperOrigin-RevId: 255964454

src/main/java/com/google/devtools/build/lib/collect/Extrema.java

diff --git a/src/main/java/com/google/devtools/build/lib/collect/Extrema.java b/src/main/java/com/google/devtools/build/lib/collect/Extrema.java
index 6f0b9cf..e706a94 100644
--- a/src/main/java/com/google/devtools/build/lib/collect/Extrema.java
+++ b/src/main/java/com/google/devtools/build/lib/collect/Extrema.java
@@ -18,26 +18,45 @@
 import java.util.PriorityQueue;
 
 /**
- * A stream aggregator that, given a {@code k}, aggregates a sequence of elements into the {@code k}
- * most extreme.
+ * A streaming aggregator that, given a {@code k}, allows a streaming aggregation of {@code n}
+ * elements into the {@code min(k, n)} most extreme, in {@code O(min(k, n))} memory and {@code O(n *
+ * log(min(k, n)))} time.
  */
-public class Extrema<T extends Comparable<T>> {
+public class Extrema<T> {
   private final int k;
   private final Comparator<T> extremaComparator;
   private final PriorityQueue<T> priorityQueue;
 
   /**
-   * Creates an {@link Extrema} that aggregates a sequence of elements into the {@code k} smallest.
+   * Creates an {@link Extrema} that can aggregate {@code n} elements into the {@code min(k, n)}
+   * smallest.
    */
   public static <T extends Comparable<T>> Extrema<T> min(int k) {
-    return new Extrema<>(k, Comparator.<T>naturalOrder());
+    return min(k, Comparator.<T>naturalOrder());
   }
 
   /**
-   * Creates an {@link Extrema} that aggregates a sequence of elements into the {@code k} largest.
+   * Creates an {@link Extrema} that can aggregate {@code n} elements into the {@code min(k, n)}
+   * smallest, per the given {@code comparator}.
+   */
+  public static <T> Extrema<T> min(int k, Comparator<T> comparator) {
+    return new Extrema<>(k, comparator);
+  }
+
+  /**
+   * Creates an {@link Extrema} that can aggregate {@code n} elements into the {@code min(k, n)}
+   * largest.
    */
   public static <T extends Comparable<T>> Extrema<T> max(int k) {
-    return new Extrema<>(k, Comparator.<T>naturalOrder().reversed());
+    return max(k, Comparator.<T>naturalOrder());
+  }
+
+  /**
+   * Creates an {@link Extrema} that can aggregate {@code n} elements into the {@code min(k, n)}
+   * largest, per the given {@code comparator}.
+   */
+  public static <T> Extrema<T> max(int k, Comparator<T> comparator) {
+    return new Extrema<>(k, comparator.reversed());
   }
 
   /**
@@ -77,8 +96,8 @@
 
   /**
    * For an {@link Extrema} created with {@code k} and with {@code n} calls to {@link #aggregate}
-   * since the most recent call to {@link #clear}, returns the min(k, n) most extreme elements
-   * {@link #aggregate}'ed since the most recent call to {@link #clear}.
+   * since the most recent call to {@link #clear}, returns the {@code min(k, n)} most extreme of the
+   * those elements.
    */
   public ImmutableList<T> getExtremeElements() {
     return ImmutableList.sortedCopyOf(extremaComparator, priorityQueue);

src/test/java/com/google/devtools/build/lib/collect/ExtremaTest.java

diff --git a/src/test/java/com/google/devtools/build/lib/collect/ExtremaTest.java b/src/test/java/com/google/devtools/build/lib/collect/ExtremaTest.java
index 1f86a04..6a081e8 100644
--- a/src/test/java/com/google/devtools/build/lib/collect/ExtremaTest.java
+++ b/src/test/java/com/google/devtools/build/lib/collect/ExtremaTest.java
@@ -17,6 +17,7 @@
 
 import com.google.common.collect.ImmutableList;
 import java.util.Collections;
+import java.util.Comparator;
 import java.util.List;
 import java.util.stream.Collectors;
 import java.util.stream.IntStream;
@@ -42,6 +43,36 @@
   }
 
   @Test
+  public void customComparator() {
+    class BoxedInt {
+      private final int i;
+
+      private BoxedInt(int i) {
+        this.i = i;
+      }
+    }
+    Extrema<BoxedInt> extrema =
+        Extrema.max(
+            2,
+            new Comparator<BoxedInt>() {
+              @Override
+              public int compare(BoxedInt bi1, BoxedInt bi2) {
+                return Integer.compare(bi1.i, bi2.i);
+              }
+            });
+    extrema.aggregate(new BoxedInt(4));
+    extrema.aggregate(new BoxedInt(1));
+    extrema.aggregate(new BoxedInt(2));
+    extrema.aggregate(new BoxedInt(3));
+    extrema.aggregate(new BoxedInt(5));
+    ImmutableList<Integer> extremeElements =
+        extrema.getExtremeElements().stream()
+            .map(bi -> bi.i)
+            .collect(ImmutableList.toImmutableList());
+    assertThat(extremeElements).containsExactly(5, 4).inOrder();
+  }
+
+  @Test
   public void minExtremaSmallK() {
     runRangeTest(Extrema.min(5), 1, 100, ImmutableList.of(1, 2, 3, 4, 5));
   }