001: // Copyright (c) 2002 Cunningham & Cunningham, Inc.
002: // Released under the terms of the GNU General Public License version 2 or later.
003:
004: package eg;
005:
006: import fit.*;
007: import java.util.*;
008: import java.io.File;
009:
010: public class AllPairs extends AllCombinations {
011:
012: public int rank;
013: public int steps = 0;
014: public Map toItem = new HashMap();
015: public List vars = new ArrayList();
016: public SortedSet pairs = new TreeSet();
017:
018: protected void combinations() {
019: populate();
020: generate();
021: }
022:
023: // Populate /////////////////////////////////
024:
025: protected void populate() {
026: doAllVars();
027: doAllVarPairs();
028: }
029:
030: protected void doAllVars() {
031: rank = 0;
032: for (int i = 0; i < lists.size(); i++) {
033: List files = (List) lists.get(i);
034: Var var = new Var(i, files);
035: vars.add(var);
036: doAllItems(var, files);
037: }
038: }
039:
040: protected void doAllItems(Var var, List files) {
041: for (int i = 0; i < files.size(); i++) {
042: Item item = new Item(var, i, rank++);
043: toItem.put(((File) files.get(i)).getName(), item);
044: var.items.add(item);
045: }
046: }
047:
048: protected void doAllVarPairs() {
049: for (int i = 0; i < vars.size(); i++) {
050: for (int j = i + 1; j < vars.size(); j++) {
051: doAllItemPairs((Var) vars.get(i), (Var) vars.get(j));
052: }
053: }
054: }
055:
056: protected void doAllItemPairs(Var vl, Var vr) {
057: for (int l = 0; l < vl.size(); l++) {
058: for (int r = 0; r < vr.size(); r++) {
059: pairs.add(new Pair(vl.get(l), vr.get(r)));
060: }
061: }
062: }
063:
064: // Generate /////////////////////////////////
065:
066: protected void generate() {
067: while (((Pair) pairs.first()).used == 0) {
068: emit(nextCase());
069: }
070: }
071:
072: private Item[] nextCase() {
073: Item slug[] = new Item[vars.size()];
074: while (!isFull(slug)) {
075: Pair p = nextFit(slug);
076: fill(slug, p);
077: }
078: return slug;
079: }
080:
081: protected void fill(Item[] slug, Pair pair) {
082: slug[pair.left.var.index] = pair.left;
083: slug[pair.right.var.index] = pair.right;
084: pair.used++;
085: pairs.add(pair);
086: }
087:
088: protected boolean isFull(Item[] slug) {
089: for (int i = 0; i < slug.length; i++) {
090: if (slug[i] == null) {
091: return false;
092: }
093: }
094: return true;
095: }
096:
097: protected Pair nextFit(Item[] slug) {
098: List hold = new ArrayList();
099: Pair pair;
100: while (!(pair = nextPair()).isFit(slug)) {
101: hold.add(pair);
102: }
103: pairs.addAll(hold);
104: return pair;
105: }
106:
107: protected Pair nextPair() {
108: Pair first = (Pair) pairs.first();
109: pairs.remove(first);
110: steps++;
111: return first;
112: }
113:
114: protected void emit(Item[] slug) {
115: List combination = new ArrayList();
116: for (int i = 0; i < slug.length; i++) {
117: combination.add(slug[i].file());
118: }
119: doCase(combination);
120: }
121:
122: // Helper Classes ///////////////////////////
123:
124: public class Var {
125: List files;
126: int index;
127: List items = new ArrayList();
128:
129: Var(int index, List files) {
130: this .index = index;
131: this .files = files;
132: }
133:
134: int size() {
135: return items.size();
136: }
137:
138: Item get(int index) {
139: return (Item) items.get(index);
140: }
141: }
142:
143: public class Item {
144: Var var;
145: int index;
146: int rank;
147:
148: Item(Var var, int i, int n) {
149: this .var = var;
150: index = i;
151: rank = n;
152: }
153:
154: File file() {
155: return (File) var.files.get(index);
156: }
157:
158: public String toString() {
159: return file().getName();
160: }
161:
162: boolean isFit(Item[] slug) {
163: return slug[var.index] == null || slug[var.index] == this ;
164: }
165: }
166:
167: public class Pair implements Comparable {
168: public Item left, right;
169: public int used = 0;
170:
171: Pair(Item left, Item right) {
172: this .left = left;
173: this .right = right;
174: }
175:
176: public String toString() {
177: return left + "-" + right + " (" + used + ")";
178: }
179:
180: boolean isFit(Item[] slug) {
181: return left.isFit(slug) && right.isFit(slug);
182: }
183:
184: public int rank() {
185: return rank * (rank * used + left.rank) + right.rank;
186: }
187:
188: public int compareTo(Object o) {
189: return rank() - ((Pair) o).rank();
190: }
191: }
192:
193: // Self Test Classes ////////////////////////
194:
195: public static AllPairs fut;
196: public static List cases;
197:
198: public static class Setup extends Fixture {
199:
200: public void doTable(Parse table) {
201: fut = new AllPairs();
202: cases = new ArrayList();
203: super .doTable(table);
204: fut.populate();
205: }
206:
207: public void doCell(Parse cell, int i) {
208: if (!cell.text().equals("")) {
209: while (fut.lists.size() <= i) {
210: fut.lists.add(new ArrayList());
211: }
212: ((List) fut.lists.get(i)).add(new File(cell.text()));
213: right(cell);
214: }
215: }
216: }
217:
218: public static class Cases extends RowFixture {
219: public static class Case {
220: public int number;
221: public Item[] items;
222:
223: Case(int n, Item[] i) {
224: number = n;
225: items = i;
226: }
227: }
228:
229: public Object[] query() {
230: while (((Pair) fut.pairs.first()).used == 0) {
231: cases.add(fut.nextCase());
232: }
233: List result = new ArrayList();
234: for (int i = 0; i < cases.size(); i++) {
235: result.add(new Case(i + 1, (Item[]) cases.get(i)));
236: }
237: return result.toArray();
238: }
239:
240: public Class getTargetClass() {
241: return Case.class;
242: }
243: }
244:
245: public static class Pairs extends RowFixture {
246: public Object[] query() {
247: return fut.pairs.toArray();
248: }
249:
250: public Class getTargetClass() {
251: return Pair.class;
252: }
253:
254: public Object parse(String s, Class type) throws Exception {
255: if (s.equals("null")) {
256: return null;
257: }
258: if (type.equals(Item.class)) {
259: return fut.toItem.get(s);
260: }
261: return super .parse(s, type);
262: }
263: }
264:
265: public static class Step extends ColumnFixture {
266: static Pair next;
267: static Item slug[] = new Item[3];
268: static List hold = new ArrayList();
269:
270: public String next() {
271: next = fut.nextPair();
272: hold.add(next);
273: return next.toString();
274: }
275:
276: public String nextFit() {
277: next = fut.nextFit(slug);
278: hold.add(next);
279: return next.toString();
280: }
281:
282: public int rank() {
283: return next.rank();
284: }
285:
286: public boolean isFit() {
287: boolean isFit = next.isFit(slug);
288: if (isFit) {
289: fut.fill(slug, next);
290: fut.pairs.addAll(hold);
291: hold = new ArrayList();
292: }
293: return isFit;
294: }
295:
296: public int hold() {
297: return hold.size();
298: }
299:
300: public Item[] slug() {
301: return slug;
302: }
303:
304: public boolean isFull() {
305: boolean result = fut.isFull(slug);
306: if (result) {
307: cases.add(slug);
308: slug = new Item[3];
309: }
310: return result;
311: }
312:
313: public Object parse(String s, Class type) throws Exception {
314: if (s.equals("null")) {
315: return null;
316: }
317: if (type.equals(Item.class)) {
318: return fut.toItem.get(s);
319: }
320: return super .parse(s, type);
321: }
322: }
323:
324: public static class Stats extends ColumnFixture {
325: public int[] items;
326: public int pairs;
327: public int steps;
328: public long msec;
329:
330: public int cases() {
331: AllPairs ap = new AllPairs();
332: setup(ap);
333: ap.populate();
334: return generate(ap);
335: }
336:
337: void setup(AllPairs ap) {
338: int name = 0;
339: for (int i = 0; i < items.length; i++) {
340: List l = new ArrayList();
341: for (int j = 0; j < items[i]; j++) {
342: l.add(new File(Integer.toString(name++)));
343: }
344: ap.lists.add(l);
345: }
346: }
347:
348: int generate(AllPairs ap) {
349: int cases = 0;
350: msec = System.currentTimeMillis();
351: while (((Pair) ap.pairs.first()).used == 0) {
352: ap.nextCase();
353: cases++;
354: }
355: pairs = ap.pairs.size();
356: steps = ap.steps;
357: msec = System.currentTimeMillis() - msec;
358: return cases;
359: }
360: }
361: }
|