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