001package org.maltparser.core.syntaxgraph; 002 003import java.util.Iterator; 004import java.util.NoSuchElementException; 005import java.util.Set; 006import java.util.SortedMap; 007import java.util.SortedSet; 008import java.util.TreeMap; 009import java.util.TreeSet; 010 011import org.maltparser.core.exception.MaltChainedException; 012import org.maltparser.core.pool.ObjectPoolList; 013import org.maltparser.core.symbol.SymbolTableHandler; 014import org.maltparser.core.syntaxgraph.edge.Edge; 015import org.maltparser.core.syntaxgraph.edge.GraphEdge; 016import org.maltparser.core.syntaxgraph.node.ComparableNode; 017import org.maltparser.core.syntaxgraph.node.DependencyNode; 018import org.maltparser.core.syntaxgraph.node.Node; 019import org.maltparser.core.syntaxgraph.node.NonTerminal; 020import org.maltparser.core.syntaxgraph.node.NonTerminalNode; 021import org.maltparser.core.syntaxgraph.node.PhraseStructureNode; 022import org.maltparser.core.syntaxgraph.node.Root; 023import org.maltparser.core.syntaxgraph.node.TokenNode; 024/** 025* 026* 027* @author Johan Hall 028*/ 029public class PhraseStructureGraph extends Sentence implements PhraseStructure { 030 protected final ObjectPoolList<Edge> edgePool; 031 protected final SortedSet<Edge> graphEdges; 032 protected final SortedMap<Integer, NonTerminal> nonTerminalNodes; 033 protected final ObjectPoolList<NonTerminal> nonTerminalPool; 034 protected final Root root; 035 036 public PhraseStructureGraph(SymbolTableHandler symbolTables) throws MaltChainedException { 037 super(symbolTables); 038 039 root = new Root(); 040 root.setBelongsToGraph(this); 041 042 graphEdges = new TreeSet<Edge>(); 043 edgePool = new ObjectPoolList<Edge>() { 044 protected Edge create() { return new GraphEdge(); } 045 public void resetObject(Edge o) throws MaltChainedException { o.clear(); } 046 }; 047 048 nonTerminalNodes = new TreeMap<Integer,NonTerminal>(); 049 nonTerminalPool = new ObjectPoolList<NonTerminal>() { 050 protected NonTerminal create() throws MaltChainedException { return new NonTerminal(); } 051 public void resetObject(NonTerminal o) throws MaltChainedException { o.clear(); } 052 }; 053 } 054 055 public PhraseStructureNode addTerminalNode() throws MaltChainedException { 056 return addTokenNode(); 057 } 058 059 public PhraseStructureNode addTerminalNode(int index) throws MaltChainedException { 060 return addTokenNode(index); 061 } 062 063 public PhraseStructureNode getTerminalNode(int index) { 064 return getTokenNode(index); 065 } 066 067 public int nTerminalNode() { 068 return nTokenNode(); 069 } 070 071 public PhraseStructureNode addNonTerminalNode(int index) throws MaltChainedException { 072 NonTerminal node = nonTerminalPool.checkOut(); 073 node.setIndex(index); 074 node.setBelongsToGraph(this); 075 nonTerminalNodes.put(index,node); 076 return node; 077 } 078 079 public PhraseStructureNode addNonTerminalNode() throws MaltChainedException { 080 int index = getHighestNonTerminalIndex(); 081 if (index > 0) { 082 return addNonTerminalNode(index+1); 083 } 084 return addNonTerminalNode(1); 085 } 086 087 public PhraseStructureNode getNonTerminalNode(int index) throws MaltChainedException { 088 return nonTerminalNodes.get(index); 089 } 090 091 public int getHighestNonTerminalIndex() { 092 try { 093 return nonTerminalNodes.lastKey(); 094 } catch (NoSuchElementException e) { 095 return 0; 096 } 097 } 098 099 public Set<Integer> getNonTerminalIndices() { 100 return new TreeSet<Integer>(nonTerminalNodes.keySet()); 101 } 102 103 public boolean hasNonTerminals() { 104 return !nonTerminalNodes.isEmpty(); 105 } 106 107 public int nNonTerminals() { 108 return nonTerminalNodes.size(); 109 } 110 111 public PhraseStructureNode getPhraseStructureRoot() { 112 return root; 113 } 114 115 public Edge addPhraseStructureEdge(PhraseStructureNode parent, PhraseStructureNode child) throws MaltChainedException { 116 if (parent == null || child == null) { 117 throw new MaltChainedException("Parent or child node is missing."); 118 } else if (parent instanceof NonTerminalNode && !child.isRoot()) { 119 Edge e = edgePool.checkOut(); 120 e.setBelongsToGraph(this); 121 e.setEdge((Node)parent, (Node)child, Edge.PHRASE_STRUCTURE_EDGE); 122 graphEdges.add(e); 123 return e; 124 } else { 125 throw new MaltChainedException("Parent or child node is not of correct node type."); 126 } 127 } 128 129 public void removePhraseStructureEdge(PhraseStructureNode parent, PhraseStructureNode child) throws MaltChainedException { 130 if (parent == null || child == null) { 131 throw new MaltChainedException("Parent or child node is missing."); 132 } else if (parent instanceof NonTerminalNode && !child.isRoot()) { 133 for (Edge e : graphEdges) { 134 if (e.getSource() == parent && e.getTarget() == child) { 135 e.clear(); 136 graphEdges.remove(e); 137 if (e instanceof GraphEdge) { 138 edgePool.checkIn(e); 139 } 140 } 141 } 142 } else { 143 throw new SyntaxGraphException("Head node is not a root node or a terminal node."); 144 } 145 } 146 147 public Edge addSecondaryEdge(ComparableNode source, ComparableNode target) throws MaltChainedException { 148 if (source == null || target == null) { 149 throw new SyntaxGraphException("Head or dependent node is missing."); 150 } else if (!target.isRoot()) { 151 Edge e = edgePool.checkOut(); 152 e.setBelongsToGraph(this); 153 e.setEdge((Node)source, (Node)target, Edge.SECONDARY_EDGE); 154 graphEdges.add(e); 155 return e; 156 } 157 return null; 158 } 159 160 public void removeSecondaryEdge(ComparableNode source, ComparableNode target) throws MaltChainedException { 161 if (source == null || target == null) { 162 throw new SyntaxGraphException("Head or dependent node is missing."); 163 } else if (!target.isRoot()) { 164 Iterator<Edge> ie = ((Node)target).getIncomingEdgeIterator(); 165 while (ie.hasNext()) { 166 Edge e = ie.next(); 167 if (e.getSource() == source) { 168 ie.remove(); 169 graphEdges.remove(e); 170 edgePool.checkIn(e); 171 } 172 } 173 } 174 } 175 176 public int nEdges() { 177 return graphEdges.size(); 178 } 179 180 public SortedSet<Edge> getEdges() { 181 return graphEdges; 182 } 183 184 public boolean isContinuous() { 185 for (int index : nonTerminalNodes.keySet()) { 186 NonTerminalNode node = nonTerminalNodes.get(index); 187 if (!node.isContinuous()) { 188 return false; 189 } 190 } 191 return true; 192 } 193 194 public boolean isContinuousExcludeTerminalsAttachToRoot() { 195 for (int index : nonTerminalNodes.keySet()) { 196 NonTerminalNode node = nonTerminalNodes.get(index); 197 if (!node.isContinuousExcludeTerminalsAttachToRoot()) { 198 return false; 199 } 200 } 201 return true; 202 } 203 204// public void makeContinuous() throws MaltChainedException { 205// if (root != null) { 206// root.reArrangeChildrenAccordingToLeftAndRightProperDesendant(); 207// } 208// } 209 210 public void clear() throws MaltChainedException { 211 edgePool.checkInAll(); 212 graphEdges.clear(); 213 root.clear(); 214 root.setBelongsToGraph(this); 215 nonTerminalPool.checkInAll(); 216 nonTerminalNodes.clear(); 217 super.clear(); 218 } 219 220 public String toStringTerminalNode(TokenNode node) { 221 final StringBuilder sb = new StringBuilder(); 222 final DependencyNode depnode = node; 223 224 sb.append(node.toString().trim()); 225 if (depnode.hasHead()) { 226 sb.append('\t'); 227 try { 228 sb.append(depnode.getHead().getIndex()); 229 sb.append('\t'); 230 sb.append(depnode.getHeadEdge().toString()); 231 } catch (MaltChainedException e) { 232 System.err.println(e); 233 } 234 } 235 sb.append('\n'); 236 237 return sb.toString(); 238 } 239 240 public String toStringNonTerminalNode(NonTerminalNode node) { 241 final StringBuilder sb = new StringBuilder(); 242 243 sb.append(node.toString().trim()); 244 sb.append('\n'); 245 Iterator<Edge> ie = ((Node)node).getOutgoingEdgeIterator(); 246 while (ie.hasNext()) { 247 Edge e = ie.next(); 248 if (e.getTarget() instanceof TokenNode) { 249 sb.append(" T"); 250 sb.append(e.getTarget().getIndex()); 251 } 252 if (e.getTarget() instanceof NonTerminalNode) { 253 sb.append(" N"); 254 sb.append(e.getTarget().getIndex()); 255 } 256 sb.append('\t'); 257 sb.append(e.toString()); 258 sb.append('\n'); 259 } 260 return sb.toString(); 261 } 262 263 public String toString() { 264 final StringBuilder sb = new StringBuilder(); 265 for (int index : terminalNodes.keySet()) { 266 sb.append(toStringTerminalNode(terminalNodes.get(index))); 267 } 268 sb.append('\n'); 269 sb.append(toStringNonTerminalNode((NonTerminalNode)getPhraseStructureRoot())); 270 for (int index : nonTerminalNodes.keySet()) { 271 sb.append(toStringNonTerminalNode(nonTerminalNodes.get(index))); 272 } 273 274 return sb.toString(); 275 } 276}