001package org.maltparser.parser.algorithm.stack;
002
003import java.util.ArrayList;
004import java.util.Stack;
005
006import org.maltparser.core.exception.MaltChainedException;
007import org.maltparser.core.syntaxgraph.DependencyStructure;
008import org.maltparser.core.syntaxgraph.node.DependencyNode;
009import org.maltparser.parser.DependencyParserConfig;
010import org.maltparser.parser.Oracle;
011import org.maltparser.parser.ParserConfiguration;
012import org.maltparser.parser.history.GuideUserHistory;
013import org.maltparser.parser.history.action.GuideUserAction;
014/**
015 * @author Johan Hall
016 *
017 */
018public class SwapLazyOracle extends Oracle {
019        private ArrayList<Integer> swapArray;
020        private boolean swapArrayActive = false;
021        
022        public SwapLazyOracle(DependencyParserConfig manager, GuideUserHistory history) throws MaltChainedException {
023                super(manager, history);
024                setGuideName("swaplazy");
025                swapArray = new ArrayList<Integer>();
026        }
027        
028        public GuideUserAction predict(DependencyStructure gold, ParserConfiguration configuration) throws MaltChainedException {
029                final StackConfig config = (StackConfig)configuration;
030                final Stack<DependencyNode> stack = config.getStack();
031
032                if (!swapArrayActive) {
033                        createSwapArray(gold);
034                        swapArrayActive = true;
035                }
036                if (stack.size() < 2) {
037                        return updateActionContainers(NonProjective.SHIFT, null);
038                } else {
039                        final DependencyNode left = stack.get(stack.size()-2);
040                        final DependencyNode right = stack.get(stack.size()-1);
041                        final int leftIndex = left.getIndex();
042                        final int rightIndex = right.getIndex();
043                        if (swapArray.get(leftIndex) > swapArray.get(rightIndex) && necessarySwap(gold, config.getDependencyGraph(), right, config.getInput())) {
044                                return updateActionContainers(NonProjective.SWAP, null);
045                        } else if (!left.isRoot() && gold.getTokenNode(leftIndex).getHead().getIndex() == rightIndex 
046                                        && nodeComplete(gold, config.getDependencyGraph(), leftIndex)) {
047                                return updateActionContainers(NonProjective.LEFTARC, gold.getTokenNode(leftIndex).getHeadEdge().getLabelSet());
048                        } else if (gold.getTokenNode(rightIndex).getHead().getIndex() == leftIndex 
049                                        && nodeComplete(gold, config.getDependencyGraph(), rightIndex)) {
050                                return updateActionContainers(NonProjective.RIGHTARC, gold.getTokenNode(rightIndex).getHeadEdge().getLabelSet());
051                        } else {
052                                return updateActionContainers(NonProjective.SHIFT, null);
053                        }
054                }
055        }
056        
057        private boolean nodeComplete(DependencyStructure gold, DependencyStructure parseDependencyGraph, int nodeIndex) {
058                final DependencyNode goldNode = gold.getTokenNode(nodeIndex);
059                final DependencyNode parseNode =  parseDependencyGraph.getTokenNode(nodeIndex);
060                if (goldNode.hasLeftDependent()) {
061                        if (!parseNode.hasLeftDependent()) {
062                                return false;
063                        } else if (goldNode.getLeftmostDependent().getIndex() != parseNode.getLeftmostDependent().getIndex()) {
064                                return false;
065                        }
066                }
067                if (goldNode.hasRightDependent()) {
068                        if (!parseNode.hasRightDependent()) {
069                                return false;
070                        } else if (goldNode.getRightmostDependent().getIndex() != parseNode.getRightmostDependent().getIndex()) {
071                                return false;
072                        }
073                }
074                return true;
075        }
076        
077        private boolean necessarySwap(DependencyStructure gold, DependencyStructure parse, DependencyNode node, Stack<DependencyNode> input) throws MaltChainedException {
078                DependencyNode left = node;
079                int index = input.size() - 1;
080                if (index < 0) {
081                        return true;
082                }
083                DependencyNode right = input.peek();
084                
085                int rc = -1;
086                while (projectiveInterval(parse, left, right)) {
087                        if (rc == right.getIndex()) {
088                                return false;
089                        }
090                        if (gold.getDependencyNode(node.getIndex()).getHead().getIndex() == right.getIndex()) {
091                                return !leftComplete(gold, node);
092                        }
093                        if (gold.getDependencyNode(right.getIndex()).getHead().getIndex() == node.getIndex()) {
094                                if (gold.getDependencyNode(right.getIndex()).hasRightDependent()) {
095                                          rc = gold.getDependencyNode(right.getIndex()).getRightmostProperDescendantIndex();
096                                }
097                                else {
098                                  return false;
099                                } 
100                        }
101                        if (index > 0) {
102                                left = right;
103                                right = input.get(--index);
104                        } else {
105                                break;
106                        }
107                }
108                
109                return true;
110        }
111        
112        private boolean projectiveInterval(DependencyStructure parse, DependencyNode left, DependencyNode right) throws MaltChainedException {
113                final int l = swapArray.get(left.getIndex());
114                final int r = swapArray.get(right.getIndex());
115                DependencyNode node = null;
116                if (l > r) {
117                        return false;
118                } else {
119                        for (int i = l + 1; i < r; i++) {
120                                for (int j = 0; j < swapArray.size(); j++) {
121                                        if (swapArray.get(j) == i) {
122                                                node = parse.getDependencyNode(j);
123                                                break;
124                                        }
125                                }
126                                while (node.hasHead()) {
127                                        node = node.getHead();
128                                }
129                                if (!(node == left || node == right)) {
130                                        return false; 
131                                }
132                        }
133                        return true;
134                }
135        }
136        
137        private boolean leftComplete(DependencyStructure gold, DependencyNode right) throws MaltChainedException {
138                final DependencyNode goldNode = gold.getDependencyNode(right.getIndex());
139                if (!goldNode.hasLeftDependent()) {
140                        return true;
141                } else if (!right.hasLeftDependent()) {
142                        return false;
143                } else if (goldNode.getLeftmostDependent().getIndex() == right.getLeftmostDependent().getIndex()) {
144                        return true;
145                }
146                return false;
147        }
148        
149        public void finalizeSentence(DependencyStructure dependencyGraph) throws MaltChainedException {
150                swapArrayActive = false;
151        }
152        
153        public void terminate() throws MaltChainedException {
154                
155        }
156        
157        private void createSwapArray(DependencyStructure goldDependencyGraph) throws MaltChainedException {
158                swapArray.clear();
159                final int n = goldDependencyGraph.getHighestDependencyNodeIndex();
160                for (int i = 0; i <= n; i++) {
161                        swapArray.add(new Integer(i));
162                }
163                createSwapArray(goldDependencyGraph.getDependencyRoot(), 0);
164        }
165        
166        private int createSwapArray(DependencyNode node, int order) {
167                int o = order; 
168                if (node != null) {
169                        for (int i=0; i < node.getLeftDependentCount(); i++) {
170                                o = createSwapArray(node.getLeftDependent(i), o);
171                        }
172                        swapArray.set(node.getIndex(), o++);
173                        for (int i=node.getRightDependentCount(); i >= 0; i--) {
174                                o = createSwapArray(node.getRightDependent(i), o);
175                        }
176                }
177                return o;
178        }
179}