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

namespace Implab.Parallels {

    /// <summary>
    /// Very simple thred-safe FIFO queue based on the sinle linked list.
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <remarks>
    /// This queue uses interlocked operations to add and remove nodes,
    /// each node stores a single value. The queue provides mean performance,
    /// moderate overhead and situable for a small amount of elements.
    /// </remarks>
    public class SimpleAsyncQueue<T> : IEnumerable<T> {
        class Node {
            public Node(T value) {
                this.value = value;
            }
            public readonly T value;
            public volatile Node next;
        }

        // the reader and the writer are maintained completely independent,
        // the reader can read next item when m_first.next is not null
        // the writer creates a new node, moves m_last to this node and
        // only after that restores the reference from the previous node
        // making the reader able to read the new node.

        volatile Node m_first; // position on the node which is already read
        volatile Node m_last; // position on the node which is already written

        public SimpleAsyncQueue() {
            m_first = m_last = new Node(default(T));
        }

        public void Enqueue(T value) {
            var next = new Node(value);

            // Interlocked.CompareExchange implies Thread.MemoryBarrier();
            // to ensure that the next node is completely constructed
            var last = Interlocked.Exchange(ref m_last, next);

            // release-fence
            last.next = next;

        }

        public bool TryDequeue(out T value) {
            Node first = m_first;
            Node next = first.next;

            if (next == null) {
                value = default(T);
                return false;
            }

            var first2 = Interlocked.CompareExchange(ref m_first, next, first);

            if (first != first2) {
                // head is updated by someone else

                SpinWait spin = new SpinWait();
                do {
                    first = first2;
                    next = first.next;
                    if (next == null) {
                        value = default(T);
                        return false;
                    }

                    first2 = Interlocked.CompareExchange(ref m_first, next, first);
                    if (first == first2)
                        break;
                    spin.SpinOnce();
                } while (true);
            }

            value = next.value;
            return true;
        }

        /// <summary>
        /// Creates a thin copy of the current linked list.
        /// </summary>
        /// <remarks>Iterating over the snapshot is thread safe and
        /// will produce repeatble results. Each snapshot stores only
        /// two references one for the first and one for last elements
        /// from list.
        /// <returns>Enumerable collection.</returns>
        public IEnumerable<T> Snapshot() {
            var first = m_first;
            var last = m_last;

            var current = m_first;
            while(current != m_last) {
                current = current.next;
                yield return current.value;
            }
        }

        public IEnumerator<T> GetEnumerator() {
            for (var current = m_first.next; current != null; current = current.next) {
                yield return current.value;
            }
        }

        IEnumerator IEnumerable.GetEnumerator() {
            return GetEnumerator();
        }

    }
}