1 /* 2 * Copyright (C) 2014 The Guava Authors 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 package com.google.common.collect; 18 19 import static com.google.common.truth.Truth.assertThat; 20 21 import com.google.common.annotations.GwtCompatible; 22 import com.google.common.math.IntMath; 23 import com.google.common.primitives.Ints; 24 import java.math.RoundingMode; 25 import java.util.Collections; 26 import java.util.Comparator; 27 import java.util.List; 28 import junit.framework.TestCase; 29 30 /** 31 * Tests for {@code TopKSelector}. 32 * 33 * @author Louis Wasserman 34 */ 35 @GwtCompatible 36 public class TopKSelectorTest extends TestCase { 37 testNegativeK()38 public void testNegativeK() { 39 try { 40 TopKSelector.<String>least(-1); 41 fail(); 42 } catch (IllegalArgumentException expected) { 43 } 44 try { 45 TopKSelector.<String>greatest(-1); 46 fail(); 47 } catch (IllegalArgumentException expected) { 48 } 49 try { 50 TopKSelector.least(-1, Ordering.natural()); 51 fail(); 52 } catch (IllegalArgumentException expected) { 53 } 54 try { 55 TopKSelector.greatest(-1, Ordering.natural()); 56 fail(); 57 } catch (IllegalArgumentException expected) { 58 } 59 } 60 testZeroK()61 public void testZeroK() { 62 TopKSelector<Integer> top = TopKSelector.least(0); 63 for (int i = 0; i < 10; i++) { 64 top.offer(i); 65 } 66 assertThat(top.topK()).isEmpty(); 67 } 68 testNoElementsOffered()69 public void testNoElementsOffered() { 70 TopKSelector<Integer> top = TopKSelector.least(10); 71 assertThat(top.topK()).isEmpty(); 72 } 73 testOfferedFewerThanK()74 public void testOfferedFewerThanK() { 75 TopKSelector<Integer> top = TopKSelector.least(10); 76 top.offer(3); 77 top.offer(5); 78 top.offer(2); 79 assertThat(top.topK()).containsExactly(2, 3, 5).inOrder(); 80 } 81 testOfferedKPlusOne()82 public void testOfferedKPlusOne() { 83 for (List<Integer> list : Collections2.permutations(Ints.asList(1, 2, 3, 4, 5))) { 84 TopKSelector<Integer> top = TopKSelector.least(4); 85 top.offerAll(list); 86 assertThat(top.topK()).containsExactly(1, 2, 3, 4).inOrder(); 87 } 88 } 89 testOfferedThreeK()90 public void testOfferedThreeK() { 91 for (List<Integer> list : Collections2.permutations(Ints.asList(1, 2, 3, 4, 5, 6))) { 92 TopKSelector<Integer> top = TopKSelector.least(2); 93 top.offerAll(list); 94 assertThat(top.topK()).containsExactly(1, 2).inOrder(); 95 } 96 } 97 testDifferentComparator()98 public void testDifferentComparator() { 99 TopKSelector<String> top = TopKSelector.least(3, String.CASE_INSENSITIVE_ORDER); 100 top.offerAll(ImmutableList.of("a", "B", "c", "D", "e", "F")); 101 assertThat(top.topK()).containsExactly("a", "B", "c").inOrder(); 102 } 103 testWorstCase()104 public void testWorstCase() { 105 int n = 2000000; 106 int k = 200000; 107 final long[] compareCalls = {0}; 108 Comparator<Integer> cmp = 109 new Comparator<Integer>() { 110 @Override 111 public int compare(Integer o1, Integer o2) { 112 compareCalls[0]++; 113 return o1.compareTo(o2); 114 } 115 }; 116 TopKSelector<Integer> top = TopKSelector.least(k, cmp); 117 top.offer(1); 118 for (int i = 1; i < n; i++) { 119 top.offer(0); 120 } 121 assertThat(top.topK()).containsExactlyElementsIn(Collections.nCopies(k, 0)); 122 assertThat(compareCalls[0]).isAtMost(10L * n * IntMath.log2(k, RoundingMode.CEILING)); 123 } 124 testExceedMaxIteration()125 public void testExceedMaxIteration() { 126 /* 127 * Bug #5692 occurred when TopKSelector called Arrays.sort incorrectly. 128 */ 129 TopKSelector<Integer> top = TopKSelector.least(7); 130 top.offerAll(Ints.asList(5, 7, 6, 2, 4, 3, 1, 0, 0, 0, 0, 0, 0, 0)); 131 assertThat(top.topK()).isEqualTo(Ints.asList(0, 0, 0, 0, 0, 0, 0)); 132 } 133 } 134