using System.Collections;

namespace NewLife.Collections;

/// <summary>基于数组实现的线程安全栈。快速高效，不会形成内存碎片。</summary>
/// <remarks>
/// 链表做的原子栈<see cref="System.Collections.Concurrent.ConcurrentStack&lt;T&gt;"/>，本来是为了做对象池用的，但是链表节点自身也会形成内存碎片，给GC压力，十分纠结。
/// 一直认为用数组做存储是效率最好的，但是纠结于无法实现原子操作，而迟迟不敢动手。
/// 
/// 最好指定初始容量，因为采用数组作为存储结构最大的缺点就是容量固定，从而导致满存储时必须重新分配数组，并且复制。
/// 
/// 在 @Aimeast 的指点下，有所感悟，我们没必要严格的追求绝对安全，只要把冲突可能性降到尽可能低即可。
/// 
/// 安全栈有问题，如果在同一个位置同时压入和弹出，可能会导致这个位置为空，后面再弹出的时候，只得到空值。
/// 通过增加一个锁定数组来解决这个问题，锁定数组实现不严格的数字对比锁定，保证性能。
/// </remarks>
/// <typeparam name="T"></typeparam>
[Serializable]
public class SafeStack<T> : DisposeBase, IStack<T>, IEnumerable<T>, ICollection, IEnumerable where T : class, ISafeStackItem
{
    #region 属性
    /// <summary>数据数组。用于存放对象。</summary>
    private T[] _array;

    private Int32 _Count;
    /// <summary>元素个数，同时也是下一个空位的位置指针</summary>
    public Int32 Count { get { return _Count; } }

    /// <summary>最大容量</summary>
    public Int32 Capacity { get { return _array.Length; } }
    #endregion

    #region 构造
    /// <summary>实例化一个容纳4个元素的安全栈</summary>
    public SafeStack() : this(256) { }

    /// <summary>实例化一个指定大小的安全栈</summary>
    /// <param name="capacity"></param>
    public SafeStack(Int32 capacity) { _array = new T[capacity]; lastNotFree = new Int32[capacity]; }

    /// <summary>使用指定枚举实例化一个安全栈</summary>
    /// <param name="collection"></param>
    public SafeStack(IEnumerable collection)
    {
        var list = new List<T>();
        foreach (var item in collection)
        {
            list.Add((T)item);
        }
        _array = list.ToArray();
        _Count = _array.Length;
        lastNotFree = new Int32[_Count];
    }

    /// <summary>
    /// 销毁
    /// </summary>
    /// <param name="disposing"></param>
    protected override void Dispose(Boolean disposing)
    {
        base.Dispose(disposing);

        _array.TryDispose();
        _array = null;
    }
    #endregion

    #region 核心方法
#if DEBUG
    Int32 total = 0;
    Int32 times = 0;

    /// <summary>平均</summary>
    public Int32 Avg { get { return times == 0 ? 0 : total / times; } }
#endif

    /// <summary>向栈压入一个对象</summary>
    /// <remarks>重点解决多线程环境下资源争夺以及使用lock造成性能损失的问题</remarks>
    /// <param name="item"></param>
    public void Push(T item)
    {
        // 原有对象直接保存
        if (item.Slot >= 0)
        {
            _array[item.Slot] = item;
            LastNotFree = item.Slot;
            Interlocked.Increment(ref _Count);
            return;
        }

        var len = _array.Length;
        // 从head开始，循环遍历数组
        var head = LastFree;
        for (int i = 0; i < len; i++, len = _array.Length)
        {
            if (_Count >= len) CheckSize();

            var k = i + head;
            if (k >= len) k -= len;

            // 尝试交换，成功后返回
            if (_array[k] == null && Interlocked.CompareExchange<T>(ref _array[k], item, null) == null)
            {
                item.Slot = k;
                // 记录位置，下一次从这里开始找
                LastNotFree = k;
                Interlocked.Increment(ref _Count);
                LastFree = k + 1;
#if DEBUG
                total += i + 1;
                times++;
#endif
                return;
            }
        }
#if DEBUG
        total += len;
        times++;
#endif
        throw new Exception("Error On Push");
    }

    Object _lock_CheckSize = new Object();
    void CheckSize()
    {
        // 如果当前已经用完，那么马上扩容。当然，有可能扩容前就被别人抢到后面的位置，所以，这里要尽快加锁
        if (_Count < _array.Length) return;
        lock (_lock_CheckSize)
        {
            if (_Count < _array.Length) return;

            // 稍等一会，可能某些读取尚未完成
            Thread.SpinWait(100);

            // 以4为最小值，成倍扩容
            Int32 size = _array.Length < 4 ? 4 : _array.Length * 2;
            var _arr = new T[size];
            _array.CopyTo(_arr, 0);
            _array = _arr;

            var _arr2 = new Int32[size];
            lastNotFree.CopyTo(_arr2, 0);
            lastNotFree = _arr2;
        }
    }

    /// <summary>从栈中弹出一个对象</summary>
    /// <returns></returns>
    public T Pop()
    {
        T item;
        if (!TryPop(out item)) throw new InvalidOperationException("栈为空！");

        return item;
    }

    /// <summary>尝试从栈中弹出一个对象</summary>
    /// <param name="item"></param>
    /// <returns></returns>
    public Boolean TryPop(out T item)
    {
        var len = _array.Length;
        if (_Count >= len) CheckSize();

        // 从tails开始，反向循环遍历数组
        var tails = LastNotFree;
        for (int i = len - 1; i >= 0; i--)
        {
            var k = i + tails + 1;
            if (k >= len) k -= len;

            // 先判断一次再交换，掠夺式获取数组元素，Exchange比CompareExchange更轻量级
            if (_array[k] != null && (item = Interlocked.Exchange<T>(ref _array[k], null)) != null)
            {
                // 记录位置，下一次从这里开始找
                LastFree = k;
                Interlocked.Decrement(ref _Count);
#if DEBUG
                total += len - i;
                times++;
#endif
                return true;
            }
        }

        item = null;
        return false;
    }

    //volatile Int32 LastFree = 0;
    //volatile Int32 LastNotFree = 0;

    // 记录最后的空闲位置和非空闲位置，一级缓存
    //const Int32 SIZE_OF_CACHE = 100000;
    // 指向下一个空位置
    //volatile Int32 lastFreeIndex = 0;
    volatile Int32 lastNotFreeIndex = 0;
    //Int32[] lastFree = new Int32[SIZE_OF_CACHE];
    Int32[] lastNotFree;// = new Int32[SIZE_OF_CACHE];

    volatile Int32 LastFree = 0;
    //Int32 LastFree
    //{
    //    get
    //    {
    //        var k = lastFreeIndex;
    //        if (k <= 0) return 0;
    //        lastFreeIndex--;
    //        return lastFree[k - 1];
    //    }
    //    set
    //    {
    //        var k = lastFreeIndex;
    //        if (k >= SIZE_OF_CACHE) return;
    //        lastFreeIndex++;
    //        lastFree[k] = value;
    //    }
    //}

    Int32 LastNotFree
    {
        get
        {
            var k = lastNotFreeIndex;
            if (k <= 0) return 0;
            lastNotFreeIndex--;
            return lastNotFree[k - 1];
        }
        set
        {
            var k = lastNotFreeIndex;
            if (k >= lastNotFree.Length) return;
            lastNotFreeIndex++;
            lastNotFree[k] = value;
        }
    }
    #endregion

    #region 集合方法
    /// <summary>清空</summary>
    public void Clear()
    {
        // 先把指针移到开头，再执行清空操作，减少冲突可能性
        var len = Count;
        _Count = 0;
        for (int i = 0; i < _array.Length && i < len; i++) _array[i] = default(T);
    }

    /// <summary>转为数组</summary>
    /// <returns></returns>
    public T[] ToArray()
    {
        var len = Count;
        if (len < 1) return null;

        T[] arr = new T[len];
        Array.Copy(_array, 0, arr, 0, len);
        return arr;
    }
    #endregion

    #region ICollection 成员
    void ICollection.CopyTo(Array array, int index)
    {
        if (Count < 1 || array == null || index >= array.Length) return;

        //_array.CopyTo(array, index);
        Array.Copy(_array, 0, array, index, Count);
    }

    bool ICollection.IsSynchronized { get { return true; } }

    private Object _syncRoot;
    object ICollection.SyncRoot
    {
        get
        {
            if (_syncRoot == null)
            {
                Interlocked.CompareExchange(ref _syncRoot, new object(), null);
            }
            return _syncRoot;
        }
    }
    #endregion

    #region IEnumerable 成员
    /// <summary>获取枚举器</summary>
    /// <returns></returns>
    public IEnumerator<T> GetEnumerator()
    {
        for (int i = 0; i < _array.Length && i < Count; i++) yield return _array[i];
    }

    IEnumerator IEnumerable.GetEnumerator() { return _array.GetEnumerator(); }
    #endregion
}

/// <summary>安全栈项接口。采用安全栈存储的数据必须实现该接口</summary>
public interface ISafeStackItem
{
    /// <summary>存储位置</summary>
    Int32 Slot { get; set; }
}