// Licensed to the .NET Foundation under one or more agreements.
// The .NET Foundation licenses this file to you under the MIT license.

using System.Diagnostics;

namespace System.Linq
{
    /// <summary>
    /// An immutable node in a singly-linked list of items.
    /// </summary>
    /// <typeparam name="TSource">The type of the node's item.</typeparam>
    internal sealed class SingleLinkedNode<TSource>
    {
        /// <summary>
        /// Constructs a tail node.
        /// </summary>
        /// <param name="item">The item to place in the tail node.</param>
        public SingleLinkedNode(TSource item)
        {
            Item = item;
        }

        /// <summary>
        /// Constructs a node linked to the specified node.
        /// </summary>
        /// <param name="linked">The linked node.</param>
        /// <param name="item">The item to place in this node.</param>
        private SingleLinkedNode(SingleLinkedNode<TSource> linked, TSource item)
        {
            Debug.Assert(linked is not null);
            Linked = linked;
            Item = item;
        }

        /// <summary>
        /// The item held by this node.
        /// </summary>
        public TSource Item { get; }

        /// <summary>
        /// The next node in the singly-linked list.
        /// </summary>
        public SingleLinkedNode<TSource>? Linked { get; }

        /// <summary>
        /// Creates a new node that holds the specified item and is linked to this node.
        /// </summary>
        /// <param name="item">The item to place in the new node.</param>
        public SingleLinkedNode<TSource> Add(TSource item) => new SingleLinkedNode<TSource>(this, item);

        /// <summary>
        /// Gets the number of items in this and subsequent nodes by walking the linked list.
        /// </summary>
        public int GetCount()
        {
            int count = 0;
            for (SingleLinkedNode<TSource>? node = this; node is not null; node = node.Linked)
            {
                count++;
            }

            return count;
        }

        /// <summary>
        /// Gets the node at a logical index by walking the linked list.
        /// </summary>
        /// <param name="index">The logical index.</param>
        /// <remarks>
        /// The caller should make sure <paramref name="index"/> is less than this node's count.
        /// </remarks>
        public SingleLinkedNode<TSource> GetNode(int index)
        {
            Debug.Assert(index >= 0 && index < GetCount());

            SingleLinkedNode<TSource> node = this;
            for (; index > 0; index--)
            {
                node = node.Linked!;
                Debug.Assert(node is not null);
            }

            return node;
        }

        /// <summary>
        /// Returns an array that contains the items of this node's singly-linked list in reverse.
        /// </summary>
        /// <param name="count">The number of items in this node.</param>
        public TSource[] ToArray(int count)
        {
            Debug.Assert(count == GetCount());

            TSource[] array = new TSource[count];
            FillReversed(array);
            return array;
        }

        /// <summary>
        /// Fills a start of a span with the items of this node's singly-linked list.
        /// </summary>
        /// <param name="span">The span to fill. Must be at least the size required.</param>
        public void Fill(Span<TSource> span)
        {
            int index = 0;
            for (SingleLinkedNode<TSource>? node = this; node is not null; node = node.Linked)
            {
                span[index] = node.Item;
                index++;
            }
        }

        /// <summary>
        /// Fills the end of a span with the items of this node's singly-linked list in reverse.
        /// </summary>
        /// <param name="span">The span to fill.</param>
        public void FillReversed(Span<TSource> span)
        {
            int index = span.Length;
            for (SingleLinkedNode<TSource>? node = this; node is not null; node = node.Linked)
            {
                --index;
                span[index] = node.Item;
            }
        }
    }
}