01 /*
02 * Java Genetic Algorithm Library (jenetics-4.3.0).
03 * Copyright (c) 2007-2018 Franz Wilhelmstötter
04 *
05 * Licensed under the Apache License, Version 2.0 (the "License");
06 * you may not use this file except in compliance with the License.
07 * You may obtain a copy of the License at
08 *
09 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 *
17 * Author:
18 * Franz Wilhelmstötter (franz.wilhelmstoetter@gmail.com)
19 */
20 package io.jenetics.ext.util;
21
22 import io.jenetics.util.ISeq;
23
24 /**
25 * Tree specification, where the nodes of the whole tree are stored in an array.
26 * The tree
27 * <pre>
28 * 0
29 * ├── 1
30 * │ ├── 4
31 * │ └── 5
32 * ├── 2
33 * │ └── 6
34 * └── 3
35 * ├── 7
36 * │ ├── 10
37 * │ └── 11
38 * ├── 8
39 * └── 9
40 * </pre>
41 * will be stored in breadth-first order and will look like this:
42 * <pre>
43 * ┌─┬───┐ ┌──────┬──┐
44 * 0 1 2 3 4 5 6 7 8 9 10 11
45 * └─│─│─┴─┘ │ │ │
46 * └─│─────┘ │ │
47 * └───────┴───┘
48 * </pre>
49 * The child nodes are always stored on the right side of the parent flattenedNodes. So
50 * you have to read the tree from left to right. All children of a parent node
51 * are stored continuously after the {@code childOffset} and are defined by the
52 * sub-array {@code [childOffset, childOffset + childCount)}.
53 *
54 * @author <a href="mailto:franz.wilhelmstoetter@gmail.com">Franz Wilhelmstötter</a>
55 * @version 3.9
56 * @since 3.9
57 */
58 public interface FlatTree<V, T extends FlatTree<V, T>> extends Tree<V, T> {
59
60 /**
61 * Return the index of the first child node in the underlying node array.
62 * {@code -1} is returned if {@code this} node is a leaf.
63 *
64 * @return Return the index of the first child node in the underlying node
65 * array, or {@code -1} if {@code this} node is a leaf
66 */
67 public int childOffset();
68
69 /**
70 * Return the whole flattened tree values in breadth-first order. This is
71 * equivalent to
72 * <pre>{@code
73 * final ISeq<T> seq = getRoot().breadthFirstStream()
74 * .collect(ISeq.toISeq());
75 * }</pre>
76 *
77 * @return the flattened tree values in breadth-first order
78 */
79 public default ISeq<T> flattenedNodes() {
80 return getRoot().breadthFirstStream().collect(ISeq.toISeq());
81 }
82
83 }
|