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

namespace GZip
{
    /// <summary>
    /// Вспомогательный класс для методов синхронизации потоков
    /// </summary>
    internal static class SyncHelper
    {
        /// <summary>
        /// Атомарная операция сравнения-присваивания
        /// </summary>
        /// <param name="location">Целевой объект</param>
        /// <param name="comparand">Значение, с которым сравниваем <see cref="location"/></param>
        /// <param name="newValue">Новое значение для целевого объекта, если результат сравнения это равенство</param>
        /// <returns>true, если произошла замена целевого объекта</returns>
        public static bool CAS<T>( ref T location, T comparand, T newValue ) where T : class
        {
            return comparand == Interlocked.CompareExchange( ref location, newValue, comparand );
        }
    }

    /// <summary>
    /// Потокобезопасная очередь
    /// </summary>
    public class ConcurrentQueue<T> where T : class
    {
        /// <summary>
        /// Узел односвязного списка
        /// </summary>
        private class Node<TItem> where TItem : class
        {
            /// <summary>
            /// Ссылка на следующий элемент в очереди.
            /// </summary>
            /// <remarks>Next должен быть именно полем класса - его нельзя сделать полем класса, т.к. он используется в CAS операции</remarks>
            public Node<TItem> Next;

            /// <summary>
            /// Элемент в коллекции
            /// </summary>
            public TItem Item;
        }

        private Node<T> head;
        private Node<T> tail;

        private int _count;

        /// <summary>
        /// Возвращает true если очередь пуста
        /// </summary>
        public bool IsEmpty
        {
            get
            {
                return head == tail;
            }
        }

        /// <summary>
        /// Число объектов в очереди
        /// </summary>
        public int Count
        {
            get
            {
                return _count;
            }
        }

        /// <summary>
        /// Конструктор
        /// </summary>
        public ConcurrentQueue()
        {
            head = new Node<T>();
            tail = head;
        }

        /// <summary>
        /// Добавляет элемент в очередь
        /// </summary>
        /// <param name="item">Элемент</param>
        public void Enqueue( T item )
        {
            Node<T> oldTail = null;

            var newNode = new Node<T>();
            newNode.Item = item;

            var newNodeAdded = false;
            while( !newNodeAdded )
            {
                oldTail = tail;
                var oldTailNext = oldTail.Next;
                if( tail != oldTail )
                    continue;

                if( oldTailNext == null )
                    newNodeAdded = SyncHelper.CAS( ref tail.Next, null, newNode );
                else
                    SyncHelper.CAS( ref tail, oldTail, oldTailNext );
            }

            SyncHelper.CAS( ref tail, oldTail, newNode );
            Interlocked.Increment( ref _count );
        }

        /// <summary>
        /// Удаляет элемент из очереди
        /// </summary>
        /// <returns>Удаленный элемент</returns>
        public T Dequeue()
        {
            T item = null;
            var hasAdvancedHead = false;
            while( !hasAdvancedHead )
            {
                var oldHead = head;
                var oldTail = tail;
                var oldHeadNext = oldHead.Next;
                if( oldHead != head )
                    continue;

                if( oldHead == oldTail )
                {
                    if( oldHeadNext == null )
                        oldTail.Item = null;

                    SyncHelper.CAS( ref tail, oldTail, oldHeadNext );
                }
                else
                {
                    item = oldHeadNext.Item;
                    hasAdvancedHead = SyncHelper.CAS( ref head, oldHead, oldHeadNext );

                    if( hasAdvancedHead )
                        oldHead.Item = null;
                }
            }

            Interlocked.Decrement( ref _count );

            return item;
        }
    }
}