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