001/*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements.  See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License.  You may obtain a copy of the License at
008 *
009 *      http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017package org.apache.commons.collections4.iterators;
018
019import java.util.ArrayList;
020import java.util.Arrays;
021import java.util.Collection;
022import java.util.HashMap;
023import java.util.Iterator;
024import java.util.List;
025import java.util.Map;
026import java.util.NoSuchElementException;
027
028/**
029 * This iterator creates permutations of an input collection, using the
030 * Steinhaus-Johnson-Trotter algorithm (also called plain changes).
031 * <p>
032 * The iterator will return exactly n! permutations of the input collection.
033 * The {@code remove()} operation is not supported, and will throw an
034 * {@code UnsupportedOperationException}.
035 * <p>
036 * NOTE: in case an empty collection is provided, the iterator will
037 * return exactly one empty list as result, as 0! = 1.
038 *
039 * @param <E>  the type of the objects being permuted
040 *
041 * @version $Id: PermutationIterator.html 972421 2015-11-14 20:00:04Z tn $
042 * @since 4.0
043 */
044public class PermutationIterator<E> implements Iterator<List<E>> {
045
046    /**
047     * Permutation is done on theses keys to handle equal objects.
048     */
049    private int[] keys;
050
051    /**
052     * Mapping between keys and objects.
053     */
054    private Map<Integer, E> objectMap;
055
056    /**
057     * Direction table used in the algorithm:
058     * <ul>
059     *   <li>false is left</li>
060     *   <li>true is right</li>
061     * </ul>
062     */
063    private boolean[] direction;
064
065    /**
066     * Next permutation to return. When a permutation is requested
067     * this instance is provided and the next one is computed.
068     */
069    private List<E> nextPermutation;
070
071    /**
072     * Standard constructor for this class.
073     * @param coll  the collection to generate permutations for
074     * @throws NullPointerException if coll is null
075     */
076    public PermutationIterator(final Collection<? extends E> coll) {
077        if (coll == null) {
078            throw new NullPointerException("The collection must not be null");
079        }
080
081        keys = new int[coll.size()];
082        direction = new boolean[coll.size()];
083        Arrays.fill(direction, false);
084        int value = 1;
085        objectMap = new HashMap<Integer, E>();
086        for (E e : coll) {
087            objectMap.put(Integer.valueOf(value), e);
088            keys[value - 1] = value;
089            value++;
090        }
091        nextPermutation = new ArrayList<E>(coll);
092    }
093
094    /**
095     * Indicates if there are more permutation available.
096     * @return true if there are more permutations, otherwise false
097     */
098    public boolean hasNext() {
099        return nextPermutation != null;
100    }
101
102    /**
103     * Returns the next permutation of the input collection.
104     * @return a list of the permutator's elements representing a permutation
105     * @throws NoSuchElementException if there are no more permutations
106     */
107    public List<E> next() {
108        if (!hasNext()) {
109            throw new NoSuchElementException();
110        }
111
112        // find the largest mobile integer k
113        int indexOfLargestMobileInteger = -1;
114        int largestKey = -1;
115        for (int i = 0; i < keys.length; i++) {
116            if ((direction[i] && i < keys.length - 1 && keys[i] > keys[i + 1]) ||
117                (!direction[i] && i > 0 && keys[i] > keys[i - 1])) {
118                if (keys[i] > largestKey) {
119                    largestKey = keys[i];
120                    indexOfLargestMobileInteger = i;
121                }
122            }
123        }
124        if (largestKey == -1) {
125            List<E> toReturn = nextPermutation;
126            nextPermutation = null;
127            return toReturn;
128        }
129
130        // swap k and the adjacent integer it is looking at
131        final int offset = direction[indexOfLargestMobileInteger] ? 1 : -1;
132        final int tmpKey = keys[indexOfLargestMobileInteger];
133        keys[indexOfLargestMobileInteger] = keys[indexOfLargestMobileInteger + offset];
134        keys[indexOfLargestMobileInteger + offset] = tmpKey;
135        boolean tmpDirection = direction[indexOfLargestMobileInteger];
136        direction[indexOfLargestMobileInteger] = direction[indexOfLargestMobileInteger + offset];
137        direction[indexOfLargestMobileInteger + offset] = tmpDirection;
138
139        // reverse the direction of all integers larger than k and build the result
140        final List<E> nextP = new ArrayList<E>();
141        for (int i = 0; i < keys.length; i++) {
142            if (keys[i] > largestKey) {
143                direction[i] = !direction[i];
144            }
145            nextP.add(objectMap.get(Integer.valueOf(keys[i])));
146        }
147        final List<E> result = nextPermutation;
148        nextPermutation = nextP;
149        return result;
150    }
151
152    public void remove() {
153        throw new UnsupportedOperationException("remove() is not supported");
154    }
155
156}