001    package org.maltparser.core.syntaxgraph;
002    
003    import java.util.Iterator;
004    import java.util.NoSuchElementException;
005    import java.util.Set;
006    import java.util.SortedMap;
007    import java.util.SortedSet;
008    import java.util.TreeMap;
009    import java.util.TreeSet;
010    
011    import org.maltparser.core.exception.MaltChainedException;
012    import org.maltparser.core.pool.ObjectPoolList;
013    import org.maltparser.core.symbol.SymbolTableHandler;
014    import org.maltparser.core.syntaxgraph.edge.Edge;
015    import org.maltparser.core.syntaxgraph.edge.GraphEdge;
016    import org.maltparser.core.syntaxgraph.node.ComparableNode;
017    import org.maltparser.core.syntaxgraph.node.DependencyNode;
018    import org.maltparser.core.syntaxgraph.node.Node;
019    import org.maltparser.core.syntaxgraph.node.NonTerminal;
020    import org.maltparser.core.syntaxgraph.node.NonTerminalNode;
021    import org.maltparser.core.syntaxgraph.node.PhraseStructureNode;
022    import org.maltparser.core.syntaxgraph.node.Root;
023    import org.maltparser.core.syntaxgraph.node.TokenNode;
024    /**
025    *
026    *
027    * @author Johan Hall
028    */
029    public 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 boolean isContinuous() {
181                    for (int index : nonTerminalNodes.keySet()) {
182                            NonTerminalNode node = nonTerminalNodes.get(index);
183                            if (!node.isContinuous()) {
184                                    return false;
185                            }
186                    }
187                    return true;
188            }
189            
190            public boolean isContinuousExcludeTerminalsAttachToRoot() {
191                    for (int index : nonTerminalNodes.keySet()) {
192                            NonTerminalNode node = nonTerminalNodes.get(index);
193                            if (!node.isContinuousExcludeTerminalsAttachToRoot()) {
194                                    return false;
195                            }
196                    }
197                    return true;
198            }
199            
200    //      public void makeContinuous() throws MaltChainedException {
201    //              if (root != null) {
202    //                      root.reArrangeChildrenAccordingToLeftAndRightProperDesendant();
203    //              }
204    //      }
205            
206            public void clear() throws MaltChainedException {
207                    edgePool.checkInAll();
208                    graphEdges.clear();
209                    root.clear();
210                    root.setBelongsToGraph(this);
211                    nonTerminalPool.checkInAll();
212                    nonTerminalNodes.clear();
213                    super.clear();
214            }
215            
216            public String toStringTerminalNode(TokenNode node) {
217                    final StringBuilder sb = new StringBuilder();
218                    final DependencyNode depnode = node;
219    
220                    sb.append(node.toString().trim());
221                    if (depnode.hasHead()) {
222                            sb.append('\t');
223                            try {
224                                    sb.append(depnode.getHead().getIndex());
225                                    sb.append('\t');
226                                    sb.append(depnode.getHeadEdge().toString());
227                            } catch (MaltChainedException e) {
228                                    System.out.println(e);
229                            }
230                    }
231                    sb.append('\n');
232    
233                    return sb.toString();
234            }
235            
236            public String toStringNonTerminalNode(NonTerminalNode node) {
237                    final StringBuilder sb = new StringBuilder();
238    
239                    sb.append(node.toString().trim());
240                    sb.append('\n');
241                    Iterator<Edge> ie = ((Node)node).getOutgoingEdgeIterator();
242                    while (ie.hasNext()) {
243                            Edge e = ie.next();
244                            if (e.getTarget() instanceof TokenNode) {
245                                    sb.append("   T");
246                                    sb.append(e.getTarget().getIndex());
247                            }
248                            if (e.getTarget() instanceof NonTerminalNode) {
249                                    sb.append("   N");
250                                    sb.append(e.getTarget().getIndex());
251                            }
252                            sb.append('\t');
253                            sb.append(e.toString());
254                            sb.append('\n');
255                    }
256                    return sb.toString();
257            }
258            
259            public String toString() {
260                    final StringBuilder sb = new StringBuilder();
261                    for (int index : terminalNodes.keySet()) {
262                            sb.append(toStringTerminalNode(terminalNodes.get(index)));
263                    }
264                    sb.append('\n');
265                    sb.append(toStringNonTerminalNode((NonTerminalNode)getPhraseStructureRoot()));
266                    for (int index : nonTerminalNodes.keySet()) {
267                            sb.append(toStringNonTerminalNode(nonTerminalNodes.get(index)));
268                    }
269                    
270                    return sb.toString();
271            }
272    }