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