KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > SOFA > SOFAnode > Util > DFSRChecker > optimizer > OptExplicit


1 /*
2  * $Id: OptExplicit.java,v 1.4 2005/07/08 12:04:12 kofron Exp $
3  *
4  * Copyright 2004
5  * Distributed Systems Research Group
6  * Department of Software Engineering
7  * Faculty of Mathematics and Physics
8  * Charles University, Prague
9  *
10  * Copyright 2005
11  * Formal Methods In Software Engineering Group
12  * Institute of Computer Science
13  * Academy of Sciences of the Czech Republic
14  *
15  * This code was developed by Jan Kofron <kofron@nenya.ms.mff.cuni.cz>
16  */
17
18 package SOFA.SOFAnode.Util.DFSRChecker.optimizer;
19
20
21 import java.util.Stack JavaDoc;
22 import java.util.TreeMap JavaDoc;
23 import java.util.TreeSet JavaDoc;
24
25
26 import SOFA.SOFAnode.Util.DFSRChecker.DFSR.CheckingException;
27 import SOFA.SOFAnode.Util.DFSRChecker.DFSR.Options;
28 import SOFA.SOFAnode.Util.DFSRChecker.node.AdjustmentNode;
29 import SOFA.SOFAnode.Util.DFSRChecker.node.AndParallelNode;
30 import SOFA.SOFAnode.Util.DFSRChecker.node.CompositionNode;
31 import SOFA.SOFAnode.Util.DFSRChecker.node.ExplicitNode;
32 import SOFA.SOFAnode.Util.DFSRChecker.node.InvalidParameterException;
33 import SOFA.SOFAnode.Util.DFSRChecker.node.TreeNode;
34 import SOFA.SOFAnode.Util.DFSRChecker.state.Signature;
35 import SOFA.SOFAnode.Util.DFSRChecker.state.State;
36 import SOFA.SOFAnode.Util.DFSRChecker.state.TransitionPair;
37
38 /**
39  * This class is used for building the explicit automata. The class constructor
40  * is intended to obtain the top most treenode and to traverse the parse tree
41  * and built the explicit automata in suitable situations. The construction of
42  * the explicit automaton is done in similiar way as if the state space is
43  * traversed while checking the compliance.
44  */
45 public class OptExplicit {
46
47     /** Creates a new instance of ExplicitAutomaton */
48     public OptExplicit(TreeNode node, int threshold) {
49         this.node = node;
50         this.threshold = threshold;
51     }
52
53     /**
54      * Performs the DFS traversing and builds the explicit automata
55      *
56      * @return the topmost treenode
57      */
58     public TreeNode perform() throws InvalidParameterException {
59
60         Stack JavaDoc shouldbuild = new Stack JavaDoc(); // indicates whether an explicit
61 // automaton here would improve the performance
62 boolean buildflag = false;
63         Stack JavaDoc stack = new Stack JavaDoc();
64         int memoryleft = Options.totalmemory - Options.statememory;
65         memoryleft *= 3000;
66         
67         // this is a simple heuristic - each state has an
68 // average size of Signature.getSize() bytes
69 // and 2 transitions which results in the size of (3 * size) bytes per state, so
70 // there can be for about 300 / size states within 1kB and 300 000 / size states automaton
71 // within 1MB.
72
73         stack.push(node);
74         shouldbuild.push(new Boolean JavaDoc(buildflag));
75
76         while (stack.size() > 0) {
77             TreeNode actual = (TreeNode) stack.pop();
78             buildflag = ((Boolean JavaDoc) shouldbuild.pop()).booleanValue();
79
80             TreeNode[] children = actual.getChildren();
81
82             if ((actual instanceof AndParallelNode) || (actual instanceof AdjustmentNode) || (actual instanceof CompositionNode))
83                 buildflag = true;
84
85             for (int i = 0; i < children.length; ++i) {
86                 long weight = children[i].getWeight();
87                 if ((weight < threshold) && (buildflag)) {
88                     children[i] = buildExplicit(children[i]);
89                     memoryleft -= weight;
90                     threshold = memoryleft < threshold ? memoryleft : threshold;
91                 } else {
92                     stack.push(children[i]);
93                     shouldbuild.push(new Boolean JavaDoc(buildflag));
94                 }
95
96             }
97         }
98
99         // adjust the memory available for the state cache
100 Options.statememory += (Signature.getSize() * memoryleft / 300000);
101
102         return node;
103     }
104
105     /**
106      * Builds an explicit automaton from given subtree
107      *
108      * @param node
109      * the subtree sources for the explicit automaton
110      * @return the explicit automaton
111      */
112     private TreeNode buildExplicit(TreeNode node) throws InvalidParameterException {
113         TreeMap JavaDoc restrans = new TreeMap JavaDoc();
114         State resinit;
115         TreeSet JavaDoc resaccept = new TreeSet JavaDoc();
116         TreeSet JavaDoc visited = new TreeSet JavaDoc();
117
118         Stack JavaDoc stack = new Stack JavaDoc();
119
120         State actual = node.getInitial();
121         //actual.getSignature();
122
123         resinit = actual;
124         if (node.isAccepting(actual))
125             resaccept.add(actual);
126
127         stack.push(actual);
128
129         while (stack.size() > 0) {
130             actual = (State) stack.pop();
131             actual.getSignature();
132
133             if (!visited.contains(actual)) {
134
135                 if (node.isAccepting(actual))
136                     resaccept.add(actual);
137
138                 TransitionPair[] trans;
139                 try {
140                     trans = (TransitionPair[]) node.getTransitions(actual).transitions;
141                 }
142                 // only consent could generate this exception, but it shouldn't
143 // be optimized in this way
144 catch (CheckingException e) {
145                     throw new RuntimeException JavaDoc("Internal checker error");
146                 }
147
148                 restrans.put(actual, trans);
149
150                 for (int i = 0; i < trans.length; ++i) {
151                     stack.push(trans[i].state);
152                 }
153
154                 visited.add(actual);
155             }
156         }
157
158         return new ExplicitNode(resinit, restrans, resaccept, node.protocol, node);
159     }
160
161     //----------------------------------------------------------------
162 /**
163      * The top most treenode
164      */
165     private TreeNode node;
166
167     /**
168      * The treshold indicates how big automama should be conversed to explicit
169      * automata
170      */
171     private int threshold;
172
173 }
Popular Tags