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.util.Objects.requireNonNull;
023 import static io.jenetics.internal.util.SerialIO.readIntArray;
024 import static io.jenetics.internal.util.SerialIO.readObjectArray;
025 import static io.jenetics.internal.util.SerialIO.writeIntArray;
026 import static io.jenetics.internal.util.SerialIO.writeObjectArray;
027
028 import java.io.IOException;
029 import java.io.InvalidObjectException;
030 import java.io.ObjectInput;
031 import java.io.ObjectInputStream;
032 import java.io.ObjectOutput;
033 import java.io.Serializable;
034 import java.util.Arrays;
035 import java.util.Iterator;
036 import java.util.Optional;
037 import java.util.function.Function;
038 import java.util.stream.IntStream;
039 import java.util.stream.Stream;
040
041 import io.jenetics.util.ISeq;
042
043 /**
044 * Default implementation of the {@link FlatTree} interface. Beside the
045 * flattened and dense layout it is also an <em>immutable</em> implementation of
046 * the {@link Tree} interface. It can only be created from an existing tree.
047 *
048 * <pre>{@code
049 * final Tree<String, ?> immutable = FlatTreeNode.ofTree(TreeNode.parse(...));
050 * }</pre>
051 *
052 * @implNote
053 * This class is immutable and thread-safe.
054 *
055 * @author <a href="mailto:franz.wilhelmstoetter@gmail.com">Franz Wilhelmstötter</a>
056 * @version 6.0
057 * @since 3.9
058 */
059 public final class FlatTreeNode<V>
060 implements
061 FlatTree<V, FlatTreeNode<V>>,
062 Serializable
063 {
064 private static final long serialVersionUID = 3L;
065
066 private static final int NULL_INDEX = -1;
067
068 private final int _index;
069 private final Object[] _elements;
070 private final int[] _childOffsets;
071 private final int[] _childCounts;
072
073 private FlatTreeNode(
074 final int index,
075 final Object[] elements,
076 final int[] childOffsets,
077 final int[] childCounts
078 ) {
079 _index = index;
080 _elements = requireNonNull(elements);
081 _childOffsets = requireNonNull(childOffsets);
082 _childCounts = requireNonNull(childCounts);
083 }
084
085 /**
086 * Returns the root of the tree that contains this node. The root is the
087 * ancestor with no parent. This implementation have a runtime complexity
088 * of O(1).
089 *
090 * @return the root of the tree that contains this node
091 */
092 @Override
093 public FlatTreeNode<V> root() {
094 return nodeAt(0);
095 }
096
097 @Override
098 public boolean isRoot() {
099 return _index == 0;
100 }
101
102 private FlatTreeNode<V> nodeAt(final int index) {
103 return new FlatTreeNode<>(
104 index,
105 _elements,
106 _childOffsets,
107 _childCounts
108 );
109 }
110
111 @SuppressWarnings("unchecked")
112 @Override
113 public V value() {
114 return (V)_elements[_index];
115 }
116
117 @Override
118 public Optional<FlatTreeNode<V>> parent() {
119 int index = NULL_INDEX;
120 for (int i = _index; --i >= 0 && index == NULL_INDEX;) {
121 if (isParent(i)) {
122 index = i;
123 }
124 }
125
126 return index != NULL_INDEX
127 ? Optional.of(nodeAt(index))
128 : Optional.empty();
129 }
130
131 private boolean isParent(final int index) {
132 return _childCounts[index] > 0 &&
133 _childOffsets[index] <= _index &&
134 _childOffsets[index] + _childCounts[index] > _index;
135 }
136
137 @Override
138 public FlatTreeNode<V> childAt(final int index) {
139 if (index < 0 || index >= childCount()) {
140 throw new IndexOutOfBoundsException(Integer.toString(index));
141 }
142
143 return nodeAt(childOffset() + index);
144 }
145
146 @Override
147 public int childCount() {
148 return _childCounts[_index];
149 }
150
151 /**
152 * Return the index of the first child node in the underlying node array.
153 * {@code -1} is returned if {@code this} node is a leaf.
154 *
155 * @return Return the index of the first child node in the underlying node
156 * array, or {@code -1} if {@code this} node is a leaf
157 */
158 @Override
159 public int childOffset() {
160 return _childOffsets[_index];
161 }
162
163 @Override
164 public ISeq<FlatTreeNode<V>> flattenedNodes() {
165 return stream().collect(ISeq.toISeq());
166 }
167
168 @Override
169 public Iterator<FlatTreeNode<V>> breadthFirstIterator() {
170 return _index == 0
171 ? new IntIterator<>(_elements.length, this::nodeAt)
172 : FlatTree.super.breadthFirstIterator();
173 }
174
175 @Override
176 public Stream<FlatTreeNode<V>> breadthFirstStream() {
177 return _index == 0
178 ? IntStream.range(0, _elements.length).mapToObj(this::nodeAt)
179 : FlatTree.super.breadthFirstStream();
180 }
181
182 /**
183 * Return a sequence of all <em>mapped</em> nodes of the whole underlying
184 * tree. This is a convenient method for
185 * <pre>{@code
186 * final ISeq<B> seq = stream()
187 * .map(mapper)
188 * .collect(ISeq.toISeq())
189 * }</pre>
190 *
191 * @param mapper the mapper function
192 * @param <B> the mapped type
193 * @return a sequence of all <em>mapped</em> nodes
194 */
195 public <B> ISeq<B>
196 map(final Function<? super FlatTreeNode<V>, ? extends B> mapper) {
197 return stream()
198 .map(mapper)
199 .collect(ISeq.toISeq());
200 }
201
202 @Override
203 public boolean identical(final Tree<?, ?> other) {
204 return other == this ||
205 other instanceof FlatTreeNode &&
206 ((FlatTreeNode)other)._index == _index &&
207 ((FlatTreeNode)other)._elements == _elements;
208 }
209
210 @Override
211 public int hashCode() {
212 return Tree.hashCode(this);
213 }
214
215 @Override
216 public boolean equals(final Object obj) {
217 return obj == this ||
218 obj instanceof FlatTreeNode &&
219 (equals((FlatTreeNode<?>)obj) || Tree.equals((Tree<?, ?>)obj, this));
220 }
221
222 private boolean equals(final FlatTreeNode<?> tree) {
223 return tree._index == _index &&
224 Arrays.equals(tree._elements, _elements) &&
225 Arrays.equals(tree._childCounts, _childCounts) &&
226 Arrays.equals(tree._childOffsets, _childOffsets);
227 }
228
229 @Override
230 public String toString() {
231 return toParenthesesString();
232 }
233
234 @Override
235 public int size() {
236 return _index == 0
237 ? _elements.length
238 : countChildren(_index) + 1;
239 }
240
241 private int countChildren(final int index) {
242 int count = _childCounts[index];
243 for (int i = 0; i < _childCounts[index]; ++i) {
244 count += countChildren(_childOffsets[index] + i);
245 }
246 return count;
247 }
248
249 /* *************************************************************************
250 * Static factories
251 * ************************************************************************/
252
253 /**
254 * Create a new, immutable {@code FlatTreeNode} from the given {@code tree}.
255 *
256 * @param tree the source tree
257 * @param <V> the tree value types
258 * @return a new {@code FlatTreeNode} from the given {@code tree}
259 * @throws NullPointerException if the given {@code tree} is {@code null}
260 * @deprecated Use {@link #ofTree(Tree)} instead
261 */
262 @Deprecated(since = "6.1", forRemoval = true)
263 public static <V> FlatTreeNode<V> of(final Tree<? extends V, ?> tree) {
264 return ofTree(tree);
265 }
266
267 /**
268 * Create a new, immutable {@code FlatTreeNode} from the given {@code tree}.
269 *
270 * @param tree the source tree
271 * @param <V> the tree value types
272 * @return a new {@code FlatTreeNode} from the given {@code tree}
273 * @throws NullPointerException if the given {@code tree} is {@code null}
274 */
275 public static <V> FlatTreeNode<V> ofTree(final Tree<? extends V, ?> tree) {
276 requireNonNull(tree);
277
278 final int size = tree.size();
279 assert size >= 1;
280
281 final var elements = new Object[size];
282 final var childOffsets = new int[size];
283 final var childCounts = new int[size];
284
285 int childOffset = 1;
286 int index = 0;
287
288 for (Tree<?, ?> node : tree) {
289 elements[index] = node.value();
290 childCounts[index] = node.childCount();
291 childOffsets[index] = node.isLeaf() ? NULL_INDEX : childOffset;
292
293 childOffset += node.childCount();
294 ++index;
295 }
296 assert index == size;
297
298 return new FlatTreeNode<>(
299 0,
300 elements,
301 childOffsets,
302 childCounts
303 );
304 }
305
306 /**
307 * Parses a (parentheses) tree string, created with
308 * {@link Tree#toParenthesesString()}. The tree string might look like this:
309 * <pre>
310 * mul(div(cos(1.0),cos(π)),sin(mul(1.0,z)))
311 * </pre>
312 *
313 * @see Tree#toParenthesesString(Function)
314 * @see Tree#toParenthesesString()
315 * @see TreeNode#parse(String)
316 *
317 * @since 5.0
318 *
319 * @param tree the parentheses tree string
320 * @return the parsed tree
321 * @throws NullPointerException if the given {@code tree} string is
322 * {@code null}
323 * @throws IllegalArgumentException if the given tree string could not be
324 * parsed
325 */
326 public static FlatTreeNode<String> parse(final String tree) {
327 return ofTree(ParenthesesTreeParser.parse(tree, Function.identity()));
328 }
329
330 /**
331 * Parses a (parentheses) tree string, created with
332 * {@link Tree#toParenthesesString()}. The tree string might look like this
333 * <pre>
334 * 0(1(4,5),2(6),3(7(10,11),8,9))
335 * </pre>
336 * and can be parsed to an integer tree with the following code:
337 * <pre>{@code
338 * final Tree<Integer, ?> tree = FlatTreeNode.parse(
339 * "0(1(4,5),2(6),3(7(10,11),8,9))",
340 * Integer::parseInt
341 * );
342 * }</pre>
343 *
344 * @see Tree#toParenthesesString(Function)
345 * @see Tree#toParenthesesString()
346 * @see TreeNode#parse(String, Function)
347 *
348 * @since 5.0
349 *
350 * @param <B> the tree node value type
351 * @param tree the parentheses tree string
352 * @param mapper the mapper which converts the serialized string value to
353 * the desired type
354 * @return the parsed tree object
355 * @throws NullPointerException if one of the arguments is {@code null}
356 * @throws IllegalArgumentException if the given parentheses tree string
357 * doesn't represent a valid tree
358 */
359 public static <B> FlatTreeNode<B> parse(
360 final String tree,
361 final Function<? super String, ? extends B> mapper
362 ) {
363 return ofTree(ParenthesesTreeParser.parse(tree, mapper));
364 }
365
366
367 /* *************************************************************************
368 * Java object serialization
369 * ************************************************************************/
370
371 private Object writeReplace() {
372 return new Serial(Serial.FLAT_TREE_NODE, this);
373 }
374
375 private void readObject(final ObjectInputStream stream)
376 throws InvalidObjectException
377 {
378 throw new InvalidObjectException("Serialization proxy required.");
379 }
380
381
382 void write(final ObjectOutput out) throws IOException {
383 final FlatTreeNode<V> node = _index == 0
384 ? this
385 : FlatTreeNode.ofTree(this);
386
387 writeObjectArray(node._elements, out);
388 writeIntArray(node._childOffsets, out);
389 writeIntArray(node._childCounts, out);
390 }
391
392 @SuppressWarnings("rawtypes")
393 static FlatTreeNode read(final ObjectInput in)
394 throws IOException, ClassNotFoundException
395 {
396 return new FlatTreeNode(
397 0,
398 readObjectArray(in),
399 readIntArray(in),
400 readIntArray(in)
401 );
402 }
403
404 }
|