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}