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