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.utilities.datastructures;
020
021import org.dllearner.core.AbstractSearchTreeNode;
022import org.dllearner.core.Heuristic;
023
024import java.util.*;
025
026public class AbstractSearchTree <T extends AbstractSearchTreeNode> {
027
028        // all nodes in the search tree (used for selecting most promising node)
029        protected NavigableSet<T> nodes;
030
031        // the sort order on the set
032        protected Heuristic<T> sortOrderComp;
033
034        // root of search tree
035        protected T root;
036        
037        /**
038         * create a new search tree
039         * @param heuristic the comparator to use for the nodes
040         */
041        public AbstractSearchTree(Heuristic<T> heuristic) {
042                sortOrderComp = heuristic;
043        }
044
045        /**
046         * add node to the search tree
047         * @param parentNode the parent node or null if root
048         * @param node the node to add
049         */
050        public void addNode(T parentNode, T node) {
051                // link to parent (unless start node)
052                if(parentNode == null) {
053                        this.setRoot(node);
054                } else {
055                        parentNode.addChild(node);
056                }
057        }
058        
059        /**
060         * internally used by tree<->node contract to notify a tree about an added node
061         * @param node the node
062         */
063        public final void notifyNode(T node) {
064                if (node.getParent() == null || nodes.contains(node.getParent())) {
065                        if (allowedNode(node))
066                                nodes.add(node);
067                }
068        }
069
070        /**
071         * filter certain nodes to be permitted in the node-set
072         * @param node node to test
073         * @return whether node is allowed in the node-set
074         */
075        protected boolean allowedNode(T node) {
076                return true;
077        }
078
079        /**
080         * set the tree root to a node
081         * @param node the node
082         */
083        public void setRoot(T node) {
084                if (this.root != null || !this.nodes.isEmpty()) {
085                        throw new Error("Tree Root already set");
086                }
087                this.root = node;
088                node.notifyTree(this);
089        }
090
091        /**
092         * must be called before modifying a node, to support immutable set element pattern
093         * @param node the node
094         */
095        public final void updatePrepare(T node) {
096                for (T child : (Collection<T>)node.getChildren()) {
097                        if (allowedNode(child))
098                                updatePrepare(child);
099                }
100                nodes.remove(node);
101        }
102        
103        /**
104         * must be called after modifying a node, to support immutable set element pattern
105         */
106        public final void updateDone(T node) {
107                if (allowedNode(node)) {
108                        nodes.add(node);
109                        for (T child : (Collection<T>)node.getChildren()) {
110                                updateDone(child);
111                        }
112                }
113        }
114
115        /**
116         * @return an iterator over the elements in this search tree in descending comparison order
117         */
118        public Iterator<T> descendingIterator() {
119                return nodes.descendingIterator();
120        }
121
122        /**
123         * @return a set of the nodes in the search tree ordered in descending comparison order
124         */
125        public SortedSet<T> descendingSet() {
126                return nodes.descendingSet();
127        }
128
129        /**
130         * @return best node according to comparator
131         */
132        public T best() {
133                return nodes.last();
134        }
135
136        /**
137         * @return the underlying set of all tree nodes
138         */
139        public Set<T> getNodeSet() {
140                return nodes;
141        }
142
143        /**
144         * @return the tree size
145         */
146        public int size() {
147                return nodes.size();
148        }
149
150        /**
151         * @return the tree root node
152         */
153        public T getRoot() {
154                return root;
155        }
156
157        public Heuristic<T> getHeuristic() {
158                return (Heuristic<T>)sortOrderComp;
159        }
160}