Robust/src/Analysis/Scheduling/CombinationUtil.java

   1 package Analysis.Scheduling;
   2
   3 import java.util.Vector;
   4
   5 public class CombinationUtil {
   6   static CombinationUtil cu;
   7
   8   public CombinationUtil() {
   9   }
  10
  11   public static CombinationUtil allocateCombinationUtil() {
  12     if(cu == null) {
  13       cu = new CombinationUtil();
  14     }
  15     return cu;
  16   }
  17
  18   public static RootsGenerator allocateRootsGenerator(Vector<Vector<ScheduleNode>> snodevecs,
  19                                                       int rootNum) {
  20     return CombinationUtil.allocateCombinationUtil().new RootsGenerator(snodevecs, rootNum);
  21   }
  22
  23   public static CombineGenerator allocateCombineGenerator(Vector<Vector<ScheduleNode>> rootnodes,
  24                                                           Vector<Vector<ScheduleNode>> node2combine) {
  25     return CombinationUtil.allocateCombinationUtil().new CombineGenerator(rootnodes, node2combine);
  26   }
  27
  28   public class RootsGenerator {
  29     Vector<Vector<ScheduleNode>> sNodeVecs;
  30     Vector<Vector<ScheduleNode>> node2Combine;
  31     Vector<Vector<ScheduleNode>> rootNodes;
  32     int rootNum;
  33
  34     public RootsGenerator(Vector<Vector<ScheduleNode>> snodevecs, int rootNum) {
  35       this.sNodeVecs = snodevecs;
  36       this.rootNum = rootNum;
  37       this.node2Combine = null;
  38       this.rootNodes = null;
  39     }
  40
  41     public boolean nextGen() {
  42       boolean trial = false;
  43       if(this.rootNodes == null) {
  44         int num2choose = this.rootNum;
  45         this.rootNodes = new Vector<Vector<ScheduleNode>>();
  46         this.rootNodes.add(new Vector<ScheduleNode>());
  47         Vector<ScheduleNode> toadd = this.sNodeVecs.elementAt(0);
  48         for(int i = 0; i < toadd.size(); i++) {
  49           // should be only one element: startup object
  50           this.rootNodes.elementAt(0).add(toadd.elementAt(i));
  51           num2choose--;
  52         }
  53         int next = 1;
  54         trial = trial(num2choose, next);
  55         toadd = null;
  56       } else {
  57         if(this.rootNodes.size() == 1) {
  58           return false;
  59         }
  60         int next = this.rootNodes.lastElement().elementAt(0).getCid() + 1;
  61         int num2choose = 0;
  62         while(next == this.sNodeVecs.size()) {
  63           // backtrack
  64           num2choose = this.rootNodes.lastElement().size();
  65           this.rootNodes.removeElementAt(this.rootNodes.size() - 1);
  66           if(this.rootNodes.size() == 1) {
  67             // only startup object left, no more choices
  68             return false;
  69           }
  70           next = this.rootNodes.lastElement().elementAt(0).getCid() + 1;
  71         }
  72         num2choose++;
  73         // reduce one from the last one
  74         this.rootNodes.lastElement().removeElementAt(this.rootNodes.lastElement().size() - 1);
  75         if(this.rootNodes.lastElement().size() == 0) {
  76           this.rootNodes.removeElementAt(this.rootNodes.size() - 1);
  77         }
  78
  79         trial = trial(num2choose, next);
  80       }
  81       if(trial) {
  82         // left nodes are all to be combined
  83         this.node2Combine = new Vector<Vector<ScheduleNode>>();
  84         int next = 1;
  85         int index = 0;
  86         for(int i = 1; i < this.rootNodes.size(); i++) {
  87           int tmp = this.rootNodes.elementAt(i).elementAt(0).getCid();
  88           while(next < tmp) {
  89             Vector<ScheduleNode> toadd = this.sNodeVecs.elementAt(next);
  90             if(toadd != null) {
  91               this.node2Combine.add(new Vector<ScheduleNode>());
  92               for(index = 0; index < toadd.size(); index++) {
  93                 this.node2Combine.lastElement().add(toadd.elementAt(index));
  94               }
  95               toadd = null;
  96             } else {
  97               this.node2Combine.add(null);
  98             }
  99             next++;
 100           }
 101           Vector<ScheduleNode> toadd = this.sNodeVecs.elementAt(tmp);
 102           if(toadd.size() > this.rootNodes.elementAt(i).size()) {
 103             this.node2Combine.add(new Vector<ScheduleNode>());
 104             for(index = this.rootNodes.elementAt(i).size(); index < toadd.size(); index++) {
 105               this.node2Combine.lastElement().add(toadd.elementAt(index));
 106             }
 107           }
 108           toadd = null;
 109           next++;
 110         }
 111         while(next < this.sNodeVecs.size()) {
 112           Vector<ScheduleNode> toadd = this.sNodeVecs.elementAt(next);
 113           if(toadd != null) {
 114             this.node2Combine.add(new Vector<ScheduleNode>());
 115             for(index = 0; index < toadd.size(); index++) {
 116               this.node2Combine.lastElement().add(toadd.elementAt(index));
 117             }
 118             toadd = null;
 119           } else {
 120             this.node2Combine.add(null);
 121           }
 122           next++;
 123         }
 124       }
 125       return trial;
 126     }
 127
 128     private boolean trial(int num2choose, int next) {
 129       int index = 0;
 130       boolean first = true;
 131       while(num2choose > 0) {
 132         if(first) {
 133           if(next == this.sNodeVecs.size()) {
 134             // no more nodes available to add
 135             return false;
 136           }
 137         }
 138         if(this.sNodeVecs.elementAt(next) != null) {
 139           if(first) {
 140             this.rootNodes.add(new Vector<ScheduleNode>());
 141             first = false;
 142           }
 143           this.rootNodes.lastElement().add(this.sNodeVecs.elementAt(next).elementAt(index));
 144           num2choose--;
 145           index++;
 146           if(index == this.sNodeVecs.elementAt(next).size()) {
 147             index = 0;
 148             next++;
 149             first = true;
 150           }
 151         } else {
 152           next++;
 153           first = true;
 154         }
 155       }
 156       return true;
 157     }
 158
 159     public Vector<Vector<ScheduleNode>> getNode2Combine() {
 160       return node2Combine;
 161     }
 162
 163     public Vector<Vector<ScheduleNode>> getRootNodes() {
 164       return rootNodes;
 165     }
 166   }
 167
 168   public class Combine {
 169     public ScheduleNode node;
 170     public int root;
 171     public int index;
 172
 173     public Combine(ScheduleNode n) {
 174       this.node = n;
 175       this.root = -1;
 176       this.index = -1;
 177     }
 178   }
 179
 180   public class CombineGenerator {
 181     Vector<Vector<ScheduleNode>> rootNodes;
 182     Vector<Vector<int[]>> rootNStates;
 183     Vector<Vector<ScheduleNode>> node2Combine;
 184     Vector<Vector<Combine>> combine;
 185     int[] lastchoices;
 186     boolean first4choice;
 187
 188     public CombineGenerator(Vector<Vector<ScheduleNode>> rootnodes, Vector<Vector<ScheduleNode>> node2combine) {
 189       this.rootNodes = rootnodes;
 190       this.node2Combine = node2combine;
 191       this.rootNStates = new Vector<Vector<int[]>>();
 192       for(int i = 0; i < this.rootNodes.size(); i++) {
 193         this.rootNStates.add(new Vector<int[]>());
 194         for(int j = 0; j < this.rootNodes.elementAt(i).size(); j++) {
 195           this.rootNStates.elementAt(i).add(new int[this.node2Combine.size()]);
 196           for(int k = 0; k < this.node2Combine.size(); k++) {
 197             this.rootNStates.elementAt(i).elementAt(j)[k] = 0;
 198           }
 199         }
 200       }
 201       this.combine = new Vector<Vector<Combine>>();
 202       for(int i = 0; i < this.node2Combine.size(); i++) {
 203         if(this.node2Combine.elementAt(i) == null) {
 204           this.combine.add(null);
 205         } else {
 206           this.combine.add(new Vector<Combine>());
 207           for(int j = 0; j < this.node2Combine.elementAt(i).size(); j++) {
 208             this.combine.elementAt(i).add(new Combine(this.node2Combine.elementAt(i).elementAt(j)));
 209           }
 210         }
 211       }
 212       this.lastchoices = null;
 213       this.first4choice = false;
 214     }
 215
 216     public Vector<Vector<Combine>> getCombine() {
 217       return combine;
 218     }
 219
 220     public boolean nextGen() {
 221       boolean trial = false;
 222       if(this.lastchoices == null) {
 223         // first time
 224         this.lastchoices = new int[this.node2Combine.size()];
 225         for(int i = 0; i < this.lastchoices.length; i++) {
 226           this.lastchoices[i] = 0;
 227         }
 228         this.first4choice = true;
 229         trial = trial();
 230       } else {
 231         trial = trial();
 232         while(!trial) {
 233           // no more available combination under this choice
 234           // choose another choice
 235           int next = this.node2Combine.size() - 1;
 236           boolean iter = false;
 237           do {
 238             if(this.node2Combine.elementAt(next) != null) {
 239               this.lastchoices[next]++;
 240               if((this.lastchoices[next] == this.rootNodes.size() ||
 241                   (this.rootNodes.elementAt(this.lastchoices[next]).elementAt(0).getCid() >
 242                    this.node2Combine.elementAt(next).elementAt(0).getCid()))) {
 243                 // break the rule that a node can only be combined to nodes with smaller colorid.
 244                 // or no more buckets
 245                 // backtrack
 246                 next--;
 247                 iter = true;
 248               } else {
 249                 iter = false;
 250               }
 251             } else {
 252               next--;
 253               iter = true;
 254             }
 255           } while(iter && !(next < 0));
 256           if(next < 0) {
 257             return false;
 258           }
 259           for(next += 1; next < this.node2Combine.size(); next++) {
 260             this.lastchoices[next] = 0;
 261           }
 262           this.first4choice = true;
 263           trial = trial();
 264         }
 265       }
 266       return trial;
 267     }
 268
 269     private boolean trial() {
 270       boolean suc = false;
 271       if(this.first4choice) {
 272         // first time for each choice
 273         // put all the objects of one color into the first bucket indicated by the choice
 274         int next = 0;
 275         suc = firstexpand(next, this.first4choice);
 276         this.first4choice = false;
 277       } else {
 278         int next = this.node2Combine.size() - 1;
 279         int layer = 0;
 280         suc = innertrial(next, layer);
 281       }
 282       return suc;
 283     }
 284
 285     private boolean firstexpand(int next, boolean first) {
 286       for(int i = next; i < this.node2Combine.size(); i++) {
 287         if(this.node2Combine.elementAt(i) != null) {
 288           int choice = this.lastchoices[i];
 289           for(int j = 0; j < this.node2Combine.elementAt(i).size(); j++) {
 290             Combine tmp = this.combine.elementAt(i).elementAt(j);
 291             if(!first) {
 292               this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]--;
 293             }
 294             tmp.root = choice;
 295             tmp.index = 0;
 296             if(!first) {
 297               this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]++;
 298             }
 299           }
 300           if(first) {
 301             this.rootNStates.elementAt(choice).elementAt(0)[i] = this.node2Combine.elementAt(i).size();
 302             for(int j = 1; j < this.rootNodes.elementAt(choice).size(); j++) {
 303               this.rootNStates.elementAt(choice).elementAt(j)[i] = 0;
 304             }
 305           }
 306         }
 307       }
 308       return true;
 309     }
 310
 311     private boolean innertrial(int next, int layer) {
 312       if((this.combine.elementAt(next) == null) ||
 313          (this.combine.elementAt(next).size() < 2)) {
 314         // skip over empty buckets and bucket with only one obj ( make sure
 315         // at least one obj is existing in the chosen bucket)
 316         if(next - 1 < 0) {
 317           return false;
 318         } else {
 319           return innertrial(next - 1, ++layer);
 320         }
 321       }
 322       Combine tmp = this.combine.elementAt(next).lastElement();
 323       // try to move it backward
 324       int root = tmp.root;
 325       int index = tmp.index;
 326       index++;
 327       if(index == this.rootNodes.elementAt(root).size()) {
 328         // no more place in this color bucket
 329         index = 0;
 330         root++;
 331       } else if(this.rootNStates.elementAt(root).elementAt(index - 1)[next] <
 332                 this.rootNStates.elementAt(root).elementAt(index)[next] + 2) {
 333         // break the law of non-increase order inside one color bucket
 334         // try next bucket of another color
 335         index = 0;
 336         root++;
 337       }
 338       if(root == this.rootNodes.size()) {
 339         // no more bucket
 340         // backtrack
 341         root = tmp.root;
 342         index = tmp.index;
 343         int t = this.combine.elementAt(next).size() - 2;
 344         while(true) {
 345           while(!(t < 0)) {
 346             tmp = this.combine.elementAt(next).elementAt(t);
 347             if ((tmp.root != root) || (tmp.index != index)) {
 348               break;
 349             }
 350             t--;
 351           }
 352           if(t < 0) {
 353             // try the bucket in node2combine before
 354             if(next - 1 < 0) {
 355               return false;
 356             } else {
 357               return innertrial(next - 1, ++layer);
 358             }
 359           } else if(tmp.root != root) {
 360             if((tmp.root == this.lastchoices[next]) &&
 361                (this.rootNStates.elementAt(this.lastchoices[next]).elementAt(0)[next] == 1)) {
 362               // only 1 obj left in the chosen bucket
 363               // can not move this one
 364               // try the bucket in node2combine before
 365               if(next - 1 < 0) {
 366                 return false;
 367               } else {
 368                 return innertrial(next - 1, ++layer);
 369               }
 370             }
 371             this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]--;
 372             //tmp.root = root;
 373             int newroot = tmp.root + 1;
 374             tmp.root = newroot;
 375             tmp.index = 0;
 376             this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]++;
 377             // make all left things in this color bucket reset
 378             for(t++; t < this.combine.elementAt(next).size(); t++) {
 379               tmp = this.combine.elementAt(next).elementAt(t);
 380               this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]--;
 381               tmp.root = newroot;
 382               tmp.index = 0;
 383               this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]++;
 384             }
 385             if(layer != 0) {
 386               return firstexpand(next+1, this.first4choice);
 387             }
 388             return true;
 389           } else if(tmp.index != index) {
 390             if(this.rootNStates.elementAt(root).elementAt(tmp.index)[next] ==
 391                this.rootNStates.elementAt(root).elementAt(index)[next]) {
 392               // break the law of non-increase order inside one color bucket
 393               // go on search forward
 394               index = tmp.index;
 395             } else if(this.rootNStates.elementAt(root).elementAt(tmp.index)[next] <
 396                       this.rootNStates.elementAt(root).elementAt(index)[next] + 2) {
 397               // break the law of non-increase order inside one color bucket
 398               // and now they only differ by 1
 399               // propagate this difference to see if it can fix
 400               boolean suc = propagateOne(next, root, index, t, tmp);
 401               if(suc) {
 402                 return suc;
 403               } else {
 404                 // go on search forward
 405                 index = tmp.index;
 406               }
 407             } else {
 408               this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]--;
 409               int tmproot = tmp.root;
 410               int tmpindex = tmp.index;
 411               tmp.root = root;
 412               tmp.index = index;
 413               this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]++;
 414               int desroot = tmp.root;
 415               int desindex = tmp.index;
 416               // make all left things in this color bucket reset
 417               t++;
 418               boolean first = true;
 419               while(t < this.combine.elementAt(next).size()) {
 420                 int k = 0;
 421                 if(first) {
 422                   k = 1;
 423                   first = false;
 424                 }
 425                 for(; (k < this.rootNStates.elementAt(tmproot).elementAt(tmpindex)[next]) && (t < this.combine.elementAt(next).size()); t++) {
 426                   tmp = this.combine.elementAt(next).elementAt(t);
 427                   this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]--;
 428                   tmp.root = desroot;
 429                   tmp.index = desindex;
 430                   this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]++;
 431                 }
 432                 if(k == this.rootNStates.elementAt(tmproot).elementAt(tmpindex)[next]) {
 433                   desindex++;
 434                 }
 435               }
 436               if(layer != 0) {
 437                 return firstexpand(next+1, this.first4choice);
 438               }
 439               return true;
 440             }
 441           }
 442         }
 443       } else {
 444         if((tmp.root != this.lastchoices[next]) ||
 445            (this.rootNStates.elementAt(this.lastchoices[next]).elementAt(0)[next] > 1)) {
 446           this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]--;
 447           tmp.root = root;
 448           tmp.index = index;
 449           this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]++;
 450           if(layer != 0) {
 451             return firstexpand(next+1, this.first4choice);
 452           }
 453           return true;
 454         } else {
 455           // only 1 obj with the color next exist on the chosen bucket this time,
 456           // can not move it, try objs in forward color bucket
 457           if(next - 1 < 0) {
 458             return false;
 459           } else {
 460             return innertrial(next - 1, ++layer);
 461           }
 462         }
 463       }
 464     }
 465
 466     private boolean propagateOne(int next, int rooti, int indexi, int ti, Combine tmp) {
 467       int root = rooti;
 468       int index = indexi;
 469       int t = ti;
 470       int rootbk = tmp.root;
 471       int indexbk = tmp.index;
 472       this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]--;
 473       tmp.root = root;
 474       tmp.index = index;
 475       this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]++;
 476       t += 2;
 477       Combine tmpt = null;
 478       if(this.rootNStates.elementAt(root).elementAt(index - 1)[next] <
 479          this.rootNStates.elementAt(root).elementAt(index)[next]) {
 480         // need to continue propagate
 481         while(t < this.combine.elementAt(next).size()) {
 482           tmpt = this.combine.elementAt(next).elementAt(t);
 483           if ((tmpt.root != root) || (tmpt.index != index)) {
 484             break;
 485           }
 486           t++;
 487         }
 488         if(t == this.combine.elementAt(next).size()) {
 489           // last element of this color bucket
 490           if(index + 1 < this.rootNodes.elementAt(root).size()) {
 491             // there is available place inside the same color bucket
 492             Combine tmpbk = this.combine.elementAt(next).elementAt(t - 1);
 493             boolean suc = propagateOne(next, root, index + 1, t - 1, tmpbk);
 494             /*if(!suc) {
 495                 // fail, roll back
 496                 this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]--;
 497                 tmp.root = rootbk;
 498                 tmp.index = indexbk;
 499                 this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]++;
 500                }*/
 501             return suc;
 502           } else if(root+1 < this.rootNodes.size()) {           // check if there are another bucket
 503             // yes
 504             this.rootNStates.elementAt(tmpt.root).elementAt(tmpt.index)[next]--;
 505             tmpt.root = root + 1;
 506             tmpt.index = 0;
 507             this.rootNStates.elementAt(tmpt.root).elementAt(tmpt.index)[next]++;
 508             return firstexpand(next+1, this.first4choice);
 509           } else {
 510             // no, roll back
 511             this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]--;
 512             tmp.root = rootbk;
 513             tmp.index = indexbk;
 514             this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]++;
 515             return false;
 516           }
 517         } else if(tmpt.root != root) {
 518           Combine tmpbk = this.combine.elementAt(next).elementAt(t - 1);
 519           this.rootNStates.elementAt(tmpbk.root).elementAt(tmpbk.index)[next]--;
 520           tmpbk.root = tmpt.root;
 521           tmpbk.index = 0;
 522           this.rootNStates.elementAt(tmpbk.root).elementAt(tmpbk.index)[next]++;
 523           root = tmpt.root;
 524           index = tmpt.index;
 525           // make all left things in this color bucket reset
 526           for(t += 1; t < this.combine.elementAt(next).size(); t++) {
 527             tmpt = this.combine.elementAt(next).elementAt(t);
 528             this.rootNStates.elementAt(tmpt.root).elementAt(tmpt.index)[next]--;
 529             tmpt.root = root;
 530             tmpt.index = 0;
 531             this.rootNStates.elementAt(tmpt.root).elementAt(tmpt.index)[next]++;
 532           }
 533           return firstexpand(next+1, this.first4choice);
 534         } else if(tmpt.index != index) {
 535           Combine tmpbk = this.combine.elementAt(next).elementAt(t - 1);
 536           boolean suc = propagateOne(next, root, tmpt.index, t - 1, tmpbk);
 537           if(!suc) {
 538             // fail, roll back
 539             this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]--;
 540             tmp.root = rootbk;
 541             tmp.index = indexbk;
 542             this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]++;
 543           }
 544           return suc;
 545         }
 546         // won't reach here, only to avoid compiler's complain
 547         return true;
 548       } else {
 549         return true;
 550       }
 551     }
 552   }
 553 }