using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace DataStruct
{
    /// <summary>
    /// 循环链表
    /// </summary>
    internal class CircleLinkedList
    {
        public Node first;//头节点指针
        public Node last;//尾指针

        public CircleLinkedList()
        {
            for (int i = 0; i <= 5; i++)
            {
                InsertInHead(i);
            }
        }

        /// <summary>
        /// 前插法--插入元素
        /// </summary>
        /// <param name="data"></param>
        public void InsertInHead(int data)
        {
            Node newNode = new Node(data);
            newNode.Next = first;
            first = newNode;
            if (last == null)
            {
                last = newNode;
            }
            last.Next = first;
        }

        /// <summary>
        /// 尾插法插入元素
        /// </summary>
        /// <param name="data"></param>
        public void InsertInLast(int data)
        {
            Node newNode = new Node(data);
            if (first == null)
            {
                first = newNode;
                last = newNode;
            }
            newNode.Next = first;
            last.Next = newNode;
            last = newNode;
        }

        /// <summary>
        /// 删除元素
        /// </summary>
        /// <param name="data"></param>
        public void DeleteByValue(int data)
        {
            if (first == null)
            {
                return;
            }
            //只有一个元素
            if (first.Next == first)
            {
                if (first.Data == data)
                {
                    first = null;
                    last = null;
                }
                return;
            }

            Node currentNode = first;
            Node preNode = null;

            while (currentNode.Next != first)
            {
                if (currentNode.Data == data)
                {
                    break;
                }
                preNode = currentNode;
                currentNode = currentNode.Next;
            }

            //没有找到要删除的节点
            if (currentNode.Data != data)
            {
                return;
            }

            //删除头节点
            if (currentNode == first)
            {
                first = first.Next;
                last.Next = first;
                return;
            }
            //删除尾节点
            if (currentNode == last)
            {
                preNode.Next = first;
                last = preNode;
                return;
            }
            //删除中间节点
            preNode.Next = currentNode.Next;
        }

        /// <summary>
        /// 删除:按索引删除 删除单链表中第index个节点
        /// </summary>
        /// <param name="index"></param>
        public void DeleteByIndex(int index)
        {
            //删除第一个节点
            if (index == 1)
            {
                if (first.Next == first)//只有一个节点
                {
                    first = null;
                    last = null;
                    return;
                }
                first = first.Next;
                last.Next = first;
                return;
            }

            Node currentNode = first;
            Node preNode = null;
            int i = 1;
            //找到第i个节点
            while (i != index)
            {
                preNode = currentNode;
                currentNode = currentNode.Next;
                i++;
            }

            preNode.Next = preNode.Next.Next;
            //如果是最后一个节点
            if (currentNode.Next == first)
            {
                last = preNode;
            }
        }

        /// <summary>
        /// 查找:按索引查找 查找单链表中第index个节点
        /// </summary>
        /// <param name="index"></param>
        /// <returns></returns>
        public Node GetByIndex(int index)
        {
            Node currentNode = first;
            int i = 1;
            while (i != index)
            {
                currentNode = currentNode.Next;
                i++;
            }
            return currentNode;
        }

        /// <summary>
        /// 查找:按值查找
        /// </summary>
        /// <param name="data"></param>
        /// <returns></returns>
        public Node GetByData(int data)
        {
            Node currentNode = first;
            while (currentNode.Next != first)
            {
                if (currentNode.Data == data)
                {
                    break;
                }
                currentNode = currentNode.Next;
            }
            //如果是最后一个元素或者只有一个元素的话 需要单独比较一下
            if (currentNode.Data == data)
            {
                return currentNode;
            }
            return null;
        }

        /// <summary>
        /// 插入:在第index个位置插入数据data
        /// </summary>
        /// <param name="index"></param>
        /// <param name="data"></param>
        public void Insert(int index, int data)
        {
            if (index == 1)
            {
                InsertInHead(data);
                return;
            }
            if (index > GetLength())
            {
                InsertInLast(data);
                return;
            }
            int i = 1;
            Node currentNode = first;
            Node preNode = null;
            while (i != index)
            {
                preNode = currentNode;
                currentNode = currentNode.Next;
                i++;
            }

            Node newNode = new Node(data);
            newNode.Next = currentNode;
            preNode.Next = newNode;
        }

        ///// <summary>
        ///// 链表反转
        ///// </summary>
        //public void Reverse()
        //{
        //    var tempFirst = First;
        //    var tempLast = Last;
        //    Node current = First;
        //    Node pre = null;
        //    Node prepre = null;
        //    while (current != null)
        //    {
        //        prepre = pre;
        //        pre = current;
        //        current = current.Next;
        //        pre.Next = prepre;
        //    }

        //    First = tempLast;
        //    Last = tempFirst;
        //}

        /// <summary>
        /// 链表是否为空
        /// </summary>
        /// <returns></returns>
        public bool IsEmpty()
        {
            return first == null || last == null;
        }

        /// <summary>
        /// 清空链表
        /// </summary>
        /// <returns></returns>
        public void Clear()
        {
            first = null;
            last = null;
        }

        /// <summary>
        /// 获取链表长度
        /// </summary>
        /// <returns></returns>
        public int GetLength()
        {
            if (first == null)
            {
                return 0;
            }
            if (first.Next == first)
            {
                return 1;
            }
            int count = 1;
            Node current = first;
            while (current != null && current.Next != first)
            {
                count++;
                current = current.Next;
            }
            return count;
        }

        /// <summary>
        /// 输出环形链表
        /// </summary>
        public void Print()
        {
            if (first == null)
            {
                return;
            }
            //只有一个元素
            if (first == last)
            {
                Console.Write($"{first.Data} ");
                return;
            }
            //元素数量>1
            Node current = first;
            while (current.Next != first)
            {
                Console.Write($"{current.Data} ");
                current = current.Next;
            }
            Console.Write($"{current.Data} ");

            Console.WriteLine($"头节点:{first?.Data},尾节点:{last?.Data},链表长度:{GetLength()}");
        }
    }
}