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