001 /*
002 * Java Genetic Algorithm Library (jenetics-4.4.0).
003 * Copyright (c) 2007-2019 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 import java.util.function.Function;
031
032 import io.jenetics.util.Copyable;
033 import io.jenetics.util.ISeq;
034
035 /**
036 * A general purpose node in a tree data-structure. The {@code TreeNode} is a
037 * mutable implementation of the {@link Tree} interface.
038 *
039 * @param <T> the value type of the tree node
040 *
041 * @author <a href="mailto:franz.wilhelmstoetter@gmail.com">Franz Wilhelmstötter</a>
042 * @version 4.3
043 * @since 3.9
044 */
045 public final class TreeNode<T>
046 implements
047 Tree<T, TreeNode<T>>,
048 Iterable<TreeNode<T>>,
049 Copyable<TreeNode<T>>,
050 Serializable
051 {
052 private static final long serialVersionUID = 1L;
053
054 private T _value;
055 private TreeNode<T> _parent;
056 private List<TreeNode<T>> _children;
057
058 /**
059 * Create a new tree node with no parent and children, but with the given
060 * user {@code value}.
061 *
062 * @param value the user value of the new tree node
063 */
064 private TreeNode(final T value) {
065 _value = value;
066 }
067
068
069 /* *************************************************************************
070 * Basic operations
071 **************************************************************************/
072
073 /**
074 * Sets the user object for this node.
075 *
076 * @param value the node {@code value}
077 */
078 public void setValue(final T value) {
079 _value = value;
080 }
081
082 /**
083 * Return the node value
084 *
085 * @return the node value
086 */
087 @Override
088 public T getValue() {
089 return _value;
090 }
091
092 /**
093 * Returns this node's parent if available.
094 *
095 * @return the tree-node, or an empty value if this node has no parent
096 */
097 @Override
098 public Optional<TreeNode<T>> getParent() {
099 return Optional.ofNullable(_parent);
100 }
101
102 /**
103 * Sets this node's parent, but does not change the parent's child array.
104 * This method is called from {@code insert()} and {@code remove()} to
105 * reassign a child's parent, and it should not be messaged from anywhere
106 * else.
107 *
108 * @param parent this node's new parent
109 */
110 void setParent(final TreeNode<T> parent) {
111 _parent = parent;
112 }
113
114 /**
115 * Returns the child at the specified index in this node's child array.
116 *
117 * @param index an index into this node's child array
118 * @return the tree-node in this node's child array at the specified index
119 * @throws ArrayIndexOutOfBoundsException if the {@code index} is out of
120 * bounds
121 */
122 @Override
123 public TreeNode<T> getChild(final int index) {
124 if (_children == null) {
125 throw new ArrayIndexOutOfBoundsException(format(
126 "Child index is out of bounds: %s", index
127 ));
128 }
129
130 return _children.get(index);
131 }
132
133 @Override
134 public int childCount() {
135 return _children != null ? _children.size() : 0;
136 }
137
138 /**
139 * Return an iterator that traverses the subtree rooted at {@code this} node
140 * in pre-order. The first node returned by the iterator is {@code this}
141 * node.
142 * <p>
143 * Modifying the tree by inserting, removing, or moving a node invalidates
144 * any iterator created before the modification.
145 *
146 * @see #postorderIterator
147 * @return an iterator for traversing the tree in pre-order
148 */
149 @Override
150 public Iterator<TreeNode<T>> iterator() {
151 return preorderIterator();
152 }
153
154 /**
155 * Removes the {@code child} from its present parent (if it has one), sets
156 * the child's parent to this node, and then adds the child to this node's
157 * child array at index {@code index}. The new {@code child} must not be
158 * {@code null} and must not be an ancestor of {@code this} node.
159 *
160 * @param index the index in the child array where this node is to be
161 * inserted
162 * @param child the sub-node to be inserted
163 * @return {@code this} tree-node, for method chaining
164 * @throws ArrayIndexOutOfBoundsException if {@code index} is out of bounds
165 * @throws IllegalArgumentException if {@code child} is an ancestor of
166 * {@code this} node
167 * @throws NullPointerException if the given {@code child} is {@code null}
168 */
169 public TreeNode<T> insert(final int index, final TreeNode<T> child) {
170 requireNonNull(child);
171 if (isAncestor(child)) {
172 throw new IllegalArgumentException("The new child is an ancestor.");
173 }
174
175 if (child._parent != null) {
176 child._parent.remove(child);
177 }
178
179 child.setParent(this);
180 createChildrenIfMissing();
181 _children.add(index, child);
182
183 return this;
184 }
185
186 // Only entry point for checking and creating non-existing children list.
187 private void createChildrenIfMissing() {
188 if (_children == null) {
189 _children = new ArrayList<>(2);
190 }
191 }
192
193 /**
194 * Replaces the child at the give index with the given {@code child}
195 *
196 * @param index the index of the child which will be replaced
197 * @param child the new child
198 * @return {@code this} tree-node, for method chaining
199 * @throws ArrayIndexOutOfBoundsException if the {@code index} is out of
200 * bounds
201 * @throws IllegalArgumentException if {@code child} is an ancestor of
202 * {@code this} node
203 * @throws NullPointerException if the given {@code child} is {@code null}
204 */
205 public TreeNode<T> replace(final int index, final TreeNode<T> child) {
206 requireNonNull(child);
207 if (_children == null) {
208 throw new ArrayIndexOutOfBoundsException(format(
209 "Child index is out of bounds: %s", index
210 ));
211 }
212 if (isAncestor(child)) {
213 throw new IllegalArgumentException("The new child is an ancestor.");
214 }
215
216 final TreeNode<T> oldChild = _children.set(index, child);
217 assert oldChild != null;
218 assert oldChild._parent == this;
219
220 oldChild.setParent(null);
221 child.setParent(this);
222
223 return this;
224 }
225
226 /**
227 * Removes the child at the specified index from this node's children and
228 * sets that node's parent to {@code null}.
229 *
230 * @param index the index in this node's child array of the child to remove
231 * @return {@code this} tree-node, for method chaining
232 * @throws ArrayIndexOutOfBoundsException if the {@code index} is out of
233 * bounds
234 */
235 public TreeNode<T> remove(final int index) {
236 if (_children == null) {
237 throw new ArrayIndexOutOfBoundsException(format(
238 "Child index is out of bounds: %s", index
239 ));
240 }
241
242 final TreeNode<T> child = _children.remove(index);
243 assert child._parent == this;
244 child.setParent(null);
245
246 if (_children.isEmpty()) {
247 _children = null;
248 }
249
250 return this;
251 }
252
253 /**
254 * Removes the child at the given {@code path}. If no child exists at the
255 * given path, nothing is removed.
256 *
257 * @since 4.4
258 *
259 * @param path the path of the child to replace
260 * @return {@code true} if a child at the given {@code path} existed and
261 * has been removed
262 * @throws NullPointerException if one of the given argument is {@code null}
263 */
264 public boolean removeAtPath(final Path path) {
265 final Optional<TreeNode<T>> parent = childAtPath(path)
266 .flatMap(Tree::getParent);
267
268 parent.ifPresent(p -> p.remove(path.get(path.length() - 1)));
269 return parent.isPresent();
270 }
271
272 /**
273 * Replaces the child at the given {@code path} with the given new
274 * {@code child}. If no child exists at the given path, nothing is replaced.
275 *
276 * @since 4.4
277 *
278 * @param path the path of the child to replace
279 * @param child the new child
280 * @return {@code true} if a child at the given {@code path} existed and
281 * has been replaced
282 * @throws NullPointerException if one of the given argument is {@code null}
283 */
284 public boolean replaceAtPath(final Path path, final TreeNode<T> child) {
285 requireNonNull(path);
286 requireNonNull(child);
287
288 final Optional<TreeNode<T>> old = childAtPath(path);
289 final Optional<TreeNode<T>> parent = old.flatMap(TreeNode::getParent);
290
291 if (parent.isPresent()) {
292 parent.orElseThrow(AssertionError::new)
293 .replace(path.get(path.length() - 1), child);
294 } else {
295 removeAllChildren();
296 setValue(child.getValue());
297
298 final ISeq<TreeNode<T>> nodes = child.childStream()
299 .collect(ISeq.toISeq());
300
301 for (TreeNode<T> node : nodes) {
302 attach(node);
303 }
304 }
305
306 return old.isPresent();
307 }
308
309 /* *************************************************************************
310 * Derived operations
311 **************************************************************************/
312
313 /**
314 * Detaches the subtree rooted at {@code this} node from the tree, giving
315 * {@code this} node a {@code null} parent. Does nothing if {@code this}
316 * node is the root of its tree.
317 *
318 * @return {@code this}
319 */
320 public TreeNode<T> detach() {
321 if (_parent != null) {
322 _parent.remove(this);
323 }
324
325 return this;
326 }
327
328 /**
329 * Remove the {@code child} from {@code this} node's child array, giving it
330 * a {@code null} parent.
331 *
332 * @param child the child of this node to remove
333 * @throws NullPointerException if the given {@code child} is {@code null}
334 * @throws IllegalArgumentException if the given {@code child} is not a
335 * child of this node
336 */
337 public void remove(final Tree<?, ?> child) {
338 requireNonNull(child);
339
340 if (!isChild(child)) {
341 throw new IllegalArgumentException("The given child is not a child.");
342 }
343 remove(getIndex(child));
344 }
345
346 /**
347 * Removes all children fo {@code this} node and setting their parents to
348 * {@code null}. If {@code this} node has no children, this method does
349 * nothing.
350 */
351 public void removeAllChildren() {
352 for (int i = 0, n = childCount(); i < n; ++i) {
353 remove(_children.size() - 1);
354 }
355 }
356
357 /**
358 * Remove the given {@code child} from its parent and makes it a child of
359 * this node by adding it to the end of this node's child array.
360 *
361 * @param child the new child added to this node
362 * @return {@code this} tree-node, for method chaining
363 * @throws NullPointerException if the given {@code child} is {@code null}
364 */
365 public TreeNode<T> attach(final TreeNode<T> child) {
366 requireNonNull(child);
367
368 if (child._parent == this) {
369 insert(childCount() - 1, child);
370 } else {
371 insert(childCount(), child);
372 }
373
374 return this;
375 }
376
377 /**
378 * Attaches the given {@code children} to {@code this} node.
379 *
380 * @param children the children to attach to {@code this} node
381 * @return {@code this} tree-node, for method chaining
382 * @throws NullPointerException if the given {@code children} array is
383 * {@code null}
384 */
385 @SafeVarargs
386 public final TreeNode<T> attach(final T... children) {
387 for (T child : children) {
388 attach(TreeNode.of(child));
389 }
390
391 return this;
392 }
393
394 /**
395 * Attaches the given {@code child} to {@code this} node.
396 *
397 * @param child the child to attach to {@code this} node
398 * @return {@code this} tree-node, for method chaining
399 */
400 public TreeNode<T> attach(final T child) {
401 return attach(TreeNode.of(child));
402 }
403
404 @Override
405 public TreeNode<T> copy() {
406 return ofTree(this);
407 }
408
409 /**
410 * Returns a new {@code TreeNode} consisting of all nodes of {@code this}
411 * tree, but with a different value type, created by applying the given
412 * function to the node values of {@code this} tree.
413 *
414 * @param mapper the node value mapper
415 * @param <B> the new node type
416 * @return a new tree consisting of all nodes of {@code this} tree
417 * @throws NullPointerException if the given {@code mapper} function is
418 * {@code null}
419 */
420 public <B> TreeNode<B> map(final Function<? super T, ? extends B> mapper) {
421 final TreeNode<B> target = of(mapper.apply(getValue()));
422 fill(this, target, mapper);
423 return target;
424 }
425
426
427 @Override
428 public int hashCode() {
429 return Tree.hashCode(this);
430 }
431
432 @Override
433 public boolean equals(final Object obj) {
434 return obj == this ||
435 obj instanceof TreeNode &&
436 Tree.equals(this, (TreeNode)obj);
437 }
438
439 @Override
440 public String toString() {
441 return Tree.toString(this);
442 }
443
444
445
446 /* *************************************************************************
447 * Static factory methods.
448 **************************************************************************/
449
450 /**
451 * Return a new {@code TreeNode} with a {@code null} tree value.
452 *
453 * @param <T> the tree-node type
454 * @return a new tree-node
455 */
456 public static <T> TreeNode<T> of() {
457 return of(null);
458 }
459
460 /**
461 * Return a new {@code TreeNode} with the given node {@code value}.
462 *
463 * @param value the node value
464 * @param <T> the tree-node type
465 * @return a new tree-node
466 */
467 public static <T> TreeNode<T> of(final T value) {
468 return new TreeNode<>(value);
469 }
470
471 /**
472 * Return a new {@code TreeNode} from the given source {@code tree}. The
473 * whole tree is copied.
474 *
475 * @param tree the source tree the new tree-node is created from
476 * @param mapper the tree value mapper function
477 * @param <T> the current tree value type
478 * @param <B> the mapped tree value type
479 * @return a new {@code TreeNode} from the given source {@code tree}
480 * @throws NullPointerException if one of the arguments is {@code null}
481 */
482 public static <T, B> TreeNode<B> ofTree(
483 final Tree<? extends T, ?> tree,
484 final Function<? super T, ? extends B> mapper
485 ) {
486 final TreeNode<B> target = of(mapper.apply(tree.getValue()));
487 fill(tree, target, mapper);
488 return target;
489 }
490
491 private static <T, B> void fill(
492 final Tree<? extends T, ?> source,
493 final TreeNode<B> target,
494 final Function<? super T, ? extends B> mapper
495 ) {
496 source.childStream().forEachOrdered(child -> {
497 final TreeNode<B> targetChild = of(mapper.apply(child.getValue()));
498 target.attach(targetChild);
499 fill(child, targetChild, mapper);
500 });
501 }
502
503 /**
504 * Return a new {@code TreeNode} from the given source {@code tree}. The
505 * whole tree is copied.
506 *
507 * @param tree the source tree the new tree-node is created from
508 * @param <T> the current tree value type
509 * @return a new {@code TreeNode} from the given source {@code tree}
510 * @throws NullPointerException if the source {@code tree} is {@code null}
511 */
512 public static <T> TreeNode<T> ofTree(final Tree<? extends T, ?> tree) {
513 return ofTree(tree, Function.identity());
514 }
515
516 /**
517 * Parses a (parentheses) tree string, created with
518 * {@link Tree#toParenthesesString()}. The tree string might look like this:
519 * <pre>
520 * mul(div(cos(1.0), cos(π)), sin(mul(1.0, z)))
521 * </pre>
522 *
523 * @see Tree#toParenthesesString(Function)
524 * @see Tree#toParenthesesString()
525 * @see TreeNode#parse(String, Function)
526 *
527 * @since 4.3
528 *
529 * @param tree the parentheses tree string
530 * @return the parsed tree
531 * @throws NullPointerException if the given {@code tree} string is
532 * {@code null}
533 * @throws IllegalArgumentException if the given tree string could not be
534 * parsed
535 */
536 public static TreeNode<String> parse(final String tree) {
537 return TreeParser.parse(tree, Function.identity());
538 }
539
540 /**
541 * Parses a (parentheses) tree string, created with
542 * {@link Tree#toParenthesesString()}. The tree string might look like this
543 * <pre>
544 * 0(1(4,5),2(6),3(7(10,11),8,9))
545 * </pre>
546 * and can be parsed to an integer tree with the following code:
547 * <pre>{@code
548 * final Tree<Integer, ?> tree = TreeNode.parse(
549 * "0(1(4,5),2(6),3(7(10,11),8,9))",
550 * Integer::parseInt
551 * );
552 * }</pre>
553 *
554 * @see Tree#toParenthesesString(Function)
555 * @see Tree#toParenthesesString()
556 * @see TreeNode#parse(String)
557 *
558 * @since 4.3
559 *
560 * @param <B> the tree node value type
561 * @param tree the parentheses tree string
562 * @param mapper the mapper which converts the serialized string value to
563 * the desired type
564 * @return the parsed tree object
565 * @throws NullPointerException if one of the arguments is {@code null}
566 * @throws IllegalArgumentException if the given parentheses tree string
567 * doesn't represent a valid tree
568 */
569 public static <B> TreeNode<B> parse(
570 final String tree,
571 final Function<? super String, ? extends B> mapper
572 ) {
573 return TreeParser.parse(tree, mapper);
574 }
575
576 }
|