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