KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > SOFA > SOFAnode > Util > DFSRChecker > node > TreeNode


1 /*
2  * $Id: TreeNode.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.node;
19
20 import java.util.TreeSet JavaDoc;
21
22 import SOFA.SOFAnode.Util.DFSRChecker.DFSR.CheckingException;
23 import SOFA.SOFAnode.Util.DFSRChecker.state.State;
24 import SOFA.SOFAnode.Util.DFSRChecker.state.TransitionPairs;
25 import SOFA.SOFAnode.Util.DFSRChecker.utils.AnotatedProtocol;
26
27
28 /**
29  * This class represents the node of a tree describing the state space of an
30  * "execution".
31  */
32 abstract public class TreeNode implements Cloneable JavaDoc {
33
34     /** Creates a new instance of TreeNode */
35     public TreeNode(String JavaDoc protocol) {
36         this.protocol = protocol;
37         weight = -1;
38     }
39
40     /**
41      * @return the expected weight of this node, i.e. the size of automaton
42      * generated by its subtree.
43      */
44     abstract public long getWeight();
45
46     /**
47      * @return the vector of node's children.
48      */
49     public TreeNode[] getChildren() {
50         return nodes;
51     }
52
53     /**
54      * Changes the pointer at position of index to the newChild.
55      */
56     public void changeChild(int index, TreeNode newChild) throws ArrayIndexOutOfBoundsException JavaDoc {
57         nodes[index] = newChild;
58     }
59
60     /**
61      * Performs the forward cutting optimalization for this node. This is the
62      * default implementation for the majority of node types
63      *
64      * @param livingevents
65      * the already active events
66      * @return the "optimized" tree, i.e. without some nodes and edges
67      */
68     public TreeNode forwardCut(TreeSet JavaDoc livingevents) {
69         TreeNode active = null;
70         int cnt = 0;
71
72         for (int i = 0; i < nodes.length; ++i) {
73             nodes[i] = nodes[i].forwardCut(livingevents);
74             if (nodes[i] != null) {
75                 ++cnt;
76                 active = nodes[i];
77             }
78         }
79
80         // no child node's survived
81 if (cnt == 0)
82             return null;
83
84         // only one child node's survived and it hasn't been the only child
85 // else we have to return the original node
86 else if ((cnt == 1) && (nodes.length > 1))
87             return active;
88
89         // some of the child nodes have died
90 else if (nodes.length != cnt) {
91             TreeNode[] newchildren = new TreeNode[cnt];
92
93             for (int i = 0, j = 0; i < cnt; ++i) {
94                 while (nodes[j] == null)
95                     ++j;
96
97                 newchildren[i] = nodes[j++];
98             }
99
100             nodes = newchildren;
101
102         }
103
104         return this;
105     }
106
107     /**
108      * This method creates a new (deep) copy of this node. This is needed for forward
109      * cutting optimization.
110      *
111      * @return the deepcopy of this node
112      */
113     public TreeNode copy() {
114         TreeNode newnode = null;
115         try {
116             newnode = (TreeNode) this.clone();
117         } catch (CloneNotSupportedException JavaDoc e) {
118             return null;
119         }
120
121         newnode.nodes = new TreeNode[this.nodes.length];
122
123         for (int i = 0; i < this.nodes.length; ++i) {
124             newnode.nodes[i] = this.nodes[i].copy();
125         }
126
127         return newnode;
128     }
129     
130     /**
131      * Counts the number of leaves of this subtree
132      * @return the number of leaves
133      */
134     public int getLeafCount() {
135         int cnt = 0;
136         for (int i = 0; i < nodes.length; ++i)
137             cnt += nodes[i].getLeafCount();
138         
139         return cnt;
140     }
141     
142     /**
143      * @return AnotatedProtocol for printing and error trace understanding.
144      */
145     abstract public AnotatedProtocol getAnotatedProtocol(State state);
146
147     //--------------------------------------------------------------------------
148 /**
149      * @return the initial state of the automat
150      */
151     abstract public State getInitial();
152
153     /**
154      * @return true if this is an accepting state, false otherwise
155      */
156     abstract public boolean isAccepting(State state);
157
158     /**
159      * Retrieve the list of transition from a given state
160      *
161      * @param state find all transitions from this state
162      * @return the list of pairs of transitions (and their names)
163      * @throws InvalidParameterException means internal error - bad parameter passed to an eventnode
164      * @throws CheckingException means a composition error was detected
165      */
166     abstract public TransitionPairs getTransitions(State state) throws InvalidParameterException, CheckingException;
167
168     /**
169      * @return the symbolic name of the treenode denoting its type
170      */
171     abstract public String JavaDoc[] getTypeName();
172
173     //--------------------------------------------------------------------------
174 /** private attributes */
175
176     /**
177      * Child nodes of this node
178      */
179     protected TreeNode[] nodes;
180
181     /**
182      * The weight of the node - it is counted in a lazy way
183      */
184     protected long weight;
185
186     /**
187      * The protocol represented by this node
188      */
189     public String JavaDoc protocol;
190
191 }
192
193
Popular Tags