1 /************************************************************** 2 * 3 * Licensed to the Apache Software Foundation (ASF) under one 4 * or more contributor license agreements. See the NOTICE file 5 * distributed with this work for additional information 6 * regarding copyright ownership. The ASF licenses this file 7 * to you under the Apache License, Version 2.0 (the 8 * "License"); you may not use this file except in compliance 9 * with the License. You may obtain a copy of the License at 10 * 11 * http://www.apache.org/licenses/LICENSE-2.0 12 * 13 * Unless required by applicable law or agreed to in writing, 14 * software distributed under the License is distributed on an 15 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY 16 * KIND, either express or implied. See the License for the 17 * specific language governing permissions and limitations 18 * under the License. 19 * 20 *************************************************************/ 21 22 package org.apache.openoffice.ooxml.schema.iterator; 23 24 25 /** Enumerate all permutations of a given array with elements of type T. 26 * The permutations are created in place, i.e. the array given to the constructor 27 * is modified as side effect of calling HasMore(). 28 * 29 * The algorithm is taken from "The Art of Computer Programming, Volume 4, 30 * Fasicle 2, by Donald E. Knuth" from section 7.2.1.2, Algorithm P. 31 */ 32 public class PermutationIterator<T> 33 { PermutationIterator( final T[] aItems)34 public PermutationIterator ( 35 final T[] aItems) 36 { 37 // Count the nodes. 38 mnItemCount = aItems.length; 39 40 // Set up three arrays, one with the actual nodes, one for the inversions 41 // and one for directions. 42 maItems = aItems; 43 maInversions = new int[mnItemCount]; 44 maDirections = new int[mnItemCount]; 45 for (int nIndex=0; nIndex<mnItemCount; ++nIndex) 46 { 47 maInversions[nIndex] = 0; 48 maDirections[nIndex] = 1; 49 } 50 51 mbHasMorePermutations = mnItemCount>0; 52 mbIsNextPermutationReady = true; 53 } 54 55 56 57 HasMore()58 public boolean HasMore () 59 { 60 if ( ! mbIsNextPermutationReady) 61 ProvideNextPermutation(); 62 return mbHasMorePermutations; 63 } 64 65 66 67 Next()68 public T[] Next() 69 { 70 assert(mbHasMorePermutations && mbIsNextPermutationReady); 71 mbIsNextPermutationReady = false; 72 return maItems; 73 } 74 75 76 77 ProvideNextPermutation()78 private void ProvideNextPermutation () 79 { 80 mbIsNextPermutationReady = true; 81 82 // Create the next permutation. 83 int nJ = mnItemCount; 84 int nS = 0; 85 86 while (true) 87 { 88 final int nQ = maInversions[nJ-1] + maDirections[nJ-1]; 89 if (nQ>=0 && nQ<nJ) 90 { 91 // Exchange j-cj+s and j-q+s 92 final int nIndexA = nJ-maInversions[nJ - 1]+nS - 1; 93 final int nIndexB = nJ-nQ+nS - 1; 94 final T aItem = maItems[nIndexA]; 95 maItems[nIndexA] = maItems[nIndexB]; 96 maItems[nIndexB] = aItem; 97 98 // cj=q 99 maInversions[nJ - 1] = nQ; 100 101 // Next permutation is ready. 102 break; 103 } 104 else 105 { 106 if (nQ==nJ) 107 { 108 // Increase s. 109 if (nJ == 1) 110 { 111 // All permutations generated. 112 mbHasMorePermutations = false; 113 break; 114 } 115 else 116 { 117 ++nS; 118 } 119 } 120 121 // Switch direction. 122 maDirections[nJ - 1] = -maDirections[nJ - 1]; 123 --nJ; 124 } 125 } 126 } 127 128 129 130 131 private final int mnItemCount; 132 private final T[] maItems; 133 private final int[] maInversions; 134 private final int[] maDirections; 135 private boolean mbIsNextPermutationReady; 136 private boolean mbHasMorePermutations; 137 } 138