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.util.Objects.requireNonNull;
023 import static io.jenetics.internal.util.Hashes.hash;
024
025 import java.io.Serializable;
026 import java.util.Arrays;
027 import java.util.Iterator;
028 import java.util.Objects;
029 import java.util.Optional;
030 import java.util.function.Function;
031 import java.util.stream.IntStream;
032 import java.util.stream.Stream;
033
034 import io.jenetics.util.ISeq;
035 import io.jenetics.util.MSeq;
036
037 /**
038 * Default implementation of the {@link FlatTree} interface.
039 *
040 * @author <a href="mailto:franz.wilhelmstoetter@gmail.com">Franz Wilhelmstötter</a>
041 * @version 4.1
042 * @since 3.9
043 */
044 public final class FlatTreeNode<T>
045 implements
046 FlatTree<T, FlatTreeNode<T>>,
047 Serializable
048 {
049 private static final long serialVersionUID = 1L;
050
051 private final int _index;
052 private final MSeq<T> _nodes;
053 private final int[] _childOffsets;
054 private final int[] _childCounts;
055
056 private FlatTreeNode(
057 final int index,
058 final MSeq<T> nodes,
059 final int[] childOffsets,
060 final int[] childCounts
061 ) {
062 _index = index;
063 _nodes = requireNonNull(nodes);
064 _childOffsets = requireNonNull(childOffsets);
065 _childCounts = requireNonNull(childCounts);
066 }
067
068 /**
069 * Returns the root of the tree that contains this node. The root is the
070 * ancestor with no parent. This implementation have a runtime complexity
071 * of O(1).
072 *
073 * @return the root of the tree that contains this node
074 */
075 @Override
076 public FlatTreeNode<T> getRoot() {
077 return nodeAt(0);
078 }
079
080 @Override
081 public boolean isRoot() {
082 return _index == 0;
083 }
084
085 private FlatTreeNode<T> nodeAt(final int index) {
086 return new FlatTreeNode<T>(
087 index,
088 _nodes,
089 _childOffsets,
090 _childCounts
091 );
092 }
093
094 @Override
095 public T getValue() {
096 return _nodes.get(_index);
097 }
098
099 @Override
100 public Optional<FlatTreeNode<T>> getParent() {
101 return stream()
102 .filter(node -> node.childStream().anyMatch(this::identical))
103 .findFirst();
104 }
105
106 @Override
107 public FlatTreeNode<T> getChild(final int index) {
108 if (index < 0 || index >= childCount()) {
109 throw new IndexOutOfBoundsException(Integer.toString(index));
110 }
111
112 return new FlatTreeNode<T>(
113 childOffset() + index,
114 _nodes,
115 _childOffsets,
116 _childCounts
117 );
118 }
119
120 @Override
121 public int childCount() {
122 return _childCounts[_index];
123 }
124
125 /**
126 * Return the index of the first child node in the underlying node array.
127 * {@code -1} is returned if {@code this} node is a leaf.
128 *
129 * @return Return the index of the first child node in the underlying node
130 * array, or {@code -1} if {@code this} node is a leaf
131 */
132 @Override
133 public int childOffset() {
134 return _childOffsets[_index];
135 }
136
137 @Override
138 public ISeq<FlatTreeNode<T>> flattenedNodes() {
139 return stream().collect(ISeq.toISeq());
140 }
141
142 /**
143 * Return a stream of all nodes of the whole underlying tree. This method
144 * call is equivalent to
145 * <pre>{@code
146 * final Stream<FlatTreeNode<T>> nodes = getRoot().breadthFirstStream();
147 * }</pre>
148 *
149 * @return a stream of all nodes of the whole underlying tree
150 */
151 public Stream<FlatTreeNode<T>> stream() {
152 return IntStream.range(0, _nodes.size()).mapToObj(this::nodeAt);
153 }
154
155 /**
156 * Return a sequence of all <em>mapped</em> nodes of the whole underlying
157 * tree. This is a convenient method for
158 * <pre>{@code
159 * final ISeq<B> seq = stream()
160 * .map(mapper)
161 * .collect(ISeq.toISeq())
162 * }</pre>
163 *
164 * @param mapper the mapper function
165 * @param <B> the mapped type
166 * @return a sequence of all <em>mapped</em> nodes
167 */
168 public <B> ISeq<B> map(final Function<FlatTreeNode<T>, ? extends B> mapper) {
169 return stream()
170 .map(mapper)
171 .collect(ISeq.toISeq());
172 }
173
174 @Override
175 public boolean identical(final Tree<?, ?> other) {
176 return other == this ||
177 other instanceof FlatTreeNode &&
178 ((FlatTreeNode)other)._index == _index &&
179 ((FlatTreeNode)other)._nodes == _nodes;
180 }
181
182 @Override
183 public int hashCode() {
184 return hash(_index, hash(_nodes, hash(_childCounts, hash(_childOffsets))));
185 }
186
187 @Override
188 public boolean equals(final Object obj) {
189 return obj instanceof FlatTreeNode &&
190 ((FlatTreeNode)obj)._index == _index &&
191 Objects.equals(((FlatTreeNode)obj)._nodes, _nodes) &&
192 Arrays.equals(((FlatTreeNode)obj)._childCounts, _childCounts) &&
193 Arrays.equals(((FlatTreeNode)obj)._childOffsets, _childOffsets);
194 }
195
196 @Override
197 public String toString() {
198 return Objects.toString(getValue());
199 }
200
201 /**
202 * Create a new {@code FlatTreeNode} from the given {@code tree}.
203 *
204 * @param tree the source tree
205 * @param <V> the tree value types
206 * @return a new {@code FlatTreeNode} from the given {@code tree}
207 * @throws NullPointerException if the given {@code tree} is {@code null}
208 */
209 public static <V> FlatTreeNode<V> of(final Tree<? extends V, ?> tree) {
210 requireNonNull(tree);
211
212 final int size = tree.size();
213 final MSeq<V> elements = MSeq.ofLength(size);
214 final int[] childOffsets = new int[size];
215 final int[] childCounts = new int[size];
216
217 assert size >= 1;
218 final FlatTreeNode<V> root = new FlatTreeNode<>(
219 0,
220 elements,
221 childOffsets,
222 childCounts
223 );
224
225 int childOffset = 1;
226 int index = 0;
227 final Iterator<? extends Tree<? extends V, ?>> it =
228 tree.breadthFirstIterator();
229
230 while (it.hasNext()) {
231 final Tree<? extends V, ?> node = it.next();
232
233 elements.set(index, node.getValue());
234 childCounts[index] = node.childCount();
235 childOffsets[index] = node.isLeaf() ? -1 : childOffset;
236
237 childOffset += node.childCount();
238 ++index;
239 }
240
241 return root;
242 }
243
244 }
|