// Licensed to the .NET Foundation under one or more agreements.
// The .NET Foundation licenses this file to you under the MIT license.
// See the LICENSE file in the project root for more information.

using System.Diagnostics;
using System.Diagnostics.CodeAnalysis;
using System.Runtime.CompilerServices;

namespace System.Windows.Forms
{
    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 Node(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 Node(value);

            if (Count == 0)
            {
                // Nothing in the list yet
                First = Last = node;
            }
            else
            {
                // Add at the end
                Debug.Assert(First != null && Last != null);
                Last!.Next = node;
                Last = node;
            }

            Count++;
            return node;
        }

        public Enumerator GetEnumerator() => new Enumerator(this);

        public class Node
        {
            public Node(T value) => Value = value;
            public Node? Next { get; set; }
            public T Value { get; set; }

            public static implicit operator T(Node? node) => node is null ? default! : node.Value;
        }

        public struct Enumerator
        {
            private readonly SinglyLinkedList<T> _list;
            private bool _removed;
            private bool _finished;
            private Node? _current;
            private Node? _previous;

            public Enumerator(SinglyLinkedList<T> list)
            {
                _list = list;
                _current = null;
                _previous = null;
                _removed = false;
                _finished = false;
            }

            public 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 != 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 != null);
                    _list.Last = _previous;
                    _previous!.Next = null;
                    _current = _previous;
                }
                else
                {
                    // In the middle
                    Debug.Assert(_previous != 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 != 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;
            }
        }
    }
}
