KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > edu > umd > cs > findbugs > ba > vna > MergeTree


1 /*
2  * FindBugs - Find Bugs in Java programs
3  * Copyright (C) 2005, University of Maryland
4  *
5  * This library is free software; you can redistribute it and/or
6  * modify it under the terms of the GNU Lesser General Public
7  * License as published by the Free Software Foundation; either
8  * version 2.1 of the License, or (at your option) any later version.
9  *
10  * This library is distributed in the hope that it will be useful,
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13  * Lesser General Public License for more details.
14  *
15  * You should have received a copy of the GNU Lesser General Public
16  * License along with this library; if not, write to the Free Software
17  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
18  */

19
20 package edu.umd.cs.findbugs.ba.vna;
21
22 import java.util.BitSet JavaDoc;
23 import java.util.HashMap JavaDoc;
24 import java.util.LinkedList JavaDoc;
25 import java.util.Map JavaDoc;
26
27 import edu.umd.cs.findbugs.SystemProperties;
28
29 /**
30  * Data structure to keep track of which input ValueNumbers were
31  * combined to produce which other output ValueNumbers.
32  *
33  * @author David Hovemeyer
34  */

35 public class MergeTree {
36     public static final boolean DEBUG = SystemProperties.getBoolean("vna.merge.debug");
37     
38     private ValueNumberFactory factory;
39     private Map JavaDoc<ValueNumber, BitSet JavaDoc> outputToInputMap;
40     
41     /**
42      * Constructor.
43      *
44      * @param factory the ValueNumberFactory
45      */

46     public MergeTree(ValueNumberFactory factory) {
47         this.factory = factory;
48         this.outputToInputMap = new HashMap JavaDoc<ValueNumber, BitSet JavaDoc>();
49     }
50     
51     /**
52      * Map an input ValueNumber to an output ValueNumber.
53      *
54      * @param input the input ValueNumber
55      * @param output the output ValueNumber
56      */

57     public void mapInputToOutput(ValueNumber input, ValueNumber output) {
58         BitSet JavaDoc inputSet = getInputSet(output);
59         inputSet.set(input.getNumber());
60         if (DEBUG) {
61             System.out.println(input.getNumber()+ "->" + output.getNumber());
62             System.out.println("Input set for " + output.getNumber() + " is now " + inputSet);
63         }
64     }
65
66     /**
67      * Get the set of input ValueNumbers which directly contributed to
68      * the given output ValueNumber.
69      *
70      * @param output the output ValueNumber
71      * @return the set of direct input ValueNumbers
72      */

73     public BitSet JavaDoc getInputSet(ValueNumber output) {
74         BitSet JavaDoc outputSet = outputToInputMap.get(output);
75         if (outputSet == null) {
76             if (DEBUG) {
77                 System.out.println("Create new input set for " + output.getNumber());
78             }
79             outputSet = new BitSet JavaDoc();
80             outputToInputMap.put(output, outputSet);
81         }
82         return outputSet;
83     }
84     
85     /**
86      * Get the transitive set of input ValueNumbers which contributed
87      * (directly or indirectly) to the given output ValueNumber.
88      *
89      * @param output the output ValueNumber
90      * @return the transitive set of input ValueNumbers
91      */

92     public BitSet JavaDoc getTransitiveInputSet(ValueNumber output) {
93         BitSet JavaDoc visited = new BitSet JavaDoc();
94         BitSet JavaDoc result = new BitSet JavaDoc();
95         
96         if (DEBUG) {
97             System.out.println("Output: " + output.getNumber());
98         }
99         
100         LinkedList JavaDoc<ValueNumber> workList = new LinkedList JavaDoc<ValueNumber>();
101         workList.addLast(output);
102         while (!workList.isEmpty()) {
103             ValueNumber valueNumber = workList.removeFirst();
104             if (DEBUG) {
105                 System.out.println("Check: " + valueNumber.getNumber());
106             }
107             visited.set(valueNumber.getNumber());
108             BitSet JavaDoc inputSet = getInputSet(valueNumber);
109             if (DEBUG) {
110                 System.out.println("\tInput set is " + inputSet);
111             }
112             result.or(inputSet);
113             for (int i = 0; i < factory.getNumValuesAllocated(); ++i) {
114                 if (inputSet.get(i) && !visited.get(i)) {
115                     if (DEBUG) {
116                         System.out.println("\tExplore: " + i);
117                     }
118                     workList.addLast(factory.forNumber(i));
119                 }
120             }
121         }
122         if (DEBUG) {
123             System.out.println("Result: " + result);
124         }
125         
126         return result;
127     }
128 }
129
Popular Tags