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