1 package Analysis.Scheduling;
3 import java.util.Vector;
5 public class CombinationUtil {
6 static CombinationUtil cu;
8 public CombinationUtil() {
11 public static CombinationUtil allocateCombinationUtil() {
13 cu = new CombinationUtil();
18 public static RootsGenerator allocateRootsGenerator(Vector<Vector<ScheduleNode>> snodevecs, int rootNum) {
19 return CombinationUtil.allocateCombinationUtil().new RootsGenerator(snodevecs, rootNum);
22 public static CombineGenerator allocateCombineGenerator(Vector<Vector<ScheduleNode>> rootnodes, Vector<Vector<ScheduleNode>> node2combine) {
23 return CombinationUtil.allocateCombinationUtil().new CombineGenerator(rootnodes, node2combine);
26 public class RootsGenerator {
27 Vector<Vector<ScheduleNode>> sNodeVecs;
28 Vector<Vector<ScheduleNode>> node2Combine;
29 Vector<Vector<ScheduleNode>> rootNodes;
32 public RootsGenerator(Vector<Vector<ScheduleNode>> snodevecs, int rootNum) {
33 this.sNodeVecs = snodevecs;
34 this.rootNum = rootNum;
35 this.node2Combine = null;
36 this.rootNodes = null;
39 public boolean nextGen() {
40 boolean trial = false;
41 if(this.rootNodes == null) {
42 int num2choose = this.rootNum;
43 this.rootNodes = new Vector<Vector<ScheduleNode>>();
44 this.rootNodes.add(new Vector<ScheduleNode>());
45 Vector<ScheduleNode> toadd = this.sNodeVecs.elementAt(0);
46 for(int i = 0; i < toadd.size(); i++) {
47 // should be only one element: startup object
48 this.rootNodes.elementAt(0).add(toadd.elementAt(i));
52 trial = trial(num2choose, next);
54 if(this.rootNodes.size() == 1) {
57 int next = this.rootNodes.lastElement().elementAt(0).getCid() + 1;
59 while(next == this.sNodeVecs.size()) {
61 num2choose = this.rootNodes.lastElement().size();
62 this.rootNodes.removeElementAt(this.rootNodes.size() - 1);
63 if(this.rootNodes.size() == 1) {
64 // only startup object left, no more choices
67 next = this.rootNodes.lastElement().elementAt(0).getCid() + 1;
70 // reduce one from the last one
71 this.rootNodes.lastElement().removeElementAt(this.rootNodes.lastElement().size() - 1);
72 if(this.rootNodes.lastElement().size() == 0) {
73 this.rootNodes.removeElementAt(this.rootNodes.size() - 1);
76 trial = trial(num2choose, next);
79 // left nodes are all to be combined
80 this.node2Combine = new Vector<Vector<ScheduleNode>>();
83 for(int i = 1; i < this.rootNodes.size(); i++) {
84 int tmp = this.rootNodes.elementAt(i).elementAt(0).getCid();
86 Vector<ScheduleNode> toadd = this.sNodeVecs.elementAt(next);
88 this.node2Combine.add(new Vector<ScheduleNode>());
89 for(index = 0; index < toadd.size(); index++) {
90 this.node2Combine.lastElement().add(toadd.elementAt(index));
93 this.node2Combine.add(null);
97 Vector<ScheduleNode> toadd = this.sNodeVecs.elementAt(tmp);
98 if(toadd.size() > this.rootNodes.elementAt(i).size()) {
99 this.node2Combine.add(new Vector<ScheduleNode>());
100 for(index = this.rootNodes.elementAt(i).size(); index < toadd.size(); index++) {
101 this.node2Combine.lastElement().add(toadd.elementAt(index));
106 while(next < this.sNodeVecs.size()) {
107 Vector<ScheduleNode> toadd = this.sNodeVecs.elementAt(next);
109 this.node2Combine.add(new Vector<ScheduleNode>());
110 for(index = 0; index < toadd.size(); index++) {
111 this.node2Combine.lastElement().add(toadd.elementAt(index));
114 this.node2Combine.add(null);
122 private boolean trial(int num2choose, int next) {
124 boolean first = true;
125 while(num2choose > 0) {
127 if(next == this.sNodeVecs.size()) {
128 // no more nodes available to add
132 if(this.sNodeVecs.elementAt(next) != null) {
134 this.rootNodes.add(new Vector<ScheduleNode>());
137 this.rootNodes.lastElement().add(this.sNodeVecs.elementAt(next).elementAt(index));
140 if(index == this.sNodeVecs.elementAt(next).size()) {
153 public Vector<Vector<ScheduleNode>> getNode2Combine() {
157 public Vector<Vector<ScheduleNode>> getRootNodes() {
162 public class Combine {
163 public ScheduleNode node;
167 public Combine(ScheduleNode n) {
174 public class CombineGenerator {
175 Vector<Vector<ScheduleNode>> rootNodes;
176 Vector<Vector<int[]>> rootNStates;
177 Vector<Vector<ScheduleNode>> node2Combine;
178 Vector<Vector<Combine>> combine;
180 boolean first4choice;
182 public CombineGenerator(Vector<Vector<ScheduleNode>> rootnodes, Vector<Vector<ScheduleNode>> node2combine) {
183 this.rootNodes = rootnodes;
184 this.node2Combine = node2combine;
185 this.rootNStates = new Vector<Vector<int[]>>();
186 for(int i = 0; i < this.rootNodes.size(); i++) {
187 this.rootNStates.add(new Vector<int[]>());
188 for(int j = 0; j < this.rootNodes.elementAt(i).size(); j++) {
189 this.rootNStates.elementAt(i).add(new int[this.node2Combine.size()]);
190 for(int k = 0; k < this.node2Combine.size(); k++) {
191 this.rootNStates.elementAt(i).elementAt(j)[k] = 0;
195 this.combine = new Vector<Vector<Combine>>();
196 for(int i = 0; i < this.node2Combine.size(); i++) {
197 if(this.node2Combine.elementAt(i) == null) {
198 this.combine.add(null);
200 this.combine.add(new Vector<Combine>());
201 for(int j = 0; j < this.node2Combine.elementAt(i).size(); j++) {
202 this.combine.elementAt(i).add(new Combine(this.node2Combine.elementAt(i).elementAt(j)));
206 this.lastchoices = null;
207 this.first4choice = false;
210 public Vector<Vector<Combine>> getCombine() {
214 public boolean nextGen() {
215 boolean trial = false;
216 if(this.lastchoices == null) {
218 this.lastchoices = new int[this.node2Combine.size()];
219 for(int i = 0; i < this.lastchoices.length; i++) {
220 this.lastchoices[i] = 0;
222 this.first4choice = true;
227 // no more available combination under this choice
228 // choose another choice
229 int next = this.node2Combine.size() - 1;
230 boolean iter = false;
232 if(this.node2Combine.elementAt(next) != null) {
233 this.lastchoices[next]++;
234 if((this.lastchoices[next] == this.rootNodes.size() ||
235 (this.rootNodes.elementAt(this.lastchoices[next]).elementAt(0).getCid() >
236 this.node2Combine.elementAt(next).elementAt(0).getCid()))){
237 // break the rule that a node can only be combined to nodes with smaller colorid.
238 // or no more buckets
249 }while(iter && !(next < 0));
253 for(next += 1; next < this.node2Combine.size(); next++) {
254 this.lastchoices[next] = 0;
256 this.first4choice = true;
263 private boolean trial() {
265 if(this.first4choice) {
266 // first time for each choice
267 // put all the objects of one color into the first bucket indicated by the choice
269 suc = firstexpand(next, this.first4choice);
270 this.first4choice = false;
272 int next = this.node2Combine.size() - 1;
274 suc = innertrial(next, layer);
279 private boolean firstexpand(int next, boolean first) {
280 for(int i = next; i < this.node2Combine.size(); i++) {
281 if(this.node2Combine.elementAt(i) != null) {
282 int choice = this.lastchoices[i];
283 for(int j = 0; j < this.node2Combine.elementAt(i).size(); j++) {
284 Combine tmp = this.combine.elementAt(i).elementAt(j);
286 this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]--;
291 this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]++;
295 this.rootNStates.elementAt(choice).elementAt(0)[i] = this.node2Combine.elementAt(i).size();
296 for(int j = 1; j < this.rootNodes.elementAt(choice).size(); j++) {
297 this.rootNStates.elementAt(choice).elementAt(j)[i] = 0;
305 private boolean innertrial(int next, int layer) {
306 if((this.combine.elementAt(next) == null) ||
307 (this.combine.elementAt(next).size() < 2)) {
308 // skip over empty buckets and bucket with only one obj ( make sure
309 // at least one obj is existing in the chosen bucket)
313 return innertrial(next - 1, ++layer);
316 Combine tmp = this.combine.elementAt(next).lastElement();
317 // try to move it backward
319 int index = tmp.index;
321 if(index == this.rootNodes.elementAt(root).size()) {
322 // no more place in this color bucket
325 }else if(this.rootNStates.elementAt(root).elementAt(index - 1)[next] <
326 this.rootNStates.elementAt(root).elementAt(index)[next] + 2) {
327 // break the law of non-increase order inside one color bucket
328 // try next bucket of another color
332 if(root == this.rootNodes.size()) {
337 int t = this.combine.elementAt(next).size() - 2;
340 tmp = this.combine.elementAt(next).elementAt(t);
341 if ((tmp.root != root) || (tmp.index != index)) {
347 // try the bucket in node2combine before
351 return innertrial(next - 1, ++layer);
353 } else if(tmp.root != root) {
354 if((tmp.root == this.lastchoices[next]) &&
355 (this.rootNStates.elementAt(this.lastchoices[next]).elementAt(0)[next] == 1)) {
356 // only 1 obj left in the chosen bucket
357 // can not move this one
358 // try the bucket in node2combine before
362 return innertrial(next - 1, ++layer);
365 this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]--;
367 int newroot = tmp.root + 1;
370 this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]++;
371 // make all left things in this color bucket reset
372 for(t++; t < this.combine.elementAt(next).size(); t++) {
373 tmp = this.combine.elementAt(next).elementAt(t);
374 this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]--;
377 this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]++;
380 return firstexpand(next+1, this.first4choice);
383 } else if(tmp.index != index) {
384 if(this.rootNStates.elementAt(root).elementAt(tmp.index)[next] ==
385 this.rootNStates.elementAt(root).elementAt(index)[next]) {
386 // break the law of non-increase order inside one color bucket
387 // go on search forward
389 } else if(this.rootNStates.elementAt(root).elementAt(tmp.index)[next] <
390 this.rootNStates.elementAt(root).elementAt(index)[next] + 2) {
391 // break the law of non-increase order inside one color bucket
392 // and now they only differ by 1
393 // propagate this difference to see if it can fix
394 boolean suc = propagateOne(next, root, index, t, tmp);
398 // go on search forward
402 this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]--;
403 int tmproot = tmp.root;
404 int tmpindex = tmp.index;
407 this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]++;
408 int desroot = tmp.root;
409 int desindex = tmp.index;
410 // make all left things in this color bucket reset
412 boolean first = true;
413 while(t < this.combine.elementAt(next).size()) {
419 for(; (k < this.rootNStates.elementAt(tmproot).elementAt(tmpindex)[next]) && (t < this.combine.elementAt(next).size()); t++) {
420 tmp = this.combine.elementAt(next).elementAt(t);
421 this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]--;
423 tmp.index = desindex;
424 this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]++;
426 if(k == this.rootNStates.elementAt(tmproot).elementAt(tmpindex)[next]) {
431 return firstexpand(next+1, this.first4choice);
438 if((tmp.root != this.lastchoices[next]) ||
439 (this.rootNStates.elementAt(this.lastchoices[next]).elementAt(0)[next] > 1)) {
440 this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]--;
443 this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]++;
445 return firstexpand(next+1, this.first4choice);
449 // only 1 obj with the color next exist on the chosen bucket this time,
450 // can not move it, try objs in forward color bucket
454 return innertrial(next - 1, ++layer);
460 private boolean propagateOne(int next, int rooti, int indexi, int ti, Combine tmp) {
464 int rootbk = tmp.root;
465 int indexbk = tmp.index;
466 this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]--;
469 this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]++;
472 if(this.rootNStates.elementAt(root).elementAt(index - 1)[next] <
473 this.rootNStates.elementAt(root).elementAt(index)[next]) {
474 // need to continue propagate
475 while(t < this.combine.elementAt(next).size()) {
476 tmpt = this.combine.elementAt(next).elementAt(t);
477 if ((tmpt.root != root) || (tmpt.index != index)) {
482 if(t == this.combine.elementAt(next).size()) {
483 // last element of this color bucket
484 if(index + 1 < this.rootNodes.elementAt(root).size()) {
485 // there is available place inside the same color bucket
486 Combine tmpbk = this.combine.elementAt(next).elementAt(t - 1);
487 boolean suc = propagateOne(next, root, index + 1, t - 1, tmpbk);
490 this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]--;
493 this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]++;
496 } else if(root+1 < this.rootNodes.size()) { // check if there are another bucket
498 this.rootNStates.elementAt(tmpt.root).elementAt(tmpt.index)[next]--;
499 tmpt.root = root + 1;
501 this.rootNStates.elementAt(tmpt.root).elementAt(tmpt.index)[next]++;
502 return firstexpand(next+1, this.first4choice);
505 this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]--;
508 this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]++;
511 } else if(tmpt.root != root) {
512 Combine tmpbk = this.combine.elementAt(next).elementAt(t - 1);
513 this.rootNStates.elementAt(tmpbk.root).elementAt(tmpbk.index)[next]--;
514 tmpbk.root = tmpt.root;
516 this.rootNStates.elementAt(tmpbk.root).elementAt(tmpbk.index)[next]++;
519 // make all left things in this color bucket reset
520 for(t += 1; t < this.combine.elementAt(next).size(); t++) {
521 tmpt = this.combine.elementAt(next).elementAt(t);
522 this.rootNStates.elementAt(tmpt.root).elementAt(tmpt.index)[next]--;
525 this.rootNStates.elementAt(tmpt.root).elementAt(tmpt.index)[next]++;
527 return firstexpand(next+1, this.first4choice);
528 } else if(tmpt.index != index) {
529 Combine tmpbk = this.combine.elementAt(next).elementAt(t - 1);
530 boolean suc = propagateOne(next, root, tmpt.index, t - 1, tmpbk);
533 this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]--;
536 this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]++;
540 // won't reach here, only to avoid compiler's complain