// Licensed to the .NET Foundation under one or more agreements.
// The .NET Foundation licenses this file to you under the MIT license.
 
using System.Runtime.CompilerServices;
 
namespace System.Windows.Forms;
 
/// <devdoc>
///  This class is used in <see cref="RefCountedCache{TObject, TCacheEntryData, TKey}"/> which is performance
///  sensitive. Do not make changes without validating performance impacts.
/// </devdoc>
internal class SinglyLinkedList<T>
{
    public SinglyLinkedList() { }
 
    public int Count { get; private set; }
    public Node? First { get; private set; }
    public Node? Last { get; private set; }
 
    public Node AddFirst(T value)
    {
        Node node = new(value);
 
        if (Count == 0)
        {
            // Nothing in the list yet
            First = Last = node;
        }
        else
        {
            // Last doesn't change, insert in the front
            node.Next = First;
            First = node;
        }
 
        Count++;
        return node;
    }
 
    public Node AddLast(T value)
    {
        Node node = new(value);
 
        if (Count == 0)
        {
            // Nothing in the list yet
            First = Last = node;
        }
        else
        {
            // Add at the end
            Debug.Assert(First is not null && Last is not null);
            Last!.Next = node;
            Last = node;
        }
 
        Count++;
        return node;
    }
 
    public Enumerator GetEnumerator() => new(this);
 
    public class Node(T value)
    {
        public Node? Next { get; set; }
        public T Value { get; set; } = value;
 
        public static implicit operator T(Node? node) => node is null ? default! : node.Value;
    }
 
    public struct Enumerator(SinglyLinkedList<T> list)
    {
        private readonly SinglyLinkedList<T> _list = list;
        private bool _removed = false;
        private bool _finished = false;
        private Node? _current = null;
        private Node? _previous = null;
 
        public readonly Node Current => _current!;
 
        /// <summary>
        ///  Resets the enumerator.
        /// </summary>
        public void Reset()
        {
            _finished = false;
            _removed = false;
            _current = null;
            _previous = null;
        }
 
        /// <summary>
        ///  Attempts to move to the next node. Sets <see cref="Current"/> when successful. If there are no more
        ///  nodes returns false and <see cref="Current"/> will be null.
        /// </summary>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public bool MoveNext()
        {
            // This code has been carefully laid out to optimize for successful MoveNext(). Do not change the
            // code without careful performance measurement.
 
            _removed = false;
            bool result = true;
            if (_finished || _list.Count == 0)
            {
                result = false;
            }
            else if (_current is null)
            {
                // At the start
                _current = _list.First;
            }
            else if (_current.Next is not null)
            {
                // Not to the end yet
                _previous = _current;
                _current = _current.Next;
            }
            else
            {
                // At the end
                _finished = true;
                _current = null;
                result = false;
            }
 
            return result;
        }
 
        /// <summary>
        ///  Removes the <see cref="Current"/> node. Note that this will make <see cref="Current"/> the prior node
        ///  so that <see cref="MoveNext"/> will place on the next node (if any).
        /// </summary>
        /// <exception cref="InvalidOperationException">
        ///  Thrown if attempting to remove without successfully calling <see cref="MoveNext"/>. Will also
        ///  throw if <see cref="RemoveCurrent"/> or <see cref="MoveCurrentToFront"/> is called more than once
        ///  without calling <see cref="MoveNext"/>.
        /// </exception>
        public void RemoveCurrent()
        {
            if (_current is null || _removed)
                throw new InvalidOperationException();
 
            // Do not change the code without careful performance measurement.
 
            // MoveNext after removing should give the next node, if any
 
            if (_current == _list.First)
            {
                // Front of the list, set next to first
                _list.First = _current.Next;
                _current = null;
            }
            else if (_current == _list.Last)
            {
                // End of list, set last to previous
                Debug.Assert(_previous is not null);
                _list.Last = _previous;
                _previous!.Next = null;
                _current = _previous;
            }
            else
            {
                // In the middle
                Debug.Assert(_previous is not null);
                Node? next = _current.Next;
                _current = _previous;
                _previous!.Next = next;
            }
 
            _removed = true;
            _list.Count--;
        }
 
        /// <summary>
        ///  Moves the <see cref="Current"/> node to the front of the list. Note that this will make
        ///  <see cref="Current"/> the prior node so that <see cref="MoveNext"/> will place on the next node
        ///  (if any).
        /// </summary>
        /// <exception cref="InvalidOperationException">
        ///  Thrown if attempting to move without successfully calling <see cref="MoveNext"/>. Will also
        ///  throw if <see cref="RemoveCurrent"/> or <see cref="MoveCurrentToFront"/> is called more than once
        ///  without calling <see cref="MoveNext"/>.
        /// </exception>
        public void MoveCurrentToFront()
        {
            if (_current is null || _removed)
                throw new InvalidOperationException();
 
            if (_current == _list.First)
            {
                // Already at the front, reposition to the start
                _current = null;
                return;
            }
 
            Debug.Assert(_previous is not null);
 
            if (_current.Next is null)
            {
                // End of the list, set last to the prior node and clear next
                Debug.Assert(_list.Last == _current);
                _list.Last = _previous;
                _previous.Next = null;
            }
            else
            {
                // In the middle, attach the prior node to the next node
                _previous.Next = _current.Next;
            }
 
            // Set the current node's next node to the current first node and set to first.
            _current.Next = _list.First;
            _list.First = _current;
 
            // Set current to the prior node so MoveNext moves to the next node
            _current = _previous;
            _removed = true;
        }
    }
}