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}