TreeNode.java
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 }