using System;
using System.Threading;

namespace Implab.Parallels {
    public class MTLinkedList<TNode> where TNode : MTLinkedListNode<TNode> {
        TNode m_first;
        TNode m_last;

        public void InsertAfter( TNode pos, TNode node) {
            Safe.ArgumentNotNull(node, "node");
            if (!Attach(node))
                throw new InvalidOperationException("The specified node already attached to a list");

            TNode next;

            while (true) {
                // insert first if pos == null
                next = pos == null ? m_first : pos.next;
                node.prev = pos;
                node.next = next;
                if (next == m_first) {
                    if (next != Interlocked.CompareExchange(ref m_first, node, next))
                        continue;
                    // race
                } else {
                    if (next != Interlocked.CompareExchange(ref pos.next, node, next))
                        continue;
                    // race
                }
                break;
            }

            while (true) {
                if (next == null) {
                    if (pos != Interlocked.CompareExchange(ref m_last, node, pos))
                        continue;
                } else {
                    if (pos != Interlocked.CompareExchange(ref next.prev, node, pos))
                        continue;
                }
                break;
            }
        }

        public void InsertBefore( TNode pos, TNode node) {
            Safe.ArgumentNotNull(node, "node");

            if (!Attach(node))
                return;

            TNode prev;

            while (true) {
                // insert first if pos == null
                prev = pos == null ? m_last : pos.prev;
                node.next = pos;
                node.prev = prev;
                if (prev == m_last) {
                    if (prev != Interlocked.CompareExchange(ref m_last, node, prev))
                        continue;
                    // race
                } else {
                    if (prev != Interlocked.CompareExchange(ref pos.prev, node, prev))
                        continue;
                    // race
                }
                break;
            }

            while (true) {
                if (prev == null) {
                    if (pos != Interlocked.CompareExchange(ref m_first, node, pos))
                        continue;
                } else {
                    if (pos != Interlocked.CompareExchange(ref prev.next, node, pos))
                        continue;
                }
                break;
            }
        }

        bool Detach(TNode node) {
            MTLinkedList<TNode> parent;

            do {
                parent = node.parentList;
                if (parent == null || parent != this)
                    return false;
            } while(parent != Interlocked.CompareExchange(ref node.parentList, null, parent));
        }

        bool Attach(TNode node) {
            MTLinkedList<TNode> parent;

            do {
                parent = node.parentList;
                if (parent != null)
                    return false;
            } while(parent != Interlocked.CompareExchange(ref node.parentList, this, parent));
        }

        public void Remove(TNode node) {
            Safe.ArgumentNotNull(node, "node");

            if (!Detach(node))
                return;

            TNode prev;
            TNode next;

            while (true) {
                prev = node.prev;
                next = node.next;

                if (prev == null) {
                    if (node != Interlocked.CompareExchange(ref m_first, next, node))
                        continue;
                } else {
                    if (node != Interlocked.CompareExchange(ref prev.next, next, node))
                        continue;
                }

                break;
            }

            while (true) {
                if (next == null) {
                    if (node != Interlocked.CompareExchange(ref m_last, prev, node))
                        continue;
                } else {
                    if (node != Interlocked.CompareExchange(ref next.prev, prev, node))
                        continue;
                }
                break;
            }
        }

    }
}