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