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