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