1 package net.obsearch.example;
2
3 import java.util.LinkedList;
4 import java.util.List;
5
6 import antlr.BaseAST;
7 import antlr.Token;
8 import antlr.collections.AST;
9
10 /*
11 OBSearch: a distributed similarity search engine
12 This project is to similarity search what 'bit-torrent' is to downloads.
13 Copyright (C) 2007 Arnoldo Jose Muller Molina
14
15 This program is free software: you can redistribute it and/or modify
16 it under the terms of the GNU General Public License as published by
17 the Free Software Foundation, either version 3 of the License, or
18 (at your option) any later version.
19
20 This program is distributed in the hope that it will be useful,
21 but WITHOUT ANY WARRANTY; without even the implied warranty of
22 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
23 GNU General Public License for more details.
24
25 You should have received a copy of the GNU General Public License
26 along with this program. If not, see <http://www.gnu.org/licenses/>.
27 */
28 /**
29 * This class provides extra functionality required by tree edit distance
30 * algorithms and the like.
31 * @author Arnoldo Jose Muller Molina
32 * @since 0.7
33 */
34
35 public final class SliceAST
36 extends BaseAST {
37
38 /**
39 * Serial version of the class.
40 */
41 private static final long serialVersionUID = -7669115912647058933L;
42
43 /**
44 * Number of children this node has.
45 */
46 public int decendants = -1;
47
48 /**
49 * The text of this node.
50 */
51 public String text;
52
53 /**
54 * Updates descendants information.
55 * @return An integer that represents the number of children of this node.
56 */
57 public final int updateDecendantInformationAux() {
58 decendants = 0;
59 SliceAST n = getLeftmostChild();
60 while (n != null) {
61 decendants += n.updateDecendantInformationAux();
62 n = (SliceAST) n.getNextSibling();
63 }
64 return decendants + 1;
65 }
66
67 /**
68 * Updates descendants information.
69 */
70 public final void updateDecendantInformation() {
71 decendants = updateDecendantInformationAux();
72 }
73
74 /**
75 * Returns the number of decendants of this node.
76 * @return The number of children of this node.
77 */
78 public final int getDescendants() {
79 return decendants;
80 }
81
82 /**
83 * @return The size of the Tree (includes the root node)
84 */
85 public final int getSize() {
86 return this.decendants;
87 }
88
89 /**
90 * Get the token text for this node.
91 * @return The text of the node.
92 */
93 @Override
94 public final String getText() {
95 return text;
96 }
97
98 /**
99 * Get the token type for this node.
100 * @return The type of node
101 */
102 @Override
103 public final int getType() {
104 return -1;
105 }
106
107 /**
108 * Initialize the node.
109 * @param t
110 * Node type
111 * @param txt
112 * Node tag
113 */
114 public final void initialize(final int t, final String txt) {
115 setType(t);
116 setText(txt);
117 }
118
119 /**
120 * Initialize the node from another node.
121 * @param t
122 * Another node.
123 */
124 public final void initialize(final AST t) {
125 setText(t.getText());
126 setType(t.getType());
127 }
128
129 /**
130 * Default constructor.
131 */
132 public SliceAST() {
133 }
134
135 /**
136 * Initialize the node.
137 * @param t
138 * Node type
139 * @param txt
140 * Node text
141 */
142 public SliceAST(final int t, final String txt) {
143 text = txt;
144 }
145
146 /**
147 * Initialize the node from a token.
148 * @param tok
149 * The token to use as initializer.
150 */
151 public SliceAST(final Token tok) {
152 text = tok.getText();
153 }
154
155 /**
156 * Clone the node with this constructor.
157 * @param t
158 * Another SliceAST
159 */
160 public SliceAST(final SliceAST t) {
161 text = t.text;
162 }
163
164 /**
165 * Initialize from the given token.
166 * @param tok
167 * A token.
168 */
169 @Override
170 public final void initialize(final Token tok) {
171 setText(tok.getText());
172 setType(tok.getType());
173 }
174
175 /**
176 * Set the token text for this node.
177 * @param text_
178 * The text to use.
179 */
180 @Override
181 public final void setText(final String text_) {
182 text = text_;
183 }
184
185 /**
186 * Set the token type for this node. Currently ignored.
187 * @param ttype_
188 * Type to use
189 */
190 @Override
191 public final void setType(final int ttype_) {
192
193 }
194
195 /**
196 * Get the leftmost child of this node.
197 * @return The leftmost child of this node.
198 */
199 public final SliceAST getLeftmostChild() {
200 return (SliceAST) super.getFirstChild();
201 }
202
203 /**
204 * Print out a child-sibling tree in LISP notation.
205 * @return A child-sibling tree in LISP notation
206 */
207 public final String prettyPrint() {
208 final SliceAST t = this;
209 String ts = "";
210 if (t.getFirstChild() != null)
211 ts += " (";
212 ts += " " + toString();
213 if (t.getFirstChild() != null) {
214 ts += ((SliceAST) t.getFirstChild()).prettyPrint();
215 }
216 if (t.getFirstChild() != null)
217 ts += " )";
218 if (t.getNextSibling() != null) {
219 ts += ((SliceAST) t.getNextSibling()).prettyPrint();
220 }
221 return ts;
222 }
223
224 /**
225 * Little speed up to the normal equalsTree method. Returns tree if this and
226 * t are equal
227 * @param t
228 * Another tree to compare.
229 * @return True if both trees are equal.
230 * @see antlr.BaseAST#equalsTree(antlr.collections.AST)
231 */
232 /*public final boolean equalsTree(final SliceAST t) {
233
234 if (t.decendants != this.decendants) { // little speed up! ;)
235 return false;
236 } else {
237 return super.equalsTree(t);
238 }
239 }*/
240
241 /** Is t an exact structural and equals() match of this tree. The
242 * 'this' reference is considered the start of a sibling list.
243 */
244 public final boolean equalsList(AST t) {
245 AST sibling;
246
247 // the empty tree is not a match of any non-null tree.
248 if (t == null) {
249 return false;
250 }
251
252 // Otherwise, start walking sibling lists. First mismatch, return false.
253 for (sibling = this;
254 sibling != null && t != null;
255 sibling = sibling.getNextSibling(), t = t.getNextSibling())
256 {
257 // as a quick optimization, check roots first.
258 if (!sibling.equals(t)) {
259 return false;
260 }
261 // if roots match, do full list match test on children.
262 if (sibling.getFirstChild() != null) {
263 if (!sibling.getFirstChild().equalsList(t.getFirstChild())) {
264 return false;
265 }
266 }
267 // sibling has no kids, make sure t doesn't either
268 else if (t.getFirstChild() != null) {
269 return false;
270 }
271 }
272 if (sibling == null && t == null) {
273 return true;
274 }
275 // one sibling list has more than the other
276 return false;
277 }
278
279 public final boolean equalsTree(AST t) {
280 // check roots first.
281 if (!this.equals(t)) return false;
282 // if roots match, do full list match test on children.
283 if (this.getFirstChild() != null) {
284 if (!this.getFirstChild().equalsList(t.getFirstChild())) return false;
285 }
286 // sibling has no kids, make sure t doesn't either
287 else if (t.getFirstChild() != null) {
288 return false;
289 }
290 return true;
291 }
292
293 public final boolean equals(AST t) {
294 SliceAST j = (SliceAST) t;
295 return t != null && this.text.equals(t.getText()) && this.getSize() == j.getSize();
296 }
297 /*
298 public final boolean equalsTree(SliceAST t) {
299 // check roots first.
300
301 if (!this.text.equals(t.text)) return false;
302 // if roots match, do full list match test on children.
303 if (this.getFirstChild() != null) {
304 if (!this.getFirstChild().equalsList(t.getFirstChild())) return false;
305 }
306 // sibling has no kids, make sure t doesn't either
307 else if (t.getFirstChild() != null) {
308 return false;
309 }
310 return true;
311 }*/
312
313 /** Get the first child of this node; null if not children */
314 public final AST getFirstChild() {
315 return down;
316 }
317
318 /** Get the next sibling in line after this one */
319 public final AST getNextSibling() {
320 return right;
321 }
322
323 /*
324 public final boolean equalsList(AST t) {
325 AST sibling;
326
327 // the empty tree is not a match of any non-null tree.
328 if (t == null) {
329 return false;
330 }
331
332 // Otherwise, start walking sibling lists. First mismatch, return false.
333 for (sibling = this;
334 sibling != null && t != null;
335 sibling = sibling.getNextSibling(), t = t.getNextSibling())
336 {
337 // as a quick optimization, check roots first.
338 if (! ((SliceAST)sibling).text.equals(((SliceAST)t).text)) {
339 return false;
340 }
341 // if roots match, do full list match test on children.
342 if (sibling.getFirstChild() != null) {
343 if (!sibling.getFirstChild().equalsList(t.getFirstChild())) {
344 return false;
345 }
346 }
347 // sibling has no kids, make sure t doesn't either
348 else if (t.getFirstChild() != null) {
349 return false;
350 }
351 }
352 if (sibling == null && t == null) {
353 return true;
354 }
355 // one sibling list has more than the other
356 return false;
357 }
358 */
359 /**
360 * @return A list of the nodes in depth first order
361 */
362 public final synchronized List < SliceAST > depthFirst() {
363 final LinkedList < SliceAST > res = new LinkedList < SliceAST >();
364 depthFirstAux(res);
365 return res;
366 }
367
368 /**
369 * Auxiliary function for {@link #depthFirst()}.
370 * @param res
371 * Where the result will be stored.
372 */
373 protected final void depthFirstAux(final LinkedList < SliceAST > res) {
374 res.add(this);
375 final SliceAST down = (SliceAST) getFirstChild();
376 if (down != null) {
377 down.depthFirstAux(res);
378 }
379 final SliceAST right = (SliceAST) getNextSibling();
380 if (right != null) {
381 right.depthFirstAux(res);
382 }
383 }
384
385 public final String toFuriaChanTree(){
386 StringBuilder sb = new StringBuilder();
387 toFuriaChanTreeAux(sb);
388 return sb.toString();
389 }
390
391 private final void toFuriaChanTreeAux(StringBuilder ts) {
392 AST t = this;
393 ts.append(this.toString());
394 if (t.getFirstChild() != null) {
395 ts.append("(");
396
397 ((SliceAST) t.getFirstChild()).toFuriaChanTreeAux(ts);
398
399 ts.append(")");
400 }
401 if(t.getNextSibling() != null){
402 ts.append(",");
403 ((SliceAST)t.getNextSibling()).toFuriaChanTreeAux(ts);
404 }
405 }
406
407 }