001 /*
002 * Java Genetic Algorithm Library (jenetics-6.0.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 */
259 public static <V> FlatTreeNode<V> of(final Tree<? extends V, ?> tree) {
260 requireNonNull(tree);
261
262 final int size = tree.size();
263 assert size >= 1;
264
265 final Object[] elements = new Object[size];
266 final int[] childOffsets = new int[size];
267 final int[] childCounts = new int[size];
268
269 int childOffset = 1;
270 int index = 0;
271
272 for (Tree<?, ?> node : tree) {
273 elements[index] = node.value();
274 childCounts[index] = node.childCount();
275 childOffsets[index] = node.isLeaf() ? -1 : childOffset;
276
277 childOffset += node.childCount();
278 ++index;
279 }
280
281 return new FlatTreeNode<>(
282 0,
283 elements,
284 childOffsets,
285 childCounts
286 );
287 }
288
289 /**
290 * Parses a (parentheses) tree string, created with
291 * {@link Tree#toParenthesesString()}. The tree string might look like this:
292 * <pre>
293 * mul(div(cos(1.0),cos(π)),sin(mul(1.0,z)))
294 * </pre>
295 *
296 * @see Tree#toParenthesesString(Function)
297 * @see Tree#toParenthesesString()
298 * @see TreeNode#parse(String)
299 *
300 * @since 5.0
301 *
302 * @param tree the parentheses tree string
303 * @return the parsed tree
304 * @throws NullPointerException if the given {@code tree} string is
305 * {@code null}
306 * @throws IllegalArgumentException if the given tree string could not be
307 * parsed
308 */
309 public static FlatTreeNode<String> parse(final String tree) {
310 return of(ParenthesesTreeParser.parse(tree, Function.identity()));
311 }
312
313 /**
314 * Parses a (parentheses) tree string, created with
315 * {@link Tree#toParenthesesString()}. The tree string might look like this
316 * <pre>
317 * 0(1(4,5),2(6),3(7(10,11),8,9))
318 * </pre>
319 * and can be parsed to an integer tree with the following code:
320 * <pre>{@code
321 * final Tree<Integer, ?> tree = FlatTreeNode.parse(
322 * "0(1(4,5),2(6),3(7(10,11),8,9))",
323 * Integer::parseInt
324 * );
325 * }</pre>
326 *
327 * @see Tree#toParenthesesString(Function)
328 * @see Tree#toParenthesesString()
329 * @see TreeNode#parse(String, Function)
330 *
331 * @since 5.0
332 *
333 * @param <B> the tree node value type
334 * @param tree the parentheses tree string
335 * @param mapper the mapper which converts the serialized string value to
336 * the desired type
337 * @return the parsed tree object
338 * @throws NullPointerException if one of the arguments is {@code null}
339 * @throws IllegalArgumentException if the given parentheses tree string
340 * doesn't represent a valid tree
341 */
342 public static <B> FlatTreeNode<B> parse(
343 final String tree,
344 final Function<? super String, ? extends B> mapper
345 ) {
346 return of(ParenthesesTreeParser.parse(tree, mapper));
347 }
348
349
350 /* *************************************************************************
351 * Java object serialization
352 * ************************************************************************/
353
354 private Object writeReplace() {
355 return new Serial(Serial.FLAT_TREE_NODE, this);
356 }
357
358 private void readObject(final ObjectInputStream stream)
359 throws InvalidObjectException
360 {
361 throw new InvalidObjectException("Serialization proxy required.");
362 }
363
364
365 void write(final ObjectOutput out) throws IOException {
366 final FlatTreeNode<V> node = _index == 0
367 ? this
368 : FlatTreeNode.of(this);
369
370 writeObjectArray(node._elements, out);
371 writeIntArray(node._childOffsets, out);
372 writeIntArray(node._childCounts, out);
373 }
374
375 @SuppressWarnings("rawtypes")
376 static FlatTreeNode read(final ObjectInput in)
377 throws IOException, ClassNotFoundException
378 {
379 return new FlatTreeNode(
380 0,
381 readObjectArray(in),
382 readIntArray(in),
383 readIntArray(in)
384 );
385 }
386
387 }
|