hextriclosan commented on code in PR #721: URL: https://github.com/apache/commons-collections/pull/721#discussion_r3767892166
########## src/main/java/org/apache/commons/collections4/iterators/LexicographicPermutationIterator.java: ########## @@ -0,0 +1,198 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * https://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.commons.collections4.iterators; + +import java.util.ArrayList; +import java.util.Collection; +import java.util.Collections; +import java.util.Comparator; +import java.util.Iterator; +import java.util.List; +import java.util.NoSuchElementException; +import java.util.Objects; + +/** + * This iterator creates permutations of an input collection, using the + * lexicographical order. + * <p> + * The iterator might return fewer than n! permutations of the input collection, + * because duplicated permutations are skipped: equal elements are not + * distinguished from one another. + * The {@code remove()} operation is not supported, and will throw an + * {@code UnsupportedOperationException}. + * </p> + * <p> + * NOTE: in case an empty collection is provided, the iterator will + * return exactly one empty list as result, as 0! = 1. + * </p> + * + * @param <E> the type of the objects being permuted + * @see PermutationIterator + * @since 4.6.0 + */ +public class LexicographicPermutationIterator<E> implements Iterator<List<E>> { + + /** + * The comparator used to define order of generation, + * or null if it uses the natural ordering. + */ + private final Comparator<? super E> comparator; + + /** + * Next permutation to return. When a permutation is requested + * this instance is provided and the next one is computed. + */ + private List<E> nextPermutation; + + /** + * Standard constructor for this class, using the natural ordering of the elements. + * + * @param collection The collection to generate permutations for + * @throws NullPointerException if collection is null + */ + public LexicographicPermutationIterator(final Collection<? extends E> collection) { + this(collection, null); + } + + /** + * Constructs an instance using the given comparator to order the elements. + * + * @param collection The collection to generate permutations for + * @param comparator The comparator used to define the order of generation, + * or null to use the natural ordering of the elements + * @throws NullPointerException if collection is null + */ + public LexicographicPermutationIterator(final Collection<? extends E> collection, final Comparator<? super E> comparator) { + Objects.requireNonNull(collection, "collection"); + nextPermutation = new ArrayList<>(collection); + this.comparator = comparator; + } Review Comment: The described behavior is real and the javadoc was actively misleading about it. I've pushed doc and test changes rather than the sort, and here's the reasoning. The truncation is intentional. This class is the iterator form of the classic next-permutation step: it starts wherever the input puts it and advances to the smallest arrangement greater than the current one, exactly as `std::next_permutation` does in C++. Sorted input is a precondition for enumerating the full set, in the same way sorted input is a precondition for `Collections.binarySearch`. That precondition simply wasn't documented. I'd rather not sort in the constructor, because sorting is not a neutral addition. It removes a capability that cannot be recovered: - Resuming. A caller that persisted the last arrangement it processed can construct an iterator from it and carry on. With a constructor sort there is no way to express "start here". - Splitting the work. The permutation space can be divided across threads or machines by handing each worker a different starting arrangement. Same problem. A caller who wants the complete set can always sort before constructing, and that is one line at the call site. A caller who wants to start partway through has no recourse if the constructor sorts. The asymmetry is what decides it for me: preserving the given order is strictly the more expressive of the two designs. There's also a ready alternative for callers who want all n! without thinking about order, namely `PermutationIterator`, which reaches every arrangement from any starting point because Steinhaus-Johnson-Trotter enumerates the whole group. The two classes are genuinely different tools, and I've added a note making the differences explicit so the @see link stops implying they're interchangeable. ########## src/test/java/org/apache/commons/collections4/iterators/LexicographicPermutationIteratorTest.java: ########## @@ -0,0 +1,343 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * https://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.commons.collections4.iterators; + +import static java.util.Collections.emptyList; +import static org.junit.jupiter.api.Assertions.assertEquals; +import static org.junit.jupiter.api.Assertions.assertFalse; +import static org.junit.jupiter.api.Assertions.assertThrows; +import static org.junit.jupiter.api.Assertions.assertTrue; + +import java.util.ArrayList; +import java.util.Arrays; +import java.util.Comparator; +import java.util.Iterator; +import java.util.List; +import java.util.NoSuchElementException; +import java.util.Objects; +import java.util.stream.Collectors; +import java.util.stream.StreamSupport; + +import org.junit.jupiter.api.BeforeEach; +import org.junit.jupiter.api.Test; + +/** + * Test class for LexicographicPermutationIterator. + */ +class LexicographicPermutationIteratorTest extends AbstractIteratorTest<List<Character>> { + + /** + * A comparator that orders nothing, identified only by an id, used to check that + * equal comparators make equal iterators. + * + * @param <T> the type of the objects compared + */ + private static final class CustomComparator<T> implements Comparator<T> { + + private final int id; + + CustomComparator(final int id) { + this.id = id; + } + + @Override + public int compare(final T o1, final T o2) { + return 0; + } + + @Override + public boolean equals(final Object o) { + if (this == o) { + return true; + } + + if (o == null || getClass() != o.getClass()) { + return false; + } + + final CustomComparator<?> cmp = (CustomComparator<?>) o; + return id == cmp.id; + } + + @Override + public int hashCode() { + return id; + } + } + + /** + * A value holder that deliberately does not implement {@link Comparable}, used to + * check that a supplied comparator is honored. + * + * @param <T> the type of the wrapped value + */ + private static final class NonComparableObject<T> { + + private final T value; + + NonComparableObject(final T value) { + this.value = value; + } + + @Override + public boolean equals(final Object o) { + if (this == o) { + return true; + } + + if (o == null || getClass() != o.getClass()) { + return false; + } + + final NonComparableObject<?> that = (NonComparableObject<?>) o; + return Objects.equals(value, that.value); + } + + T getValue() { + return value; + } + + @Override + public int hashCode() { + return Objects.hash(value); + } + } + + @SuppressWarnings("boxing") // OK in test code + protected Character[] testArray = { 'A', 'B', 'C' }; + + protected List<Character> testList; + + @Override + public LexicographicPermutationIterator<Character> makeEmptyIterator() { + return new LexicographicPermutationIterator<>(new ArrayList<>()); + } + + @Override + public LexicographicPermutationIterator<Character> makeObject() { + return new LexicographicPermutationIterator<>(testList); + } + + @BeforeEach + public void setUp() { + testList = new ArrayList<>(); + testList.addAll(Arrays.asList(testArray)); + } + + @Override + public boolean supportsEmptyIterator() { + return false; + } + + @Override + public boolean supportsRemove() { + return false; + } + + @Test + void testCustomComparator() { + final Iterator<List<Character>> permutationIterator = new LexicographicPermutationIterator<>(Arrays.asList('C', 'B', 'A'), + Comparator.reverseOrder()); + Review Comment: Good news on this one: the test already covers what you're after, and I can show it. I patched `compareElements` to ignore the comparator and ran the suite. `testCustomComparator` fails, and so does `testCustomComparatorWithNonComparableObjects`. The reason `['C','B','A']` works as input is that it's the maximum under natural ordering. An implementation that ignored the comparator would find no pivot, terminate after a single permutation, and fail on the second `assertTrue`. The test therefore separates "comparator honoured, 6 permutations in reverse-lexicographic order" from "comparator ignored, 1 permutation". You're right that neither test exercised input unsorted under its own comparator. I've added `testUnsortedCollectionStartsAtGivenArrangementWithComparator` for exactly that, passing ['B','C','A'] with `reverseOrder()` and asserting the four permutations that follow it. Starting at the given arrangement is the intended contract here rather than a bug, for the reasons in the other thread, and that test now pins it. -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected]
