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