using System;
using System.Collections;
using System.Collections.Generic;
using System.ComponentModel;
using System.Threading;

namespace NewLife.Collections
{
    /// <summary>双向链表</summary>
    /// <remarks>
    /// 原子操作线程安全说明：
    /// 1，绝大部分时候只提供正向遍历链表，所以Next方向是线程安全的，Prev则难以保证
    /// </remarks>
    /// <typeparam name="T"></typeparam>
    public class LinkList<T> : ICollection<T>
    {
        #region 属性
        private Node _Head;
        /// <summary>头部</summary>
        protected Node Head => _Head;

        private Node _Tail;
        /// <summary>尾部</summary>
        protected Node Tail => _Tail;

        private Int32 _Count;
        /// <summary>元素个数</summary>
        public Int32 Count => _Count;

        Boolean ICollection<T>.IsReadOnly => false;
        #endregion

        #region 方法
        /// <summary>添加项</summary>
        /// <param name="item"></param>
        public void Add(T item)
        {
            var node = new Node(item);

            // 首次可能为空
            while (_Head == null)
            {
                // 如果为空，就替换成功，否则重新判断
                if (Interlocked.CompareExchange(ref _Head, node, null) == null)
                {
                    // 设置Head后，需要尽快设置Tail，别的线程等着附加到尾部
                    _Tail = node;

                    Interlocked.Increment(ref _Count);

                    return;
                }
            }

            // 原子操作里面，把上一个节点的Next换成当前的下一个节点
            while (true)
            {
                // 可能别的线程已经修改
                var t = _Tail;

                // 如果节点的Next为空，则说明它就是最后一个。原子操作避免多线程同时添加出错
                if (t != null && Interlocked.CompareExchange(ref t.Next, node, null) == null)
                {
                    // 抢到末尾节点Next
                    node.Prev = t;

                    // 尽快设置尾部，别的线程才能使用
                    _Tail = node;

                    break;
                }
            }

            Interlocked.Increment(ref _Count);
        }

        /// <summary>删除项</summary>
        /// <param name="item"></param>
        /// <returns></returns>
        public Boolean Remove(T item)
        {
            for (var node = Head; node != null; node = node.Next)
            {
                if (Equals(node.Value, item))
                {
                    var p = node.Prev;
                    var n = node.Next;

                    // 原子操作里面，把上一个节点的Next换成当前的下一个节点
                    if (p != null)
                    {
                        // 如果更换失败，则可能是别的线程在处理，忽略
                        if (Interlocked.CompareExchange(ref p.Next, n, node) == node)
                        {
                            if (_Tail == node) _Tail = p;
                        }
                    }
                    // 当前节点就是头部
                    else
                    {
                        if (_Head == node) _Head = n;
                    }

                    // 原子操作里面，把下一个节点的Prev换成当前的上一个节点
                    if (n != null)
                    {
                        // 如果更换失败，则可能是别的线程在处理，忽略
                        if (Interlocked.CompareExchange(ref n.Prev, p, node) == node)
                        {
                            if (_Head == node) _Head = n;
                        }
                    }
                    // 当前节点是尾部
                    else
                    {
                        if (_Tail == node) _Tail = p;
                    }

                    Interlocked.Decrement(ref _Count);

                    return true;
                }
            }

            return false;
        }

        /// <summary>清空链表</summary>
        public void Clear()
        {
            _Head = _Tail = null;
            _Count = 0;
        }

        /// <summary>是否包含</summary>
        /// <param name="item"></param>
        /// <returns></returns>
        public Boolean Contains(T item)
        {
            for (var node = Head; node != null; node = node.Next)
            {
                if (Equals(node.Value, item)) return true;
            }

            return false;
        }

        /// <summary>拷贝到数组</summary>
        /// <param name="array"></param>
        /// <param name="arrayIndex"></param>
        public void CopyTo(T[] array, Int32 arrayIndex)
        {
            var k = 0;
            for (var node = Head; node != null; node = node.Next, k++)
            {
                array[arrayIndex + k] = node.Value;
            }
        }

        /// <summary>枚举</summary>
        /// <returns></returns>
        public IEnumerator<T> GetEnumerator()
        {
            for (var node = Head; node != null; node = node.Next)
            {
                yield return node.Value;
            }
        }

        IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
        #endregion

        #region 辅助
        /// <summary>已重载。</summary>
        /// <returns></returns>
        public override String ToString() => $"LinkList({Count:n0})";
        #endregion

        #region 节点
        /// <summary>双链表节点</summary>
        [EditorBrowsable(EditorBrowsableState.Never)]
        protected class Node
        {
            #region 属性
            /// <summary>数值</summary>
            public T Value { get; set; }

            /// <summary>前一个</summary>
            public Node Prev;

            /// <summary>下一个</summary>
            public Node Next;
            #endregion

            #region 构造
            /// <summary>实例化一个双链表节点</summary>
            public Node() { }

            /// <summary>实例化一个双链表节点</summary>
            /// <param name="value"></param>
            public Node(T value) => Value = value;
            #endregion
        }
        #endregion
    }
}