FoldedTreeSet implements SortedSet<E> { public boolean compact(long timeout) { if (!isEmpty()) { long start = Time.monotonicNow(); Node<E> node = root.getLeftMostNode(); while (node != null) { if (node.prev != null && !node.prev.isFull()) { Node<E> prev = node.prev; int count = Math.min(Node.NODE_SIZE - prev.size, node.size); System.arraycopy(node.entries, node.leftIndex, prev.entries, prev.rightIndex + 1, count); node.leftIndex += count; node.size -= count; prev.rightIndex += count; prev.size += count; } if (node.isEmpty()) { Node<E> temp = node.next; deleteNode(node); node = temp; continue; } else if (!node.isFull()) { if (node.leftIndex != 0) { System.arraycopy(node.entries, node.leftIndex, node.entries, 0, node.size); Arrays.fill(node.entries, node.size, node.rightIndex + 1, null); node.leftIndex = 0; node.rightIndex = node.size - 1; } } node = node.next; if (Time.monotonicNow() - start > timeout) { return false; } } } return true; } FoldedTreeSet();  FoldedTreeSet(Comparator<E> comparator); @Override Comparator<? super E> comparator(); @Override SortedSet<E> subSet(E fromElement, E toElement); @Override SortedSet<E> headSet(E toElement); @Override SortedSet<E> tailSet(E fromElement); @Override E first(); @Override E last(); @Override int size(); @Override boolean isEmpty(); E get(Object obj, Comparator<?> cmp); E get(E entry); @Override @SuppressWarnings("unchecked") boolean contains(Object obj); @Override Iterator<E> iterator(); @Override Object[] toArray(); @Override @SuppressWarnings("unchecked") T[] toArray(T[] a); E addOrReplace(E entry); @Override boolean add(E entry); boolean addSortedLast(E entry); E removeAndGet(Object obj, Comparator<?> cmp); E removeAndGet(Object obj); boolean remove(Object obj, Comparator<?> cmp); @Override boolean remove(Object obj); @Override boolean containsAll(Collection<?> c); @Override boolean addAll(Collection<? extends E> c); @Override boolean retainAll(Collection<?> c); @Override boolean removeAll(Collection<?> c); @Override void clear(); double fillRatio(); boolean compact(long timeout);  }
@Test public void testCompact() { FoldedTreeSet<Holder> set = new FoldedTreeSet<>(); long[] longs = new long[24553]; for (int i = 0; i < longs.length; i++) { Holder val = new Holder(srand.nextLong()); while (set.contains(val)) { val = new Holder(srand.nextLong()); } longs[i] = val.getId(); set.add(val); } assertEquals(longs.length, set.size()); long[] longs2 = new long[longs.length]; for (int i = 0; i < longs2.length; i++) { Holder val = new Holder(srand.nextLong()); while (set.contains(val)) { val = new Holder(srand.nextLong()); } longs2[i] = val.getId(); set.add(val); } assertEquals(longs.length + longs2.length, set.size()); for (long val : longs) { assertTrue(set.remove(new Holder(val))); } assertEquals(longs2.length, set.size()); assertFalse(set.compact(0)); assertTrue(set.compact(Long.MAX_VALUE)); assertEquals(longs2.length, set.size()); for (long val : longs) { assertFalse(set.remove(new Holder(val))); } for (long val : longs2) { assertEquals(val, set.get(new Holder(val)).getId()); } }