package org.maltparser.core.syntaxgraph;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Observable;
import java.util.Set;
import java.util.SortedMap;
import java.util.SortedSet;
import java.util.TreeMap;
import java.util.TreeSet;
import org.maltparser.core.exception.MaltChainedException;
import org.maltparser.core.helper.SystemLogger;
import org.maltparser.core.pool.ObjectPoolList;
import org.maltparser.core.symbol.SymbolTable;
import org.maltparser.core.symbol.SymbolTableHandler;
import org.maltparser.core.syntaxgraph.ds2ps.LosslessMapping;
import org.maltparser.core.syntaxgraph.edge.Edge;
import org.maltparser.core.syntaxgraph.edge.GraphEdge;
import org.maltparser.core.syntaxgraph.node.ComparableNode;
import org.maltparser.core.syntaxgraph.node.DependencyNode;
import org.maltparser.core.syntaxgraph.node.Node;
import org.maltparser.core.syntaxgraph.node.NonTerminal;
import org.maltparser.core.syntaxgraph.node.NonTerminalNode;
import org.maltparser.core.syntaxgraph.node.PhraseStructureNode;
import org.maltparser.core.syntaxgraph.node.Root;
import org.maltparser.core.syntaxgraph.node.TokenNode;
/**
*
*
* @author Johan Hall
*/
public class MappablePhraseStructureGraph extends Sentence implements DependencyStructure, PhraseStructure {
private final ObjectPoolList<Edge> edgePool;
private final SortedSet<Edge> graphEdges;
private Root root;
private boolean singleHeadedConstraint;
private final SortedMap<Integer, NonTerminal> nonTerminalNodes;
private final ObjectPoolList<NonTerminal> nonTerminalPool;
private LosslessMapping mapping;
private RootLabels rootLabels;
public MappablePhraseStructureGraph(SymbolTableHandler symbolTables) throws MaltChainedException {
super(symbolTables);
setSingleHeadedConstraint(true);
root = new Root();
root.setBelongsToGraph(this);
graphEdges = new TreeSet<Edge>();
edgePool = new ObjectPoolList<Edge>() {
protected Edge create() { return new GraphEdge(); }
public void resetObject(Edge o) throws MaltChainedException { o.clear(); }
};
nonTerminalNodes = new TreeMap<Integer,NonTerminal>();
nonTerminalPool = new ObjectPoolList<NonTerminal>() {
protected NonTerminal create() throws MaltChainedException { return new NonTerminal(); }
public void resetObject(NonTerminal o) throws MaltChainedException { o.clear(); }
};
clear();
}
public DependencyNode addDependencyNode() throws MaltChainedException {
return addTokenNode();
}
public DependencyNode addDependencyNode(int index) throws MaltChainedException {
if (index == 0) {
return root;
}
return addTokenNode(index);
}
public DependencyNode getDependencyNode(int index) throws MaltChainedException {
if (index == 0) {
return root;
}
return getTokenNode(index);
}
public int nDependencyNode() {
return nTokenNode() + 1;
}
public int getHighestDependencyNodeIndex() {
if (hasTokens()) {
return getHighestTokenIndex();
}
return 0;
}
public Edge addDependencyEdge(int headIndex, int dependentIndex) throws MaltChainedException {
DependencyNode head = null;
DependencyNode dependent = null;
if (headIndex == 0) {
head = root;
} else if (headIndex > 0) {
head = getOrAddTerminalNode(headIndex);
}
if (dependentIndex > 0) {
dependent = getOrAddTerminalNode(dependentIndex);
}
return addDependencyEdge(head, dependent);
}
public Edge addDependencyEdge(DependencyNode head, DependencyNode dependent) throws MaltChainedException {
if (head == null || dependent == null || head.getBelongsToGraph() != this || dependent.getBelongsToGraph() != this) {
throw new SyntaxGraphException("Head or dependent node is missing.");
} else if (!dependent.isRoot()) {
if (singleHeadedConstraint && dependent.hasHead()) {
throw new SyntaxGraphException("The dependent already have a head. ");
}
DependencyNode hc = ((DependencyNode)head).findComponent();
DependencyNode dc = ((DependencyNode)dependent).findComponent();
if (hc != dc) {
link(hc, dc);
numberOfComponents--;
}
Edge e = edgePool.checkOut();
e.setBelongsToGraph(this);
e.setEdge((Node)head, (Node)dependent, Edge.DEPENDENCY_EDGE);
graphEdges.add(e);
return e;
} else {
throw new SyntaxGraphException("Head node is not a root node or a terminal node.");
}
}
public Edge moveDependencyEdge(int newHeadIndex, int dependentIndex) throws MaltChainedException {
DependencyNode newHead = null;
DependencyNode dependent = null;
if (newHeadIndex == 0) {
newHead = root;
} else if (newHeadIndex > 0) {
newHead = terminalNodes.get(newHeadIndex);
}
if (dependentIndex > 0) {
dependent = terminalNodes.get(dependentIndex);
}
return moveDependencyEdge(newHead, dependent);
}
public Edge moveDependencyEdge(DependencyNode newHead, DependencyNode dependent) throws MaltChainedException {
if (dependent == null || !dependent.hasHead() || newHead.getBelongsToGraph() != this || dependent.getBelongsToGraph() != this) {
return null;
}
Edge headEdge = dependent.getHeadEdge();
LabelSet labels = null;
if (headEdge.isLabeled()) {
labels = checkOutNewLabelSet();
for (SymbolTable table : headEdge.getLabelTypes()) {
labels.put(table, headEdge.getLabelCode(table));
}
}
headEdge.clear();
headEdge.setBelongsToGraph(this);
headEdge.setEdge((Node)newHead, (Node)dependent, Edge.DEPENDENCY_EDGE);
if (labels != null) {
headEdge.addLabel(labels);
labels.clear();
checkInLabelSet(labels);
}
return headEdge;
}
public void removeDependencyEdge(int headIndex, int dependentIndex) throws MaltChainedException {
Node head = null;
Node dependent = null;
if (headIndex == 0) {
head = root;
} else if (headIndex > 0) {
head = terminalNodes.get(headIndex);
}
if (dependentIndex > 0) {
dependent = terminalNodes.get(dependentIndex);
}
removeDependencyEdge(head, dependent);
}
protected void removeDependencyEdge(Node head, Node dependent) throws MaltChainedException {
if (head == null || dependent == null || head.getBelongsToGraph() != this || dependent.getBelongsToGraph() != this) {
throw new SyntaxGraphException("Head or dependent node is missing.");
} else if (!dependent.isRoot()) {
Iterator<Edge> ie = dependent.getIncomingEdgeIterator();
while (ie.hasNext()) {
Edge e = ie.next();
if (e.getSource() == head) {
ie.remove();
graphEdges.remove(e);
edgePool.checkIn(e);
}
}
} else {
throw new SyntaxGraphException("Head node is not a root node or a terminal node.");
}
}
public Edge addSecondaryEdge(ComparableNode source, ComparableNode target) throws MaltChainedException {
if (source == null || target == null || source.getBelongsToGraph() != this || target.getBelongsToGraph() != this) {
throw new SyntaxGraphException("Head or dependent node is missing.");
} else if (!target.isRoot()) {
Edge e = edgePool.checkOut();
e.setBelongsToGraph(this);
e.setEdge((Node)source, (Node)target, Edge.SECONDARY_EDGE);
graphEdges.add(e);
return e;
}
return null;
}
public void removeSecondaryEdge(ComparableNode source, ComparableNode target) throws MaltChainedException {
if (source == null || target == null || source.getBelongsToGraph() != this || target.getBelongsToGraph() != this) {
throw new SyntaxGraphException("Head or dependent node is missing.");
} else if (!target.isRoot()) {
Iterator<Edge> ie = ((Node)target).getIncomingEdgeIterator();
while (ie.hasNext()) {
Edge e = ie.next();
if (e.getSource() == source) {
ie.remove();
graphEdges.remove(e);
edgePool.checkIn(e);
}
}
}
}
public boolean hasLabeledDependency(int index) throws MaltChainedException {
return (getDependencyNode(index).hasHead() && getDependencyNode(index).getHeadEdge().isLabeled());
}
public boolean isConnected() {
return (numberOfComponents == 1);
}
public boolean isProjective() throws MaltChainedException {
for (int i : terminalNodes.keySet()) {
if (!terminalNodes.get(i).isProjective()) {
return false;
}
}
return true;
}
public boolean isTree() {
return isConnected() && isSingleHeaded();
}
public boolean isSingleHeaded() {
for (int i : terminalNodes.keySet()) {
if (!terminalNodes.get(i).hasAtMostOneHead()) {
return false;
}
}
return true;
}
public boolean isSingleHeadedConstraint() {
return singleHeadedConstraint;
}
public void setSingleHeadedConstraint(boolean singleHeadedConstraint) {
this.singleHeadedConstraint = singleHeadedConstraint;
}
public int nNonProjectiveEdges() throws MaltChainedException {
int c = 0;
for (int i : terminalNodes.keySet()) {
if (!terminalNodes.get(i).isProjective()) {
c++;
}
}
return c;
}
public int nEdges() {
return graphEdges.size();
}
public SortedSet<Edge> getEdges() {
return graphEdges;
}
public SortedSet<Integer> getDependencyIndices() {
SortedSet<Integer> indices = new TreeSet<Integer>(terminalNodes.keySet());
indices.add(0);
return indices;
}
protected DependencyNode link(DependencyNode x, DependencyNode y) {
if (x.getRank() > y.getRank()) {
y.setComponent(x);
} else {
x.setComponent(y);
if (x.getRank() == y.getRank()) {
y.setRank(y.getRank()+1);
}
return y;
}
return x;
}
public void linkAllTerminalsToRoot() throws MaltChainedException {
clear();
for (int i : terminalNodes.keySet()) {
DependencyNode node = terminalNodes.get(i);
addDependencyEdge(root,node);
}
}
public void linkAllTreesToRoot() throws MaltChainedException {
for (int i : terminalNodes.keySet()) {
if (!terminalNodes.get(i).hasHead()) {
Edge e = addDependencyEdge(root,terminalNodes.get(i));
mapping.updatePhraseStructureGraph(this, e, false);
}
}
}
public LabelSet getDefaultRootEdgeLabels() throws MaltChainedException {
if (rootLabels == null) {
return null;
}
return rootLabels.getDefaultRootLabels();
}
public String getDefaultRootEdgeLabelSymbol(SymbolTable table) throws MaltChainedException {
if (rootLabels == null) {
return null;
}
return rootLabels.getDefaultRootLabelSymbol(table);
}
public int getDefaultRootEdgeLabelCode(SymbolTable table) throws MaltChainedException {
if (rootLabels == null) {
return -1;
}
return rootLabels.getDefaultRootLabelCode(table);
}
public void setDefaultRootEdgeLabel(SymbolTable table, String defaultRootSymbol) throws MaltChainedException {
if (rootLabels == null) {
rootLabels = new RootLabels();
}
rootLabels.setDefaultRootLabel(table, defaultRootSymbol);
}
public void setDefaultRootEdgeLabels(String rootLabelOption, SortedMap<String, SymbolTable> edgeSymbolTables) throws MaltChainedException {
if (rootLabels == null) {
rootLabels = new RootLabels();
}
rootLabels.setRootLabels(rootLabelOption, edgeSymbolTables);
}
public void clear() throws MaltChainedException {
edgePool.checkInAll();
graphEdges.clear();
root.clear();
root.setBelongsToGraph(this);
nonTerminalPool.checkInAll();
nonTerminalNodes.clear();
if (mapping != null) {
mapping.clear();
}
super.clear();
numberOfComponents++;
}
public DependencyNode getDependencyRoot() {
return root;
}
public PhraseStructureNode addTerminalNode() throws MaltChainedException {
return addTokenNode();
}
public PhraseStructureNode addTerminalNode(int index) throws MaltChainedException {
return addTokenNode(index);
}
public PhraseStructureNode getTerminalNode(int index) {
return getTokenNode(index);
}
public int nTerminalNode() {
return nTokenNode();
}
public PhraseStructureNode addNonTerminalNode(int index) throws MaltChainedException {
NonTerminal node = nonTerminalPool.checkOut();
node.setIndex(index);
node.setBelongsToGraph(this);
nonTerminalNodes.put(index,node);
return node;
}
public PhraseStructureNode addNonTerminalNode() throws MaltChainedException {
int index = getHighestNonTerminalIndex();
if (index > 0) {
return addNonTerminalNode(index+1);
}
return addNonTerminalNode(1);
}
public PhraseStructureNode getNonTerminalNode(int index) throws MaltChainedException {
return nonTerminalNodes.get(index);
}
public int getHighestNonTerminalIndex() {
try {
return nonTerminalNodes.lastKey();
} catch (NoSuchElementException e) {
return 0;
}
}
public Set<Integer> getNonTerminalIndices() {
return new TreeSet<Integer>(nonTerminalNodes.keySet());
}
public boolean hasNonTerminals() {
return !nonTerminalNodes.isEmpty();
}
public int nNonTerminals() {
return nonTerminalNodes.size();
}
public PhraseStructureNode getPhraseStructureRoot() {
return root;
}
public Edge addPhraseStructureEdge(PhraseStructureNode parent, PhraseStructureNode child) throws MaltChainedException {
if (parent == null || child == null) {
throw new MaltChainedException("Parent or child node is missing in sentence "+getSentenceID());
} else if (parent.getBelongsToGraph() != this || child.getBelongsToGraph() != this) {
throw new MaltChainedException("Parent or child node is not a member of the graph in sentence "+getSentenceID());
} else if (parent == child) {
throw new MaltChainedException("It is not allowed to add a phrase structure edge connecting the same node in sentence "+getSentenceID());
} else if (parent instanceof NonTerminalNode && !child.isRoot()) {
Edge e = edgePool.checkOut();
e.setBelongsToGraph(this);
e.setEdge((Node)parent, (Node)child, Edge.PHRASE_STRUCTURE_EDGE);
graphEdges.add(e);
return e;
} else {
throw new MaltChainedException("Parent or child node is not of correct node type.");
}
}
public void update(Observable o, Object arg) {
if (o instanceof Edge && mapping != null) {
try {
mapping.update(this, (Edge)o, arg);
} catch (MaltChainedException ex) {
if (SystemLogger.logger().isDebugEnabled()) {
SystemLogger.logger().debug("",ex);
} else {
SystemLogger.logger().error(ex.getMessageChain());
}
System.exit(1);
}
}
}
public LosslessMapping getMapping() {
return mapping;
}
public void setMapping(LosslessMapping mapping) {
this.mapping = mapping;
}
public void addLabel(Element element, String labelFunction, String label) throws MaltChainedException {
super.addLabel(element, labelFunction, label);
}
public void removePhraseStructureEdge(PhraseStructureNode parent, PhraseStructureNode child) throws MaltChainedException {
if (parent == null || child == null) {
throw new MaltChainedException("Parent or child node is missing.");
} else if (parent instanceof NonTerminalNode && !child.isRoot()) {
for (Edge e : graphEdges) {
if (e.getSource() == parent && e.getTarget() == child) {
e.clear();
graphEdges.remove(e);
if (e instanceof GraphEdge) {
edgePool.checkIn(e);
}
}
}
} else {
throw new SyntaxGraphException("Head node is not a root node or a terminal node.");
}
}
public boolean isContinuous() {
for (int index : nonTerminalNodes.keySet()) {
NonTerminalNode node = nonTerminalNodes.get(index);
if (!node.isContinuous()) {
return false;
}
}
return true;
}
public boolean isContinuousExcludeTerminalsAttachToRoot() {
for (int index : nonTerminalNodes.keySet()) {
NonTerminalNode node = nonTerminalNodes.get(index);
if (!node.isContinuousExcludeTerminalsAttachToRoot()) {
return false;
}
}
return true;
}
// public void makeContinuous() throws MaltChainedException {
// if (root != null) {
// root.reArrangeChildrenAccordingToLeftAndRightProperDesendant();
// }
// }
public String toStringTerminalNode(TokenNode node) {
final StringBuilder sb = new StringBuilder();
final DependencyNode depnode = node;
sb.append(node.toString().trim());
if (depnode.hasHead()) {
sb.append('\t');
try {
sb.append(depnode.getHead().getIndex());
sb.append('\t');
sb.append(depnode.getHeadEdge().toString());
} catch (MaltChainedException e) {
System.out.println(e);
}
}
sb.append('\n');
return sb.toString();
}
public String toStringNonTerminalNode(NonTerminalNode node) {
final StringBuilder sb = new StringBuilder();
sb.append(node.toString().trim());
sb.append('\n');
Iterator<Edge> ie = ((Node)node).getOutgoingEdgeIterator();
while (ie.hasNext()) {
Edge e = ie.next();
if (e.getTarget() instanceof TokenNode) {
sb.append(" T");
sb.append(e.getTarget().getIndex());
}
if (e.getTarget() instanceof NonTerminalNode) {
sb.append(" N");
sb.append(e.getTarget().getIndex());
}
sb.append('\t');
sb.append(e.toString());
sb.append('\n');
}
return sb.toString();
}
public String toString() {
StringBuilder sb = new StringBuilder();
for (int index : terminalNodes.keySet()) {
sb.append(toStringTerminalNode(terminalNodes.get(index)));
}
sb.append('\n');
sb.append(toStringNonTerminalNode((NonTerminalNode)getPhraseStructureRoot()));
for (int index : nonTerminalNodes.keySet()) {
sb.append(toStringNonTerminalNode(nonTerminalNodes.get(index)));
}
return sb.toString();
}
}