AVLGroupTree extends AbstractCollection<Centroid> implements Serializable { @SuppressWarnings("WeakerAccess") public int floorSum(long sum) { int floor = IntAVLTree.NIL; for (int node = tree.root(); node != IntAVLTree.NIL; ) { final int left = tree.left(node); final long leftCount = aggregatedCounts[left]; if (leftCount <= sum) { floor = node; sum -= leftCount + count(node); node = tree.right(node); } else { node = tree.left(node); } } return floor; } AVLGroupTree();   AVLGroupTree(final boolean record); int size(); int prev(int node); int next(int node); double mean(int node); int count(int node); List<Double> data(int node); void add(double centroid, int count, List<Double> data); @Override boolean add(Centroid centroid); @SuppressWarnings("WeakerAccess") void update(int node, double centroid, int count, List<Double> data, boolean forceInPlace); void remove(int node); @SuppressWarnings("WeakerAccess") int floor(double centroid); @SuppressWarnings("WeakerAccess") int floorSum(long sum); int first(); @SuppressWarnings("WeakerAccess") int last(); @SuppressWarnings("WeakerAccess") long headSum(int node); @Override Iterator<Centroid> iterator(); int sum();  }
@Test public void testFloorSum() { AVLGroupTree x = new AVLGroupTree(false); int total = 0; for (int i = 0; i < 1000; ++i) { int count = randomIntBetween(1, 10); x.add(randomDouble(), count, null); total += count; } assertEquals(IntAVLTree.NIL, x.floorSum(-1)); for (long i = 0; i < total + 10; ++i) { final int floorNode = x.floorSum(i); assertTrue(x.headSum(floorNode) <= i); final int next = x.next(floorNode); assertTrue(next == IntAVLTree.NIL || x.headSum(next) > i); } }