Robust/src/Analysis/SSJava/BuildLattice.java

   1 package Analysis.SSJava;
   2
   3 import java.util.HashMap;
   4 import java.util.HashSet;
   5 import java.util.Iterator;
   6 import java.util.Map;
   7 import java.util.Set;
   8
   9 import IR.Descriptor;
  10 import Util.Pair;
  11
  12 public class BuildLattice {
  13
  14   public static int seed = 0;
  15   private LocationInference infer;
  16
  17   private final HNode topNode;
  18   private final HNode bottomNode;
  19
  20   public BuildLattice(LocationInference infer) {
  21     this.infer = infer;
  22     topNode = new HNode(infer.ssjava.TOP);
  23     bottomNode = new HNode(infer.ssjava.BOTTOM);
  24   }
  25
  26   public SSJavaLattice<String> buildLattice(Descriptor desc) {
  27
  28     HierarchyGraph inputGraph = infer.getSkeletonCombinationHierarchyGraph(desc);
  29     LocationSummary locSummary = infer.getLocationSummary(desc);
  30
  31     BasisSet basisSet = inputGraph.computeBasisSet();
  32     debug_print(inputGraph);
  33
  34     Family family = generateFamily(basisSet);
  35     Map<Set<Integer>, Set<Set<Integer>>> mapImSucc = coveringGraph(basisSet, family);
  36
  37     SSJavaLattice<String> lattice = buildLattice(basisSet, inputGraph, locSummary, mapImSucc);
  38     return lattice;
  39
  40   }
  41
  42   private SSJavaLattice<String> buildLattice(BasisSet basisSet, HierarchyGraph inputGraph,
  43       LocationSummary locSummary, Map<Set<Integer>, Set<Set<Integer>>> mapImSucc) {
  44
  45     SSJavaLattice<String> lattice =
  46         new SSJavaLattice<String>(SSJavaAnalysis.TOP, SSJavaAnalysis.BOTTOM);
  47
  48     Map<Set<Integer>, String> mapFToLocName = new HashMap<Set<Integer>, String>();
  49
  50     Set<Set<Integer>> keySet = mapImSucc.keySet();
  51     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
  52       Set<Integer> higher = (Set<Integer>) iterator.next();
  53
  54       String higherName = generateElementName(basisSet, inputGraph, mapFToLocName, higher);
  55
  56       HNode higherNode = inputGraph.getHNode(higherName);
  57       if (higherNode != null && higherNode.isSharedNode()) {
  58         lattice.addSharedLoc(higherName);
  59       }
  60       Set<Descriptor> descSet = inputGraph.getDescSetOfNode(higherNode);
  61       for (Iterator iterator2 = descSet.iterator(); iterator2.hasNext();) {
  62         Descriptor d = (Descriptor) iterator2.next();
  63         locSummary.addMapHNodeNameToLocationName(d.getSymbol(), higherName);
  64       }
  65       // locSummary.addMapHNodeNameToLocationName(higherName, higherName);
  66
  67       Set<Set<Integer>> lowerSet = mapImSucc.get(higher);
  68       for (Iterator iterator2 = lowerSet.iterator(); iterator2.hasNext();) {
  69         Set<Integer> lower = (Set<Integer>) iterator2.next();
  70
  71         String lowerName = generateElementName(basisSet, inputGraph, mapFToLocName, lower);
  72         locSummary.addMapHNodeNameToLocationName(lowerName, lowerName);
  73
  74         HNode lowerNode = inputGraph.getHNode(higherName);
  75         if (lowerNode != null && lowerNode.isSharedNode()) {
  76           lattice.addSharedLoc(lowerName);
  77         }
  78
  79         if (higher.size() == 0) {
  80           // empty case
  81           lattice.put(lowerName);
  82         } else {
  83           lattice.addRelationHigherToLower(higherName, lowerName);
  84         }
  85
  86       }
  87
  88     }
  89
  90     return lattice;
  91   }
  92
  93   public HNode getCombinationNodeInSCGraph(Descriptor desc, HNode nodeFromSimpleGraph) {
  94
  95     HierarchyGraph scGraph = infer.getSkeletonCombinationHierarchyGraph(desc);
  96
  97     if (nodeFromSimpleGraph.isSkeleton()) {
  98       return scGraph.getCurrentHNode(nodeFromSimpleGraph);
  99     }
 100
 101     Set<HNode> combineSkeletonNodeSet =
 102         infer.getSimpleHierarchyGraph(desc).getCombineSetByCombinationNode(nodeFromSimpleGraph);
 103     HNode combinationNodeInSCGraph =
 104         infer.getSkeletonCombinationHierarchyGraph(desc).getMapCombineNodeSetToCombinationNode()
 105             .get(combineSkeletonNodeSet);
 106
 107     // Set<HNode> combineSkeletonNodeSet =
 108     // infer.getSimpleHierarchyGraph(desc).getCombineSetByCombinationNode(simpleGraphNode);
 109     // HNode combinationNodeInSCGraph =
 110     // infer.getSkeletonCombinationHierarchyGraph(desc).getCombinationNode(combineSkeletonNodeSet);
 111     return combinationNodeInSCGraph;
 112   }
 113
 114   public SSJavaLattice<String> insertIntermediateNodesToStraightLine(Descriptor desc,
 115       SSJavaLattice<String> skeletonLattice) {
 116
 117     // perform DFS that starts from each skeleton/combination node and ends by another
 118     // skeleton/combination node
 119
 120     HierarchyGraph simpleGraph = infer.getSimpleHierarchyGraph(desc);
 121     HierarchyGraph scGraph = infer.getSkeletonCombinationHierarchyGraph(desc);
 122     LocationSummary locSummary = infer.getLocationSummary(desc);
 123
 124     SSJavaLattice<String> lattice = skeletonLattice.clone();
 125
 126     Set<HNode> visited = new HashSet<HNode>();
 127
 128     Set<HNode> nodeSet = simpleGraph.getNodeSet();
 129
 130     Map<TripleItem, String> mapIntermediateLoc = new HashMap<TripleItem, String>();
 131
 132     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
 133       HNode node = (HNode) iterator.next();
 134       System.out.println("node=" + node);
 135       if (node.isSkeleton() && (!visited.contains(node))) {
 136         visited.add(node);
 137
 138         Set<HNode> outSet = simpleGraph.getOutgoingNodeSet(node);
 139         for (Iterator iterator2 = outSet.iterator(); iterator2.hasNext();) {
 140           HNode outNode = (HNode) iterator2.next();
 141
 142           if (!outNode.isSkeleton()) {
 143             if (outNode.isCombinationNode()) {
 144               // expand the combination node 'outNode'
 145               // here we need to expand the corresponding combination location in the lattice
 146               HNode combinationNodeInSCGraph = getCombinationNodeInSCGraph(desc, outNode);
 147
 148               Set<HNode> combineSkeletonNodeSet =
 149                   simpleGraph.getCombineSetByCombinationNode(outNode);
 150
 151               // System.out.println("combineSkeletonNodeSet=" + combineSkeletonNodeSet);
 152
 153               Set<HNode> combinationNodeSet =
 154                   simpleGraph.getCombinationNodeSetByCombineNodeSet(combineSkeletonNodeSet);
 155
 156               // System.out.println("combinationNodeSet=" + combinationNodeSet);
 157
 158               Set<HNode> endNodeSetFromSimpleGraph =
 159                   simpleGraph.getDirectlyReachableSkeletonCombinationNodeFrom(outNode,
 160                       combinationNodeSet);
 161               // System.out.println("-endNodeSetFromSimpleGraph=" + endNodeSetFromSimpleGraph);
 162               Set<HNode> endCombNodeSet = new HashSet<HNode>();
 163               for (Iterator iterator3 = endNodeSetFromSimpleGraph.iterator(); iterator3.hasNext();) {
 164                 HNode endNode = (HNode) iterator3.next();
 165                 endCombNodeSet.add(getCombinationNodeInSCGraph(desc, endNode));
 166               }
 167               visited.add(outNode);
 168
 169               // follows the straight line up to another skeleton/combination node
 170               if (endCombNodeSet.size() > 0) {
 171                 endCombNodeSet =
 172                     removeTransitivelyReachToNode(desc, combinationNodeInSCGraph, endCombNodeSet);
 173                 recurDFS(desc, lattice, combinationNodeInSCGraph, endCombNodeSet, visited,
 174                     mapIntermediateLoc, 1, locSummary, outNode);
 175               }
 176
 177             } else {
 178               // we have a node that is neither combination or skeleton node
 179               System.out.println("%%%skeleton node=" + node + "  outNode=" + outNode);
 180               HNode startNode = scGraph.getCurrentHNode(node);
 181
 182               // if (node.getDescriptor() != null) {
 183               // // node is a skeleton node and it might be merged into another node in the SC
 184               // graph.
 185               // startNode = scGraph.getHNode(node.getDescriptor());
 186               // } else {
 187               // // this node has already been merged before the SC graph.
 188               // startNode = node;
 189               // }
 190
 191               Set<HNode> endNodeSetFromSimpleGraph =
 192                   simpleGraph.getDirectlyReachableSkeletonCombinationNodeFrom(outNode, null);
 193
 194               System.out.println("endNodeSetFromSimpleGraph=" + endNodeSetFromSimpleGraph
 195                   + "   from=" + outNode);
 196               Set<HNode> endCombNodeSet = new HashSet<HNode>();
 197               for (Iterator iterator3 = endNodeSetFromSimpleGraph.iterator(); iterator3.hasNext();) {
 198                 HNode endNode = (HNode) iterator3.next();
 199                 endCombNodeSet.add(getCombinationNodeInSCGraph(desc, endNode));
 200               }
 201               System.out.println("endCombNodeSet=" + endCombNodeSet);
 202               visited.add(outNode);
 203               if (endCombNodeSet.size() > 0) {
 204                 // follows the straight line up to another skeleton/combination node
 205                 endCombNodeSet = removeTransitivelyReachToNode(desc, startNode, endCombNodeSet);
 206               } else if (endCombNodeSet.size() == 0) {
 207                 // the outNode is (directly/transitively) connected to the bottom node
 208                 // therefore, we just add a dummy bottom HNode to the endCombNodeSet.
 209                 endCombNodeSet.add(bottomNode);
 210               }
 211               recurDFSNormalNode(desc, lattice, startNode, endCombNodeSet, visited,
 212                   mapIntermediateLoc, 1, locSummary, outNode);
 213             }
 214
 215           }
 216
 217         }
 218       } else if (!node.isSkeleton() && !node.isCombinationNode() && !node.isMergeNode()
 219           && !visited.contains(node)) {
 220
 221         // an intermediate node 'node' may be located between "TOP" location and a skeleton node
 222         int sizeIncomingNode = simpleGraph.getIncomingNodeSet(node).size();
 223
 224         if (sizeIncomingNode == 0) {
 225           // this node will be directly connected to the TOP location
 226           // start adding the following nodes from this node
 227
 228           Set<HNode> endNodeSetFromSimpleGraph =
 229               simpleGraph.getDirectlyReachableSkeletonCombinationNodeFrom(node, null);
 230
 231           Set<HNode> endCombNodeSet = new HashSet<HNode>();
 232           for (Iterator iterator3 = endNodeSetFromSimpleGraph.iterator(); iterator3.hasNext();) {
 233             HNode endNode = (HNode) iterator3.next();
 234             endCombNodeSet.add(getCombinationNodeInSCGraph(desc, endNode));
 235           }
 236
 237           HNode startNode = topNode;
 238           visited.add(startNode);
 239           if (endCombNodeSet.size() > 0) {
 240             // follows the straight line up to another skeleton/combination node
 241             // endCombNodeSet = removeTransitivelyReachToNode(desc, node, endCombNodeSet);
 242             recurDFSNormalNode(desc, lattice, startNode, endCombNodeSet, visited,
 243                 mapIntermediateLoc, 1, locSummary, node);
 244           }
 245
 246         }
 247
 248       }
 249     }
 250
 251     return lattice;
 252
 253   }
 254
 255   private Set<HNode> removeTransitivelyReachToNode(Descriptor desc, HNode startNode,
 256       Set<HNode> endNodeSet) {
 257
 258     // if an end node is not directly connected to the start node in the SC graph
 259     // replace it with a directly connected one which transitively reaches to it.
 260
 261     HierarchyGraph scGraph = infer.getSkeletonCombinationHierarchyGraph(desc);
 262     Set<HNode> newEndNodeSet = new HashSet<HNode>();
 263
 264     for (Iterator iterator = endNodeSet.iterator(); iterator.hasNext();) {
 265       HNode endNode = (HNode) iterator.next();
 266       if (scGraph.isDirectlyConnectedTo(startNode, endNode)) {
 267         newEndNodeSet.add(endNode);
 268       } else {
 269         HNode newEndNode =
 270             getDirectlyReachableNodeFromStartNodeReachToEndNode(scGraph, startNode, endNode);
 271         // System.out.println("#### old END NODE=" + endNode + " --->" + newEndNode);
 272         newEndNodeSet.add(newEndNode);
 273       }
 274     }
 275
 276     // System.out.println("removeTransitivelyReachToNode=" + endNodeSet + "  newSet=" +
 277     // newEndNodeSet);
 278
 279     return newEndNodeSet;
 280
 281   }
 282
 283   private HNode getDirectlyReachableNodeFromStartNodeReachToEndNode(HierarchyGraph scGraph,
 284       HNode startNode, HNode endNode) {
 285     Set<HNode> connected = new HashSet<HNode>();
 286     recurDirectlyReachableNodeFromStartNodeReachToEndNode(scGraph, startNode, endNode, connected);
 287     return connected.iterator().next();
 288   }
 289
 290   private void recurDirectlyReachableNodeFromStartNodeReachToEndNode(HierarchyGraph scGraph,
 291       HNode startNode, HNode curNode, Set<HNode> connected) {
 292
 293     Set<HNode> inNodeSet = scGraph.getIncomingNodeSet(curNode);
 294     for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) {
 295       HNode inNode = (HNode) iterator.next();
 296       if (inNode.equals(startNode)) {
 297         connected.add(curNode);
 298       } else {
 299         // System.out.println("inNode=" + inNode);
 300         recurDirectlyReachableNodeFromStartNodeReachToEndNode(scGraph, startNode, inNode, connected);
 301       }
 302     }
 303
 304   }
 305
 306   private void recurDFSNormalNode(Descriptor desc, SSJavaLattice<String> lattice, HNode startNode,
 307       Set<HNode> endNodeSet, Set<HNode> visited, Map<TripleItem, String> mapIntermediateLoc,
 308       int idx, LocationSummary locSummary, HNode curNode) {
 309
 310     TripleItem item = new TripleItem(startNode, endNodeSet, idx);
 311     // System.out.println("item=" + item);
 312     if (!mapIntermediateLoc.containsKey(item)) {
 313       // need to create a new intermediate location in the lattice
 314       String newLocName = "ILOC" + (seed++);
 315       String above;
 316       if (idx == 1) {
 317         above = startNode.getName();
 318       } else {
 319         int prevIdx = idx - 1;
 320         TripleItem prevItem = new TripleItem(startNode, endNodeSet, prevIdx);
 321         above = mapIntermediateLoc.get(prevItem);
 322       }
 323
 324       Set<String> belowSet = new HashSet<String>();
 325       for (Iterator iterator = endNodeSet.iterator(); iterator.hasNext();) {
 326         HNode endNode = (HNode) iterator.next();
 327         belowSet.add(endNode.getName());
 328       }
 329
 330       lattice.insertNewLocationBetween(above, belowSet, newLocName);
 331
 332       mapIntermediateLoc.put(item, newLocName);
 333     }
 334
 335     String locName = mapIntermediateLoc.get(item);
 336     HierarchyGraph graph = infer.getSimpleHierarchyGraph(desc);
 337
 338     Set<Descriptor> descSet = graph.getDescSetOfNode(curNode);
 339     for (Iterator iterator = descSet.iterator(); iterator.hasNext();) {
 340       Descriptor d = (Descriptor) iterator.next();
 341       locSummary.addMapHNodeNameToLocationName(d.getSymbol(), locName);
 342     }
 343     // locSummary.addMapHNodeNameToLocationName(curNode.getName(), locName);
 344
 345     Set<HNode> outSet = graph.getOutgoingNodeSet(curNode);
 346     for (Iterator iterator2 = outSet.iterator(); iterator2.hasNext();) {
 347       HNode outNode = (HNode) iterator2.next();
 348       if (!outNode.isSkeleton() && !outNode.isCombinationNode() && !visited.contains(outNode)) {
 349         visited.add(outNode);
 350         recurDFSNormalNode(desc, lattice, startNode, endNodeSet, visited, mapIntermediateLoc,
 351             idx + 1, locSummary, outNode);
 352       }
 353     }
 354
 355   }
 356
 357   private void recurDFS(Descriptor desc, SSJavaLattice<String> lattice,
 358       HNode combinationNodeInSCGraph, Set<HNode> endNodeSet, Set<HNode> visited,
 359       Map<TripleItem, String> mapIntermediateLoc, int idx, LocationSummary locSummary, HNode curNode) {
 360
 361     TripleItem item = new TripleItem(combinationNodeInSCGraph, endNodeSet, idx);
 362
 363     if (!mapIntermediateLoc.containsKey(item)) {
 364       // need to create a new intermediate location in the lattice
 365       String above;
 366       if (idx == 1) {
 367         String newLocName = combinationNodeInSCGraph.getName();
 368         mapIntermediateLoc.put(item, newLocName);
 369       } else {
 370         String newLocName = "ILOC" + (seed++);
 371         int prevIdx = idx - 1;
 372         TripleItem prevItem = new TripleItem(combinationNodeInSCGraph, endNodeSet, prevIdx);
 373         above = mapIntermediateLoc.get(prevItem);
 374
 375         Set<String> belowSet = new HashSet<String>();
 376         for (Iterator iterator = endNodeSet.iterator(); iterator.hasNext();) {
 377           HNode endNode = (HNode) iterator.next();
 378           belowSet.add(endNode.getName());
 379         }
 380         lattice.insertNewLocationBetween(above, belowSet, newLocName);
 381         mapIntermediateLoc.put(item, newLocName);
 382
 383       }
 384
 385     }
 386
 387     HierarchyGraph graph = infer.getSimpleHierarchyGraph(desc);
 388     String locName = mapIntermediateLoc.get(item);
 389     Set<Descriptor> descSet = graph.getDescSetOfNode(curNode);
 390     for (Iterator iterator = descSet.iterator(); iterator.hasNext();) {
 391       Descriptor d = (Descriptor) iterator.next();
 392       locSummary.addMapHNodeNameToLocationName(d.getSymbol(), locName);
 393     }
 394
 395     // System.out.println("-TripleItem=" + item);
 396     // System.out.println("-curNode=" + curNode.getName() + " locName=" + locName);
 397
 398     Set<HNode> outSet = graph.getOutgoingNodeSet(curNode);
 399     for (Iterator iterator2 = outSet.iterator(); iterator2.hasNext();) {
 400       HNode outNode = (HNode) iterator2.next();
 401       if (!outNode.isSkeleton() && !visited.contains(outNode)) {
 402         if (combinationNodeInSCGraph.equals(getCombinationNodeInSCGraph(desc, outNode))) {
 403           visited.add(outNode);
 404           recurDFS(desc, lattice, combinationNodeInSCGraph, endNodeSet, visited,
 405               mapIntermediateLoc, idx + 1, locSummary, outNode);
 406         }
 407       }
 408     }
 409
 410   }
 411
 412   private String generateElementName(BasisSet basisSet, HierarchyGraph inputGraph,
 413       Map<Set<Integer>, String> mapF2LocName, Set<Integer> F) {
 414
 415     if (mapF2LocName.containsKey(F)) {
 416       return mapF2LocName.get(F);
 417     }
 418
 419     HNode node = basisSet.getHNode(F);
 420     if (node != null) {
 421       mapF2LocName.put(F, node.getName());
 422       return node.getName();
 423     } else {
 424       if (inputGraph.BASISTOPELEMENT.equals(F)) {
 425         return SSJavaAnalysis.BOTTOM;
 426       } else {
 427         String str = "LOC" + (seed++);
 428         mapF2LocName.put(F, str);
 429         return str;
 430       }
 431     }
 432   }
 433
 434   private void resetCount(Map<Set<Integer>, Integer> mapFtoCount, Family family) {
 435     for (Iterator<Set<Integer>> iter = family.FIterator(); iter.hasNext();) {
 436       Set<Integer> F = iter.next();
 437       mapFtoCount.put(F, 0);
 438     }
 439   }
 440
 441   private Map<Set<Integer>, Set<Set<Integer>>> coveringGraph(BasisSet basisSet, Family family) {
 442
 443     Map<Set<Integer>, Integer> mapFtoCount = new HashMap<Set<Integer>, Integer>();
 444     Map<Set<Integer>, Set<Set<Integer>>> mapImSucc = new HashMap<Set<Integer>, Set<Set<Integer>>>();
 445
 446     // initialize COUNT(F) to 0 for all elements of the family
 447     resetCount(mapFtoCount, family);
 448
 449     for (Iterator<Set<Integer>> iter = family.FIterator(); iter.hasNext();) {
 450       Set<Integer> F = iter.next();
 451       Set<HNode> gammaF = family.getGamma(F);
 452
 453       Set<HNode> curHNodeSet = basisSet.getHNodeSet();
 454       curHNodeSet.removeAll(gammaF);
 455       Set<Set<Integer>> Bset = basisSet.getBasisSetByHNodeSet(curHNodeSet);
 456
 457       for (Iterator iterator = Bset.iterator(); iterator.hasNext();) {
 458         Set<Integer> B = (Set<Integer>) iterator.next();
 459
 460         Set<Integer> Fprime = new HashSet<Integer>();
 461         Fprime.addAll(F);
 462         Fprime.addAll(B);
 463
 464         // COUNT(F')++;
 465         mapFtoCount.put(Fprime, mapFtoCount.get(Fprime) + 1);
 466
 467         // if |gamma(F')|==COUNT(F') + |gamma(F)|
 468         int numGammaFprime = family.getGamma(Fprime).size();
 469         int countFprime = mapFtoCount.get(Fprime);
 470         int numGammaF = family.getGamma(F).size();
 471         if (numGammaFprime == (countFprime + numGammaF)) {
 472           // ImSucc(F)=IMSucc(F) union F'
 473           addImSucc(mapImSucc, F, Fprime);
 474         }
 475
 476       }
 477       resetCount(mapFtoCount, family);
 478     }
 479
 480     // System.out.println("mapImSucc=" + mapImSucc);
 481
 482     return mapImSucc;
 483   }
 484
 485   private Set<Set<Integer>> getImSucc(Map<Set<Integer>, Set<Set<Integer>>> mapImSucc, Set<Integer> F) {
 486     if (!mapImSucc.containsKey(F)) {
 487       mapImSucc.put(F, new HashSet<Set<Integer>>());
 488     }
 489     return mapImSucc.get(F);
 490   }
 491
 492   private void addImSucc(Map<Set<Integer>, Set<Set<Integer>>> mapImSucc, Set<Integer> F,
 493       Set<Integer> Fprime) {
 494
 495     if (!mapImSucc.containsKey(F)) {
 496       mapImSucc.put(F, new HashSet<Set<Integer>>());
 497     }
 498
 499     mapImSucc.get(F).add(Fprime);
 500
 501   }
 502
 503   private Family generateFamily(BasisSet basisSet) {
 504
 505     Family family = new Family();
 506
 507     for (Iterator<Set<Integer>> iterator = basisSet.basisIterator(); iterator.hasNext();) {
 508       Set<Integer> B = iterator.next();
 509
 510       Set<Pair<Set<Integer>, Set<HNode>>> tobeadded = new HashSet<Pair<Set<Integer>, Set<HNode>>>();
 511
 512       for (Iterator<Set<Integer>> iterator2 = family.FIterator(); iterator2.hasNext();) {
 513         Set<Integer> F = iterator2.next();
 514
 515         Set<Integer> Fprime = new HashSet<Integer>();
 516         Fprime.addAll(F);
 517         Fprime.addAll(B);
 518
 519         Set<HNode> gammaFPrimeSet = new HashSet<HNode>();
 520         gammaFPrimeSet.addAll(family.getGamma(F));
 521         gammaFPrimeSet.add(basisSet.getHNode(B));
 522
 523         if (!family.containsF(Fprime)) {
 524           Pair<Set<Integer>, Set<HNode>> pair =
 525               new Pair<Set<Integer>, Set<HNode>>(Fprime, gammaFPrimeSet);
 526           tobeadded.add(pair);
 527         } else {
 528           family.updateGammaF(Fprime, gammaFPrimeSet);
 529         }
 530       }
 531
 532       for (Iterator<Pair<Set<Integer>, Set<HNode>>> iterator2 = tobeadded.iterator(); iterator2
 533           .hasNext();) {
 534         Pair<Set<Integer>, Set<HNode>> pair = iterator2.next();
 535         family.addFElement(pair.getFirst());
 536         family.updateGammaF(pair.getFirst(), pair.getSecond());
 537       }
 538
 539     }
 540     return family;
 541   }
 542
 543   private void debug_print(HierarchyGraph inputGraph) {
 544     System.out.println("\nBuild Lattice:" + inputGraph.getName());
 545     // System.out.println("Node2Index:\n" + inputGraph.getMapHNodeToUniqueIndex());
 546     // System.out.println("Node2Basis:\n" + inputGraph.getMapHNodeToBasis());
 547   }
 548
 549 }
 550
 551 class Identifier {
 552   public HNode node;
 553   public int idx;
 554
 555   public Identifier(HNode n, int i) {
 556     node = n;
 557     idx = i;
 558   }
 559
 560   public int hashCode() {
 561     return node.hashCode() + idx;
 562   }
 563
 564   public boolean equals(Object obj) {
 565
 566     if (obj instanceof Identifier) {
 567       Identifier in = (Identifier) obj;
 568       if (node.equals(in.node) && idx == in.idx) {
 569         return true;
 570       }
 571     }
 572
 573     return false;
 574   }
 575
 576 }
 577
 578 class TripleItem {
 579   public HNode higherNode;
 580   public Set<HNode> lowerNodeSet;
 581   public int idx;
 582
 583   public TripleItem(HNode h, Set<HNode> l, int i) {
 584     higherNode = h;
 585     lowerNodeSet = l;
 586     idx = i;
 587   }
 588
 589   public int hashCode() {
 590
 591     int h = 0;
 592     if (higherNode != null) {
 593       h = higherNode.hashCode();
 594     }
 595
 596     return h + lowerNodeSet.hashCode() + idx;
 597   }
 598
 599   public boolean equals(Object obj) {
 600
 601     if (obj instanceof TripleItem) {
 602       TripleItem in = (TripleItem) obj;
 603       if ((higherNode == null || (higherNode != null && higherNode.equals(in.higherNode)))
 604           && lowerNodeSet.equals(in.lowerNodeSet) && idx == in.idx) {
 605         return true;
 606       }
 607     }
 608
 609     return false;
 610   }
 611
 612   public String toString() {
 613     return higherNode + "-" + idx + "->" + lowerNodeSet;
 614   }
 615 }