View Javadoc

1   // Solver.java, created Jun 15, 2003 1:02:13 AM by joewhaley
2   // Copyright (C) 2003 John Whaley <jwhaley@alum.mit.edu>
3   // Licensed under the terms of the GNU LGPL; see COPYING for details.
4   package joeq.Compiler.Dataflow;
5   
6   import java.util.Collection;
7   import java.util.Comparator;
8   import java.util.Iterator;
9   import java.util.List;
10  import java.util.SortedSet;
11  import java.util.TreeSet;
12  import jwutil.collections.MapFactory;
13  import jwutil.graphs.Graph;
14  import jwutil.graphs.Traversals;
15  
16  /***
17   * SortedSetSolver
18   * 
19   * @author John Whaley
20   * @version $Id: SortedSetSolver.java 1931 2004-09-22 22:17:47Z joewhaley $
21   */
22  public class SortedSetSolver extends WorklistSolver {
23      
24      /*** All locations in the graph, stored in a list. */
25      protected List allNodes;
26      /*** Worklist of locations, sorted by priority. */
27      protected SortedSet worklist;
28      /*** Location ordering function. */
29      protected Comparator ordering;
30  
31      public SortedSetSolver(MapFactory f) {
32          super(f);
33      }
34      public SortedSetSolver() {
35          super();
36      }
37      public SortedSetSolver(Comparator c) {
38          super();
39          setOrder(c);
40      }
41  
42      /*** Set the default ordering for this solver.
43       * 
44       * @param c comparator object that implements the ordering
45       */
46      public void setOrder(Comparator c) {
47          this.ordering = c;
48      }
49      
50      /* (non-Javadoc)
51       * @see joeq.Compiler.Dataflow.Solver#initialize(joeq.Compiler.Dataflow.Problem, jwutil.graphs.Graph)
52       */
53      public void initialize(Problem p, Graph graph) {
54          super.initialize(p, graph);
55          allNodes = Traversals.reversePostOrder(graphNavigator, boundaries);
56          if (TRACE) System.out.println("Order: "+allNodes);
57      }
58  
59      /* (non-Javadoc)
60       * @see joeq.Compiler.Dataflow.Solver#allLocations()
61       */
62      public Iterator allLocations() {
63          return allNodes.iterator();
64      }
65  
66      /* (non-Javadoc)
67       * @see Compiler.Dataflow.WorklistSolver#initializeWorklist()
68       */
69      protected void initializeWorklist() {
70          worklist = new TreeSet(ordering);
71          worklist.addAll(allNodes);
72          worklist.removeAll(boundaries);
73      }
74      
75      /* (non-Javadoc)
76       * @see joeq.Compiler.Dataflow.WorklistSolver#hasNext()
77       */
78      protected boolean hasNext() {
79          return !worklist.isEmpty();
80      }
81  
82      /* (non-Javadoc)
83       * @see joeq.Compiler.Dataflow.WorklistSolver#pull()
84       */
85      protected Object pull() {
86          Iterator i = worklist.iterator();
87          Object o = i.next();
88          i.remove();
89          return o;
90      }
91      
92      /* (non-Javadoc)
93       * @see joeq.Compiler.Dataflow.WorklistSolver#pushAll(java.util.Collection)
94       */
95      protected void pushAll(Collection c) {
96          worklist.addAll(c);
97      }
98  }