Robust/src/Analysis/Scheduling/ScheduleAnalysis.java

   1 package Analysis.Scheduling;
   2
   3 import Analysis.TaskStateAnalysis.*;
   4 import IR.*;
   5
   6 import java.util.*;
   7
   8 /** This class holds flag transition diagram(s) can be put on one core.
   9  */
  10 public class ScheduleAnalysis {
  11
  12     State state;
  13     TaskAnalysis taskanalysis;
  14     Vector<ScheduleNode> scheduleNodes;
  15     Vector<ClassNode> classNodes;
  16     Vector<ScheduleEdge> scheduleEdges;
  17     Hashtable<ClassDescriptor, ClassNode> cd2ClassNode;
  18     boolean sorted = false;
  19
  20     int transThreshold;
  21
  22     int coreNum;
  23     Vector<Vector<ScheduleNode>> scheduleGraphs;
  24     Vector<Vector<Schedule>> schedulings;
  25
  26     public ScheduleAnalysis(State state, TaskAnalysis taskanalysis) {
  27         this.state = state;
  28         this.taskanalysis = taskanalysis;
  29         this.scheduleNodes = new Vector<ScheduleNode>();
  30         this.classNodes = new Vector<ClassNode>();
  31         this.scheduleEdges = new Vector<ScheduleEdge>();
  32         this.cd2ClassNode = new Hashtable<ClassDescriptor, ClassNode>();
  33         this.transThreshold = 45;
  34         this.coreNum = -1;
  35         this.scheduleGraphs = null;
  36         this.schedulings = null;
  37     }
  38
  39     public void setTransThreshold(int tt) {
  40         this.transThreshold = tt;
  41     }
  42
  43     public int getCoreNum() {
  44         return coreNum;
  45     }
  46
  47     public void setCoreNum(int coreNum) {
  48         this.coreNum = coreNum;
  49     }
  50
  51     public Iterator getScheduleGraphs() {
  52         return this.scheduleGraphs.iterator();
  53     }
  54
  55     public Iterator getSchedulingsIter() {
  56         return this.schedulings.iterator();
  57     }
  58
  59     public Vector<Vector<Schedule>> getSchedulings() {
  60         return this.schedulings;
  61     }
  62
  63     // for test
  64     public Vector<ScheduleEdge> getSEdges4Test() {
  65         return scheduleEdges;
  66     }
  67
  68     public void preSchedule() {
  69         Hashtable<ClassDescriptor, ClassNode> cdToCNodes = new Hashtable<ClassDescriptor, ClassNode>();
  70         // Build the combined flag transition diagram
  71         // First, for each class create a ClassNode
  72         for(Iterator it_classes = state.getClassSymbolTable().getDescriptorsIterator(); it_classes.hasNext(); ) {
  73             ClassDescriptor cd = (ClassDescriptor) it_classes.next();
  74             Set<FlagState> fStates = taskanalysis.getFlagStates(cd);
  75
  76             //Sort flagState nodes inside this ClassNode
  77             Vector<FlagState> sFStates = FlagState.DFS.topology(fStates, null);
  78
  79             Vector rootnodes  = taskanalysis.getRootNodes(cd);
  80             if(((rootnodes != null) && (rootnodes.size() > 0)) || (cd.getSymbol().equals(TypeUtil.StartupClass))) {
  81                 ClassNode cNode = new ClassNode(cd, sFStates);
  82                 cNode.setSorted(true);
  83                 classNodes.add(cNode);
  84                 cd2ClassNode.put(cd, cNode);
  85                 cdToCNodes.put(cd, cNode);
  86                 cNode.calExeTime();
  87
  88                 // for test
  89                 if(cd.getSymbol().equals("C")) {
  90                     cNode.setTransTime(45);
  91                 }
  92             }
  93             fStates = null;
  94             sFStates = null;
  95         }
  96
  97         // For each ClassNode create a ScheduleNode containing it
  98         int i = 0;
  99         for(i = 0; i < classNodes.size(); i++) {
 100             ScheduleNode sn = new ScheduleNode(classNodes.elementAt(i), 0);
 101             classNodes.elementAt(i).setScheduleNode(sn);
 102             scheduleNodes.add(sn);
 103             try {
 104                 sn.calExeTime();
 105             } catch (Exception e) {
 106                 e.printStackTrace();
 107             }
 108         }
 109
 110         // Create 'new' edges between the ScheduleNodes.
 111         Vector<ScheduleEdge> toBreakDown = new Vector<ScheduleEdge>();
 112         for(i = 0; i < classNodes.size(); i++) {
 113             ClassNode cNode = classNodes.elementAt(i);
 114             ClassDescriptor cd = cNode.getClassDescriptor();
 115             Vector rootnodes  = taskanalysis.getRootNodes(cd);
 116             if(rootnodes != null) {
 117                 for(int h = 0; h < rootnodes.size(); h++){
 118                     FlagState root=(FlagState)rootnodes.elementAt(h);
 119                     Vector allocatingTasks = root.getAllocatingTasks();
 120                     if(allocatingTasks != null) {
 121                         for(int k = 0; k < allocatingTasks.size(); k++) {
 122                             TaskDescriptor td = (TaskDescriptor)allocatingTasks.elementAt(k);
 123                             Vector<FEdge> fev = (Vector<FEdge>)taskanalysis.getFEdgesFromTD(td);
 124                             int numEdges = fev.size();
 125                             ScheduleNode sNode = cNode.getScheduleNode();
 126                             for(int j = 0; j < numEdges; j++) {
 127                                 FEdge pfe = fev.elementAt(j);
 128                                 FEdge.NewObjInfo noi = pfe.getNewObjInfo(cd);
 129                                 if ((noi == null) || (noi.getNewRate() == 0) || (noi.getProbability() == 0)) {
 130                                     // fake creating edge, do not need to create corresponding 'new' edge
 131                                     continue;
 132                                 }
 133                                 if(noi.getRoot() == null) {
 134                                     // set root FlagState
 135                                     noi.setRoot(root);
 136                                 }
 137                                 FlagState pfs = (FlagState)pfe.getTarget();
 138                                 ClassDescriptor pcd = pfs.getClassDescriptor();
 139                                 ClassNode pcNode = cdToCNodes.get(pcd);
 140
 141                                 ScheduleEdge sEdge = new ScheduleEdge(sNode, "new", root, ScheduleEdge.NEWEDGE, 0);
 142                                 sEdge.setFEdge(pfe);
 143                                 sEdge.setSourceCNode(pcNode);
 144                                 sEdge.setTargetCNode(cNode);
 145                                 sEdge.setTargetFState(root);
 146                                 sEdge.setNewRate(noi.getNewRate());
 147                                 sEdge.setProbability(noi.getProbability());
 148                                 pcNode.getScheduleNode().addEdge(sEdge);
 149                                 scheduleEdges.add(sEdge);
 150                                 if((j !=0 ) || (k != 0) || (h != 0)) {
 151                                     toBreakDown.add(sEdge);
 152                                 }
 153                             }
 154                             fev = null;
 155                         }
 156                         allocatingTasks = null;
 157                     }
 158                 }
 159                 rootnodes = null;
 160             }
 161         }
 162         cdToCNodes = null;
 163
 164         // Break down the 'cycle's
 165         try {
 166             for(i = 0; i < toBreakDown.size(); i++ ) {
 167                 cloneSNodeList(toBreakDown.elementAt(i), false);
 168             }
 169             toBreakDown = null;
 170         } catch (Exception e) {
 171             e.printStackTrace();
 172             System.exit(-1);
 173         }
 174
 175         // Remove fake 'new' edges
 176         for(i = 0; i < scheduleEdges.size(); i++) {
 177             ScheduleEdge se = (ScheduleEdge)scheduleEdges.elementAt(i);
 178             if((0 == se.getNewRate()) || (0 == se.getProbability())) {
 179                 scheduleEdges.removeElement(se);
 180                 scheduleNodes.removeElement(se.getTarget());
 181             }
 182         }
 183
 184         // Do topology sort of the ClassNodes and ScheduleEdges.
 185         Vector<ScheduleEdge> ssev = new Vector<ScheduleEdge>();
 186         Vector<ScheduleNode> tempSNodes = ClassNode.DFS.topology(scheduleNodes, ssev);
 187         scheduleNodes.removeAllElements();
 188         scheduleNodes = tempSNodes;
 189         tempSNodes = null;
 190         scheduleEdges.removeAllElements();
 191         scheduleEdges = ssev;
 192         ssev = null;
 193         sorted = true;
 194
 195         SchedulingUtil.printScheduleGraph("scheduling_ori.dot", this.scheduleNodes);
 196     }
 197
 198     public void scheduleAnalysis() {
 199         // First iteration
 200         int i = 0;
 201         //Access the ScheduleEdges in reverse topology order
 202         Hashtable<FEdge, Vector<ScheduleEdge>> fe2ses = new Hashtable<FEdge, Vector<ScheduleEdge>>();
 203         Hashtable<ScheduleNode, Vector<FEdge>> sn2fes = new Hashtable<ScheduleNode, Vector<FEdge>>();
 204         ScheduleNode preSNode = null;
 205         for(i = scheduleEdges.size(); i > 0; i--) {
 206             ScheduleEdge se = (ScheduleEdge)scheduleEdges.elementAt(i-1);
 207             if(ScheduleEdge.NEWEDGE == se.getType()) {
 208                 if(preSNode == null) {
 209                     preSNode = (ScheduleNode)se.getSource();
 210                 }
 211
 212                 boolean split = false;
 213                 FEdge fe = se.getFEdge();
 214                 if(fe.getSource() == fe.getTarget()) {
 215                     // back edge
 216                     try {
 217                         int repeat = (int)Math.ceil(se.getNewRate() * se.getProbability() / 100);
 218                         int rate = 0;
 219                         if(repeat > 1){
 220                             for(int j = 1; j< repeat; j++ ) {
 221                                 cloneSNodeList(se, true);
 222                             }
 223                             se.setNewRate(1);
 224                             se.setProbability(100);
 225                         }
 226                         try {
 227                             rate = (int)Math.ceil(se.getListExeTime()/ calInExeTime(se.getSourceFState()));
 228                         } catch (Exception e) {
 229                             e.printStackTrace();
 230                         }
 231                         for(int j = rate - 1; j > 0; j--) {
 232                             for(int k = repeat; k > 0; k--) {
 233                                 cloneSNodeList(se, true);
 234                             }
 235                         }
 236                     } catch (Exception e) {
 237                         e.printStackTrace();
 238                         System.exit(-1);
 239                     }
 240                 } else {
 241                     // if preSNode is not the same as se's source ScheduleNode
 242                     // handle any ScheduleEdges previously put into fe2ses whose source ScheduleNode is preSNode
 243                     boolean same = (preSNode == se.getSource());
 244                     if(!same) {
 245                         // check the topology sort, only process those after se.getSource()
 246                         if(preSNode.getFinishingTime() < se.getSource().getFinishingTime()) {
 247                             if(sn2fes.containsKey(preSNode)) {
 248                                 Vector<FEdge> fes = sn2fes.remove(preSNode);
 249                                 for(int j = 0; j < fes.size(); j++) {
 250                                     FEdge tempfe = fes.elementAt(j);
 251                                     Vector<ScheduleEdge> ses = fe2ses.get(tempfe);
 252                                     ScheduleEdge tempse = ses.elementAt(0);
 253                                     int temptime = tempse.getListExeTime();
 254                                     // find out the ScheduleEdge with least exeTime
 255                                     for(int k = 1; k < ses.size(); k++) {
 256                                         int ttemp = ses.elementAt(k).getListExeTime();
 257                                         if(ttemp < temptime) {
 258                                             tempse = ses.elementAt(k);
 259                                             temptime = ttemp;
 260                                         }
 261                                     }
 262                                     // handle the tempse
 263                                     handleScheduleEdge(tempse, true);
 264                                     ses.removeElement(tempse);
 265                                     // handle other ScheduleEdges
 266                                     for(int k = 0; k < ses.size(); k++) {
 267                                         handleScheduleEdge(ses.elementAt(k), false);
 268                                     }
 269                                     ses = null;
 270                                     fe2ses.remove(tempfe);
 271                                 }
 272                                 fes = null;
 273                             }
 274                         }
 275                         preSNode = (ScheduleNode)se.getSource();
 276                     }
 277
 278                     // if fe is the last task inside this ClassNode, delay the expanding and merging until we find all such 'new' edges
 279                     // associated with a last task inside this ClassNode
 280                     if(!fe.getTarget().edges().hasNext()) {
 281                         if(fe2ses.get(fe) == null) {
 282                             fe2ses.put(fe, new Vector<ScheduleEdge>());
 283                         }
 284                         if(sn2fes.get((ScheduleNode)se.getSource()) == null) {
 285                             sn2fes.put((ScheduleNode)se.getSource(), new Vector<FEdge>());
 286                         }
 287                         if(!fe2ses.get(fe).contains(se)) {
 288                             fe2ses.get(fe).add(se);
 289                         }
 290                         if(!sn2fes.get((ScheduleNode)se.getSource()).contains(fe)) {
 291                             sn2fes.get((ScheduleNode)se.getSource()).add(fe);
 292                         }
 293                     } else {
 294                         // As this is not a last task, first handle available ScheduleEdges previously put into fe2ses
 295                         if((same) && (sn2fes.containsKey(preSNode))) {
 296                             Vector<FEdge> fes = sn2fes.remove(preSNode);
 297                             for(int j = 0; j < fes.size(); j++) {
 298                                 FEdge tempfe = fes.elementAt(j);
 299                                 Vector<ScheduleEdge> ses = fe2ses.get(tempfe);
 300                                 ScheduleEdge tempse = ses.elementAt(0);
 301                                 int temptime = tempse.getListExeTime();
 302                                 // find out the ScheduleEdge with least exeTime
 303                                 for(int k = 1; k < ses.size(); k++) {
 304                                     int ttemp = ses.elementAt(k).getListExeTime();
 305                                     if(ttemp < temptime) {
 306                                         tempse = ses.elementAt(k);
 307                                         temptime = ttemp;
 308                                     }
 309                                 }
 310                                 // handle the tempse
 311                                 handleScheduleEdge(tempse, true);
 312                                 ses.removeElement(tempse);
 313                                 // handle other ScheduleEdges
 314                                 for(int k = 0; k < ses.size(); k++) {
 315                                     handleScheduleEdge(ses.elementAt(k), false);
 316                                 }
 317                                 ses = null;
 318                                 fe2ses.remove(tempfe);
 319                             }
 320                             fes = null;
 321                         }
 322
 323                         if((!(se.getTransTime() < this.transThreshold)) && (se.getSourceCNode().getTransTime() < se.getTransTime())) {
 324                             split = true;
 325                             splitSNode(se, true);
 326                         } else {
 327                             // handle this ScheduleEdge
 328                             handleScheduleEdge(se, true);
 329                         }
 330                     }
 331                 }
 332             }
 333         }
 334         if(!fe2ses.isEmpty()) {
 335             Set<FEdge> keys = fe2ses.keySet();
 336             Iterator it_keys = keys.iterator();
 337             while(it_keys.hasNext()) {
 338                 FEdge tempfe = (FEdge)it_keys.next();
 339                 Vector<ScheduleEdge> ses = fe2ses.get(tempfe);
 340                 ScheduleEdge tempse = ses.elementAt(0);
 341                 int temptime = tempse.getListExeTime();
 342                 // find out the ScheduleEdge with least exeTime
 343                 for(int k = 1; k < ses.size(); k++) {
 344                     int ttemp = ses.elementAt(k).getListExeTime();
 345                     if(ttemp < temptime) {
 346                         tempse = ses.elementAt(k);
 347                         temptime = ttemp;
 348                     }
 349                 }
 350                 // handle the tempse
 351                 handleScheduleEdge(tempse, true);
 352                 ses.removeElement(tempse);
 353                 // handle other ScheduleEdges
 354                 for(int k = 0; k < ses.size(); k++) {
 355                     handleScheduleEdge(ses.elementAt(k), false);
 356                 }
 357                 ses = null;
 358             }
 359             keys = null;
 360             fe2ses.clear();
 361             sn2fes.clear();
 362         }
 363         fe2ses = null;
 364         sn2fes = null;
 365
 366         SchedulingUtil.printScheduleGraph("scheduling_extend.dot", this.scheduleNodes);
 367     }
 368
 369     private void handleScheduleEdge(ScheduleEdge se, boolean merge) {
 370         try {
 371             int rate = 0;
 372             int repeat = (int)Math.ceil(se.getNewRate() * se.getProbability() / 100);
 373             if(merge) {
 374                 try {
 375                     rate = (int)Math.ceil((se.getTransTime() - calInExeTime(se.getSourceFState()))/ se.getListExeTime());
 376                     if(rate < 0 ) {
 377                         rate = 0;
 378                     }
 379                 } catch (Exception e) {
 380                     e.printStackTrace();
 381                 }
 382                 if(0 == rate) {
 383                     // clone the whole ScheduleNode lists starting with se's target
 384                     for(int j = 1; j < repeat; j++ ) {
 385                         cloneSNodeList(se, true);
 386                     }
 387                     se.setNewRate(1);
 388                     se.setProbability(100);
 389                 } else {
 390                     repeat -= rate;
 391                     if(repeat > 0){
 392                         // clone the whole ScheduleNode lists starting with se's target
 393                         for(int j = 0; j < repeat; j++ ) {
 394                             cloneSNodeList(se, true);
 395                         }
 396                         se.setNewRate(rate);
 397                         se.setProbability(100);
 398                     }
 399                 }
 400                 // merge the original ScheduleNode to the source ScheduleNode
 401                 ((ScheduleNode)se.getSource()).mergeSEdge(se);
 402                 scheduleNodes.remove(se.getTarget());
 403                 scheduleEdges.remove(se);
 404                 // As se has been changed into an internal edge inside a ScheduleNode,
 405                 // change the source and target of se from original ScheduleNodes into ClassNodes.
 406                 if(se.getType() == ScheduleEdge.NEWEDGE) {
 407                     se.setTarget(se.getTargetCNode());
 408                     se.setSource(se.getSourceCNode());
 409                     se.getTargetCNode().addEdge(se);
 410                 }
 411             } else {
 412                 // clone the whole ScheduleNode lists starting with se's target
 413                 for(int j = 1; j < repeat; j++ ) {
 414                     cloneSNodeList(se, true);
 415                 }
 416                 se.setNewRate(1);
 417                 se.setProbability(100);
 418             }
 419         } catch (Exception e) {
 420             e.printStackTrace();
 421             System.exit(-1);
 422         }
 423     }
 424
 425     private void cloneSNodeList(ScheduleEdge sEdge, boolean copyIE) throws Exception {
 426         Hashtable<ClassNode, ClassNode> cn2cn = new Hashtable<ClassNode, ClassNode>(); // hashtable from classnode in orignal se's targe to cloned one
 427         ScheduleNode csNode = (ScheduleNode)((ScheduleNode)sEdge.getTarget()).clone(cn2cn, 0);
 428         scheduleNodes.add(csNode);
 429
 430         // Clone all the external in ScheduleEdges
 431         int i;
 432         if(copyIE) {
 433             Vector inedges = sEdge.getTarget().getInedgeVector();
 434             for(i = 0; i < inedges.size(); i++) {
 435                 ScheduleEdge tse = (ScheduleEdge)inedges.elementAt(i);
 436                 ScheduleEdge se;
 437                 switch(tse.getType()) {
 438                 case ScheduleEdge.NEWEDGE: {
 439                     se = new ScheduleEdge(csNode, "new", tse.getFstate(), tse.getType(), 0);
 440                     se.setProbability(100);
 441                     se.setNewRate(1);
 442                     break;
 443                 }
 444                 case ScheduleEdge.TRANSEDGE: {
 445                     se = new ScheduleEdge(csNode, "transmit", tse.getFstate(), tse.getType(), 0);
 446                     se.setProbability(tse.getProbability());
 447                     se.setNewRate(tse.getNewRate());
 448                     break;
 449                 }
 450                 default: {
 451                     throw new Exception("Error: not valid ScheduleEdge here");
 452                 }
 453                 }
 454                 se.setSourceCNode(tse.getSourceCNode());
 455                 se.setTargetCNode(cn2cn.get(tse.getTargetCNode()));
 456                 se.setFEdge(tse.getFEdge());
 457                 se.setTargetFState(tse.getTargetFState());
 458                 se.setIsclone(true);
 459                 tse.getSource().addEdge(se);
 460                 scheduleEdges.add(se);
 461             }
 462             inedges = null;
 463         } else {
 464             sEdge.getTarget().removeInedge(sEdge);
 465             sEdge.setTarget(csNode);
 466             csNode.getInedgeVector().add(sEdge);
 467             sEdge.setTargetCNode(cn2cn.get(sEdge.getTargetCNode()));
 468             sEdge.setIsclone(true);
 469         }
 470
 471         Queue<ScheduleNode> toClone = new LinkedList<ScheduleNode>(); // all nodes to be cloned
 472         Queue<ScheduleNode> clone = new LinkedList<ScheduleNode>(); //clone nodes
 473         Queue<Hashtable> qcn2cn = new LinkedList<Hashtable>(); // queue of the mappings of classnodes inside cloned ScheduleNode
 474         Vector<ScheduleNode> origins = new Vector<ScheduleNode>(); // queue of source ScheduleNode cloned
 475         Hashtable<ScheduleNode, ScheduleNode> sn2sn = new Hashtable<ScheduleNode, ScheduleNode>(); // mapping from cloned ScheduleNode to clone ScheduleNode
 476         clone.add(csNode);
 477         toClone.add((ScheduleNode)sEdge.getTarget());
 478         origins.addElement((ScheduleNode)sEdge.getTarget());
 479         sn2sn.put((ScheduleNode)sEdge.getTarget(), csNode);
 480         qcn2cn.add(cn2cn);
 481         while(!toClone.isEmpty()) {
 482             Hashtable<ClassNode, ClassNode> tocn2cn = new Hashtable<ClassNode, ClassNode>();
 483             csNode = clone.poll();
 484             ScheduleNode osNode = toClone.poll();
 485             cn2cn = qcn2cn.poll();
 486             // Clone all the external ScheduleEdges and the following ScheduleNodes
 487             Vector edges = osNode.getEdgeVector();
 488             for(i = 0; i < edges.size(); i++) {
 489                 ScheduleEdge tse = (ScheduleEdge)edges.elementAt(i);
 490                 ScheduleNode tSNode = (ScheduleNode)((ScheduleNode)tse.getTarget()).clone(tocn2cn, 0);
 491                 scheduleNodes.add(tSNode);
 492                 clone.add(tSNode);
 493                 toClone.add((ScheduleNode)tse.getTarget());
 494                 origins.addElement((ScheduleNode)tse.getTarget());
 495                 sn2sn.put((ScheduleNode)tse.getTarget(), tSNode);
 496                 qcn2cn.add(tocn2cn);
 497                 ScheduleEdge se = null;
 498                 switch(tse.getType()) {
 499                 case ScheduleEdge.NEWEDGE: {
 500                     se = new ScheduleEdge(tSNode, "new", tse.getFstate(), tse.getType(), 0);
 501                     break;
 502                 }
 503                 case ScheduleEdge.TRANSEDGE: {
 504                     se = new ScheduleEdge(tSNode, "transmit", tse.getFstate(), tse.getType(), 0);
 505                     break;
 506                 }
 507                 default: {
 508                     throw new Exception("Error: not valid ScheduleEdge here");
 509                 }
 510                 }
 511                 se.setSourceCNode(cn2cn.get(tse.getSourceCNode()));
 512                 se.setTargetCNode(tocn2cn.get(tse.getTargetCNode()));
 513                 se.setFEdge(tse.getFEdge());
 514                 se.setTargetFState(tse.getTargetFState());
 515                 se.setProbability(tse.getProbability());
 516                 se.setNewRate(tse.getNewRate());
 517                 se.setIsclone(true);
 518                 csNode.addEdge(se);
 519                 scheduleEdges.add(se);
 520             }
 521             tocn2cn = null;
 522             edges = null;
 523         }
 524
 525         toClone = null;
 526         clone = null;
 527         qcn2cn = null;
 528         cn2cn = null;
 529     }
 530
 531     private int calInExeTime(FlagState fs) throws Exception {
 532         int exeTime = 0;
 533         ClassDescriptor cd = fs.getClassDescriptor();
 534         ClassNode cNode = cd2ClassNode.get(cd);
 535         exeTime = cNode.getFlagStates().elementAt(0).getExeTime() - fs.getExeTime();
 536         while(true) {
 537             Vector inedges = cNode.getInedgeVector();
 538             // Now that there are associate ScheduleEdges, there may be multiple inedges of a ClassNode
 539             if(inedges.size() > 1) {
 540                 throw new Exception("Error: ClassNode's inedges more than one!");
 541             }
 542             if(inedges.size() > 0) {
 543                 ScheduleEdge sEdge = (ScheduleEdge)inedges.elementAt(0);
 544                 cNode = (ClassNode)sEdge.getSource();
 545                 exeTime += cNode.getFlagStates().elementAt(0).getExeTime();
 546             }else {
 547                 break;
 548             }
 549             inedges = null;
 550         }
 551         exeTime = cNode.getScheduleNode().getExeTime() - exeTime;
 552         return exeTime;
 553     }
 554
 555     private ScheduleNode splitSNode(ScheduleEdge se, boolean copy) {
 556         assert(ScheduleEdge.NEWEDGE == se.getType());
 557
 558         FEdge fe = se.getFEdge();
 559         FlagState fs = (FlagState)fe.getTarget();
 560         FlagState nfs = (FlagState)fs.clone();
 561         fs.getEdgeVector().removeAllElements();
 562         nfs.getInedgeVector().removeAllElements();
 563         ClassNode sCNode = se.getSourceCNode();
 564
 565         // split the subtree whose root is nfs from the whole flag transition tree
 566         Vector<FlagState> sfss = sCNode.getFlagStates();
 567         Vector<FlagState> fStates = new Vector<FlagState>();
 568         Queue<FlagState> toiterate = new LinkedList<FlagState>();
 569         toiterate.add(nfs);
 570         fStates.add(nfs);
 571         while(!toiterate.isEmpty()){
 572             FlagState tfs = toiterate.poll();
 573             Iterator it_edges = tfs.edges();
 574             while(it_edges.hasNext()) {
 575                 FlagState temp = (FlagState)((FEdge)it_edges.next()).getTarget();
 576                 if(!fStates.contains(temp)) {
 577                     fStates.add(temp);
 578                     toiterate.add(temp);
 579                     sfss.removeElement(temp);
 580                 }
 581             }
 582         }
 583         sfss = null;
 584         Vector<FlagState> sFStates = FlagState.DFS.topology(fStates, null);
 585         fStates = null;
 586         // create a ClassNode and ScheduleNode for this subtree
 587         ClassNode cNode = new ClassNode(sCNode.getClassDescriptor(), sFStates);
 588         ScheduleNode sNode = new ScheduleNode(cNode, 0);
 589         cNode.setScheduleNode(sNode);
 590         cNode.setSorted(true);
 591         cNode.setTransTime(sCNode.getTransTime());
 592         classNodes.add(cNode);
 593         scheduleNodes.add(sNode);
 594         try {
 595             sNode.calExeTime();
 596         } catch (Exception e) {
 597             e.printStackTrace();
 598         }
 599         // flush the exeTime of fs and its ancestors
 600         fs.setExeTime(0);
 601         toiterate.add(fs);
 602         while(!toiterate.isEmpty()) {
 603             FlagState tfs = toiterate.poll();
 604             int ttime = tfs.getExeTime();
 605             Iterator it_inedges = tfs.inedges();
 606             while(it_inedges.hasNext()) {
 607                 FEdge fEdge = (FEdge)it_inedges.next();
 608                 FlagState temp = (FlagState)fEdge.getSource();
 609                 int time = fEdge.getExeTime() + ttime;
 610                 if(temp.getExeTime() > time) {
 611                     temp.setExeTime(time);
 612                     toiterate.add(temp);
 613                 }
 614             }
 615         }
 616         toiterate = null;
 617
 618         // create a 'trans' ScheudleEdge between this new ScheduleNode and se's source ScheduleNode
 619         ScheduleEdge sEdge = new ScheduleEdge(sNode, "transmit", fs, ScheduleEdge.TRANSEDGE, 0);//new ScheduleEdge(sNode, "transmit", cNode.getClassDescriptor(), false, 0);
 620         sEdge.setFEdge(fe);
 621         sEdge.setSourceCNode(sCNode);
 622         sEdge.setTargetCNode(cNode);
 623         sEdge.setTargetFState(nfs);
 624         // TODO
 625         // Add calculation codes for calculating transmit time of an object
 626         sEdge.setTransTime(cNode.getTransTime());
 627         se.getSource().addEdge(sEdge);
 628         scheduleEdges.add(sEdge);
 629         // remove the ClassNodes and internal ScheduleEdges out of this subtree to the new ScheduleNode
 630         ScheduleNode oldSNode = (ScheduleNode)se.getSource();
 631         Iterator it_isEdges = oldSNode.getScheduleEdgesIterator();
 632         Vector<ScheduleEdge> toremove = new Vector<ScheduleEdge>();
 633         Vector<ClassNode> rCNodes = new Vector<ClassNode>();
 634         rCNodes.addElement(sCNode);
 635         if(it_isEdges != null){
 636             while(it_isEdges.hasNext()) {
 637                 ScheduleEdge tse = (ScheduleEdge)it_isEdges.next();
 638                 if(rCNodes.contains(tse.getSourceCNode())) {
 639                     if(sCNode == tse.getSourceCNode()) {
 640                         if ((tse.getSourceFState() != fs) && (sFStates.contains(tse.getSourceFState()))) {
 641                             tse.setSource(cNode);
 642                             tse.setSourceCNode(cNode);
 643                         } else {
 644                             continue;
 645                         }
 646                     }
 647                     sNode.getScheduleEdges().addElement(tse);
 648                     sNode.getClassNodes().addElement(tse.getTargetCNode());
 649                     rCNodes.addElement(tse.getTargetCNode());
 650                     oldSNode.getClassNodes().removeElement(tse.getTargetCNode());
 651                     toremove.addElement(tse);
 652                 }
 653             }
 654         }
 655         oldSNode.getScheduleEdges().removeAll(toremove);
 656         toremove.clear();
 657         // redirect ScheudleEdges out of this subtree to the new ScheduleNode
 658         Iterator it_sEdges = se.getSource().edges();
 659         while(it_sEdges.hasNext()) {
 660             ScheduleEdge tse = (ScheduleEdge)it_sEdges.next();
 661             if((tse != se) && (tse != sEdge) && (tse.getSourceCNode() == sCNode)) {
 662                 if((tse.getSourceFState() != fs) && (sFStates.contains(tse.getSourceFState()))) {
 663                     tse.setSource(sNode);
 664                     tse.setSourceCNode(cNode);
 665                     sNode.getEdgeVector().addElement(tse);
 666                     toremove.add(tse);
 667                 }
 668             }
 669         }
 670         se.getSource().getEdgeVector().removeAll(toremove);
 671         toremove = null;
 672         sFStates = null;
 673
 674         try {
 675             if(!copy) {
 676                 //merge se into its source ScheduleNode
 677                 ((ScheduleNode)se.getSource()).mergeSEdge(se);
 678                 scheduleNodes.remove(se.getTarget());
 679                 scheduleEdges.removeElement(se);
 680                 // As se has been changed into an internal edge inside a ScheduleNode,
 681                 // change the source and target of se from original ScheduleNodes into ClassNodes.
 682                 if(se.getType() == ScheduleEdge.NEWEDGE) {
 683                     se.setTarget(se.getTargetCNode());
 684                     se.setSource(se.getSourceCNode());
 685                     se.getTargetCNode().addEdge(se);
 686                 }
 687             } else {
 688                 handleScheduleEdge(se, true);
 689             }
 690         } catch (Exception e) {
 691             e.printStackTrace();
 692             System.exit(-1);
 693         }
 694
 695         return sNode;
 696     }
 697
 698     public void schedule() throws Exception {
 699         if(this.coreNum == -1) {
 700             throw new Exception("Error: un-initialized coreNum when doing scheduling.");
 701         }
 702
 703         if(this.scheduleGraphs == null) {
 704             this.scheduleGraphs = new Vector<Vector<ScheduleNode>>();
 705         }
 706
 707         int reduceNum = this.scheduleNodes.size() - this.coreNum;
 708
 709         // Enough cores, no need to merge more ScheduleEdge
 710         if(!(reduceNum > 0)) {
 711             this.scheduleGraphs.addElement(this.scheduleNodes);
 712             int gid = 1;
 713             String path = "scheduling_" + gid + ".dot";
 714             SchedulingUtil.printScheduleGraph(path, this.scheduleNodes);
 715         } else {
 716             // sort the ScheduleEdges in dececending order of transmittime
 717             Vector<ScheduleEdge> sEdges = new Vector<ScheduleEdge>();
 718             sEdges.addElement(this.scheduleEdges.elementAt(0));
 719             for(int i = 1; i < this.scheduleEdges.size(); i++) {
 720                 ScheduleEdge temp = this.scheduleEdges.elementAt(i);
 721                 int j = sEdges.size() - 1;
 722                 do {
 723                     if(temp.getTransTime() > sEdges.elementAt(j--).getTransTime()) {
 724                         break;
 725                     }
 726                 } while(j >= 0);
 727                 sEdges.add(j+1, temp);
 728             }
 729
 730             int temp = sEdges.elementAt(reduceNum - 1).getTransTime();
 731             for(int i = sEdges.size() - 1; i > reduceNum - 1; i--) {
 732                 if(sEdges.elementAt(i).getTransTime() != temp) {
 733                     sEdges.removeElementAt(i);
 734                 } else {
 735                     break;
 736                 }
 737             }
 738             int start = reduceNum - 2;
 739             for(; start >= 0; start--) {
 740                 if(sEdges.elementAt(start).getTransTime() != temp) {
 741                     start++;
 742                     reduceNum -= start;
 743                     break;
 744                 }
 745             }
 746             if(start < 0) {
 747                 start = 0;
 748             }
 749
 750             // generate scheduling
 751             Vector candidates = new Vector();
 752             for(int i = start; i < sEdges.size(); i++) {
 753                 candidates.addElement(Integer.valueOf(i));
 754             }
 755             Combination combGen = new Combination(candidates, reduceNum);
 756             int gid = 1;
 757             do {
 758                 Vector toreduce = combGen.next();
 759                 if(toreduce != null) {
 760                     Vector<ScheduleEdge> reduceEdges = new Vector<ScheduleEdge>();
 761                     for(int i = 0; i < start; i++) {
 762                         reduceEdges.add(sEdges.elementAt(i));
 763                     }
 764                     for(int i = 0; i < toreduce.size(); i++) {
 765                         reduceEdges.add(sEdges.elementAt(((Integer)toreduce.elementAt(i)).intValue()));
 766                     }
 767                     Vector<ScheduleNode> sNodes = generateScheduling(reduceEdges, gid++);
 768                     this.scheduleGraphs.add(sNodes);
 769                     reduceEdges = null;
 770                     sNodes = null;
 771                 } else {
 772                     break;
 773                 }
 774                 toreduce = null;
 775             }while(true);
 776             sEdges = null;
 777             candidates = null;
 778
 779         }
 780
 781         if(this.schedulings == null) {
 782             this.schedulings = new Vector<Vector<Schedule>>();
 783         }
 784
 785         Vector<TaskDescriptor> multiparamtds = new Vector<TaskDescriptor>();
 786         Iterator it_tasks = state.getTaskSymbolTable().getDescriptorsIterator();
 787         while(it_tasks.hasNext()) {
 788             TaskDescriptor td = (TaskDescriptor)it_tasks.next();
 789             if(td.numParameters() > 1) {
 790                 multiparamtds.addElement(td);
 791             }
 792         }
 793
 794         for(int i = 0; i < this.scheduleGraphs.size(); i++) {
 795             Hashtable<TaskDescriptor, Vector<Schedule>> td2cores = new Hashtable<TaskDescriptor, Vector<Schedule>>(); // multiparam tasks reside on which cores
 796             Vector<ScheduleNode> scheduleGraph = this.scheduleGraphs.elementAt(i);
 797             Vector<Schedule> scheduling = new Vector<Schedule>(scheduleGraph.size());
 798             // for each ScheduleNode create a schedule node representing a core
 799             Hashtable<ScheduleNode, Integer> sn2coreNum = new Hashtable<ScheduleNode, Integer>();
 800             int j = 0;
 801             for(j = 0; j < scheduleGraph.size(); j++) {
 802                 sn2coreNum.put(scheduleGraph.elementAt(j), j);
 803             }
 804             int startupcore = 0;
 805             boolean setstartupcore = false;
 806             Schedule startup = null;
 807             for(j = 0; j < scheduleGraph.size(); j++) {
 808                 Schedule tmpSchedule = new Schedule(j);
 809                 ScheduleNode sn = scheduleGraph.elementAt(j);
 810
 811                 Vector<ClassNode> cNodes = sn.getClassNodes();
 812                 for(int k = 0; k < cNodes.size(); k++) {
 813                     Iterator it_flags = cNodes.elementAt(k).getFlags();
 814                     while(it_flags.hasNext()) {
 815                         FlagState fs = (FlagState)it_flags.next();
 816                         Iterator it_edges = fs.edges();
 817                         while(it_edges.hasNext()) {
 818                             TaskDescriptor td = ((FEdge)it_edges.next()).getTask();
 819                             tmpSchedule.addTask(td);
 820                             if(!td2cores.containsKey(td)) {
 821                                 td2cores.put(td, new Vector<Schedule>());
 822                             }
 823                             Vector<Schedule> tmpcores = td2cores.get(td);
 824                             if(!tmpcores.contains(tmpSchedule)) {
 825                                 tmpcores.add(tmpSchedule);
 826                             }
 827                             // if the FlagState can be fed to some multi-param tasks,
 828                             // need to record corresponding ally cores later
 829                             if(td.numParameters() > 1) {
 830                                 tmpSchedule.addFState4TD(td, fs);
 831                             }
 832                             if(td.getParamType(0).getClassDesc().getSymbol().equals(TypeUtil.StartupClass)) {
 833                                 assert(!setstartupcore);
 834                                 startupcore = j;
 835                                 startup = tmpSchedule;
 836                                 setstartupcore = true;
 837                             }
 838                         }
 839                     }
 840                 }
 841
 842                 // For each of the ScheduleEdge out of this ScheduleNode, add the target ScheduleNode into the queue inside sn
 843                 Iterator it_edges = sn.edges();
 844                 while(it_edges.hasNext()) {
 845                     ScheduleEdge se = (ScheduleEdge)it_edges.next();
 846                     ScheduleNode target = (ScheduleNode)se.getTarget();
 847                     Integer targetcore = sn2coreNum.get(target);
 848                     switch(se.getType()) {
 849                     case ScheduleEdge.NEWEDGE: {
 850                         for(int k = 0; k < se.getNewRate(); k++) {
 851                             tmpSchedule.addTargetCore(se.getFstate(), targetcore);
 852                         }
 853                         break;
 854                     }
 855                     case ScheduleEdge.TRANSEDGE: {
 856                         // 'transmit' edge
 857                         tmpSchedule.addTargetCore(se.getFstate(), targetcore, se.getTargetFState());
 858                         // check if missed some FlagState associated with some multi-parameter
 859                         // task, which has been cloned when splitting a ClassNode
 860                         FlagState fs = se.getSourceFState();
 861                         FlagState tfs = se.getTargetFState();
 862                         Iterator it = tfs.edges();
 863                         while(it.hasNext()) {
 864                             TaskDescriptor td = ((FEdge)it.next()).getTask();
 865                             if(td.numParameters() > 1) {
 866                                 if(tmpSchedule.getTasks().contains(td)) {
 867                                     tmpSchedule.addFState4TD(td, fs);
 868                                 }
 869                             }
 870                         }
 871                         break;
 872                     }
 873                     }
 874                 }
 875                 it_edges = sn.getScheduleEdgesIterator();
 876                 while(it_edges.hasNext()) {
 877                     ScheduleEdge se = (ScheduleEdge)it_edges.next();
 878                     switch(se.getType()) {
 879                     case ScheduleEdge.NEWEDGE: {
 880                         for(int k = 0; k < se.getNewRate(); k++) {
 881                             tmpSchedule.addTargetCore(se.getFstate(), j);
 882                         }
 883                         break;
 884                     }
 885                     case ScheduleEdge.TRANSEDGE: {
 886                         // 'transmit' edge
 887                         tmpSchedule.addTargetCore(se.getFstate(), j, se.getTargetFState());
 888                         break;
 889                     }
 890                     }
 891                 }
 892                 scheduling.add(tmpSchedule);
 893             }
 894
 895             int number = this.coreNum;
 896             if(scheduling.size() < number) {
 897                 number = scheduling.size();
 898             }
 899
 900             // set up all the associate ally cores
 901             if(multiparamtds.size() > 0) {
 902                 for(j = 0; j < multiparamtds.size(); ++j) {
 903                     TaskDescriptor td = multiparamtds.elementAt(j);
 904                     Vector<FEdge> fes = (Vector<FEdge>)this.taskanalysis.getFEdgesFromTD(td);
 905                     Vector<Schedule> cores = td2cores.get(td);
 906                     for(int k = 0; k < cores.size(); ++k) {
 907                         Schedule tmpSchedule = cores.elementAt(k);
 908
 909                         for(int h = 0; h < fes.size(); ++h) {
 910                             FEdge tmpfe = fes.elementAt(h);
 911                             FlagState tmpfs = (FlagState)tmpfe.getTarget();
 912                             Vector<TaskDescriptor> tmptds = new Vector<TaskDescriptor>();
 913                             if((tmpSchedule.getTargetCoreTable() == null) || (!tmpSchedule.getTargetCoreTable().contains(tmpfs))) {
 914                                 // add up all possible cores' info
 915                                 Iterator it_edges = tmpfs.edges();
 916                                 while(it_edges.hasNext()) {
 917                                     TaskDescriptor tmptd = ((FEdge)it_edges.next()).getTask();
 918                                     if(!tmptds.contains(tmptd)) {
 919                                         tmptds.add(tmptd);
 920                                         Vector<Schedule> tmpcores = td2cores.get(tmptd);
 921                                         for(int m = 0; m < tmpcores.size(); ++m) {
 922                                             if(m != tmpSchedule.getCoreNum()) {
 923                                                 // if the FlagState can be fed to some multi-param tasks,
 924                                                 // need to record corresponding ally cores later
 925                                                 if(tmptd.numParameters() > 1) {
 926                                                     tmpSchedule.addAllyCore(tmpfs, tmpcores.elementAt(m).getCoreNum());
 927                                                 } else {
 928                                                     tmpSchedule.addTargetCore(tmpfs, tmpcores.elementAt(m).getCoreNum());
 929                                                 }
 930                                             }
 931                                         }
 932                                     }
 933                                 }
 934                             }
 935                         }
 936
 937                         if(cores.size() > 1) {
 938                             Vector<FlagState> tmpfss = tmpSchedule.getFStates4TD(td);
 939                             for(int h = 0; h < tmpfss.size(); ++h) {
 940                                 for(int l = 0; l < cores.size(); ++l) {
 941                                     if(l != k) {
 942                                         tmpSchedule.addAllyCore(tmpfss.elementAt(h), cores.elementAt(l).getCoreNum());
 943                                     }
 944                                 }
 945                             }
 946                         }
 947                     }
 948                 }
 949             }
 950
 951             this.schedulings.add(scheduling);
 952         }
 953
 954     }
 955
 956     public Vector<ScheduleNode> generateScheduling(Vector<ScheduleEdge> reduceEdges, int gid) {
 957         Vector<ScheduleNode> result = new Vector<ScheduleNode>();
 958
 959         // clone the ScheduleNodes
 960         Hashtable<ScheduleNode, Hashtable<ClassNode, ClassNode>> sn2hash = new Hashtable<ScheduleNode, Hashtable<ClassNode, ClassNode>>();
 961         Hashtable<ScheduleNode, ScheduleNode> sn2sn = new Hashtable<ScheduleNode, ScheduleNode>();
 962         for(int i = 0; i < this.scheduleNodes.size(); i++) {
 963             Hashtable<ClassNode, ClassNode> cn2cn = new Hashtable<ClassNode, ClassNode>();
 964             ScheduleNode tocopy = this.scheduleNodes.elementAt(i);
 965             ScheduleNode temp = (ScheduleNode)tocopy.clone(cn2cn, gid);
 966             result.add(i, temp);
 967             sn2hash.put(temp, cn2cn);
 968             sn2sn.put(tocopy, temp);
 969             cn2cn = null;
 970         }
 971         // clone the ScheduleEdges and merge those in reduceEdges at the same time
 972         Vector<ScheduleEdge> toMerge = new Vector<ScheduleEdge>();
 973         for(int i = 0; i < this.scheduleEdges.size(); i++) {
 974             ScheduleEdge sse = this.scheduleEdges.elementAt(i);
 975             ScheduleNode csource = sn2sn.get(sse.getSource());
 976             ScheduleNode ctarget = sn2sn.get(sse.getTarget());
 977             Hashtable<ClassNode, ClassNode> sourcecn2cn = sn2hash.get(csource);
 978             Hashtable<ClassNode, ClassNode> targetcn2cn = sn2hash.get(ctarget);
 979             ScheduleEdge se =  null;
 980             switch(sse.getType()) {
 981             case ScheduleEdge.NEWEDGE: {
 982                 se = new ScheduleEdge(ctarget, "new", sse.getFstate(), sse.getType(), gid);//new ScheduleEdge(ctarget, "new", sse.getClassDescriptor(), sse.getIsNew(), gid);
 983                 se.setProbability(sse.getProbability());
 984                 se.setNewRate(sse.getNewRate());
 985                 break;
 986             }
 987             case ScheduleEdge.TRANSEDGE: {
 988                 se = new ScheduleEdge(ctarget, "transmit", sse.getFstate(), sse.getType(), gid);//new ScheduleEdge(ctarget, "transmit", sse.getClassDescriptor(), false, gid);
 989                 break;
 990             }
 991             }
 992             se.setSourceCNode(sourcecn2cn.get(sse.getSourceCNode()));
 993             se.setTargetCNode(targetcn2cn.get(sse.getTargetCNode()));
 994             se.setFEdge(sse.getFEdge());
 995             se.setTargetFState(sse.getTargetFState());
 996             se.setIsclone(true);
 997             csource.addEdge(se);
 998             if(reduceEdges.contains(sse)) {
 999                 toMerge.add(se);
1000             }
1001             sourcecn2cn = null;
1002             targetcn2cn = null;
1003         }
1004         sn2hash = null;
1005         sn2sn = null;
1006
1007         for(int i = 0; i < toMerge.size(); i++) {
1008             ScheduleEdge sEdge = toMerge.elementAt(i);
1009             // merge this edge
1010             switch(sEdge.getType()) {
1011             case ScheduleEdge.NEWEDGE: {
1012                 try {
1013                     ((ScheduleNode)sEdge.getSource()).mergeSEdge(sEdge);
1014                 } catch(Exception e) {
1015                     e.printStackTrace();
1016                     System.exit(-1);
1017                 }
1018                 break;
1019             }
1020             case ScheduleEdge.TRANSEDGE: {
1021                 try {
1022                     ((ScheduleNode)sEdge.getSource()).mergeSEdge(sEdge);
1023                 } catch(Exception e) {
1024                     e.printStackTrace();
1025                     System.exit(-1);
1026                 }
1027                 break;
1028             }
1029             }
1030             result.removeElement(sEdge.getTarget());
1031             if(ScheduleEdge.NEWEDGE == sEdge.getType()) {
1032                 // As se has been changed into an internal edge inside a ScheduleNode,
1033                 // change the source and target of se from original ScheduleNodes into ClassNodes.
1034                 sEdge.setTarget(sEdge.getTargetCNode());
1035                 sEdge.setSource(sEdge.getSourceCNode());
1036                 sEdge.getTargetCNode().addEdge(sEdge);
1037             }
1038         }
1039         toMerge = null;
1040
1041         String path = "scheduling_" + gid + ".dot";
1042         SchedulingUtil.printScheduleGraph(path, result);
1043
1044         return result;
1045     }
1046
1047     class Combination{
1048         Combination tail;
1049         Object head;
1050         Vector factors;
1051         int selectNum;
1052         int resultNum;
1053
1054         public Combination(Vector factors, int selectNum) throws Exception{
1055             this.factors = factors;
1056             if(factors.size() < selectNum) {
1057                 throw new Exception("Error: selectNum > candidates' number in combination.");
1058             }
1059             if(factors.size() == selectNum) {
1060                 this.resultNum = 1;
1061                 head = null;
1062                 tail = null;
1063                 return;
1064             }
1065             this.head = this.factors.remove(0);
1066             if(selectNum == 1) {
1067                 this.resultNum = this.factors.size() + 1;
1068                 this.tail = null;
1069                 return;
1070             }
1071             this.tail = new Combination((Vector)this.factors.clone(), selectNum - 1);
1072             this.selectNum = selectNum;
1073             this.resultNum = 1;
1074             for(int i = factors.size(); i > selectNum; i--) {
1075                 this.resultNum *= i;
1076             }
1077             for(int i = factors.size() - selectNum; i > 0; i--) {
1078                 this.resultNum /= i;
1079             }
1080         }
1081
1082         public Vector next() {
1083             if(resultNum == 0) {
1084                 return null;
1085             }
1086             if(head == null) {
1087                 resultNum--;
1088                 Vector result = this.factors;
1089                 return result;
1090             }
1091             if(this.tail == null) {
1092                 resultNum--;
1093                 Vector result = new Vector();
1094                 result.add(this.head);
1095                 if(resultNum != 0) {
1096                     this.head = this.factors.remove(0);
1097                 }
1098                 return result;
1099             }
1100             Vector result = this.tail.next();
1101             if(result == null) {
1102                 if(this.factors.size() == this.selectNum) {
1103                     this.head = null;
1104                     this.tail = null;
1105                     result = this.factors;
1106                     this.resultNum--;
1107                     return result;
1108                 }
1109                 this.head = this.factors.remove(0);
1110                 try {
1111                     this.tail = new Combination((Vector)this.factors.clone(), selectNum - 1);
1112                     result = this.tail.next();
1113                 } catch(Exception e) {
1114                     e.printStackTrace();
1115                 }
1116
1117             }
1118             result.add(0, head);
1119             resultNum--;
1120             return result;
1121         }
1122     }
1123 }