KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > jgrapht > experimental > permutation > CollectionPermutationIter


1 /* ==========================================
2  * JGraphT : a free Java graph-theory library
3  * ==========================================
4  *
5  * Project Info: http://jgrapht.sourceforge.net/
6  * Project Creator: Barak Naveh (http://sourceforge.net/users/barak_naveh)
7  *
8  * (C) Copyright 2003-2006, by Barak Naveh and Contributors.
9  *
10  * This library is free software; you can redistribute it and/or modify it
11  * under the terms of the GNU Lesser General Public License as published by
12  * the Free Software Foundation; either version 2.1 of the License, or
13  * (at your option) any later version.
14  *
15  * This library is distributed in the hope that it will be useful, but
16  * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
17  * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
18  * License for more details.
19  *
20  * You should have received a copy of the GNU Lesser General Public License
21  * along with this library; if not, write to the Free Software Foundation,
22  * Inc.,
23  * 59 Temple Place, Suite 330, Boston, MA 02111-1307, USA.
24  */
25 /* -----------------
26  * CollectionPermutationIter.java
27  * -----------------
28  * (C) Copyright 2005-2006, by Assaf Lehr and Contributors.
29  *
30  * Original Author: Assaf Lehr
31  * Contributor(s): -
32  *
33  * $Id: CollectionPermutationIter.java 504 2006-07-03 02:37:26Z perfecthash $
34  *
35  * Changes
36  * -------
37  */
38 package org.jgrapht.experimental.permutation;
39
40 import java.util.*;
41
42 import org.jgrapht.util.*;
43
44
45 /**
46  * Given a container with elements (Collection,Enumeration,array) defines a
47  * permutation iterator which returns, on each iteration, a differnt permutation
48  * of the source container. You may choose a different container
49  * type(Collection/Array/etc) for each next call. It will continue as if they
50  * were the same iterator.
51  *
52  * @author Assaf
53  * @since May 20, 2005
54  */
55 public class CollectionPermutationIter<E>
56 {
57
58     //~ Instance fields -------------------------------------------------------
59
60     private ArrayPermutationsIter permOrder;
61     private List<E> sourceArray;
62
63     /**
64      * change everry calculation.can be retrieved publicly
65      */
66     private int [] currPermutationArray;
67
68     //~ Constructors ----------------------------------------------------------
69
70     /**
71      * Note: the Set interface does not guarantee iteration order. This method
72      * iterates on the set to get the initial order and after that the data will
73      * be saved internally in another (ordered) container. So, remeber that the
74      * Initial order can be different from the objectSet.toString() method. If
75      * you want it to be the same, use a LinkedHashSet , or use the array
76      * constructor.
77      *
78      * @param objectsSet
79      */
80     public CollectionPermutationIter(Set<E> objectsSet)
81     {
82         this(
83             new ArrayList<E>(objectsSet),
84             new IntegerPermutationIter(objectsSet.size()));
85     }
86
87     /**
88      * Uses a permArray like [1,1,1,2] where some of the permutations are not
89      * relevant. Here there will be 4 permutations (only the '2' position is
90      * important)
91      *
92      * @param objectsArray
93      * @param permuter
94      */
95     public CollectionPermutationIter(List<E> objectsArray)
96     {
97         this(
98             objectsArray,
99             new IntegerPermutationIter(objectsArray.size()));
100     }
101
102     public CollectionPermutationIter(
103         List<E> objectsArray,
104         ArrayPermutationsIter permuter)
105     {
106         this.permOrder = permuter;
107         this.sourceArray = objectsArray;
108     }
109
110     //~ Methods ---------------------------------------------------------------
111
112     public boolean hasNext()
113     {
114         return this.permOrder.hasNextPermutaions();
115     }
116
117     /**
118      * On first call, returns the source as an array; on any other call
119      * thereafter, a new permutation
120      *
121      * @return null if we overflowed! the array otherwise
122      */
123     public List<E> getNextArray()
124     {
125         List<E> permutationResult; // will hold the array result
126 if (this.permOrder.hasNextPermutaions()) {
127             this.currPermutationArray = this.permOrder.nextPermutation();
128             permutationResult = applyPermutation();
129         } else {
130             permutationResult = null;
131         }
132
133         return permutationResult;
134     }
135
136     private List<E> applyPermutation()
137     {
138         ArrayList<E> output = new ArrayList<E>(sourceArray);
139
140         // Example : this.sourceArray = ["A","B","C","D"]
141 // perOrder: = [ 1 , 0 , 3 , 2 ]
142 // result : = ["B","A","D","C"]
143 for (int i = 0; i < output.size(); i++) {
144             output.set(
145                 i,
146                 this.sourceArray.get(this.currPermutationArray[i]));
147         }
148         return output;
149     }
150
151     /**
152      * Wrap result to a Set.
153      *
154      * @return null if we overflowed! the set otherwise
155      */
156     public Set<E> getNextSet()
157     {
158         List<E> result = getNextArray();
159         if (result == null) {
160             return null;
161         } else // wrap in a SET
162 {
163             Set<E> resultSet = new LinkedHashSet<E>(result);
164             return resultSet;
165         }
166     }
167
168     public int [] getCurrentPermutationArray()
169     {
170         return this.currPermutationArray;
171     }
172
173     public String JavaDoc toString()
174     {
175         StringBuffer JavaDoc sb = new StringBuffer JavaDoc();
176         sb.append("Permutation int[]=");
177         sb.append(ArrayUtil.toString(getCurrentPermutationArray()));
178
179         List<E> permutationResult = applyPermutation();
180         sb.append("\nPermutationSet Source Object[]=");
181         sb.append(this.sourceArray.toString());
182         sb.append("\nPermutationSet Result Object[]=");
183         sb.append(permutationResult.toString());
184         return sb.toString();
185     }
186 }
187
Popular Tags