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, int rootNum) {
  19     return CombinationUtil.allocateCombinationUtil().new RootsGenerator(snodevecs, rootNum);
  20   }
  21
  22   public static CombineGenerator allocateCombineGenerator(Vector<Vector<ScheduleNode>> rootnodes, Vector<Vector<ScheduleNode>> node2combine) {
  23     return CombinationUtil.allocateCombinationUtil().new CombineGenerator(rootnodes, node2combine);
  24   }
  25
  26   public class RootsGenerator {
  27     Vector<Vector<ScheduleNode>> sNodeVecs;
  28     Vector<Vector<ScheduleNode>> node2Combine;
  29     Vector<Vector<ScheduleNode>> rootNodes;
  30     int rootNum;
  31
  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;
  37     }
  38
  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));
  49           num2choose--;
  50         }
  51         int next = 1;
  52         trial = trial(num2choose, next);
  53       } else {
  54         if(this.rootNodes.size() == 1) {
  55           return false;
  56         }
  57         int next = this.rootNodes.lastElement().elementAt(0).getCid() + 1;
  58         int num2choose = 0;
  59         while(next == this.sNodeVecs.size()) {
  60           // backtrack
  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
  65             return false;
  66           }
  67           next = this.rootNodes.lastElement().elementAt(0).getCid() + 1;
  68         }
  69         num2choose++;
  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);
  74         }
  75
  76         trial = trial(num2choose, next);
  77       }
  78       if(trial) {
  79         // left nodes are all to be combined
  80         this.node2Combine = new Vector<Vector<ScheduleNode>>();
  81         int next = 1;
  82         int index = 0;
  83         for(int i = 1; i < this.rootNodes.size(); i++) {
  84           int tmp = this.rootNodes.elementAt(i).elementAt(0).getCid();
  85           while(next < tmp) {
  86             Vector<ScheduleNode> toadd = this.sNodeVecs.elementAt(next);
  87             if(toadd != null) {
  88               this.node2Combine.add(new Vector<ScheduleNode>());
  89               for(index = 0; index < toadd.size(); index++) {
  90                 this.node2Combine.lastElement().add(toadd.elementAt(index));
  91               }
  92             } else {
  93               this.node2Combine.add(null);
  94             }
  95             next++;
  96           }
  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));
 102             }
 103           }
 104           next++;
 105         }
 106         while(next < this.sNodeVecs.size()) {
 107           Vector<ScheduleNode> toadd = this.sNodeVecs.elementAt(next);
 108           if(toadd != null) {
 109             this.node2Combine.add(new Vector<ScheduleNode>());
 110             for(index = 0; index < toadd.size(); index++) {
 111               this.node2Combine.lastElement().add(toadd.elementAt(index));
 112             }
 113           } else {
 114             this.node2Combine.add(null);
 115           }
 116           next++;
 117         }
 118       }
 119       return trial;
 120     }
 121
 122     private boolean trial(int num2choose, int next) {
 123       int index = 0;
 124       boolean first = true;
 125       while(num2choose > 0) {
 126         if(first) {
 127           if(next == this.sNodeVecs.size()) {
 128             // no more nodes available to add
 129             return false;
 130           }
 131         }
 132         if(this.sNodeVecs.elementAt(next) != null) {
 133           if(first) {
 134             this.rootNodes.add(new Vector<ScheduleNode>());
 135             first = false;
 136           }
 137           this.rootNodes.lastElement().add(this.sNodeVecs.elementAt(next).elementAt(index));
 138           num2choose--;
 139           index++;
 140           if(index == this.sNodeVecs.elementAt(next).size()) {
 141             index = 0;
 142             next++;
 143             first = true;
 144           }
 145         } else {
 146           next++;
 147           first = true;
 148         }
 149       }
 150       return true;
 151     }
 152
 153     public Vector<Vector<ScheduleNode>> getNode2Combine() {
 154       return node2Combine;
 155     }
 156
 157     public Vector<Vector<ScheduleNode>> getRootNodes() {
 158       return rootNodes;
 159     }
 160   }
 161
 162   public class Combine {
 163     public ScheduleNode node;
 164     public int root;
 165     public int index;
 166
 167     public Combine(ScheduleNode n) {
 168       this.node = n;
 169       this.root = -1;
 170       this.index = -1;
 171     }
 172   }
 173
 174   public class CombineGenerator {
 175     Vector<Vector<ScheduleNode>> rootNodes;
 176     Vector<Vector<int[]>> rootNStates;
 177     Vector<Vector<ScheduleNode>> node2Combine;
 178     Vector<Vector<Combine>> combine;
 179     int[] lastchoices;
 180     boolean first4choice;
 181
 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;
 192           }
 193         }
 194       }
 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);
 199         } else {
 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)));
 203           }
 204         }
 205       }
 206       this.lastchoices = null;
 207       this.first4choice = false;
 208     }
 209
 210     public Vector<Vector<Combine>> getCombine() {
 211       return combine;
 212     }
 213
 214     public boolean nextGen() {
 215       boolean trial = false;
 216       if(this.lastchoices == null) {
 217         // first time
 218         this.lastchoices = new int[this.node2Combine.size()];
 219         for(int i = 0; i < this.lastchoices.length; i++) {
 220           this.lastchoices[i] = 0;
 221         }
 222         this.first4choice = true;
 223         trial = trial();
 224       } else {
 225         trial = trial();
 226         while(!trial) {
 227           // no more available combination under this choice
 228           // choose another choice
 229           int next = this.node2Combine.size() - 1;
 230           boolean iter = false;
 231           do {
 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
 239                 // backtrack
 240                 next--;
 241                 iter = true;
 242               } else {
 243                 iter = false;
 244               }
 245             } else {
 246               next--;
 247               iter = true;
 248             }
 249           } while(iter && !(next < 0));
 250           if(next < 0) {
 251             return false;
 252           }
 253           for(next += 1; next < this.node2Combine.size(); next++) {
 254             this.lastchoices[next] = 0;
 255           }
 256           this.first4choice = true;
 257           trial = trial();
 258         }
 259       }
 260       return trial;
 261     }
 262
 263     private boolean trial() {
 264       boolean suc = false;
 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
 268         int next = 0;
 269         suc = firstexpand(next, this.first4choice);
 270         this.first4choice = false;
 271       } else {
 272         int next = this.node2Combine.size() - 1;
 273         int layer = 0;
 274         suc = innertrial(next, layer);
 275       }
 276       return suc;
 277     }
 278
 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);
 285             if(!first) {
 286               this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]--;
 287             }
 288             tmp.root = choice;
 289             tmp.index = 0;
 290             if(!first) {
 291               this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]++;
 292             }
 293           }
 294           if(first) {
 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;
 298             }
 299           }
 300         }
 301       }
 302       return true;
 303     }
 304
 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)
 310         if(next - 1 < 0) {
 311           return false;
 312         } else {
 313           return innertrial(next - 1, ++layer);
 314         }
 315       }
 316       Combine tmp = this.combine.elementAt(next).lastElement();
 317       // try to move it backward
 318       int root = tmp.root;
 319       int index = tmp.index;
 320       index++;
 321       if(index == this.rootNodes.elementAt(root).size()) {
 322         // no more place in this color bucket
 323         index = 0;
 324         root++;
 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
 329         index = 0;
 330         root++;
 331       }
 332       if(root == this.rootNodes.size()) {
 333         // no more bucket
 334         // backtrack
 335         root = tmp.root;
 336         index = tmp.index;
 337         int t = this.combine.elementAt(next).size() - 2;
 338         while(true) {
 339           while(!(t < 0)) {
 340             tmp = this.combine.elementAt(next).elementAt(t);
 341             if ((tmp.root != root) || (tmp.index != index)) {
 342               break;
 343             }
 344             t--;
 345           }
 346           if(t < 0) {
 347             // try the bucket in node2combine before
 348             if(next - 1 < 0) {
 349               return false;
 350             } else {
 351               return innertrial(next - 1, ++layer);
 352             }
 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
 359               if(next - 1 < 0) {
 360                 return false;
 361               } else {
 362                 return innertrial(next - 1, ++layer);
 363               }
 364             }
 365             this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]--;
 366             //tmp.root = root;
 367             int newroot = tmp.root + 1;
 368             tmp.root = newroot;
 369             tmp.index = 0;
 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]--;
 375               tmp.root = newroot;
 376               tmp.index = 0;
 377               this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]++;
 378             }
 379             if(layer != 0) {
 380               return firstexpand(next+1, this.first4choice);
 381             }
 382             return true;
 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
 388               index = tmp.index;
 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);
 395               if(suc) {
 396                 return suc;
 397               } else {
 398                 // go on search forward
 399                 index = tmp.index;
 400               }
 401             } else {
 402               this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]--;
 403               int tmproot = tmp.root;
 404               int tmpindex = tmp.index;
 405               tmp.root = root;
 406               tmp.index = 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
 411               t++;
 412               boolean first = true;
 413               while(t < this.combine.elementAt(next).size()) {
 414                 int k = 0;
 415                 if(first) {
 416                   k = 1;
 417                   first = false;
 418                 }
 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]--;
 422                   tmp.root = desroot;
 423                   tmp.index = desindex;
 424                   this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]++;
 425                 }
 426                 if(k == this.rootNStates.elementAt(tmproot).elementAt(tmpindex)[next]) {
 427                   desindex++;
 428                 }
 429               }
 430               if(layer != 0) {
 431                 return firstexpand(next+1, this.first4choice);
 432               }
 433               return true;
 434             }
 435           }
 436         }
 437       } else {
 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]--;
 441           tmp.root = root;
 442           tmp.index = index;
 443           this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]++;
 444           if(layer != 0) {
 445             return firstexpand(next+1, this.first4choice);
 446           }
 447           return true;
 448         } else {
 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
 451           if(next - 1 < 0) {
 452             return false;
 453           } else {
 454             return innertrial(next - 1, ++layer);
 455           }
 456         }
 457       }
 458     }
 459
 460     private boolean propagateOne(int next, int rooti, int indexi, int ti, Combine tmp) {
 461       int root = rooti;
 462       int index = indexi;
 463       int t = ti;
 464       int rootbk = tmp.root;
 465       int indexbk = tmp.index;
 466       this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]--;
 467       tmp.root = root;
 468       tmp.index = index;
 469       this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]++;
 470       t += 2;
 471       Combine tmpt = null;
 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)) {
 478             break;
 479           }
 480           t++;
 481         }
 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);
 488             /*if(!suc) {
 489                 // fail, roll back
 490                 this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]--;
 491                 tmp.root = rootbk;
 492                 tmp.index = indexbk;
 493                 this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]++;
 494                }*/
 495             return suc;
 496           } else if(root+1 < this.rootNodes.size()) {           // check if there are another bucket
 497             // yes
 498             this.rootNStates.elementAt(tmpt.root).elementAt(tmpt.index)[next]--;
 499             tmpt.root = root + 1;
 500             tmpt.index = 0;
 501             this.rootNStates.elementAt(tmpt.root).elementAt(tmpt.index)[next]++;
 502             return firstexpand(next+1, this.first4choice);
 503           } else {
 504             // no, 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             return false;
 510           }
 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;
 515           tmpbk.index = 0;
 516           this.rootNStates.elementAt(tmpbk.root).elementAt(tmpbk.index)[next]++;
 517           root = tmpt.root;
 518           index = tmpt.index;
 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]--;
 523             tmpt.root = root;
 524             tmpt.index = 0;
 525             this.rootNStates.elementAt(tmpt.root).elementAt(tmpt.index)[next]++;
 526           }
 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);
 531           if(!suc) {
 532             // fail, roll back
 533             this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]--;
 534             tmp.root = rootbk;
 535             tmp.index = indexbk;
 536             this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]++;
 537           }
 538           return suc;
 539         }
 540         // won't reach here, only to avoid compiler's complain
 541         return true;
 542       } else {
 543         return true;
 544       }
 545     }
 546   }
 547 }