This is an automated email from the ASF dual-hosted git repository. daim pushed a commit to branch OAK-11531 in repository https://gitbox.apache.org/repos/asf/jackrabbit-oak.git
commit 917dc59cd62a62978104dc2ab9916d4bb148334f Author: Rishabh Kumar <[email protected]> AuthorDate: Wed Feb 26 19:18:54 2025 +0530 OAK-11531 : added util method to replace Guava's Iterables.mergeSorted --- .../oak/commons/collections/IterableUtils.java | 15 ++++ .../oak/commons/collections/IteratorUtils.java | 83 ++++++++++++++++++ .../oak/commons/collections/IterableUtilsTest.java | 93 ++++++++++++++++++++ .../oak/commons/collections/IteratorUtilsTest.java | 99 ++++++++++++++++++++++ oak-parent/pom.xml | 2 +- 5 files changed, 291 insertions(+), 1 deletion(-) 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..1bddc49da1 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,18 @@ 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) { + 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); + } } diff --git a/oak-parent/pom.xml b/oak-parent/pom.xml index 9195ad889c..6659a48bc0 100644 --- a/oak-parent/pom.xml +++ b/oak-parent/pom.xml @@ -615,7 +615,7 @@ <dependency> <groupId>org.apache.commons</groupId> <artifactId>commons-collections4</artifactId> - <version>4.4</version> + <version>4.5.0-M3</version> </dependency> <dependency> <groupId>org.apache.commons</groupId>
