001 /**
002 * Copyright (C) 2007-2011, 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 */
019
020 package org.dllearner.core.owl;
021
022 import java.util.LinkedList;
023 import java.util.List;
024 import java.util.Map;
025
026 /**
027 * A class description is sometimes also called "complex class" or "concept".
028 *
029 * @author Jens Lehmann
030 *
031 */
032 public abstract class Description implements Cloneable, PropertyRange, KBElement{
033
034 /**
035 *
036 */
037 private static final long serialVersionUID = -3439073654652166607L;
038 protected Description parent = null;
039 protected List<Description> children = new LinkedList<Description>();
040
041 public abstract int getArity();
042
043 /**
044 * Calculate the number of nodes for this description tree (each
045 * description can be seen as a tree).
046 *
047 * @return The number of nodes.
048 */
049 public int getNumberOfNodes() {
050 int sum = 1;
051 for (Description child : children)
052 sum += child.getNumberOfNodes();
053 return sum;
054 }
055
056 /**
057 * Selects a sub tree.
058 * @param i A position in the tree. Positions are iteratively given to nodes
059 * by leftmost depth-first search. This allows efficient selection of subtrees.
060 * (TODO: Implementation does not work if any node has more than two children
061 * like conjunction and disjunction.)
062 * @return The selected subtree.
063 */
064 public Description getSubtree(int i) {
065 if (children.size() == 0)
066 return this;
067 else if (children.size() == 1) {
068 if (i == 0)
069 return this;
070 else
071 return children.get(0).getSubtree(i - 1);
072 }
073 // arity 2
074 else {
075 // we have found it
076 if (i == 0)
077 return this;
078 // left subtree
079 int leftTreeNodes = children.get(0).getNumberOfNodes();
080 if (i <= leftTreeNodes)
081 return children.get(0).getSubtree(i - 1);
082 // right subtree
083 else
084 return children.get(1).getSubtree(i - leftTreeNodes - 1);
085 }
086 }
087
088 /**
089 * Calculates the description tree depth.
090 * @return The depth of this description.
091 */
092 public int getDepth() {
093 // compute the max over all children
094 int depth = 1;
095
096 for(Description child : children) {
097 int depthChild = child.getDepth();
098 if(depthChild+1>depth)
099 depth = 1 + depthChild;
100 }
101
102 return depth;
103 }
104
105 /**
106 * Returns a clone of this description.
107 */
108 @Override
109 public Description clone() {
110 Description node = null;
111 try {
112 node = (Description) super.clone();
113 } catch (CloneNotSupportedException e) {
114 // should never happen
115 throw new InternalError(e.toString());
116 }
117
118 // Create a deep copy, i.e. we iterate over all children and clone them.
119 // The addChild operation is used to ensure that the parent links are
120 // correct, i.e. all parent links point to the new clones instead of the
121 // old descriptions.
122 node.children = new LinkedList<Description>();
123 for(Description child : children) {
124 Description clonedChild = (Description) child.clone();
125 node.addChild(clonedChild);
126 }
127
128 return node;
129 }
130
131 /**
132 * Adds a description as child of this one. The parent link
133 * of the description will point to this one. For instance,
134 * if the description is an intersection, then this method adds
135 * an element to the intersection, e.g. A AND B becomes A AND B
136 * AND C.
137 *
138 * @param child The child description.
139 */
140 public void addChild(Description child) {
141 child.setParent(this);
142 children.add(child);
143 }
144
145 /**
146 * Adds a child description at the specified index.
147 *
148 * @see #addChild(Description)
149 * @param index
150 * @param child
151 */
152 public void addChild(int index, Description child) {
153 child.setParent(this);
154 children.add(index, child);
155 }
156
157 /**
158 * Remove the specified child description (its parent link is set
159 * to null).
160 * @param child The child to remove.
161 */
162 public void removeChild(Description child) {
163 child.setParent(null);
164 children.remove(child);
165 }
166
167 public void removeChild(int index) {
168 children.get(index).setParent(null);
169 children.remove(index);
170 }
171
172 public void replaceChild(int index, Description newChild) {
173 children.remove(index);
174 children.add(index, newChild);
175 }
176
177 /**
178 * Tests whether this description is at the root, i.e.
179 * does not have a parent.
180 *
181 * @return True if this node is the root of a description, false otherwise.
182 */
183 public boolean isRoot() {
184 return (parent == null);
185 }
186
187 public Description getParent() {
188 return parent;
189 }
190
191 public void setParent(Description parent) {
192 this.parent = parent;
193 }
194
195 public List<Description> getChildren() {
196 return children;
197 }
198
199 public Description getChild(int i) {
200 return children.get(i);
201 }
202
203 @Override
204 public String toString() {
205 return toString(null, null);
206 }
207
208
209 public String toKBSyntaxString() {
210 return toKBSyntaxString(null, null);
211 }
212
213 /**
214 * Returns a manchester syntax string of this description. For a
215 * reference, see
216 * <a href="http://www.co-ode.org/resources/reference/manchester_syntax">here</a>
217 * and <a href="http://owl-workshop.man.ac.uk/acceptedLong/submission_9.pdf">here</a> (PDF).
218 * @return The manchester syntax string for this description.
219 */
220 public abstract String toManchesterSyntaxString(String baseURI, Map<String,String> prefixes);
221
222 public abstract void accept(DescriptionVisitor visitor);
223
224 }