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