001 package org.maltparser.core.syntaxgraph.node; 002 003 import java.util.NoSuchElementException; 004 import java.util.SortedSet; 005 import java.util.TreeSet; 006 007 import org.maltparser.core.exception.MaltChainedException; 008 import org.maltparser.core.helper.SystemLogger; 009 import org.maltparser.core.symbol.SymbolTable; 010 import org.maltparser.core.syntaxgraph.LabelSet; 011 import org.maltparser.core.syntaxgraph.PhraseStructure; 012 import org.maltparser.core.syntaxgraph.SyntaxGraphException; 013 import org.maltparser.core.syntaxgraph.TokenStructure; 014 import org.maltparser.core.syntaxgraph.edge.Edge; 015 import org.maltparser.core.syntaxgraph.headrules.Direction; 016 import org.maltparser.core.syntaxgraph.headrules.HeadRules; 017 018 public class NonTerminal extends GraphNode implements PhraseStructureNode, NonTerminalNode { 019 public final static int INDEX_OFFSET = 10000000; 020 protected final SortedSet<PhraseStructureNode> children; 021 protected PhraseStructureNode parent; 022 protected int index; 023 024 public NonTerminal() throws MaltChainedException { 025 super(); 026 index = -1; 027 children = new TreeSet<PhraseStructureNode>(); 028 } 029 030 public void addIncomingEdge(Edge in) throws MaltChainedException { 031 super.addIncomingEdge(in); 032 if (in.getType() == Edge.PHRASE_STRUCTURE_EDGE && in.getSource() instanceof PhraseStructureNode) { 033 parent = (PhraseStructureNode)in.getSource(); 034 } 035 } 036 037 public void removeIncomingEdge(Edge in) throws MaltChainedException { 038 super.removeIncomingEdge(in); 039 if (in.getType() == Edge.PHRASE_STRUCTURE_EDGE && in.getSource() instanceof PhraseStructureNode) { 040 if (in.getSource() == parent) { 041 this.parent = null; 042 } 043 } 044 } 045 046 public void addOutgoingEdge(Edge out) throws MaltChainedException { 047 super.addOutgoingEdge(out); 048 if (out.getType() == Edge.PHRASE_STRUCTURE_EDGE && out.getTarget() instanceof PhraseStructureNode) { 049 children.add((PhraseStructureNode)out.getTarget()); 050 // boolean notSorted = true; 051 // PhraseStructureNode prev = children.first(); 052 // for (PhraseStructureNode node : children) { 053 // if (prev != node) { 054 // if (node.compareTo(prev) == -1) { 055 // notSorted = false; 056 // System.out.println("NS"); 057 // break; 058 // } 059 // } 060 // prev = node; 061 // } 062 // if (notSorted == false) { 063 // SortedSet<PhraseStructureNode> tmp = new TreeSet<PhraseStructureNode>(children); 064 // children.clear(); 065 // for (PhraseStructureNode node : tmp) { 066 // children.add(node); 067 // } 068 // } 069 } 070 } 071 072 public void removeOutgoingEdge(Edge out) throws MaltChainedException { 073 super.removeOutgoingEdge(out); 074 if (out.getType() == Edge.PHRASE_STRUCTURE_EDGE && out.getTarget() instanceof PhraseStructureNode) { 075 children.remove(out.getTarget()); 076 } 077 } 078 079 public PhraseStructureNode getParent() { 080 return parent; 081 } 082 083 public Edge getParentEdge() throws MaltChainedException { 084 for (Edge e : incomingEdges) { 085 if (e.getSource() == parent && e.getType() == Edge.PHRASE_STRUCTURE_EDGE) { 086 return e; 087 } 088 } 089 return null; 090 } 091 092 public String getParentEdgeLabelSymbol(SymbolTable table) throws MaltChainedException { 093 for (Edge e : incomingEdges) { 094 if (e.getSource() == parent && e.getType() == Edge.PHRASE_STRUCTURE_EDGE) { 095 return e.getLabelSymbol(table); 096 } 097 } 098 return null; 099 } 100 101 public int getParentEdgeLabelCode(SymbolTable table) throws MaltChainedException { 102 for (Edge e : incomingEdges) { 103 if (e.getSource() == parent && e.getType() == Edge.PHRASE_STRUCTURE_EDGE) { 104 return e.getLabelCode(table); 105 } 106 } 107 return -1; 108 } 109 110 public boolean hasParentEdgeLabel(SymbolTable table) throws MaltChainedException { 111 for (Edge e : incomingEdges) { 112 if (e.getSource() == parent && e.getType() == Edge.PHRASE_STRUCTURE_EDGE) { 113 return e.hasLabel(table); 114 } 115 } 116 return false; 117 } 118 119 public int getHeight() { 120 int max = -1; 121 for (PhraseStructureNode node : children) { 122 if (node instanceof Token) { 123 if (max < 0) { 124 max = 0; 125 } 126 } else { 127 int nodeheight = ((NonTerminalNode)node).getHeight(); 128 if (max < nodeheight) { 129 max = nodeheight; 130 } 131 } 132 } 133 return max + 1; 134 } 135 136 public SortedSet<PhraseStructureNode> getChildren() { 137 return new TreeSet<PhraseStructureNode>(children); 138 } 139 140 public PhraseStructureNode getChild(int index) { 141 if (index >= 0 && index < children.size()) { 142 int i = 0; 143 for (PhraseStructureNode node : children) { 144 if (i == index) { 145 return node; 146 } 147 i++; 148 } 149 // return children.toArray(new PhraseStructureNode[children.size()])[index]; 150 } 151 return null; 152 } 153 154 public PhraseStructureNode getLeftChild() { 155 for (PhraseStructureNode node : children) { 156 return node; 157 } 158 return null; 159 } 160 161 public PhraseStructureNode getRightChild() { 162 int n = children.size(); 163 int i = 1; 164 for (PhraseStructureNode node : children) { 165 if (i == n) { 166 return node; 167 } 168 i++; 169 } 170 return null; 171 } 172 173 public int nChildren() { 174 return children.size(); 175 } 176 177 public boolean hasNonTerminalChildren() { 178 for (PhraseStructureNode node : children) { 179 if (node instanceof NonTerminal) { 180 return true; 181 } 182 } 183 return false; 184 } 185 186 public boolean hasTerminalChildren() { 187 for (PhraseStructureNode node : children) { 188 if (node instanceof Token) { 189 return true; 190 } 191 } 192 return false; 193 } 194 195 public TokenNode getLexicalHead(HeadRules headRules) throws MaltChainedException { 196 return identifyHead(headRules); 197 } 198 199 public PhraseStructureNode getHeadChild(HeadRules headRules) throws MaltChainedException { 200 return identifyHeadChild(headRules); 201 } 202 203 public TokenNode getLexicalHead() throws MaltChainedException { 204 return identifyHead(null); 205 } 206 207 public PhraseStructureNode getHeadChild() throws MaltChainedException { 208 return identifyHeadChild(null); 209 } 210 211 private PhraseStructureNode identifyHeadChild(HeadRules headRules) throws MaltChainedException { 212 PhraseStructureNode headChild = (headRules == null)?null:headRules.getHeadChild(this); 213 if (headChild == null) { 214 Direction direction = (headRules == null)?Direction.LEFT:headRules.getDefaultDirection(this); 215 if (direction == Direction.LEFT) { 216 if ((headChild = leftmostTerminalChild()) == null) { 217 headChild = leftmostNonTerminalChild(); 218 } 219 } else { 220 if ((headChild = rightmostTerminalChild()) == null) { 221 headChild = rightmostNonTerminalChild(); 222 } 223 } 224 } 225 return headChild; 226 } 227 228 public TokenNode identifyHead(HeadRules headRules) throws MaltChainedException { 229 PhraseStructureNode headChild = identifyHeadChild(headRules); 230 TokenNode lexicalHead = null; 231 if (headChild instanceof NonTerminalNode) { 232 lexicalHead = ((NonTerminalNode)headChild).identifyHead(headRules); 233 } else if (headChild instanceof TokenNode) { 234 lexicalHead = (TokenNode)headChild; 235 } 236 for (PhraseStructureNode node : children) { 237 if (node != headChild && node instanceof NonTerminalNode) { 238 ((NonTerminalNode)node).identifyHead(headRules); 239 } 240 } 241 return lexicalHead; 242 } 243 244 public int getIndex() { 245 return index; 246 } 247 248 public int getCompareToIndex() { 249 return index + INDEX_OFFSET; 250 } 251 252 private PhraseStructureNode leftmostTerminalChild() { 253 for (PhraseStructureNode node : children) { 254 if (node instanceof TokenNode) { 255 return node; 256 } 257 } 258 return null; 259 } 260 261 private PhraseStructureNode leftmostNonTerminalChild() { 262 for (PhraseStructureNode node : children) { 263 if (node instanceof NonTerminalNode) { 264 return node; 265 } 266 } 267 return null; 268 } 269 270 private PhraseStructureNode rightmostTerminalChild() { 271 try { 272 if (children.last() instanceof TokenNode) { 273 return children.last(); 274 } 275 } catch (NoSuchElementException e) { } 276 277 PhraseStructureNode candidate = null; 278 for (PhraseStructureNode node : children) { 279 if (node instanceof TokenNode) { 280 candidate = node; 281 } 282 } 283 return candidate; 284 } 285 286 private PhraseStructureNode rightmostNonTerminalChild() { 287 try { 288 if (children.last() instanceof NonTerminalNode) { 289 return children.last(); 290 } 291 } catch (NoSuchElementException e) { } 292 293 PhraseStructureNode candidate = null; 294 for (PhraseStructureNode node : children) { 295 if (node instanceof NonTerminalNode) { 296 candidate = node; 297 } 298 } 299 return candidate; 300 } 301 302 // protected void getPhraseDominationSet(SortedSet<PhraseStructureNode> dominationSet) { 303 // for (PhraseStructureNode node : children) { 304 // if (node instanceof TerminalNode) { 305 // dominationSet.add(node); 306 // } else { 307 // ((NonTerminal)node).getPhraseDominationSet(dominationSet); 308 // } 309 // } 310 // } 311 // 312 // private SortedSet<PhraseStructureNode> getPhraseDominationSet() { 313 // SortedSet<PhraseStructureNode> dominationSet = new TreeSet<PhraseStructureNode>(); 314 // getPhraseDominationSet(dominationSet); 315 // return dominationSet; 316 // } 317 318 319 320 public boolean isContinuous() { 321 int lcorner = getLeftmostProperDescendant().getIndex(); 322 int rcorner = getRightmostProperDescendant().getIndex(); 323 324 if (lcorner == rcorner) { 325 return true; 326 } 327 328 TokenNode terminal = ((TokenStructure)getBelongsToGraph()).getTokenNode(lcorner); 329 while (terminal.getIndex() != rcorner) { 330 PhraseStructureNode tmp = terminal.getParent(); 331 while (true) { 332 if (tmp == this) { 333 break; 334 } 335 if (tmp == null) { 336 return false; 337 } 338 tmp = tmp.getParent(); 339 } 340 terminal = terminal.getSuccessor(); 341 } 342 343 return true; 344 } 345 346 public boolean isContinuousExcludeTerminalsAttachToRoot() { 347 int lcorner = getLeftmostProperDescendant().getIndex(); 348 int rcorner = getRightmostProperDescendant().getIndex(); 349 350 if (lcorner == rcorner) { 351 return true; 352 } 353 354 TokenNode terminal = ((TokenStructure)getBelongsToGraph()).getTokenNode(lcorner); 355 while (terminal.getIndex() != rcorner) { 356 if (terminal.getParent() != null && terminal.getParent().isRoot()) { 357 terminal = terminal.getSuccessor(); 358 continue; 359 } 360 PhraseStructureNode tmp = terminal.getParent(); 361 while (true) { 362 if (tmp == this) { 363 break; 364 } 365 if (tmp == null) { 366 return false; 367 } 368 tmp = tmp.getParent(); 369 } 370 terminal = terminal.getSuccessor(); 371 } 372 return true; 373 } 374 375 @Override 376 public boolean isRoot() { 377 return false; 378 } 379 380 381 public ComparableNode getLeftmostProperDescendant() { 382 NonTerminalNode node = this; 383 PhraseStructureNode candidate = null; 384 while (node != null) { 385 candidate = node.getLeftChild(); 386 if (candidate == null || candidate instanceof TokenNode) { 387 return candidate; 388 } 389 node = (NonTerminalNode)candidate; 390 } 391 return null; 392 } 393 394 public ComparableNode getRightmostProperDescendant() { 395 NonTerminalNode node = this; 396 PhraseStructureNode candidate = null; 397 while (node != null) { 398 candidate = node.getRightChild(); 399 if (candidate == null || candidate instanceof TokenNode) { 400 return candidate; 401 } 402 node = (NonTerminalNode)candidate; 403 } 404 return null; 405 } 406 407 public ComparableNode getLeftmostDescendant() throws MaltChainedException { 408 return getLeftmostProperDescendant(); 409 } 410 411 public ComparableNode getRightmostDescendant() throws MaltChainedException { 412 return getRightmostProperDescendant(); 413 } 414 415 // public void reArrangeChildrenAccordingToLeftAndRightProperDesendant() throws MaltChainedException { 416 // int i = 0; 417 // int leftMostCorner = -1; 418 // int leftMostCornerChildIndex = -1; 419 // while (i < children.size()) { 420 // if (leftMostCorner == -1) { 421 // leftMostCorner = getChild(i).getLeftmostProperDescendantIndex(); 422 // leftMostCornerChildIndex = i; 423 // } else if (getChild(i) instanceof NonTerminal && getChild(i).getLeftmostProperDescendantIndex() < leftMostCorner) { 424 // NonTerminalNode child = (NonTerminal)getChild(i); 425 // PhraseStructureNode leftMostCornerChild = getChild(leftMostCornerChildIndex); 426 // if (leftMostCornerChild.getParent() != null) { 427 // LabelSet labelSet = leftMostCornerChild.getParentEdge().getLabelSet(); 428 // ((PhraseStructure)getBelongsToGraph()).removePhraseStructureEdge(this, leftMostCornerChild); 429 // Edge e = ((PhraseStructure)getBelongsToGraph()).addPhraseStructureEdge(child, leftMostCornerChild); 430 // e.addLabel(labelSet); 431 // } 432 // child.reArrangeChildrenAccordingToLeftAndRightProperDesendant(); 433 // i = -1; 434 // leftMostCorner = -1; 435 // leftMostCornerChildIndex = -1; 436 // } else { 437 // leftMostCorner = getChild(i).getLeftmostProperDescendantIndex(); 438 // leftMostCornerChildIndex = i; 439 // } 440 // i++; 441 // } 442 // 443 // for (int j = 0, n=children.size(); j < n; j++) { 444 // if (getChild(j) instanceof NonTerminalNode) { 445 // ((NonTerminalNode)getChild(j)).reArrangeChildrenAccordingToLeftAndRightProperDesendant(); 446 // } 447 // } 448 // } 449 450 @Override 451 public void setIndex(int index) throws MaltChainedException { 452 if (index > 0) { 453 this.index = index; //INDEX_OFFSET+index; 454 } else { 455 throw new SyntaxGraphException("The index must be a positive index"); 456 } 457 458 } 459 460 public void clear() throws MaltChainedException { 461 super.clear(); 462 children.clear(); 463 parent = null; 464 index = -1; 465 } 466 467 @Override 468 public int compareTo(ComparableNode o) { 469 final int BEFORE = -1; 470 final int EQUAL = 0; 471 final int AFTER = 1; 472 if ( this == o ) return EQUAL; 473 try { 474 final int thisLCorner = this.getLeftmostProperDescendantIndex(); 475 final int thatLCorner = (o instanceof TokenNode)?o.getCompareToIndex():o.getLeftmostProperDescendantIndex(); 476 final int thisRCorner = this.getRightmostProperDescendantIndex(); 477 final int thatRCorner = (o instanceof TokenNode)?o.getCompareToIndex():o.getRightmostProperDescendantIndex(); 478 479 // if (thisLCorner == -1 || thatLCorner == -1) { 480 // if (thisRCorner < thatRCorner) return BEFORE; 481 // if (thisRCorner > thatRCorner) return AFTER; 482 // } 483 // if (thisRCorner == -1 || thatRCorner == -1) { 484 // if (thisLCorner < thatLCorner) return BEFORE; 485 // if (thisLCorner > thatLCorner) return AFTER; 486 // } 487 488 if (thisLCorner != -1 && thatLCorner != -1 && thisRCorner != -1 && thatRCorner != -1) { 489 if (thisLCorner < thatLCorner && thisRCorner < thatRCorner) return BEFORE; 490 if (thisLCorner > thatLCorner && thisRCorner > thatRCorner) return AFTER; 491 if (thisLCorner > thatLCorner && thisRCorner < thatRCorner) return BEFORE; 492 if (thisLCorner < thatLCorner && thisRCorner > thatRCorner) return AFTER; 493 } else { 494 if (thisLCorner != -1 && thatLCorner != -1) { 495 if (thisLCorner < thatLCorner) return BEFORE; 496 if (thisLCorner > thatLCorner) return AFTER; 497 } 498 if (thisRCorner != -1 && thatRCorner != -1) { 499 if (thisRCorner < thatRCorner) return BEFORE; 500 if (thisRCorner > thatRCorner) return AFTER; 501 } 502 } 503 504 505 506 // final int thisLCorner = this.getLeftmostDescendantIndex(); 507 // final int thatLCorner = (o instanceof TerminalNode)?o.getCompareToIndex():o.getLeftmostDescendantIndex(); 508 // final int thisRCorner = this.getRightmostDescendantIndex(); 509 // final int thatRCorner = (o instanceof TerminalNode)?o.getCompareToIndex():o.getRightmostDescendantIndex(); 510 // 511 // if (thisLCorner == -1 || thatLCorner == -1) { 512 // if (thisRCorner < thatRCorner) return BEFORE; 513 // if (thisRCorner > thatRCorner) return AFTER; 514 // } 515 // if (thisRCorner == -1 || thatRCorner == -1) { 516 // if (thisLCorner < thatLCorner) return BEFORE; 517 // if (thisLCorner > thatLCorner) return AFTER; 518 // } 519 // if (thisLCorner < thatLCorner && thisRCorner < thatRCorner) return BEFORE; 520 // if (thisLCorner > thatLCorner && thisRCorner > thatRCorner) return AFTER; 521 // if (thisLCorner > thatLCorner && thisRCorner < thatRCorner) return BEFORE; 522 // if (thisLCorner < thatLCorner && thisRCorner > thatRCorner) return AFTER; 523 524 // System.out.println(thisLCorner + " " + thatLCorner + " " +thisRCorner + " " + thatRCorner); 525 526 // int thisCorner = this.getLeftmostDescendantIndex(); 527 // int thatCorner = (o instanceof TerminalNode)?o.getCompareToIndex():o.getLeftmostDescendantIndex(); 528 // if (thisCorner != -1 && thatCorner != -1) { 529 // if (thisCorner < thatCorner) return BEFORE; 530 // if (thisCorner > thatCorner) return AFTER; 531 // } 532 // thisCorner = this.getRightmostDescendantIndex(); 533 // thatCorner = (o instanceof TerminalNode)?o.getCompareToIndex():o.getRightmostDescendantIndex(); 534 // if (thisCorner != -1 && thatCorner != -1) { 535 // if (thisCorner < thatCorner) return BEFORE; 536 // if (thisCorner > thatCorner) return AFTER; 537 // } 538 } catch (MaltChainedException e) { 539 if (SystemLogger.logger().isDebugEnabled()) { 540 SystemLogger.logger().debug("",e); 541 } else { 542 SystemLogger.logger().error(e.getMessageChain()); 543 } 544 System.exit(1); 545 } 546 if (this.getCompareToIndex() < o.getCompareToIndex()) return BEFORE; 547 if (this.getCompareToIndex() > o.getCompareToIndex()) return AFTER; 548 return super.compareTo(o); 549 } 550 551 public boolean equals(Object obj) { 552 if (this == obj) return true; 553 if (!(obj instanceof NonTerminal)) return false; 554 return super.equals(obj); 555 } 556 557 public int hashCode() { 558 return 31 * 7 + super.hashCode(); 559 } 560 561 public String toString() { 562 final StringBuilder sb = new StringBuilder(); 563 sb.append(getIndex()); 564 sb.append('\t'); 565 if (getLabelTypes() != null) { 566 for (SymbolTable table : getLabelTypes()) { 567 try { 568 sb.append(getLabelSymbol(table)); 569 } catch (MaltChainedException e) { 570 System.err.println("Print error : "+e.getMessageChain()); 571 } 572 sb.append('\t'); 573 } 574 } 575 return sb.toString(); 576 } 577 578 }