001/**
002 * Copyright (C) 2007 - 2016, Jens Lehmann
003 *
004 * This file is part of DL-Learner.
005 *
006 * DL-Learner is free software; you can redistribute it and/or modify
007 * it under the terms of the GNU General Public License as published by
008 * the Free Software Foundation; either version 3 of the License, or
009 * (at your option) any later version.
010 *
011 * DL-Learner is distributed in the hope that it will be useful,
012 * but WITHOUT ANY WARRANTY; without even the implied warranty of
013 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
014 * GNU General Public License for more details.
015 *
016 * You should have received a copy of the GNU General Public License
017 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
018 */
019package org.dllearner.algorithms.qtl.datastructures.impl;
020
021import java.io.IOException;
022import java.io.ObjectInputStream;
023import java.io.ObjectOutputStream;
024import java.io.Serializable;
025import java.util.*;
026import java.util.Map.Entry;
027import java.util.function.Function;
028import java.util.regex.Matcher;
029import java.util.regex.Pattern;
030
031import org.apache.jena.vocabulary.RDF;
032import org.dllearner.algorithms.qtl.QueryTreeUtils;
033import org.dllearner.algorithms.qtl.datastructures.NodeInv;
034import org.dllearner.algorithms.qtl.datastructures.impl.QueryTreeImpl.NodeType;
035import org.dllearner.algorithms.qtl.util.NodeComparatorInv;
036import org.dllearner.algorithms.qtl.util.PrefixCCPrefixMapping;
037
038import com.google.common.collect.ComparisonChain;
039import org.apache.jena.datatypes.BaseDatatype;
040import org.apache.jena.datatypes.RDFDatatype;
041import org.apache.jena.datatypes.xsd.XSDDatatype;
042import org.apache.jena.graph.Node;
043import org.apache.jena.graph.NodeFactory;
044import org.apache.jena.graph.Node_URI;
045import org.apache.jena.rdf.model.Literal;
046import org.apache.jena.shared.PrefixMapping;
047import org.apache.jena.sparql.serializer.SerializationContext;
048import org.apache.jena.sparql.util.FmtUtils;
049import org.apache.jena.sparql.util.NodeComparator;
050
051/**
052 * @author Lorenz Buehmann
053 *
054 */
055public class RDFResourceTree extends GenericTree<Node, RDFResourceTree> implements Serializable, Comparable<RDFResourceTree>{
056        
057        public enum Rendering {
058                INDENTED, BRACES
059        }
060        
061        private int id;
062        
063        public static final Node DEFAULT_VAR_NODE = NodeFactory.createVariable("");
064        public static final Node DEFAULT_LITERAL_NODE = NodeFactory.createLiteral("DEF");
065        
066        // a datatype which only exists if node is literal
067        private RDFDatatype datatype;
068        
069        private Map<RDFResourceTree, Node> child2Edge = new IdentityHashMap<>();//HashMap<>();
070    private NavigableMap<Node, List<RDFResourceTree>> edge2Children = new TreeMap<>(new NodeComparatorInv());
071
072    private Node anchorVar;
073        public void setAnchorVar(Node anchorVar) {
074                this.anchorVar = anchorVar;
075        }
076        public Node getAnchorVar() {
077                return anchorVar;
078        }
079        public boolean hasAnchor() {
080                return anchorVar != null;
081        }
082        public boolean hasAnchor(Node node) {
083                Objects.requireNonNull(node);
084                return node.matches(anchorVar);
085        }
086//      private TreeMultimap<Node, RDFResourceTree> edge2Children = TreeMultimap.create(
087//                      new NodeComparator(), Ordering.arbitrary());
088
089
090        public static RDFResourceTree newVarNode() {
091                return new RDFResourceTree();
092        }
093
094        public static RDFResourceTree newLiteralNode() {
095                return new RDFResourceTree(DEFAULT_LITERAL_NODE);
096        }
097
098    
099    /**
100     * Creates an empty resource tree with a default variable as label.
101     */
102    public RDFResourceTree() {
103                this(0, DEFAULT_VAR_NODE);
104        }
105    
106    /**
107     * Creates an empty resource tree with a default variable as label and the given ID.
108     */
109    public RDFResourceTree(int id) {
110                this(id, DEFAULT_VAR_NODE);
111        }
112    
113        public RDFResourceTree(int id, Node data) {
114                super(data);
115                this.id = id;
116                if(data.isBlank()) {
117                        this.data = DEFAULT_VAR_NODE;
118                }
119        }
120        
121        public RDFResourceTree(Node data) {
122                this(0, data);
123        }
124        
125        /**
126         * Create empty literal node with given datatype.
127         * @param datatype the datatype
128         */
129        public RDFResourceTree(RDFDatatype datatype) {
130                this(0, datatype);
131        }
132        
133        /**
134         * Create empty literal node with given ID and datatype.
135         * @param id the ID
136         * @param datatype the datatype
137         */
138        public RDFResourceTree(int id, RDFDatatype datatype) {
139                super(DEFAULT_LITERAL_NODE);
140                this.id = id;
141                this.datatype = datatype;
142        }
143        
144        /**
145         * Create literal node with given ID, datatype and a set of literal values.
146         * @param id the ID
147         * @param datatype the datatype
148         * @param literals the literal values
149         */
150        public RDFResourceTree(int id, RDFDatatype datatype, Set<Literal> literals) {
151                super(DEFAULT_LITERAL_NODE);
152                this.id = id;
153                this.datatype = datatype;
154        }
155
156        /**
157         * Copy constructor that copies
158         * - node label
159         * - children recursively
160         * - datatype (if literal node)
161         * - anchor var (if exists)
162         * @param tree
163         */
164        public RDFResourceTree(RDFResourceTree tree) {
165                this(tree, true);
166        }
167
168        /**
169         * Copy constructor that copies
170         * - node label
171         * - datatype (if literal node)
172         * - anchor var (if exists)
173         *
174         * Children are recursivly copied only if enabled.
175         *
176         * @param tree the tree
177         * @param withChildren whether to copy also the children recursively
178         */
179        public RDFResourceTree(RDFResourceTree tree, boolean withChildren) {
180                super(tree.getData());
181                this.id = getID();
182
183                setDatatype(tree.getDatatype());
184                setAnchorVar(tree.getAnchorVar());
185
186                if(withChildren) {
187                        for (Entry<Node, List<RDFResourceTree>> entry : tree.edge2Children.entrySet()) {
188                                Node edge = entry.getKey();
189                                List<RDFResourceTree> children = entry.getValue();
190
191                                for (RDFResourceTree child : children) {
192                                        addChild(new RDFResourceTree(child), edge);
193                                }
194                        }
195                }
196        }
197        
198        /**
199         * @return the ID of the tree
200         */
201        public int getID() {
202                return id;
203        }
204
205        public void setId(int id) {
206                this.id = id;
207        }
208
209        public void addChild(RDFResourceTree child, Node edge) {
210                super.addChild(child);
211                List<RDFResourceTree> childrenForEdge = edge2Children.computeIfAbsent(edge, k -> new ArrayList<>());
212                childrenForEdge.add(child);
213
214                child2Edge.put(child, edge);
215        }
216        
217        public void addChildren(List<RDFResourceTree> children, Node edge) {
218                super.addChildren(children);
219                List<RDFResourceTree> childrenForEdge = edge2Children.computeIfAbsent(edge, k -> new ArrayList<>());
220                childrenForEdge.addAll(children);
221        }
222        
223        public void addChildAt(int index, RDFResourceTree child, Node_URI edge) throws IndexOutOfBoundsException {
224                super.addChildAt(index, child);
225                child.setParent(this);
226        }
227        
228        public void removeChild(RDFResourceTree child, Node edge) {
229                super.removeChild(child);
230                
231                List<RDFResourceTree> childrenForEdge = edge2Children.get(edge);
232                if(childrenForEdge != null) {
233                        childrenForEdge.remove(child);
234
235                        // if there are no other children for the given edge, remove whole edge
236                        if(childrenForEdge.isEmpty()) {
237                                edge2Children.remove(edge);
238                        }
239                }
240
241                child2Edge.remove(child);
242        }
243
244        public void replaceChild(RDFResourceTree oldChild, RDFResourceTree newChild, Node edge) {
245                removeChild(oldChild, edge);
246                addChild(newChild, edge);
247        }
248        
249        @Override
250        public List<RDFResourceTree> getChildren() {
251                return super.getChildren();
252        }
253        
254        /**
255         * @param edge the edge
256         * @return all children for the specified edge, or <code>null</code> if
257         * there is no child for the edge
258         */
259        public List<RDFResourceTree> getChildren(Node edge) {
260                return edge2Children.get(edge);
261        }
262
263
264        /**
265         * Returns the edge from the current node to the given child node.
266         *
267         * @param child the child node
268         * @return the edge
269         */
270        public Node getEdgeToChild(RDFResourceTree child) { 
271                return child2Edge.get(child);
272        }
273
274        /**
275         * Returns the edge from the parent node to the current node. If the current node is the root node, i.e.
276         * there is no parent, it will return <code>null</code> instead.
277         *
278         * @return the edge from the parent
279         */
280        public Node getEdgeToParent() {
281                RDFResourceTree parent = getParent();
282                if(parent != null) {
283                        return parent.getEdgeToChild(this);
284                }
285                return null;
286        }
287        
288        /**
289         * @param edge
290         *            the edge from the root node to the possible child nodes
291         * @return TRUE if there is at least one child connected by the given edge,
292         *         otherwise FALSE
293         */
294        public boolean hasChildren(Node edge) {
295                return edge2Children.get(edge) != null;
296        }
297        
298        /**
299         * @return all distinct outgoing edges.
300         */
301        public SortedSet<Node> getEdges() {
302                return edge2Children.navigableKeySet();
303        }
304        
305        /**
306         * @return all distinct outgoing edges to children of the given node type
307         */
308        public SortedSet<Node> getEdges(NodeType nodeType) {
309                SortedSet<Node> edges = new TreeSet<>(new NodeComparator());
310                for (Entry<Node, List<RDFResourceTree>> entry : edge2Children.entrySet()) {
311                        Node edge = entry.getKey();
312                        List<RDFResourceTree> children = entry.getValue();
313                        
314                        for (RDFResourceTree child : children) {
315                                if ((nodeType == NodeType.LITERAL && child.isLiteralNode())
316                                                || (nodeType == NodeType.RESOURCE && child.isResourceNode())) {
317                                        edges.add(edge);
318                                        break;
319                                }
320                        }
321                }
322                return edges;
323        }
324        
325        public boolean isResourceNode() {
326        return data.isURI();
327    }
328
329    public boolean isClassNode() {
330        return !isRoot() && getEdgeToParent().equals(RDF.type.asNode());
331        }
332        
333        public boolean isLiteralNode() {
334                return data.isLiteral();
335        }
336        
337        public boolean isLiteralValueNode() {
338                return data.isLiteral() && !data.equals(DEFAULT_LITERAL_NODE);
339        }
340    
341        public boolean isVarNode() {
342        return data.isVariable();
343    }
344        
345        public boolean isObjectPropertyEdge(Node edge) {
346                return !edge2Children.get(edge).iterator().next().isLiteralNode();
347        }
348        
349        public boolean isDataPropertyEdge(Node edge) {
350                return edge2Children.get(edge).iterator().next().isLiteralNode();
351        }
352        
353        /**
354         * @return the datatype if node is literal node
355         */
356        public RDFDatatype getDatatype() {
357                return datatype;
358        }
359        
360        public String getStringRepresentation() {
361                return getStringRepresentation(false, null, null, PrefixCCPrefixMapping.Full);
362        }
363        
364        public String getStringRepresentation(Rendering syntax) {
365                return getStringRepresentation(false, syntax, null, PrefixCCPrefixMapping.Full);
366        }
367        
368        public String getStringRepresentation(String baseIRI) {
369                return getStringRepresentation(false, null, baseIRI, PrefixCCPrefixMapping.Full);
370        }
371        
372        public String getStringRepresentation(String baseIRI, PrefixMapping pm) {
373                return getStringRepresentation(false, null, baseIRI, pm);
374        }
375        
376        public String getStringRepresentation(Rendering syntax, String baseIRI, PrefixMapping pm) {
377                return getStringRepresentation(false, syntax, baseIRI, pm);
378        }
379        
380        /**
381         * Prints the query tree and shows children of resources only if enabled.
382         * 
383         * @param stopIfChildIsResourceNode do not show children of nodes that are resources
384         * @return the query tree
385         */
386        public String getStringRepresentation(boolean stopIfChildIsResourceNode) {
387                return getStringRepresentation(stopIfChildIsResourceNode, null, null, PrefixCCPrefixMapping.Full);
388        }
389            
390        /**
391         * Prints the query tree and shows children of resources only if enabled.
392         * 
393         * @param stopIfChildIsResourceNode if a child node is not a variable, children will not be rendered
394         * @param syntax the syntax used for rendering
395         * @param baseIRI the base IRI
396         * @param pm the prefix mapping
397         * @return a rendered string representation of the tree
398         */
399        public String getStringRepresentation(boolean stopIfChildIsResourceNode, Rendering syntax, String baseIRI, PrefixMapping pm) {
400                return getStringRepresentation(stopIfChildIsResourceNode, syntax, baseIRI, pm, false);
401        }
402
403        /**
404         * Prints the query tree and shows children of resources only if enabled.
405         *
406         * @param stopIfChildIsResourceNode if a child node is not a variable, children will not be rendered
407         * @param syntax the syntax used for rendering
408         * @param baseIRI the base IRI
409         * @param pm the prefix mapping
410         * @param showID show the IDs of the nodes
411         * @return a rendered string representation of the tree
412         */
413        public String getStringRepresentation(boolean stopIfChildIsResourceNode, Rendering syntax, String baseIRI, PrefixMapping pm, boolean showID) {
414                StringBuilder sb = new StringBuilder();
415
416                SerializationContext context = new SerializationContext(pm);
417                context.setBaseIRI(baseIRI);
418
419                if(syntax == Rendering.BRACES) {
420                        buildTreeString(sb, stopIfChildIsResourceNode, 0, context);
421                } else {
422                        buildTreeStringIndented(sb, stopIfChildIsResourceNode, 1, context, showID);
423                }
424
425                return "TREE [\n" + sb.toString() + "]";
426        }
427        
428        private void buildTreeString(StringBuilder sb, boolean stopIfChildIsResourceNode, int depth, SerializationContext context) {
429                
430                // render current node
431                String ren;
432                if(isLiteralNode() && !isLiteralValueNode()) {
433                        ren = "?^^" + FmtUtils.stringForNode(NodeFactory.createURI(this.getDatatype().getURI()), context);
434                } else {
435                        ren = FmtUtils.stringForNode(this.getData(), context);
436                }
437                sb.append(ren);//.append("\n");
438                
439                // render edges + children
440                if (isRoot() || !isResourceNode() || (isResourceNode() && !stopIfChildIsResourceNode)) {
441                        for(Node edge : getEdges()) {
442                                for (RDFResourceTree child : getChildren(edge)) {
443                                        sb.append("(");
444                                        if (edge != null) {
445                                                sb.append(FmtUtils.stringForNode(edge, context));
446                                                sb.append("(");
447                                        }
448                                        child.buildTreeString(sb, stopIfChildIsResourceNode, depth + 1, context);
449                                        sb.append(")");
450                                        sb.append(")");
451//                                      sb.append("\n");
452                                }
453                        }
454                }
455        }
456        
457        private void buildTreeStringIndented(StringBuilder sb, boolean stopIfChildIsResourceNode, int depth, SerializationContext context, boolean showID) {
458                
459                // render current node
460                String ren;
461                if(isLiteralNode() && !isLiteralValueNode() && getDatatype() != null) {
462                        ren = "?^^" + FmtUtils.stringForNode(NodeFactory.createURI(this.getDatatype().getURI()), context);
463                } else {
464                        ren = FmtUtils.stringForNode(this.getData(), context);
465                }
466                if(getAnchorVar() != null) {
467                        ren += " (" + getAnchorVar() + ")";
468                }
469                if(showID) {
470                        ren += " (" + getID() + ")";
471                }
472                sb.append(ren).append("\n");
473                
474                // render edges + children
475                if (isRoot() || !isResourceNode() || (isResourceNode() && !stopIfChildIsResourceNode)) {
476                        for(Node edge : getEdges()) {
477                                for (RDFResourceTree child : getChildren(edge)) {
478                                        for (int i = 0; i < depth; i++) {
479                                                sb.append("\t");
480                                        }
481                                        if (edge != null) {
482//                                              sb.append("  ");
483                                                sb.append(FmtUtils.stringForNode(edge, context));
484                                                if(edge instanceof NodeInv) {
485                                                        sb.append(" <--- ");
486                                                } else {
487                                                        sb.append(" ---> ");
488                                                }
489
490                                        }
491                                        child.buildTreeStringIndented(sb, stopIfChildIsResourceNode, depth + 1, context, showID);
492                                }
493                        }
494                }
495        }
496        
497        @Override
498        public boolean equals(Object o) {
499                if (this == o) return true;
500                if (o == null || getClass() != o.getClass()) return false;
501                if (!super.equals(o)) return false;
502
503                RDFResourceTree that = (RDFResourceTree) o;
504
505                return (this.isResourceNode() || this.isLiteralValueNode()) && this.getData().equals(that.getData());
506        }
507
508        @Override
509        public int hashCode() {
510                int result = super.hashCode();
511                result = 31 * result + id;
512                return result;
513        }
514
515        /**
516         * @param datatype the datatype to set
517         */
518        public void setDatatype(RDFDatatype datatype) {
519                this.datatype = datatype;
520        }
521        
522        /**
523         * Serialize this instance.
524         * 
525         * @param out Target to which this instance is written.
526         * @throws IOException Thrown if exception occurs during serialization.
527         */
528        private void writeObject(final ObjectOutputStream out) throws IOException {
529                // ID
530                out.writeInt(this.id);
531                
532                // datatype
533                out.writeObject(datatype == null ? "" : this.datatype.getURI());
534                
535                // data
536                out.writeObject(this.data.toString());
537                
538                // edge + children
539                SortedSet<Node> edges = getEdges();
540                if(edges.isEmpty()) {
541                        out.writeObject(null);
542                }
543                for (Node edge : edges) {
544                        List<RDFResourceTree> children = getChildren(edge);
545                        out.writeObject(edge.toString());
546                        out.writeObject(children);
547                }
548                out.writeObject(null);
549        }
550        
551        private void readObject(ObjectInputStream ois) throws ClassNotFoundException, IOException {
552                child2Edge = new HashMap<>();
553            edge2Children = new TreeMap<>(new NodeComparator());
554                
555            // ID
556                int id = ois.readInt();
557                
558                // datatype
559                String datatypeURI = (String) ois.readObject();
560                if(datatypeURI != null) {
561                        if(datatypeURI.equals(XSDDatatype.XSD)) {
562                                setDatatype(new XSDDatatype(datatypeURI));
563                        } else {
564                                setDatatype(new BaseDatatype(datatypeURI));
565                        }
566                }
567                
568                // data
569                String dataString = (String) ois.readObject();
570                Node data;
571                if(dataString.equals(RDFResourceTree.DEFAULT_VAR_NODE.toString())) {
572                        data = RDFResourceTree.DEFAULT_VAR_NODE;
573                } else if(dataString.equals(RDFResourceTree.DEFAULT_LITERAL_NODE.toString())) {
574                        data = RDFResourceTree.DEFAULT_LITERAL_NODE;
575                } else {
576                        data = NodeFactory.createURI(dataString);
577                }
578                setData(data);
579                
580                // edge + children
581                Object edgeObject;
582                while((edgeObject = ois.readObject()) != null) {
583                        Node edge = NodeFactory.createURI((String) edgeObject);
584                        List<RDFResourceTree> children = (List<RDFResourceTree>) ois.readObject();
585                        for (RDFResourceTree child : children) {
586                                addChild(child, edge);
587                        }
588                }
589                
590        }
591
592        /* (non-Javadoc)
593         * @see java.lang.Comparable#compareTo(java.lang.Object)
594         */
595        @Override
596        public int compareTo(RDFResourceTree other) {
597                return ComparisonChain.start().
598                        compare(this.getData(), other.getData(), new NodeComparator()). // root node
599                        compare(this.getNumberOfChildren(), other.getNumberOfChildren()). // number of direct children
600                        compare(QueryTreeUtils.toOWLClassExpression(this), QueryTreeUtils.toOWLClassExpression(other)). // class expression representation
601                        result();
602        }
603
604//      static class NodeRenderer implements Function<Node, String>{
605//              @Override
606//              public String apply(Node node) {
607//                      return null;
608//              }
609//      }
610//
611//      static class TreeRenderer {
612//
613//              private Function<Node, String> nodeRenderer;
614//
615//              public String render(RDFResourceTree tree) {
616//
617//              }
618//
619//
620//      }
621}