001    package org.maltparser.parser.algorithm.twoplanar;
002    
003    import java.util.IdentityHashMap;
004    import java.util.Iterator;
005    import java.util.LinkedList;
006    import java.util.List;
007    import java.util.Map;
008    import java.util.SortedSet;
009    
010    import org.maltparser.core.exception.MaltChainedException;
011    import org.maltparser.core.syntaxgraph.DependencyStructure;
012    import org.maltparser.core.syntaxgraph.edge.Edge;
013    import org.maltparser.core.syntaxgraph.node.DependencyNode;
014    import org.maltparser.parser.DependencyParserConfig;
015    import org.maltparser.parser.Oracle;
016    import org.maltparser.parser.ParserConfiguration;
017    import org.maltparser.parser.history.GuideUserHistory;
018    import org.maltparser.parser.history.action.GuideUserAction;
019    /**
020     * @author Carlos Gomez Rodriguez
021     *
022     */
023    public class TwoPlanarArcEagerOracle extends Oracle {
024    
025            public TwoPlanarArcEagerOracle(DependencyParserConfig manager, GuideUserHistory history) throws MaltChainedException {
026                    super(manager, history);
027                    setGuideName("Two-Planar");
028            }
029            
030            /**
031             * Give this map an edge in the gold standard data, and it will tell you whether, given the links already created by the oracle, it is possible 
032             * to create the corresponding edge in one of the planes, in any plane, or in none at all (the latter will happen in non-2-planar structures). 
033             */
034            private static final int ANY_PLANE = 0;
035            private static final int FIRST_PLANE = 1;
036            private static final int SECOND_PLANE = 2;
037            private static final int NO_PLANE = 3;
038            private Map<Edge,Integer> linksToPlanes = new IdentityHashMap<Edge,Integer>();
039            
040            public GuideUserAction predict(DependencyStructure gold, ParserConfiguration config) throws MaltChainedException {
041                    TwoPlanarConfig planarConfig = (TwoPlanarConfig)config;
042                    DependencyStructure dg = planarConfig.getDependencyGraph();
043                    DependencyNode activeStackPeek = planarConfig.getActiveStack().peek();
044                    DependencyNode inactiveStackPeek = planarConfig.getInactiveStack().peek();
045                    int activeStackPeekIndex = activeStackPeek.getIndex();
046                    int inactiveStackPeekIndex = inactiveStackPeek.getIndex();
047                    int inputPeekIndex = planarConfig.getInput().peek().getIndex();
048                    
049                    //System.out.println("Initting crossings");
050                    
051                    if ( crossingsGraph == null ) initCrossingsGraph(gold);
052                    
053                    //System.out.println("Crossings initted");
054                    
055                    if (!activeStackPeek.isRoot() && gold.getTokenNode(activeStackPeekIndex).getHead().getIndex() == inputPeekIndex
056                                    && !checkIfArcExists ( dg , inputPeekIndex , activeStackPeekIndex ) )  {
057                            if ( planarConfig.getStackActivityState() == TwoPlanarConfig.FIRST_STACK )
058                            {
059                                    propagatePlaneConstraint(gold.getTokenNode(activeStackPeekIndex).getHeadEdge(), FIRST_PLANE );
060                            }
061                            else
062                            {
063                                    propagatePlaneConstraint(gold.getTokenNode(activeStackPeekIndex).getHeadEdge(), SECOND_PLANE );
064                            }
065                            //System.out.println("From " + inputPeekIndex + " to " + activeStackPeekIndex);
066                            return updateActionContainers(TwoPlanar.LEFTARC, gold.getTokenNode(activeStackPeekIndex).getHeadEdge().getLabelSet());  
067                    } 
068                    
069                    else if (gold.getTokenNode(inputPeekIndex).getHead().getIndex() == activeStackPeekIndex
070                                    && !checkIfArcExists ( dg , activeStackPeekIndex , inputPeekIndex ) ) {
071                            if ( planarConfig.getStackActivityState() == TwoPlanarConfig.FIRST_STACK )
072                            {
073                                    propagatePlaneConstraint(gold.getTokenNode(inputPeekIndex).getHeadEdge(), FIRST_PLANE );
074                            }
075                            else
076                            {
077                                    propagatePlaneConstraint(gold.getTokenNode(inputPeekIndex).getHeadEdge(), SECOND_PLANE );
078                            }
079                            //System.out.println("From " + activeStackPeekIndex + " to " + inputPeekIndex);
080                            return updateActionContainers(TwoPlanar.RIGHTARC, gold.getTokenNode(inputPeekIndex).getHeadEdge().getLabelSet());
081                    }
082                    
083                    else if (!inactiveStackPeek.isRoot() && gold.getTokenNode(inactiveStackPeekIndex).getHead().getIndex() == inputPeekIndex
084                                    && !checkIfArcExists ( dg , inputPeekIndex , inactiveStackPeekIndex ) )  {
085                            //need to create link, but on the other plane!!
086                            //TODO is this if branch really necessary? i.e. will this happen? (later branches already switch)
087                            //System.out.println("Switch one");
088                            return updateActionContainers(TwoPlanar.SWITCH, null);
089                    }
090                    
091                    else if (gold.getTokenNode(inputPeekIndex).getHead().getIndex() == inactiveStackPeekIndex
092                                    && !checkIfArcExists ( dg , inactiveStackPeekIndex , inputPeekIndex ) ) {
093                            //need to create link, but on the other plane!!
094                            //TODO is this if branch really necessary? i.e. will this happen? (later branches already switch)
095                            //System.out.println("Switch two");
096                            return updateActionContainers(TwoPlanar.SWITCH, null);
097                    }
098                    
099                    else if ( getFirstPendingLinkOnActivePlane(planarConfig,gold) != null )
100                    {
101                            //System.out.println("Reduce one");
102                            return updateActionContainers(TwoPlanar.REDUCE, null);
103                    }
104                    
105                    else if ( getFirstPendingLinkOnInactivePlane(planarConfig,gold) != null )
106                    {
107                            //System.out.println("Switch for reducing");
108                            return updateActionContainers(TwoPlanar.SWITCH, null);
109                    }
110                    
111                    //TODO: double reduce somehow? (check if reduced node is not covered by links of the other plane, or something like that).
112            
113                    else 
114                    {
115                            //System.out.println("Shift");
116                            return updateActionContainers(TwoPlanar.SHIFT, null);
117                    }
118                    
119            }
120            
121            private boolean checkIfArcExists ( DependencyStructure dg , int index1 , int index2 ) throws MaltChainedException
122            {
123                    return dg.getTokenNode(index2).hasHead() && dg.getTokenNode(index2).getHead().getIndex() == index1;
124            }
125            
126            public void finalizeSentence(DependencyStructure dependencyGraph) throws MaltChainedException {
127                    crossingsGraph = null;
128                    linksToPlanes.clear();
129            }
130            
131            public void terminate() throws MaltChainedException {}
132    
133            
134            
135            private static boolean cross ( Edge e1 , Edge e2 )
136            {
137                    int xSource = e1.getSource().getIndex();
138                    int xTarget = e1.getTarget().getIndex();
139                    int ySource = e2.getSource().getIndex();
140                    int yTarget = e2.getTarget().getIndex();
141                    int xMin = Math.min(xSource,xTarget);
142                    int xMax = Math.max(xSource,xTarget);
143                    int yMin = Math.min(ySource,yTarget);
144                    int yMax = Math.max(ySource,yTarget);
145                    //System.out.println(xMin+":"+xMax+":"+yMin+":"+yMax);
146                    return ( xMin < yMin && yMin < xMax && xMax < yMax ) || ( yMin < xMin && xMin < yMax && yMax < xMax );
147            }
148            
149            private Map<Edge,List<Edge>> crossingsGraph = null;
150            
151            private void initCrossingsGraph ( DependencyStructure dg )
152            {
153                    crossingsGraph = new IdentityHashMap<Edge,List<Edge>>();
154                    SortedSet<Edge> edges = dg.getEdges();
155                    //System.out.println(edges.size());
156                    //System.out.println(dg.nEdges());
157                    for (Iterator<Edge> iterator1 = edges.iterator(); iterator1.hasNext();) {
158                            Edge edge1 = iterator1.next();
159                            for (Iterator<Edge> iterator2 = edges.iterator(); iterator2.hasNext();) {
160                                    Edge edge2 = iterator2.next();
161                                    if ( edge1.getSource().getIndex() < edge2.getSource().getIndex() && cross(edge1,edge2) )
162                                    {
163                                            //System.out.println("Crossing!");
164                                            List<Edge> crossingEdge1 = crossingsGraph.get(edge1);
165                                            if ( crossingEdge1 == null ) { crossingEdge1 = new LinkedList<Edge>(); crossingsGraph.put(edge1, crossingEdge1); }
166                                            crossingEdge1.add(edge2);
167                                            List<Edge> crossingEdge2 = crossingsGraph.get(edge2);
168                                            if ( crossingEdge2 == null ) { crossingEdge2 = new LinkedList<Edge>(); crossingsGraph.put(edge2 , crossingEdge2); }
169                                            crossingEdge2.add(edge1);
170                                    }
171                            }
172                    }
173            }
174            
175            private List<Edge> getCrossingEdges ( Edge e )
176            {
177                    return crossingsGraph.get(e);
178            }
179            
180            private void setPlaneConstraint ( Edge e , int requiredPlane )
181            {
182                    linksToPlanes.put(e, requiredPlane);
183            }
184            
185            private int getPlaneConstraint ( Edge e )
186            {
187                    Integer constr = linksToPlanes.get(e);
188                    if ( constr == null )
189                    {
190                            setPlaneConstraint(e,ANY_PLANE);
191                            return ANY_PLANE;
192                    }
193                    else return constr;
194            }
195            
196            private void propagatePlaneConstraint ( Edge e , int requiredPlane )
197            {
198                    setPlaneConstraint(e,requiredPlane);
199                    if ( requiredPlane == FIRST_PLANE || requiredPlane == SECOND_PLANE )
200                    {
201                            List<Edge> crossingEdges = getCrossingEdges(e);
202                            if ( crossingEdges != null )
203                            {
204                                    for (Iterator<Edge> iterator = crossingEdges.iterator(); iterator.hasNext();) 
205                                    {
206                                            Edge crossingEdge = iterator.next();
207                                            assert ( requiredPlane == FIRST_PLANE || requiredPlane == SECOND_PLANE );
208                                            int crossingEdgeConstraint = getPlaneConstraint(crossingEdge);
209                                            if ( crossingEdgeConstraint == ANY_PLANE ) 
210                                            { 
211                                                    if ( requiredPlane == FIRST_PLANE )
212                                                            propagatePlaneConstraint(crossingEdge,SECOND_PLANE);
213                                                    else if ( requiredPlane == SECOND_PLANE )
214                                                            propagatePlaneConstraint(crossingEdge,FIRST_PLANE);
215                                            }
216                                            else if ( crossingEdgeConstraint == NO_PLANE ) ;                
217                                            else if ( crossingEdgeConstraint == FIRST_PLANE )
218                                            {
219                                                    if ( requiredPlane == FIRST_PLANE )
220                                                            propagatePlaneConstraint(crossingEdge,NO_PLANE);
221                                            }
222                                            else if ( crossingEdgeConstraint == SECOND_PLANE )
223                                            {
224                                                    if ( requiredPlane == SECOND_PLANE )
225                                                            propagatePlaneConstraint(crossingEdge,NO_PLANE);
226                                            }
227                                    }
228                            }
229                    }
230            }
231    
232            /**
233             * Decides in which plane link e should be created.
234             */
235            private int getLinkDecision ( Edge e , TwoPlanarConfig config )
236            {
237                    int constraint = getPlaneConstraint ( e );
238                    if ( constraint == ANY_PLANE )
239                    {
240                            //choose active plane
241                            if ( config.getStackActivityState() == TwoPlanarConfig.FIRST_STACK )
242                                    return FIRST_PLANE;
243                            else
244                                    return SECOND_PLANE;
245                    }
246                    else return constraint;
247            }
248            
249            
250            /**
251             * Gets the shortest pending link between (to or from) the input node and a node to the left of the top of the active stack,
252             * such that the link can be established on the active plane.
253             * @param config
254             * @return
255             */
256            private Edge getFirstPendingLinkOnActivePlane ( TwoPlanarConfig config , DependencyStructure gold ) throws MaltChainedException
257            {
258                    return getFirstPendingLinkOnPlane ( config , gold , config.getStackActivityState() == TwoPlanarConfig.FIRST_STACK ? FIRST_PLANE : SECOND_PLANE , 
259                                    config.getActiveStack().peek().getIndex() );
260            }
261            
262            /**
263             * Gets the shortest pending link between (to or from) the input node and a node to the left of the top of the inactive stack, 
264             * such that the link can be established on the inactive plane.
265             * @param config
266             * @return
267             */
268            private Edge getFirstPendingLinkOnInactivePlane ( TwoPlanarConfig config , DependencyStructure gold ) throws MaltChainedException
269            {
270                    return getFirstPendingLinkOnPlane ( config , gold , config.getStackActivityState() == TwoPlanarConfig.FIRST_STACK ? SECOND_PLANE : FIRST_PLANE ,
271                                    config.getInactiveStack().peek().getIndex() );
272            }
273            
274            private Edge getFirstPendingLinkOnAnyPlane ( TwoPlanarConfig config , DependencyStructure gold ) throws MaltChainedException
275            {
276                    Edge e1 = getFirstPendingLinkOnActivePlane ( config , gold );
277                    Edge e2 = getFirstPendingLinkOnInactivePlane ( config , gold );
278                    int left1 = Math.min(e1.getSource().getIndex(), e1.getTarget().getIndex());
279                    int left2 = Math.min(e2.getSource().getIndex(), e2.getTarget().getIndex());
280                    if ( left1 > left2 ) return e1;
281                    else return e2;
282            }
283            
284            /**
285             * Gets the shortest pending link between (to or from) the input node and a node to the left of rightmostLimit, such that the link
286             * can be established on the given plane.
287             * @param config
288             * @param plane
289             * @param rightmostLimit
290             * @return
291             */
292            private Edge getFirstPendingLinkOnPlane ( TwoPlanarConfig config , DependencyStructure gold ,  int plane , int rightmostLimit )
293                    throws MaltChainedException
294            {
295                    TwoPlanarConfig planarConfig = (TwoPlanarConfig)config;
296                    //DependencyStructure dg = planarConfig.getDependencyGraph(); -> no need, if rightmostLimit is well chosen, due to algorithm invariants
297                    int inputPeekIndex = planarConfig.getInput().peek().getIndex();
298                    
299                    Edge current = null;
300                    int maxIndex;
301                    if ( planarConfig.getRootHandling() == TwoPlanarConfig.NORMAL )
302                            maxIndex = -1; //count links from dummy root
303                    else
304                            maxIndex = 0; //do not count links from dummy root
305                    
306                    if ( gold.getTokenNode(inputPeekIndex).hasLeftDependent() && 
307                                    gold.getTokenNode(inputPeekIndex).getLeftmostDependent().getIndex() < rightmostLimit)
308                    {
309                            SortedSet<DependencyNode> dependents = gold.getTokenNode(inputPeekIndex).getLeftDependents();
310                            for (Iterator<DependencyNode> iterator = dependents.iterator(); iterator.hasNext();) {
311                                    DependencyNode dependent = (DependencyNode) iterator.next();
312                                    if ( dependent.getIndex() > maxIndex && dependent.getIndex() < rightmostLimit 
313                                                    && getLinkDecision(dependent.getHeadEdge(),config) == plane )
314                                    {
315                                            maxIndex = dependent.getIndex();
316                                            current = dependent.getHeadEdge();
317                                    }
318                            }
319                    }
320                    
321                    //at this point, current is the first left-pointing link, but we have to check right-pointing link as well
322                    
323                    //System.out.println("in" + inputPeekIndex + " rl" + rightmostLimit);
324                    if ( gold.getTokenNode(inputPeekIndex).getHead().getIndex() < rightmostLimit )
325                    {
326                            //System.out.println(":");
327                            if ( gold.getTokenNode(inputPeekIndex).getHead().getIndex() > maxIndex && 
328                                            getLinkDecision(gold.getTokenNode(inputPeekIndex).getHeadEdge(),config) == plane )
329                            {
330                                    //System.out.println("::");
331                                    current = gold.getTokenNode(inputPeekIndex).getHeadEdge();
332                            }
333                    }
334                    
335                    return current;
336                    
337                    
338            }
339            
340    
341    }