001/*
002 * Java Genetic Algorithm Library (jenetics-8.1.0).
003 * Copyright (c) 2007-2024 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 io.jenetics.util.ISeq;
023
024/**
025 * Tree specification, where the nodes of the whole tree are stored in an array.
026 * The tree
027 * <pre>
028 * 0
029 * ├── 1
030 * │   ├── 4
031 * │   └── 5
032 * ├── 2
033 * │   └── 6
034 * └── 3
035 *     ├── 7
036 *     │   ├── 10
037 *     │   └── 11
038 *     ├── 8
039 *     └── 9
040 * </pre>
041 * will be stored in breadth-first order and will look like this:
042 * <pre>
043 * ┌─┬─┬─┐       ┌──────┬──┐
044 * 0 1 2 3 4 5 6 7 8 9 10 11
045 *   └─│─│─┴─┘ │ │ │ │
046 *     └─│─────┘ │ │ │
047 *       └───────┴─┴─┘
048 * </pre>
049 * The child nodes are always stored on the right side of the parent flattened
050 * Nodes. So you have to read the tree from left to right. All children of a
051 * parent node are stored continuously after the {@code childOffset} and are
052 * defined by the sub-array {@code [childOffset, childOffset + childCount)}.
053 *
054 * @author <a href="mailto:franz.wilhelmstoetter@gmail.com">Franz Wilhelmstötter</a>
055 * @version 3.9
056 * @since 3.9
057 */
058public interface FlatTree<V, T extends FlatTree<V, T>> extends Tree<V, T> {
059
060        /**
061         * Return the index of the first child node in the underlying node array.
062         * {@code -1} is returned if {@code this} node is a leaf.
063         *
064         * @return Return the index of the first child node in the underlying node
065         *         array, or {@code -1} if {@code this} node is a leaf
066         */
067        int childOffset();
068
069        /**
070         * Return the whole flattened tree values in breadth-first order. This is
071         * equivalent to
072         * {@snippet lang="java":
073         * final ISeq<T> seq = getRoot().breadthFirstStream()
074         *     .collect(ISeq.toISeq());
075         * }
076         *
077         * @return the flattened tree values in breadth-first order
078         */
079        default ISeq<T> flattenedNodes() {
080                return root().breadthFirstStream().collect(ISeq.toISeq());
081        }
082
083}