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