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