This is an automated email from the ASF dual-hosted git repository.
daim pushed a commit to branch trunk
in repository https://gitbox.apache.org/repos/asf/jackrabbit-oak.git
The following commit(s) were added to refs/heads/trunk by this push:
new 48b26b59b7 OAK-11531 : added util method to replace Guava's
Iterables.mergeSorted (#2122)
48b26b59b7 is described below
commit 48b26b59b74c8f081fe05832d3d262668c257a38
Author: Rishabh Kumar <[email protected]>
AuthorDate: Mon Mar 3 17:53:44 2025 +0530
OAK-11531 : added util method to replace Guava's Iterables.mergeSorted
(#2122)
* OAK-11531 : added util method to replace Guava's Iterables.mergeSorted
* OAK-11531 : reverted pom.xml change
* OAK-11531 : added null checks for IterableUtils.mergeSorted
---------
Co-authored-by: Rishabh Kumar <[email protected]>
---
.../oak/commons/collections/IterableUtils.java | 17 ++++
.../oak/commons/collections/IteratorUtils.java | 83 ++++++++++++++++++
.../oak/commons/collections/IterableUtilsTest.java | 93 ++++++++++++++++++++
.../oak/commons/collections/IteratorUtilsTest.java | 99 ++++++++++++++++++++++
4 files changed, 292 insertions(+)
diff --git
a/oak-commons/src/main/java/org/apache/jackrabbit/oak/commons/collections/IterableUtils.java
b/oak-commons/src/main/java/org/apache/jackrabbit/oak/commons/collections/IterableUtils.java
index 9d20b68acb..52cc0a36f6 100644
---
a/oak-commons/src/main/java/org/apache/jackrabbit/oak/commons/collections/IterableUtils.java
+++
b/oak-commons/src/main/java/org/apache/jackrabbit/oak/commons/collections/IterableUtils.java
@@ -26,6 +26,7 @@ import org.jetbrains.annotations.NotNull;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Collection;
+import java.util.Comparator;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;
@@ -303,4 +304,20 @@ public class IterableUtils {
public static <I, O> Iterable<O> transform(final Iterable<I> iterable,
final Function<? super I, ? extends O> function) {
return
org.apache.commons.collections4.IterableUtils.transformedIterable(iterable,
function::apply);
}
+
+ /**
+ * Merges multiple sorted iterables into a single sorted iterable.
+ *
+ * @param <T> the type of elements returned by this iterable
+ * @param iterables the iterables to merge, must not be null
+ * @param c the c to determine the order of elements, must not be null
+ * @return an iterable that merges the input iterables in sorted order
+ * @throws NullPointerException if the iterables or c are null
+ */
+ public static <T> Iterable<T> mergeSorted(final Iterable<? extends
Iterable<? extends T>> iterables, final Comparator<? super T> c) {
+ Objects.requireNonNull(iterables, "Iterables must not be null.");
+ Objects.requireNonNull(c, "Comparator must not be null.");
+ final Iterable<T> iterable = () ->
IteratorUtils.mergeSorted(org.apache.commons.collections4.IterableUtils.transformedIterable(iterables,
Iterable::iterator), c);
+ return
org.apache.commons.collections4.IterableUtils.unmodifiableIterable(iterable);
+ }
}
diff --git
a/oak-commons/src/main/java/org/apache/jackrabbit/oak/commons/collections/IteratorUtils.java
b/oak-commons/src/main/java/org/apache/jackrabbit/oak/commons/collections/IteratorUtils.java
index 4f0c7f7d44..c392724501 100644
---
a/oak-commons/src/main/java/org/apache/jackrabbit/oak/commons/collections/IteratorUtils.java
+++
b/oak-commons/src/main/java/org/apache/jackrabbit/oak/commons/collections/IteratorUtils.java
@@ -18,10 +18,15 @@
*/
package org.apache.jackrabbit.oak.commons.collections;
+import org.apache.commons.collections4.iterators.PeekingIterator;
import org.jetbrains.annotations.NotNull;
+import java.util.Comparator;
import java.util.Iterator;
+import java.util.NoSuchElementException;
import java.util.Objects;
+import java.util.PriorityQueue;
+import java.util.Queue;
/**
* Utility methods for {@link Iterator} conversions.
@@ -61,4 +66,82 @@ public class IteratorUtils {
}
};
}
+
+ /**
+ * Merges multiple sorted iterators into a single sorted iterator.
Equivalent entries will not be de-duplicated.
+ * <p>
+ * This method assumes that the input iterators are sorted in increasing
order.
+ *
+ * @param <T> the type of elements returned by this iterator
+ * @param itrs the iterators to merge, must not be null
+ * @param c the comparator to determine the order of elements, must not be
null
+ * @return an iterator that merges the input iterators in sorted order
+ * @throws NullPointerException if the iterators or comparator are null
+ */
+ public static <T> Iterator<T> mergeSorted(final Iterable<? extends
Iterator<? extends T>> itrs, final Comparator<? super T> c) {
+ Objects.requireNonNull(itrs, "Iterators must not be null");
+ Objects.requireNonNull(c, "Comparator must not be null");
+ return
org.apache.commons.collections4.IteratorUtils.unmodifiableIterator(new
MergingIterator<>(itrs, c));
+ }
+
+ /**
+ * An iterator that merges multiple sorted iterators into a single sorted
iterator.
+ * <p>This iterator assumes that the input iterators are sorted in
increasing order.
+ * Equivalent entries will not be de-duplicated.
+ *
+ * @param <T> the type of elements returned by this iterator
+ */
+ private static class MergingIterator<T> implements Iterator<T> {
+ final Queue<PeekingIterator<T>> queue;
+
+ /**
+ * Constructs a new MergingIterator.
+ *
+ * @param itrs the iterators to merge, must not be null
+ * @param c the comparator to determine the order of elements, must
not be null
+ * @throws NullPointerException if the iterators or comparator are null
+ */
+ public MergingIterator(final Iterable<? extends Iterator<? extends T>>
itrs, final Comparator<? super T> c) {
+ Comparator<PeekingIterator<T>> heapComparator =
Comparator.comparing(PeekingIterator::peek, c);
+
+ this.queue = new PriorityQueue<>(heapComparator);
+
+ for (Iterator<? extends T> itr : itrs) {
+ if (itr.hasNext()) {
+ // only add those iterator which have elements
+ this.queue.add(PeekingIterator.peekingIterator(itr));
+ }
+ }
+ }
+
+ /**
+ * Returns {@code true} if the iteration has more elements.
+ *
+ * @return {@code true} if the iteration has more elements
+ */
+ @Override
+ public boolean hasNext() {
+ return !this.queue.isEmpty();
+ }
+
+ /**
+ * Returns the next element in the iteration.
+ *
+ * @return the next element in the iteration
+ * @throws NoSuchElementException if the iteration has no more elements
+ */
+ @Override
+ public T next() {
+ if (!hasNext()) {
+ throw new NoSuchElementException("No more elements available");
+ }
+
+ final PeekingIterator<T> nextItr = this.queue.remove();
+ T next = nextItr.next();
+ if (nextItr.hasNext()) {
+ this.queue.add(nextItr);
+ }
+ return next;
+ }
+ }
}
diff --git
a/oak-commons/src/test/java/org/apache/jackrabbit/oak/commons/collections/IterableUtilsTest.java
b/oak-commons/src/test/java/org/apache/jackrabbit/oak/commons/collections/IterableUtilsTest.java
index ab9208e754..2ab596addc 100644
---
a/oak-commons/src/test/java/org/apache/jackrabbit/oak/commons/collections/IterableUtilsTest.java
+++
b/oak-commons/src/test/java/org/apache/jackrabbit/oak/commons/collections/IterableUtilsTest.java
@@ -24,6 +24,7 @@ import org.junit.Test;
import java.util.Arrays;
import java.util.Collections;
+import java.util.Comparator;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;
@@ -536,4 +537,96 @@ public class IterableUtilsTest {
List<Integer> result = ListUtils.toList(transformed.iterator());
Assert.assertEquals(Arrays.asList(1, 2, 3), result);
}
+
+ @Test
+ public void testMergeSortedWithNonEmptyIterables() {
+ List<Integer> list1 = Arrays.asList(1, 4, 9);
+ List<Integer> list2 = Arrays.asList(2, 5, 8);
+ List<Integer> list3 = Arrays.asList(3, 6, 7);
+
+ Iterable<Iterable<Integer>> iterables = Arrays.asList(list1, list2,
list3);
+ Iterable<Integer> merged = IterableUtils.mergeSorted(iterables,
Comparator.naturalOrder());
+
+ List<Integer> expected = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9);
+ Iterator<Integer> iterator = merged.iterator();
+ for (Integer value : expected) {
+ Assert.assertTrue(iterator.hasNext());
+ Assert.assertEquals(value, iterator.next());
+ }
+ Assert.assertFalse(iterator.hasNext());
+ }
+
+ @Test
+ public void testMergeSortedWithDuplicateElementsIterables() {
+ List<Integer> list1 = Arrays.asList(1, 4, 9);
+ List<Integer> list2 = Arrays.asList(2, 5, 8);
+ List<Integer> list3 = Arrays.asList(3, 6, 9);
+
+ Iterable<Iterable<Integer>> iterables = Arrays.asList(list1, list2,
list3);
+ Iterable<Integer> merged = IterableUtils.mergeSorted(iterables,
Comparator.naturalOrder());
+
+ List<Integer> expected = Arrays.asList(1, 2, 3, 4, 5, 6, 8, 9, 9);
+ Iterator<Integer> iterator = merged.iterator();
+ for (Integer value : expected) {
+ Assert.assertTrue(iterator.hasNext());
+ Assert.assertEquals(value, iterator.next());
+ }
+ Assert.assertFalse(iterator.hasNext());
+ }
+
+ @Test
+ public void testMergeSortedWithEmptyIterables() {
+ List<Integer> list1 = Collections.emptyList();
+ List<Integer> list2 = Collections.emptyList();
+ List<Integer> list3 = Collections.emptyList();
+
+ Iterable<Iterable<Integer>> iterables = Arrays.asList(list1, list2,
list3);
+ Iterable<Integer> merged = IterableUtils.mergeSorted(iterables,
Comparator.naturalOrder());
+
+ Assert.assertFalse(merged.iterator().hasNext());
+ }
+
+ @Test
+ public void testMergeSortedWithNullIterables() {
+ Assert.assertThrows(NullPointerException.class, () -> {
+ IterableUtils.mergeSorted(null, Comparator.naturalOrder());
+ });
+ }
+
+ @Test
+ public void testMergeSortedWithNullComparator() {
+ List<Integer> list1 = Arrays.asList(1, 4, 7);
+ List<Integer> list2 = Arrays.asList(2, 5, 8);
+ List<Integer> list3 = Arrays.asList(3, 6, 9);
+
+ Iterable<Iterable<Integer>> iterables = Arrays.asList(list1, list2,
list3);
+ Assert.assertThrows(NullPointerException.class, () -> {
+ IterableUtils.mergeSorted(iterables, null);
+ });
+ }
+
+ @Test
+ public void testMergeSortedWithSingleIterable() {
+ List<Integer> list1 = Arrays.asList(1, 2, 3);
+
+ Iterable<Iterable<Integer>> iterables =
Collections.singletonList(list1);
+ Iterable<Integer> merged = IterableUtils.mergeSorted(iterables,
Comparator.naturalOrder());
+
+ List<Integer> expected = Arrays.asList(1, 2, 3);
+ Iterator<Integer> iterator = merged.iterator();
+ for (Integer value : expected) {
+ Assert.assertTrue(iterator.hasNext());
+ Assert.assertEquals(value, iterator.next());
+ }
+ Assert.assertFalse(iterator.hasNext());
+ }
+
+ @Test
+ public void testMergeSortedWithNoIterables() {
+ Iterable<Iterable<Integer>> iterables = Collections.emptyList();
+ Iterable<Integer> merged = IterableUtils.mergeSorted(iterables,
Comparator.naturalOrder());
+
+ Assert.assertFalse(merged.iterator().hasNext());
+ Assert.assertThrows(NoSuchElementException.class, () ->
merged.iterator().next());
+ }
}
diff --git
a/oak-commons/src/test/java/org/apache/jackrabbit/oak/commons/collections/IteratorUtilsTest.java
b/oak-commons/src/test/java/org/apache/jackrabbit/oak/commons/collections/IteratorUtilsTest.java
index 1b943cd1c0..02eefee034 100644
---
a/oak-commons/src/test/java/org/apache/jackrabbit/oak/commons/collections/IteratorUtilsTest.java
+++
b/oak-commons/src/test/java/org/apache/jackrabbit/oak/commons/collections/IteratorUtilsTest.java
@@ -21,8 +21,11 @@ package org.apache.jackrabbit.oak.commons.collections;
import org.junit.Assert;
import org.junit.Test;
+import java.util.Arrays;
+import java.util.Comparator;
import java.util.Iterator;
import java.util.List;
+import java.util.NoSuchElementException;
import static org.junit.Assert.fail;
@@ -44,4 +47,100 @@ public class IteratorUtilsTest {
// that's what we want
}
}
+
+ @Test
+ public void testMergeSortedWithNonEmptyIterators() {
+ List<Integer> list1 = Arrays.asList(1, 4, 7);
+ List<Integer> list2 = Arrays.asList(2, 5, 9);
+ List<Integer> list3 = Arrays.asList(3, 6, 8);
+
+ Iterable<Iterator<Integer>> iterators =
Arrays.asList(list1.iterator(), list2.iterator(), list3.iterator());
+ Iterator<Integer> merged = IteratorUtils.mergeSorted(iterators,
Comparator.naturalOrder());
+
+ List<Integer> expected = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9);
+ for (Integer value : expected) {
+ Assert.assertTrue(merged.hasNext());
+ Assert.assertEquals(value, merged.next());
+ }
+ Assert.assertFalse(merged.hasNext());
+ }
+
+ @Test
+ public void testMergeSortedWithDuplicateElementsIterators() {
+ List<Integer> list1 = Arrays.asList(1, 4, 7);
+ List<Integer> list2 = Arrays.asList(2, 5, 9);
+ List<Integer> list3 = Arrays.asList(3, 6, 9);
+
+ Iterable<Iterator<Integer>> iterators =
Arrays.asList(list1.iterator(), list2.iterator(), list3.iterator());
+ Iterator<Integer> merged = IteratorUtils.mergeSorted(iterators,
Comparator.naturalOrder());
+
+ List<Integer> expected = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 9, 9);
+ for (Integer value : expected) {
+ Assert.assertTrue(merged.hasNext());
+ Assert.assertEquals(value, merged.next());
+ }
+ Assert.assertFalse(merged.hasNext());
+ }
+
+ @Test
+ public void testMergeSortedWithEmptyIterators() {
+ List<Integer> list1 = List.of();
+ List<Integer> list2 = List.of();
+ List<Integer> list3 = List.of();
+
+ Iterable<Iterator<Integer>> iterators =
Arrays.asList(list1.iterator(), list2.iterator(), list3.iterator());
+ Iterator<Integer> merged = IteratorUtils.mergeSorted(iterators,
Comparator.naturalOrder());
+
+ Assert.assertFalse(merged.hasNext());
+ }
+
+ @Test
+ public void testMergeSortedWithNullIterators() {
+ Assert.assertThrows(NullPointerException.class, () -> {
+ IteratorUtils.mergeSorted(null, Comparator.naturalOrder());
+ });
+ }
+
+ @Test
+ public void testMergeSortedWithNullComparator() {
+ List<Integer> list1 = Arrays.asList(1, 4, 7);
+ List<Integer> list2 = Arrays.asList(2, 5, 8);
+ List<Integer> list3 = Arrays.asList(3, 6, 9);
+
+ Iterable<Iterator<Integer>> iterators =
Arrays.asList(list1.iterator(), list2.iterator(), list3.iterator());
+ Assert.assertThrows(NullPointerException.class, () -> {
+ IteratorUtils.mergeSorted(iterators, null);
+ });
+ }
+
+ @Test
+ public void testMergeSortedWithSingleIterator() {
+ List<Integer> list1 = Arrays.asList(1, 2, 3);
+
+ Iterable<Iterator<Integer>> iterators = List.of(list1.iterator());
+ Iterator<Integer> merged = IteratorUtils.mergeSorted(iterators,
Comparator.naturalOrder());
+
+ List<Integer> expected = Arrays.asList(1, 2, 3);
+ for (Integer value : expected) {
+ Assert.assertTrue(merged.hasNext());
+ Assert.assertEquals(value, merged.next());
+ }
+ Assert.assertFalse(merged.hasNext());
+ }
+
+ @Test
+ public void testMergeSortedWithNoIterators() {
+ Iterable<Iterator<Integer>> iterators = List.of();
+ Iterator<Integer> merged = IteratorUtils.mergeSorted(iterators,
Comparator.naturalOrder());
+
+ Assert.assertFalse(merged.hasNext());
+ }
+
+ @Test
+ public void testMergeSortedWithEmptyAndOneIterator() {
+ Iterable<Iterator<Integer>> iterators = List.of();
+ Iterator<Integer> merged = IteratorUtils.mergeSorted(iterators,
Comparator.naturalOrder());
+
+ Assert.assertThrows(NoSuchElementException.class, merged::next);
+ }
}
