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

namespace ConsoleApplication3
{
    internal class State
    {
        public Object Value;
    }

    internal class Idle : State {}

    internal class InProgress : State {}


    public class Ref
    {
        private static long _lastId = 0;
        private static long GetId()
        {
            var id = Interlocked.Increment(ref _lastId);
            return id;
        }

        public Ref(object value)
        {
            this.id = GetId();
            this.content = new Idle { Value = value };

        }

        public Object Value
        {
            get
            {
                return content.Value;
            }
        }

        internal long id;
        internal State content;
    }

    public class Ref<A> : Ref
    {
        public Ref(object value) : base(value)
        {

        }
        public new A Value
        {
            get
            {
                return (A)content.Value;
            }
        }
    }

    public struct CAS
    {
        public CAS(Ref refValue, object expect, object update)
        {
            this.r = refValue;
            this.expect = expect;
            this.update = update;
        }
        internal Ref r;
        internal object expect;
        internal object update;
        internal long ID { get { return r.id; } }
    }



    public static class Atomic
    {
        /// <summary>
        ///  Try to acquire a list of CASes and return, in the case of failure, the CASes that must be rolled back
        /// </summary>
        public static List<CAS> SemiCAS_loop(List<CAS> log, IEnumerable<CAS> l)
        {
            if (!l.Any())
            {
                return null;
            }

            var firstCAS = l.First();
            var state = firstCAS.r.content;
            if (state is Idle)
            {
                if (state.Value.Equals(firstCAS.expect))
                {
                    // Atomically update state to InProgress
                    var inProgress = new InProgress { Value = state.Value };
                    var swap = Interlocked.CompareExchange(ref firstCAS.r.content, inProgress, state);
                    if (swap.Equals(state))
                    {
                        // CAS succeeded, add it to the rollback log and continue
                        log.Add(firstCAS);
                        return SemiCAS_loop(log, l.Skip(1));
                    }
                    else //  CAS failed, return the rollback log.
                    {
                        return log;
                    }
                }
                else // CAS will fail, ditto.
                {
                    return log;
                }
            }
            else if (firstCAS.r.content is InProgress)
            {
                // (*This thread lost the race to acquired the CASes. *)
                return log;
            }
            else
            {
                return log;
            }
        }

        public static List<CAS> SemiCAS(IEnumerable<CAS> l)
        {
            List<CAS> log = new List<CAS>();
            return SemiCAS_loop(log, l);
        }

        // Only the thread that performed the semicas should be able to rollbwd/fwd.
        // Hence, we don't need to CAS.
        public static void Rollbwd(CAS cas)
        {
            if (cas.r.content is InProgress)
            {
                cas.r.content = new Idle { Value = cas.r.content.Value };
            }
        }

        public static void Rollfwd(CAS cas)
        {
            if (cas.r.content is Idle)
            {
                throw new InvalidOperationException("CAS.kCAS: broken invariant");
            }
            if (cas.r.content is InProgress)
            {
                // we know we have cas.r.Value == cas.expect
                cas.r.content = new Idle { Value = cas.update };
            }
        }

        public static bool KCAS(List<CAS> list)
        {
            // kCAS should sort the list of CAS to do before attempting anything to prevent deadlocks
            list.Sort((a, b) => a.ID.CompareTo(b.ID));
            var semicas = SemiCAS(list);
            if (semicas == null)
            {
                list.ForEach((cas) => Rollfwd(cas));
                return true;
            }
            else
            {
                semicas.ForEach((cas) => Rollbwd(cas));
                return false;
            }
        }
        public static void Update<A>(List<Ref> list, Func<A, A> func)
        {
            SpinWait.SpinUntil(() => {
                var casList = list.Select((r) => new CAS(r, r.Value, func((A)r.Value))).ToList();
                return KCAS(casList);
            });
        }
    }

    public class Tx
    {
        Action<Tx> txFunc;
        List<CAS> casList;

        public Tx(Action<Tx> func)
        {
            txFunc = func;
        }

        public static void Atomically(Action<Tx> func)
        {
            var tx = new Tx(func);
            tx.Commit();
        }


        public void Write<A>(Ref<A> refVar, A newValue)
        {
            var oldValue = refVar.Value;
            var cas = new CAS(refVar, oldValue, newValue);
            casList.Add(cas);
        }

        public void Update<A>(Ref<A> refVar, Func<A, A> newValueFunc)
        {
            var oldValue = refVar.Value;
            var newValue = newValueFunc((A)oldValue);
            var cas = new CAS(refVar, oldValue, newValue);
            casList.Add(cas);
        }

        private void Commit()
        {
            SpinWait.SpinUntil(() => {
                casList = new List<CAS>();
                txFunc(this);
                return Atomic.KCAS(casList);
            });
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            var a = new Ref<int>(10);
            var b = new Ref<int>(20);

            Tx.Atomically((tx) =>
            {
               tx.Write(a, a.Value + 1);
               tx.Write(b, b.Value + 1);
            });

            Console.WriteLine(a.Value);
            Console.WriteLine(b.Value);
            int c = Console.Read();
        }
    }
}