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 }