001    package org.maltparser.parser.algorithm.planar;
002    
003    import java.util.Stack;
004    
005    import org.maltparser.core.exception.MaltChainedException;
006    import org.maltparser.core.syntaxgraph.DependencyStructure;
007    import org.maltparser.core.syntaxgraph.edge.Edge;
008    import org.maltparser.core.syntaxgraph.node.DependencyNode;
009    import org.maltparser.parser.ParserConfiguration;
010    import org.maltparser.parser.TransitionSystem;
011    import org.maltparser.parser.history.GuideUserHistory;
012    import org.maltparser.parser.history.History;
013    import org.maltparser.parser.history.action.ComplexDecisionAction;
014    import org.maltparser.parser.history.action.GuideUserAction;
015    import org.maltparser.parser.transition.TransitionTable;
016    /**
017     * @author Carlos Gomez Rodriguez
018     *
019     */
020    public class Planar extends TransitionSystem {
021            protected static final int SHIFT = 1;
022            protected static final int REDUCE = 2;
023            protected static final int RIGHTARC = 3;
024            protected static final int LEFTARC = 4;
025            
026            public Planar() throws MaltChainedException {
027                    super();
028            }
029            
030            public void apply(GuideUserAction currentAction, ParserConfiguration config) throws MaltChainedException {
031                    PlanarConfig planarConfig = (PlanarConfig)config;
032                    Stack<DependencyNode> stack = planarConfig.getStack();
033                    Stack<DependencyNode> input = planarConfig.getInput();
034                    currentAction.getAction(actionContainers);
035                    Edge e = null;
036                    switch (transActionContainer.getActionCode()) {
037                    case LEFTARC:
038                            e = planarConfig.getDependencyStructure().addDependencyEdge(input.peek().getIndex(), stack.peek().getIndex());
039                            addEdgeLabels(e);
040                            break;
041                    case RIGHTARC:
042                            e = planarConfig.getDependencyStructure().addDependencyEdge(stack.peek().getIndex(), input.peek().getIndex());
043                            addEdgeLabels(e);
044                            break;
045                    case REDUCE:
046                            stack.pop();
047                            break;
048                    default: //SHIFT
049                            stack.push(input.pop()); 
050                            break;
051                    }
052            }
053            
054            public GuideUserAction getDeterministicAction(GuideUserHistory history, ParserConfiguration config) throws MaltChainedException {
055                    //PlanarConfig planarConfig = (PlanarConfig)config;
056                    //if (planarConfig.getRootHandling() != PlanarConfig.NORMAL && planarConfig.getStack().peek().isRoot()) {
057                    //      return updateActionContainers(history, Planar.SHIFT, null);
058                    //}
059                    //TODO: yeah, shift root
060                    return null;
061            }
062            
063            protected void addAvailableTransitionToTable(TransitionTable ttable) throws MaltChainedException {
064                    ttable.addTransition(SHIFT, "SH", false, null);
065                    ttable.addTransition(REDUCE, "RE", false, null);
066                    ttable.addTransition(RIGHTARC, "RA", true, null);
067                    ttable.addTransition(LEFTARC, "LA", true, null);
068            }
069            
070            protected void initWithDefaultTransitions(GuideUserHistory history) throws MaltChainedException {
071                    GuideUserAction currentAction = new ComplexDecisionAction((History)history);
072                    
073                    transActionContainer.setAction(SHIFT);
074                    transActionContainer.setAction(REDUCE);
075                    for (int i = 0; i < arcLabelActionContainers.length; i++) {
076                            arcLabelActionContainers[i].setAction(-1);
077                    }
078                    currentAction.addAction(actionContainers);
079            }
080            
081            public String getName() {
082                    return "planar arc-eager";
083            }
084    
085            public boolean permissible(GuideUserAction currentAction, ParserConfiguration config) throws MaltChainedException {
086                    currentAction.getAction(actionContainers);
087                    int trans = transActionContainer.getActionCode();
088                    PlanarConfig planarConfig = (PlanarConfig)config;
089                    DependencyNode stackPeek = planarConfig.getStack().peek();
090                    DependencyNode inputPeek = planarConfig.getInput().peek();
091                    DependencyStructure dg = planarConfig.getDependencyGraph();
092                    //int rootHandling = planarConfig.getRootHandling();
093                    boolean singleHeadConstraint = planarConfig.requiresSingleHead();
094                    boolean noCoveredRootsConstraint = planarConfig.requiresNoCoveredRoots();
095                    boolean acyclicityConstraint = planarConfig.requiresAcyclicity();
096                    boolean connectednessConstraintOnReduce = planarConfig.requiresConnectednessCheckOnReduce();
097                    boolean connectednessConstraintOnShift = planarConfig.requiresConnectednessCheckOnShift();
098                    if ((trans == LEFTARC || trans == RIGHTARC) && !isActionContainersLabeled()) {
099                            return false;
100                    }
101                    //if ((trans == LEFTARC || trans == REDUCE) && stackPeek.isRoot()) { 
102                    //      return false;
103                    //}
104                    if (trans == LEFTARC) {
105                            //avoid making root child of something
106                            if ( stackPeek.isRoot() ) 
107                                    return false;
108                            //enforce single-head constraint if present
109                            if ( stackPeek.hasHead() && singleHeadConstraint ) 
110                                    return false;
111                            //avoid two links being created from and to the same node
112                            if ( stackPeek.hasHead() && dg.getTokenNode(stackPeek.getIndex()).getHead().getIndex() == inputPeek.getIndex() )
113                                    return false;
114                            //enforce acyclicity constraint if present
115                            if ( acyclicityConstraint && stackPeek.findComponent().getIndex() == inputPeek.findComponent().getIndex() )
116                                    return false;
117                    }
118                    if (trans == RIGHTARC) {
119                            //enforce single-head constraint if present
120                            if ( inputPeek.hasHead() && singleHeadConstraint )
121                                    return false;
122                            //avoid two links being created from and to the same node
123                            if ( inputPeek.hasHead() && dg.getTokenNode(inputPeek.getIndex()).getHead().getIndex() == stackPeek.getIndex() )
124                                    return false;
125                            //enforce acyclicity constraint if present
126                            if ( acyclicityConstraint && stackPeek.findComponent().getIndex() == inputPeek.findComponent().getIndex() )
127                                    return false;
128                    }
129                    if (trans == REDUCE) {
130                            //do not reduce the dummy root
131                            if ( stackPeek.isRoot() ) 
132                                    return false;
133                            //enforce no-covered-roots constraint if present
134                            if ( !stackPeek.hasHead() && noCoveredRootsConstraint )
135                                    return false;
136                            //TODO does this line still make sense? (from Nivre arc-eager)
137                            //if ( !stackPeek.hasHead() && rootHandling == PlanarConfig.STRICT ) 
138                            //      return false;
139                            //enforce connectedness constraint if present
140                            if ( connectednessConstraintOnReduce )
141                            {
142                                    boolean path1 = ( stackPeek.findComponent().getIndex() == inputPeek.findComponent().getIndex() );
143                                    boolean path2;
144                                    if ( planarConfig.getStack().size() < 2 ) path2=false;
145                                    else
146                                    {
147                                            DependencyNode stackPrev = planarConfig.getStack().get(planarConfig.getStack().size()-2);
148                                            path2 = stackPrev.findComponent().getIndex() == stackPeek.findComponent().getIndex();
149                                    }
150                                    return path1 || path2;
151                            }
152                    }
153                    if ( trans == SHIFT )
154                    {
155                            if ( connectednessConstraintOnShift && planarConfig.getInput().size() == 1 ) //last word
156                            {
157                                    boolean path = ( planarConfig.getDependencyGraph().getTokenNode(1).findComponent().getIndex() == inputPeek.findComponent().getIndex() ); //require connection to 1st
158                                    return path;
159                            }
160                    }
161                    return true;
162            }
163            
164            public GuideUserAction defaultAction(GuideUserHistory history, ParserConfiguration configuration) throws MaltChainedException {
165                    return updateActionContainers(history, Planar.SHIFT, null);
166            }
167    }