001    package org.maltparser.parser.algorithm.stack;
002    
003    import java.util.ArrayList;
004    import java.util.Stack;
005    
006    import org.maltparser.core.exception.MaltChainedException;
007    import org.maltparser.core.syntaxgraph.DependencyStructure;
008    import org.maltparser.core.syntaxgraph.node.DependencyNode;
009    import org.maltparser.parser.DependencyParserConfig;
010    import org.maltparser.parser.Oracle;
011    import org.maltparser.parser.ParserConfiguration;
012    import org.maltparser.parser.history.GuideUserHistory;
013    import org.maltparser.parser.history.action.GuideUserAction;
014    /**
015     * @author Johan Hall
016     *
017     */
018    public 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                    StackConfig config = (StackConfig)configuration;
030                    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                            DependencyNode left = stack.get(stack.size()-2);
040                            DependencyNode right = stack.get(stack.size()-1);
041                            int leftIndex = left.getIndex();
042                            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                    if (gold.getTokenNode(nodeIndex).hasLeftDependent()) {
059                            if (!parseDependencyGraph.getTokenNode(nodeIndex).hasLeftDependent()) {
060                                    return false;
061                            } else if (gold.getTokenNode(nodeIndex).getLeftmostDependent().getIndex() != parseDependencyGraph.getTokenNode(nodeIndex).getLeftmostDependent().getIndex()) {
062                                    return false;
063                            }
064                    }
065                    if (gold.getTokenNode(nodeIndex).hasRightDependent()) {
066                            if (!parseDependencyGraph.getTokenNode(nodeIndex).hasRightDependent()) {
067                                    return false;
068                            } else if (gold.getTokenNode(nodeIndex).getRightmostDependent().getIndex() != parseDependencyGraph.getTokenNode(nodeIndex).getRightmostDependent().getIndex()) {
069                                    return false;
070                            }
071                    }
072                    return true;
073            }
074            
075            private boolean necessarySwap(DependencyStructure gold, DependencyStructure parse, DependencyNode node, Stack<DependencyNode> input) throws MaltChainedException {
076                    DependencyNode left = node;
077                    int index = input.size() - 1;
078                    if (index < 0) {
079                            return true;
080                    }
081                    DependencyNode right = input.peek();
082                    
083                    int rc = -1;
084                    while (projectiveInterval(parse, left, right)) {
085                            if (rc == right.getIndex()) {
086                                    return false;
087                            }
088                            if (gold.getDependencyNode(node.getIndex()).getHead().getIndex() == right.getIndex()) {
089                                    return !leftComplete(gold, node);
090                            }
091                            if (gold.getDependencyNode(right.getIndex()).getHead().getIndex() == node.getIndex()) {
092                                    if (gold.getDependencyNode(right.getIndex()).hasRightDependent()) {
093                                              rc = gold.getDependencyNode(right.getIndex()).getRightmostProperDescendantIndex();
094                                    }
095                                    else {
096                                      return false;
097                                    } 
098                            }
099                            if (index > 0) {
100                                    left = right;
101                                    right = input.get(--index);
102                            } else {
103                                    break;
104                            }
105                    }
106                    
107                    return true;
108            }
109            
110            private boolean projectiveInterval(DependencyStructure parse, DependencyNode left, DependencyNode right) throws MaltChainedException {
111                    int l = swapArray.get(left.getIndex());
112                    int r = swapArray.get(right.getIndex());
113                    DependencyNode node = null;
114                    if (l > r) {
115                            return false;
116                    } else {
117                            for (int i = l + 1; i < r; i++) {
118                                    for (int j = 0; j < swapArray.size(); j++) {
119                                            if (swapArray.get(j) == i) {
120                                                    node = parse.getDependencyNode(j);
121                                                    break;
122                                            }
123                                    }
124                                    while (node.hasHead()) {
125                                            node = node.getHead();
126                                    }
127                                    if (!(node == left || node == right)) {
128                                            return false; 
129                                    }
130                            }
131                            return true;
132                    }
133            }
134            
135            private boolean leftComplete(DependencyStructure gold, DependencyNode right) throws MaltChainedException {
136                    if (!gold.getDependencyNode(right.getIndex()).hasLeftDependent()) {
137                            return true;
138                    } else if (!right.hasLeftDependent()) {
139                            return false;
140                    } else if (gold.getDependencyNode(right.getIndex()).getLeftmostDependent().getIndex() == right.getLeftmostDependent().getIndex()) {
141                            return true;
142                    }
143                    return false;
144            }
145            
146            public void finalizeSentence(DependencyStructure dependencyGraph) throws MaltChainedException {
147                    swapArrayActive = false;
148            }
149            
150            public void terminate() throws MaltChainedException {
151                    
152            }
153            
154            private void createSwapArray(DependencyStructure goldDependencyGraph) throws MaltChainedException {
155                    swapArray.clear();
156                    for (int i = 0; i <= goldDependencyGraph.getHighestDependencyNodeIndex(); i++) {
157                            swapArray.add(new Integer(i));
158                    }
159                    createSwapArray(goldDependencyGraph.getDependencyRoot(), 0);
160            }
161            
162            private int createSwapArray(DependencyNode n, int order) {
163                    int o = order; 
164                    if (n != null) {
165                            for (int i=0; i < n.getLeftDependentCount(); i++) {
166                                    o = createSwapArray(n.getLeftDependent(i), o);
167                            }
168                            swapArray.set(n.getIndex(), o++);
169                            for (int i=n.getRightDependentCount(); i >= 0; i--) {
170                                    o = createSwapArray(n.getRightDependent(i), o);
171                            }
172                    }
173                    return o;
174            }
175    }