001 /*
002 * Java Genetic Algorithm Library (jenetics-3.9.0).
003 * Copyright (c) 2007-2017 Franz Wilhelmstötter
004 *
005 * Licensed under the Apache License, Version 2.0 (the "License");
006 * you may not use this file except in compliance with the License.
007 * You may obtain a copy of the License at
008 *
009 * http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 *
017 * Author:
018 * Franz Wilhelmstötter (franz.wilhelmstoetter@gmx.at)
019 */
020 package org.jenetics.ext.util;
021
022 import static java.util.Objects.requireNonNull;
023
024 import java.io.Serializable;
025 import java.util.ArrayList;
026 import java.util.Iterator;
027 import java.util.List;
028 import java.util.Optional;
029
030 import org.jenetics.util.Copyable;
031
032 /**
033 * A general purpose node in a tree data-structure. The {@code TreeNode} is a
034 * mutable implementation of the {@link Tree} interface.
035 *
036 * @param <T> the value type of the tree node
037 *
038 * @author <a href="mailto:franz.wilhelmstoetter@gmx.at">Franz Wilhelmstötter</a>
039 * @version 3.9
040 * @since 3.9
041 */
042 public final class TreeNode<T>
043 implements
044 Tree<T, TreeNode<T>>,
045 Iterable<TreeNode<T>>,
046 Copyable<TreeNode<T>>,
047 Serializable
048 {
049 private static final long serialVersionUID = 1L;
050
051 private T _value;
052 private TreeNode<T> _parent;
053 private final List<TreeNode<T>> _children = new ArrayList<>();
054
055 /**
056 * Create a new tree node with no parent and children, but with the given
057 * user {@code value}.
058 *
059 * @param value the user value of the new tree node
060 */
061 private TreeNode(final T value) {
062 _value = value;
063 }
064
065
066 /* *************************************************************************
067 * Basic operations
068 **************************************************************************/
069
070 /**
071 * Sets the user object for this node.
072 *
073 * @param value the node {@code value}
074 */
075 public void setValue(final T value) {
076 _value = value;
077 }
078
079 /**
080 * Return the node value
081 *
082 * @return the node value
083 */
084 @Override
085 public T getValue() {
086 return _value;
087 }
088
089 /**
090 * Returns this node's parent if available.
091 *
092 * @return the tree-node, or an empty value if this node has no parent
093 */
094 @Override
095 public Optional<TreeNode<T>> getParent() {
096 return Optional.ofNullable(_parent);
097 }
098
099 /**
100 * Sets this node's parent, but does not change the parent's child array.
101 * This method is called from {@code insert()} and {@code remove()} to
102 * reassign a child's parent, and it should not be messaged from anywhere
103 * else.
104 *
105 * @param parent this node's new parent
106 */
107 void setParent(final TreeNode<T> parent) {
108 _parent = parent;
109 }
110
111 /**
112 * Returns the child at the specified index in this node's child array.
113 *
114 * @param index an index into this node's child array
115 * @return the tree-node in this node's child array at the specified index
116 * @throws ArrayIndexOutOfBoundsException if the {@code index} is out of
117 * bounds
118 */
119 @Override
120 public TreeNode<T> getChild(final int index) {
121 return _children.get(index);
122 }
123
124 @Override
125 public int childCount() {
126 return _children.size();
127 }
128
129 /**
130 * Return an iterator that traverses the subtree rooted at {@code this} node
131 * in pre-order. The first node returned by the iterator is {@code this}
132 * node.
133 * <p>
134 * Modifying the tree by inserting, removing, or moving a node invalidates
135 * any iterator created before the modification.
136 *
137 * @see #postorderIterator
138 * @return an iterator for traversing the tree in pre-order
139 */
140 @Override
141 public Iterator<TreeNode<T>> iterator() {
142 return preorderIterator();
143 }
144
145 /**
146 * Removes the {@code child} from its present parent (if it has one), sets
147 * the child's parent to this node, and then adds the child to this node's
148 * child array at index {@code index}. The new {@code child} must not be
149 * {@code null} and must not be an ancestor of {@code this} node.
150 *
151 * @param index the index in the child array where this node is to be
152 * inserted
153 * @param child the sub-node to be inserted
154 * @return {@code this} tree-node, for method chaining
155 * @throws ArrayIndexOutOfBoundsException if {@code index} is out of bounds
156 * @throws IllegalArgumentException if {@code child} is an ancestor of
157 * {@code this} node
158 * @throws NullPointerException if the given {@code child} is {@code null}
159 */
160 public TreeNode<T> insert(final int index, final TreeNode<T> child) {
161 requireNonNull(child);
162 if (isAncestor(child)) {
163 throw new IllegalArgumentException("The new child is an ancestor.");
164 }
165
166 if (child._parent != null) {
167 child._parent.remove(child);
168 }
169
170 child.setParent(this);
171 _children.add(index, child);
172
173 TreeNode<T> parent = this;
174 while (parent != null) {
175 parent = parent._parent;
176 }
177
178 return this;
179 }
180
181 /**
182 * Removes the child at the specified index from this node's children and
183 * sets that node's parent to {@code null}. The child node to remove must be
184 * a {@code MutableTreeNode}.
185 *
186 * @param index the index in this node's child array of the child to remove
187 * @return {@code this} tree-node, for method chaining
188 * @throws ArrayIndexOutOfBoundsException if the {@code index} is out of
189 * bounds
190 */
191 public TreeNode<T> remove(final int index) {
192 final TreeNode<T> child = _children.remove(index);
193 assert child._parent == this;
194
195 TreeNode<T> parent = this;
196 while (parent != null) {
197 parent = parent._parent;
198 }
199
200 child.setParent(null);
201
202 return this;
203 }
204
205 /* *************************************************************************
206 * Derived operations
207 **************************************************************************/
208
209 /**
210 * Detaches the subtree rooted at {@code this} node from the tree, giving
211 * {@code this} node a {@code null} parent. Does nothing if {@code this}
212 * node is the root of its tree.
213 *
214 * @return {@code this}
215 */
216 public TreeNode<T> detach() {
217 if (_parent != null) {
218 _parent.remove(this);
219 }
220
221 return this;
222 }
223
224 /**
225 * Remove the {@code child} from {@code this} node's child array, giving it
226 * a {@code null} parent.
227 *
228 * @param child the child of this node to remove
229 * @throws NullPointerException if the given {@code child} is {@code null}
230 * @throws IllegalArgumentException if the given {@code child} is not a
231 * child of this node
232 */
233 public void remove(final TreeNode<T> child) {
234 requireNonNull(child);
235
236 if (!isChild(child)) {
237 throw new IllegalArgumentException("The given child is not a child.");
238 }
239 remove(getIndex(child));
240 }
241
242 /**
243 * Removes all children fo {@code this} node and setting their parents to
244 * {@code null}. If {@code this} node has no children, this method does
245 * nothing.
246 */
247 public void removeAllChildren() {
248 for (int i = 0; i < childCount(); ++i) {
249 remove(i);
250 }
251 }
252
253 /**
254 * Remove the given {@code child} from its parent and makes it a child of
255 * this node by adding it to the end of this node's child array.
256 *
257 * @param child the new child added to this node
258 * @return {@code this} tree-node, for method chaining
259 * @throws NullPointerException if the given {@code child} is {@code null}
260 */
261 public TreeNode<T> attach(final TreeNode<T> child) {
262 requireNonNull(child);
263
264 if (child._parent == this) {
265 insert(childCount() - 1, child);
266 } else {
267 insert(childCount(), child);
268 }
269
270 return this;
271 }
272
273 /**
274 * Attaches the given {@code children} to {@code this} node.
275 *
276 * @param children the children to attach to {@code this} node
277 * @return {@code this} tree-node, for method chaining
278 * @throws NullPointerException if the given {@code children} array is
279 * {@code null}
280 */
281 @SafeVarargs
282 public final TreeNode<T> attach(final T... children) {
283 for (T child : children) {
284 attach(TreeNode.of(child));
285 }
286
287 return this;
288 }
289
290 /**
291 * Attaches the given {@code child} to {@code this} node.
292 *
293 * @param child the child to attach to {@code this} node
294 * @return {@code this} tree-node, for method chaining
295 */
296 public TreeNode<T> attach(final T child) {
297 return attach(TreeNode.of(child));
298 }
299
300 @Override
301 public TreeNode<T> copy() {
302 return ofTree(this);
303 }
304
305 @Override
306 public int hashCode() {
307 return Tree.hashCode(this);
308 }
309
310 @Override
311 public boolean equals(final Object obj) {
312 return obj instanceof TreeNode<?> &&
313 Tree.equals(this, (TreeNode<?>)obj);
314 }
315
316 @Override
317 public String toString() {
318 return Tree.toString(this);
319 }
320
321
322
323 /* *************************************************************************
324 * Static factory methods.
325 **************************************************************************/
326
327 /**
328 * Return a new {@code TreeNode} from the given source {@code tree}. The
329 * whole tree is copied.
330 *
331 * @param tree the source tree the new tree-node is created from
332 * @param <T> the tree value type
333 * @return a new {@code TreeNode} from the given source {@code tree}
334 * @throws NullPointerException if the source {@code tree} is {@code null}
335 */
336 public static <T> TreeNode<T> ofTree(final Tree<? extends T, ?> tree) {
337 final TreeNode<T> target = of(tree.getValue());
338 fill(tree, target);
339 return target;
340 }
341
342 private static <T> void fill(
343 final Tree<? extends T, ?> source,
344 final TreeNode<T> target
345 ) {
346 source.childStream().forEachOrdered(child -> {
347 final TreeNode<T> targetChild = of(child.getValue());
348 target.attach(targetChild);
349 fill(child, targetChild);
350 });
351 }
352
353 /**
354 * Return a new {@code TreeNode} with the given node {@code value}.
355 *
356 * @param value the node value
357 * @param <T> the tree-node type
358 * @return a new tree-node
359 */
360 public static <T> TreeNode<T> of(final T value) {
361 return new TreeNode<>(value);
362 }
363
364 /**
365 * Return a new {@code TreeNode} with a {@code null} tree value.
366 *
367 * @param <T> the tree-node type
368 * @return a new tree-node
369 */
370 public static <T> TreeNode<T> of() {
371 return new TreeNode<>(null);
372 }
373
374 }
|