1 /*
2 * Zemucan: A Syntax Assistant for DB2
3 * Copyright (C) 2009, 2010 Andres Gomez Casanova
4 *
5 * This file is part of Zemucan.
6 *
7 * Zemucan is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU Lesser General Public License as published by
9 * the Free Software Foundation; either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * Zemucan is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU Lesser General Public License for more details.
16 *
17 * You should have received a copy of the GNU Lesser General Public License
18 * along with this library; if not, see <http://www.gnu.org/licenses/>.
19 *
20 * Contact:
21 * a n g o c a at y a h o o dot c o m
22 * Cra. 45 No 61 - 31, Bogota, Colombia.
23 *
24 * Author: $LastChangedBy: angoca $:
25 * Date: $LastChangedDate: 2011-03-06 09:19:05 -0500 (dom, 06 mar 2011) $:
26 * Revision: $LastChangedRevision: 1910 $:
27 * URL: $HeadURL: https://zemucan.svn.sourceforge.net/svnroot/zemucan/branches/zemucan_v1/source-code/graph/src/main/java/name/angoca/zemucan/core/graph/model/AbstractGraphNode.java $:
28 */
29 package name.angoca.zemucan.core.graph.model;
30
31 import java.util.ArrayList;
32 import java.util.Iterator;
33 import java.util.List;
34
35 import name.angoca.zemucan.core.graph.api.NullGraphNodeException;
36
37 import org.slf4j.Logger;
38 import org.slf4j.LoggerFactory;
39
40 /**
41 * Node of a graph. It could represent a word from the grammar or simply, it
42 * could assist to scan the graph.
43 * <p>
44 * Most of the changes history is in GraphNode.
45 * <p>
46 * <b>Control Version</b>
47 * <p>
48 * <ul>
49 * <li>1.0.0 Class creation.</li>
50 * </ul>
51 *
52 * @author Andres Gomez Casanova <a
53 * href="mailto:a n g o c a at y a h o o dot c o m">(AngocA)</a>
54 * @version 1.0.0 2010-08-28
55 */
56 public abstract class AbstractGraphNode implements
57 Comparable<AbstractGraphNode> {
58 /**
59 * Logger.
60 */
61 private static final Logger LOGGER = LoggerFactory
62 .getLogger(AbstractGraphNode.class);
63 /**
64 * Represents the destination ways (children) from the current node.
65 */
66 private final transient List<AbstractGraphNode> children;
67
68 /**
69 * Variable used when checking the graph that validates if this node comes
70 * from StartingNode.
71 */
72 private boolean comeFromStartingNode;
73
74 /**
75 * Variable used when checking the graph that validates if this node goes to
76 * EndingNode.
77 */
78 private boolean goToEndingNode;
79
80 /**
81 * Unique identifier of this token.
82 */
83 private final String id;
84 /**
85 * Complement to the identifier. This helps to associate the node to a
86 * graph, but it changes when two graphs are merged.
87 */
88 private String graphName;
89
90 /**
91 * Represents the source ways (parents) to the current node. This attribute
92 * is just for checking purposes and it does not play a role in the methods.
93 */
94 private final transient List<AbstractGraphNode> parents;
95
96 /**
97 * Creates an abstract node with a unique identifier and a associated graph.
98 * <p>
99 * The name of the graph is taken to complement the id of the node, because
100 * it changes when two graphs are merged.
101 *
102 * @param tokenId
103 * Unique id.
104 * @param graph
105 * Graph.
106 */
107 AbstractGraphNode(final String/* ! */tokenId, final Graph/* ! */graph) {
108 assert tokenId != null;
109 assert graph != null;
110
111 this.id = tokenId;
112 this.graphName = graph.getName();
113 this.children = new ArrayList<AbstractGraphNode>();
114
115 // For checking the graph.
116 this.parents = new ArrayList<AbstractGraphNode>();
117 this.comeFromStartingNode = false;
118 this.goToEndingNode = false;
119 }
120
121 /**
122 * Adds a possible child to the current token.
123 *
124 * @param node
125 * to connect with the current token.
126 * @throws AbstractGraphException
127 * When the GraphNode to add is null or there is a reference to
128 * StartingNode.
129 */
130 void addChild(final AbstractGraphNode/* ! */node)
131 throws AbstractGraphException {
132 if (node == null) {
133 throw new NullGraphNodeException();
134 } else if (node instanceof StartingNode) {
135 throw new ReferencingStartingNodeException(this.getId());
136 }
137 if (!this.children.contains(node)) {
138 this.children.add(node);
139 } else {
140 AbstractGraphNode.LOGGER.debug("Already existing child: {} in {}", //$NON-NLS-1$
141 node.id, this.id);
142 }
143 }
144
145 /**
146 * Adds a possible source or parent to the current node.
147 *
148 * @param node
149 * To reference to the parent node.
150 * @throws AbstractGraphException
151 * When the GraphNode to add is null or there is a reference
152 * from EndingNode
153 */
154 void addParent(final AbstractGraphNode/* ! */node)
155 throws AbstractGraphException {
156 if (node == null) {
157 throw new NullGraphNodeException();
158 } else if (node instanceof EndingNode) {
159 throw new ReferencingEndingNodeException(this.getId());
160 }
161 if (!this.parents.contains(node)) {
162 this.parents.add(node);
163 } else {
164 AbstractGraphNode.LOGGER.debug("Already existing parent: {} in {}", //$NON-NLS-1$
165 node.id, this.id);
166 }
167 }
168
169 /**
170 * Compares the two set of children, the current one with a given list.
171 *
172 * @param otherChildren
173 * Given list of children.
174 * @return If they have the same children.
175 */
176 private boolean compareChildren(
177 final List<AbstractGraphNode>/* <!>! */otherChildren) {
178 boolean equals = true;
179 final int size = otherChildren.size();
180 for (int i = 0; (i < size) && equals; i += 1) {
181 if (!this.containsChildren(otherChildren.get(i))) {
182 equals = false;
183 }
184 }
185 return equals;
186 }
187
188 /**
189 * Compares a two set of parents, the current one with a given list.
190 *
191 * @param otherParents
192 * Given list of parents.
193 * @return If they have the same parents.
194 */
195 private boolean compareParents(
196 final List<AbstractGraphNode>/* <!>! */otherParents) {
197 boolean equals = true;
198 int size;
199 size = otherParents.size();
200 for (int i = 0; (i < size) && equals; i += 1) {
201 if (!this.containsParent(otherParents.get(i))) {
202 equals = false;
203 }
204 }
205 return equals;
206 }
207
208 @Override
209 public int compareTo(final AbstractGraphNode/* ! */other) {
210 final int ret = this.id.compareTo(other.id);
211 // TODO v1.1 Test if the compare is reflexive
212 // if (other.compareTo(this) != ret){
213 // throw new RuntimeException("Different compare value");
214 // }
215 return ret;
216 }
217
218 /**
219 * Checks is the given graph token is part of one of the children of this
220 * graph token.
221 *
222 * @param graphNode
223 * Graph token to analyze.
224 * @return True is the graph token is part of the children of this token.
225 */
226 private boolean containsChildren(final AbstractGraphNode/* ! */graphNode) {
227 assert graphNode != null;
228
229 final int size = this.children.size();
230 boolean ret = false;
231 for (int i = 0; (i < size) && !ret; i += 1) {
232 if (graphNode.getId().equals(this.children.get(i).getId())) {
233 ret = true;
234 }
235 }
236 return ret;
237 }
238
239 /**
240 * Checks is the given graph token is part of one of the parents of this
241 * graph token.
242 *
243 * @param graphNode
244 * Graph token to analyze.
245 * @return True is the graph token is part of the parents of this token.
246 */
247 private boolean containsParent(final AbstractGraphNode/* ! */graphNode) {
248 assert graphNode != null;
249
250 final int size = this.parents.size();
251 boolean ret = false;
252 for (int i = 0; (i < size) && !ret; i += 1) {
253 if (graphNode.getId().equals(this.parents.get(i).getId())) {
254 ret = true;
255 }
256 }
257 return ret;
258 }
259
260 /*
261 * (non-Javadoc)
262 * @see java.lang.Object#equals(java.lang.Object)
263 */
264 @Override
265 public boolean equals(final Object/* ? */object) {
266 boolean equals = false;
267 if (object instanceof AbstractGraphNode) {
268 final AbstractGraphNode token = (AbstractGraphNode) object;
269 final List<AbstractGraphNode> otherChildren = token.children;
270 final List<AbstractGraphNode> otherParents = token.parents;
271 if (token.id.equals(this.id)
272 && (otherChildren.size() == this.children.size())
273 && (otherParents.size() == this.parents.size())) {
274 equals = this.compareChildren(otherChildren);
275 if (equals) {
276 equals = this.compareParents(otherParents);
277 }
278 }
279 }
280 return equals;
281 }
282
283 /**
284 * This method retrieves the children that come from this node. This is
285 * useful to analyze the graph, and to merge it.
286 *
287 * @return set of possibles ways.
288 */
289 final List<AbstractGraphNode>/* <!>! */getChildren() {
290 assert this.children != null;
291 boolean assertsEnabled = false;
292 // Intentional side-effect!
293 assert assertsEnabled = true;
294 if (assertsEnabled) {
295 for (final AbstractGraphNode token : this.children) {
296 assert token != null;
297 }
298 }
299 return this.children;
300 }
301
302 /**
303 * Returns the identifier of this token.
304 *
305 * @return the unique identifier of this token.
306 */
307 final String/* ! */getId() {
308 assert this.id != null;
309 return this.graphName + ":" + this.id;
310 }
311
312 /**
313 * This method retrieves all the parents that go to this node. This is
314 * useful to analyze the graph, and to merge it.
315 *
316 * @return set of parents.
317 */
318 final List<AbstractGraphNode>/* <!>! */getParents() {
319 assert this.parents != null;
320 boolean assertsEnabled = false;
321 // Intentional side-effect!
322 assert assertsEnabled = true;
323 if (assertsEnabled) {
324 for (final AbstractGraphNode token : this.parents) {
325 assert token != null;
326 }
327 }
328 return this.parents;
329 }
330
331 /**
332 * This method retrieves a copy of all the possibles ways that can be taken
333 * from this node. This is useful to scan the graph.
334 * <p>
335 * This method return a copy of the array. Not a copy of the elements.
336 *
337 * @return set of possibles ways.
338 */
339 public final Iterator<AbstractGraphNode>/* <!>! */getWays() {
340 final List<AbstractGraphNode> copy = new ArrayList<AbstractGraphNode>();
341 final List<AbstractGraphNode> currentChildren = this.getChildren();
342 for (final AbstractGraphNode node : currentChildren) {
343 // TODO v1.1 when NextNode will be used, this copy will not be done.
344 // Instead, a call to the ways of the NextNode will be done. It has
345 // to be careful to prevent to have infinitive loops, if one of the
346 // children of the node is already the parent or the node name.
347 copy.add(node);
348 }
349
350 final Iterator<AbstractGraphNode> iter = new Iterator<AbstractGraphNode>() {
351
352 /**
353 * Index of non reserved nodes.
354 */
355 private int indexNonReserved = 0;
356 /**
357 * Index of reserved nodes.
358 */
359 private int indexReserved = 0;
360 /**
361 * Next node to return.
362 */
363 private AbstractGraphNode next = null;
364
365 /*
366 * (non-Javadoc)
367 * @see java.util.Iterator#hasNext()
368 */
369 @Override
370 public boolean hasNext() {
371 this.next = null;
372 final int size = AbstractGraphNode.this.getChildren().size();
373 boolean found = false;
374 // First, the reserved nodes are checked.
375 if (this.indexReserved < size) {
376 while ((this.indexReserved < size) && !found) {
377 final AbstractGraphNode node = AbstractGraphNode.this
378 .getChildren().get(this.indexReserved);
379 if (node instanceof GraphNode) {
380 this.next = node;
381 found = true;
382 }
383 this.indexReserved += 1;
384 }
385 }
386 if ((this.indexNonReserved < size) && !found) {
387 // Then the non reserved node are checked.
388 while ((this.indexNonReserved < size) && !found) {
389 final AbstractGraphNode node = AbstractGraphNode.this
390 .getChildren().get(this.indexNonReserved);
391 if (node instanceof NonReservedGraphNode) {
392 this.next = node;
393 found = true;
394 }
395 this.indexNonReserved += 1;
396 }
397 }
398
399 return this.next != null;
400 }
401
402 /*
403 * (non-Javadoc)
404 * @see java.util.Iterator#next()
405 */
406 @Override
407 public AbstractGraphNode/* ! */next() {
408 assert this.next != null;
409 return this.next;
410 }
411
412 /*
413 * (non-Javadoc)
414 * @see java.util.Iterator#remove()
415 */
416 @Override
417 public void remove() {
418 // Nothing
419 }
420 };
421 return iter;
422 }
423
424 /*
425 * (non-Javadoc)
426 * @see java.lang.Object#hashCode()
427 */
428 @Override
429 public int hashCode() {
430 final int value = this.id.hashCode() + this.graphName.hashCode()
431 - this.children.size();
432 return value;
433 }
434
435 /**
436 * Returns the value if this node comes from StartingNode.
437 *
438 * @return the comeFromStartingNode.
439 */
440 boolean isComeFromStartingNode() {
441 return this.comeFromStartingNode;
442 }
443
444 /**
445 * Returns the true in this node goes to EndingNode.
446 *
447 * @return the goToEndingNode
448 */
449 boolean isGoToEndingNode() {
450 return this.goToEndingNode;
451 }
452
453 /**
454 * Removes a child from the list of children.
455 *
456 * @param node
457 * Node to remove.
458 * @throws NullGraphNodeException
459 * If the given node is null.
460 */
461 void removeChild(final AbstractGraphNode/* ! */node)
462 throws NullGraphNodeException {
463 if (node == null) {
464 throw new NullGraphNodeException();
465 }
466 this.children.remove(node);
467 }
468
469 /**
470 * Removes a child from the list of parents.
471 *
472 * @param node
473 * Node to remove.
474 * @throws NullGraphNodeException
475 * If the given node is null.
476 */
477 void removeParent(final AbstractGraphNode/* ! */node)
478 throws NullGraphNodeException {
479 if (node == null) {
480 throw new NullGraphNodeException();
481 }
482 this.parents.remove(node);
483 }
484
485 /**
486 * Analyzes the given token, and returns true if the current graph token
487 * represents that token.
488 *
489 * @param token
490 * token to analyze.
491 * @return true if the graph node represents that token.
492 */
493 public abstract boolean represent(final String/* ! */token);
494
495 /**
496 * Establishes if this node comes from the StartingNode. It's for checking
497 * the graph.
498 *
499 * @param comes
500 * True if this node comes from StartingNode.
501 */
502 void setComeFromStartingNode(final boolean comes) {
503 this.comeFromStartingNode = comes;
504 }
505
506 /**
507 * Establishes if this node goes to EndingNode. It's for checking the graph.
508 *
509 * @param goes
510 * True if this node goes to EndingNode.
511 */
512 void setGoToEndingNode(final boolean goes) {
513 this.goToEndingNode = goes;
514 }
515
516 /**
517 * Returns a string representation of a abstract graph token.
518 *
519 * @see java.lang.Object#toString()
520 * @return String representation of a graph token.
521 */
522 @Override
523 public String/* ! */toString() {
524 String ret = '{' + this.id + '\n' + this.parents.size();
525
526 if (this.parents.size() > 0) {
527 ret += "\t<"; //$NON-NLS-1$
528 for (final AbstractGraphNode node : this.parents) {
529 ret += node.id + "--"; //$NON-NLS-1$
530 }
531 ret = ret.substring(0, ret.length() - 2);
532 ret += '>';
533 }
534
535 ret += "\n" + this.children.size(); //$NON-NLS-1$
536 if (this.children.size() > 0) {
537 ret += "\t["; //$NON-NLS-1$
538 for (final AbstractGraphNode node : this.children) {
539 ret += node.id + "--"; //$NON-NLS-1$
540 }
541 ret = ret.substring(0, ret.length() - 2);
542 ret += ']';
543 }
544 ret += "\n" + this.comeFromStartingNode + '|' + this.goToEndingNode //$NON-NLS-1$
545 + '}';
546 assert ret != null;
547 return ret;
548 }
549
550 /**
551 * Sets the name of the associated graph.
552 *
553 * @param graphName
554 * Name of the graph.
555 */
556 void setGraphName(final String/* ! */graphName) {
557 this.graphName = graphName;
558 }
559
560 /**
561 * Retrieves the name of the associated graph.
562 *
563 * @return Name of the graph.
564 */
565 String/* ! */getGraphName() {
566 return this.graphName;
567 }
568
569 /**
570 * Concatenates a new graph name with the existing one. This is done for
571 * merging, because the graph name chances, but the old one has to be
572 * conserved.
573 *
574 * @param newGraphName
575 * Name of the new graph.
576 */
577 public void addGraphName(final String/* ! */newGraphName) {
578 this.graphName = newGraphName + ':' + this.graphName;
579 }
580 }