/*
 * Java Genetic Algorithm Library (@__identifier__@).
 * Copyright (c) @__year__@ Franz Wilhelmstötter
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 *
 * Author:
 *    Franz Wilhelmstötter (franz.wilhelmstoetter@gmail.com)
 */
package io.jenetics.ext.util;

import static java.util.Objects.requireNonNull;
import static io.jenetics.internal.util.SerialIO.readIntArray;
import static io.jenetics.internal.util.SerialIO.readObjectArray;
import static io.jenetics.internal.util.SerialIO.writeIntArray;
import static io.jenetics.internal.util.SerialIO.writeObjectArray;

import java.io.IOException;
import java.io.InvalidObjectException;
import java.io.ObjectInput;
import java.io.ObjectInputStream;
import java.io.ObjectOutput;
import java.io.Serial;
import java.io.Serializable;
import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Iterator;
import java.util.Optional;
import java.util.function.BiFunction;
import java.util.function.Function;
import java.util.stream.IntStream;
import java.util.stream.Stream;

import io.jenetics.util.ISeq;

/**
 * Default implementation of the {@link FlatTree} interface. Beside the
 * flattened and dense layout it is also an <em>immutable</em> implementation of
 * the {@link Tree} interface. It can only be created from an existing tree.
 *
 * <pre>{@code
 * final Tree<String, ?> immutable = FlatTreeNode.ofTree(TreeNode.parse(...));
 * }</pre>
 *
 * @implNote
 * This class is immutable and thread-safe.
 *
 * @author <a href="mailto:franz.wilhelmstoetter@gmail.com">Franz Wilhelmstötter</a>
 * @version 7.1
 * @since 3.9
 */
public final class FlatTreeNode<V>
	implements
		FlatTree<V, FlatTreeNode<V>>,
		Serializable
{

	/**
	 * The flattened tree nodes.
	 */
	private record Nodes(Object[] values, int[] childOffsets, int[] childCounts) {
		Nodes(final int size) {
			this(new Object[size], new int[size], new int[size]);
		}
	}

	@Serial
	private static final long serialVersionUID = 3L;

	private static final int NULL_INDEX = -1;

	private final Nodes _nodes;
	private final int _index;

	private FlatTreeNode(final Nodes nodes, final int index) {
		_nodes = requireNonNull(nodes);
		_index = index;
	}

	private FlatTreeNode(final Nodes nodes) {
		this(nodes, 0);
	}

	/**
	 * Returns the root of the tree that contains this node. The root is the
	 * ancestor with no parent. This implementation has a runtime complexity
	 * of O(1).
	 *
	 * @return the root of the tree that contains this node
	 */
	@Override
	public FlatTreeNode<V> root() {
		return nodeAt(0);
	}

	@Override
	public boolean isRoot() {
		return _index == 0;
	}

	private FlatTreeNode<V> nodeAt(final int index) {
		return new FlatTreeNode<>(_nodes, index);
	}

	@SuppressWarnings("unchecked")
	@Override
	public V value() {
		return (V)_nodes.values[_index];
	}

	@Override
	public Optional<FlatTreeNode<V>> parent() {
		int index = NULL_INDEX;
		for (int i = _index; --i >= 0 && index == NULL_INDEX;) {
			if (isParent(i)) {
				index = i;
			}
		}

		return index != NULL_INDEX
			? Optional.of(nodeAt(index))
			: Optional.empty();
	}

	private boolean isParent(final int index) {
		return _nodes.childCounts[index] > 0 &&
			_nodes.childOffsets[index] <= _index &&
			_nodes.childOffsets[index] + _nodes.childCounts[index] > _index;
	}

	@Override
	public FlatTreeNode<V> childAt(final int index) {
		if (index < 0 || index >= childCount()) {
			throw new IndexOutOfBoundsException(Integer.toString(index));
		}

		return nodeAt(childOffset() + index);
	}

	@Override
	public int childCount() {
		return _nodes.childCounts[_index];
	}

	/**
	 * Return the index of the first child node in the underlying node array.
	 * {@code -1} is returned if {@code this} node is a leaf.
	 *
	 * @return Return the index of the first child node in the underlying node
	 *         array, or {@code -1} if {@code this} node is a leaf
	 */
	@Override
	public int childOffset() {
		return _nodes.childOffsets[_index];
	}

	@Override
	public ISeq<FlatTreeNode<V>> flattenedNodes() {
		return stream().collect(ISeq.toISeq());
	}

	@Override
	public Iterator<FlatTreeNode<V>> breadthFirstIterator() {
		return isRoot()
			? new IntFunctionIterator<>(this::nodeAt, _nodes.values.length)
			: FlatTree.super.breadthFirstIterator();
	}

	@Override
	public Stream<FlatTreeNode<V>> breadthFirstStream() {
		return isRoot()
			? IntStream.range(0, _nodes.values.length).mapToObj(this::nodeAt)
			: FlatTree.super.breadthFirstStream();
	}

	/**
	 * Return a sequence of all <em>mapped</em> nodes of the whole underlying
	 * tree. This is a convenient method for
	 * <pre>{@code
	 * final ISeq<B> seq = stream()
	 *     .map(mapper)
	 *     .collect(ISeq.toISeq())
	 * }</pre>
	 *
	 * @param mapper the mapper function
	 * @param <B> the mapped type
	 * @return a sequence of all <em>mapped</em> nodes
	 */
	public <B> ISeq<B>
	map(final Function<? super FlatTreeNode<V>, ? extends B> mapper) {
		return stream()
			.map(mapper)
			.collect(ISeq.toISeq());
	}

	@Override
	public boolean identical(final Tree<?, ?> other) {
		return other == this ||
			other instanceof FlatTreeNode<?> node &&
			node._index == _index &&
			node._nodes == _nodes;
	}

	@Override
	public <U> U reduce(
		final U[] neutral,
		final BiFunction<? super V, ? super U[], ? extends U> reducer
	) {
		requireNonNull(neutral);
		requireNonNull(reducer);

		@SuppressWarnings("unchecked")
		final class Reducing {
			private U reduce(final int index) {
				return _nodes.childCounts[index] == 0
					? reducer.apply((V)_nodes.values[index], neutral)
					: reducer.apply((V)_nodes.values[index], children(index));
			}
			private U[] children(final int index) {
				final U[] values = (U[])Array.newInstance(
					neutral.getClass().getComponentType(),
					_nodes.childCounts[index]
				);
				for (int i = 0; i < _nodes.childCounts[index]; ++i) {
					values[i] = reduce(_nodes.childOffsets[index] + i);
				}
				return values;
			}
		}

		return isEmpty() ? null : new Reducing().reduce(_index);
	}

	@Override
	public int hashCode() {
		return Tree.hashCode(this);
	}

	@Override
	public boolean equals(final Object obj) {
		return obj == this ||
			(obj instanceof FlatTreeNode<?> ftn && equals(ftn)) ||
			(obj instanceof Tree<?, ?> tree && Tree.equals(tree, this));
	}

	private boolean equals(final FlatTreeNode<?> tree) {
		return tree._index == _index &&
			Arrays.equals(tree._nodes.values, _nodes.values) &&
			Arrays.equals(tree._nodes.childCounts, _nodes.childCounts) &&
			Arrays.equals(tree._nodes.childOffsets, _nodes.childOffsets);
	}

	@Override
	public String toString() {
		return toParenthesesString();
	}

	@Override
	public int size() {
		return isRoot()
			? _nodes.values.length
			: countChildren(_index) + 1;
	}

	private int countChildren(final int index) {
		int count = _nodes.childCounts[index];
		for (int i = 0; i < _nodes.childCounts[index]; ++i) {
			count += countChildren(_nodes.childOffsets[index] + i);
		}
		return count;
	}

	/* *************************************************************************
	 *  Static factories
	 * ************************************************************************/

	/**
	 * Create a new, immutable {@code FlatTreeNode} from the given {@code tree}.
	 *
	 * @param tree the source tree
	 * @param <V> the tree value types
	 * @return a {@code FlatTreeNode} from the given {@code tree}
	 * @throws NullPointerException if the given {@code tree} is {@code null}
	 */
	public static <V> FlatTreeNode<V> ofTree(final Tree<? extends V, ?> tree) {
		requireNonNull(tree);

		if (tree instanceof FlatTreeNode<?> ft && ft.isRoot()) {
			@SuppressWarnings("unchecked")
			final var result = (FlatTreeNode<V>)ft;
			return result;
		}

		final int size = tree.size();
		assert size >= 1;

		final var nodes = new Nodes(size);

		int childOffset = 1;
		int index = 0;

		for (var node : tree) {
			nodes.values[index] = node.value();
			nodes.childCounts[index] = node.childCount();
			nodes.childOffsets[index] = node.isLeaf() ? NULL_INDEX : childOffset;

			childOffset += node.childCount();
			++index;
		}
		assert index == size;

		return new FlatTreeNode<>(nodes);
	}

	/**
	 * Parses a (parentheses) tree string, created with
	 * {@link Tree#toParenthesesString()}. The tree string might look like this:
	 * <pre>
	 *  mul(div(cos(1.0),cos(π)),sin(mul(1.0,z)))
	 * </pre>
	 *
	 * @see Tree#toParenthesesString(Function)
	 * @see Tree#toParenthesesString()
	 * @see TreeNode#parse(String)
	 *
	 * @since 5.0
	 *
	 * @param tree the parentheses tree string
	 * @return the parsed tree
	 * @throws NullPointerException if the given {@code tree} string is
	 *         {@code null}
	 * @throws IllegalArgumentException if the given tree string could not be
	 *         parsed
	 */
	public static FlatTreeNode<String> parse(final String tree) {
		return ofTree(ParenthesesTreeParser.parse(tree, Function.identity()));
	}

	/**
	 * Parses a (parentheses) tree string, created with
	 * {@link Tree#toParenthesesString()}. The tree string might look like this
	 * <pre>
	 *  0(1(4,5),2(6),3(7(10,11),8,9))
	 * </pre>
	 * and can be parsed to an integer tree with the following code:
	 * <pre>{@code
	 * final Tree<Integer, ?> tree = FlatTreeNode.parse(
	 *     "0(1(4,5),2(6),3(7(10,11),8,9))",
	 *     Integer::parseInt
	 * );
	 * }</pre>
	 *
	 * @see Tree#toParenthesesString(Function)
	 * @see Tree#toParenthesesString()
	 * @see TreeNode#parse(String, Function)
	 *
	 * @since 5.0
	 *
	 * @param <B> the tree node value type
	 * @param tree the parentheses tree string
	 * @param mapper the mapper which converts the serialized string value to
	 *        the desired type
	 * @return the parsed tree object
	 * @throws NullPointerException if one of the arguments is {@code null}
	 * @throws IllegalArgumentException if the given parentheses tree string
	 *         doesn't represent a valid tree
	 */
	public static <B> FlatTreeNode<B> parse(
		final String tree,
		final Function<? super String, ? extends B> mapper
	) {
		return ofTree(ParenthesesTreeParser.parse(tree, mapper));
	}


	/* *************************************************************************
	 *  Java object serialization
	 * ************************************************************************/

	@Serial
	private Object writeReplace() {
		return new SerialProxy(SerialProxy.FLAT_TREE_NODE, this);
	}

	@Serial
	private void readObject(final ObjectInputStream stream)
		throws InvalidObjectException
	{
		throw new InvalidObjectException("Serialization proxy required.");
	}


	void write(final ObjectOutput out) throws IOException {
		final FlatTreeNode<V> node = isRoot()
			? this
			: FlatTreeNode.ofTree(this);

		writeObjectArray(node._nodes.values, out);
		writeIntArray(node._nodes.childOffsets, out);
		writeIntArray(node._nodes.childCounts, out);
	}

	@SuppressWarnings("rawtypes")
	static FlatTreeNode read(final ObjectInput in)
		throws IOException, ClassNotFoundException
	{
		return new FlatTreeNode(new Nodes(
			readObjectArray(in),
			readIntArray(in),
			readIntArray(in)
		));
	}

}
