using System;
using System.Collections.Generic;
using System.Text;

namespace Endomatic
{
    // the trick is to have three classes
    //
    // ByteDna: actual store, can be used for Append(Base)
    // Concat: combines two stores used by (Pre/Ap)pend(Dna)
    // Sequence: makes a view smaller, used for Skip/Sequence
    //
    // addining Bases needs some work, but viewing large sequences is strongly optimized.
    // 
    // use Sequence(0, Length) to get a shared immutable view
    // if you do not do this the sequence might change because of optimizations
    // only do this if you really need the consistency


    public class Dna
    {
        public static Dna Epsilon = new Dna();

        protected Dna()
        {
        }

        public virtual Dna Skip(int count)
        {
            if (count > Length)
                count = Length;
            if ((Length - count) == 0)
                return Dna.Epsilon;
            if (count == 0)
                return this;
            return Sequence(count, Length, false);
        }

        public virtual Base Get(int index)
        {
            return Base.Nothing;
        }

        public Dna Append(Dna dna)
        {
            if (dna.Length == 0)
                return this;
            if (Length == 0)
                return dna;
            return new ConcatDna(this, dna);
        }

        public Dna Prepend(Dna dna)
        {
            if (dna.Length == 0)
                return this;
            if (Length == 0)
                return dna;
            return new ConcatDna(dna, this);
        }

        public virtual Dna Append(Base value)
        {
            Dna dna = new ByteDna(1);
            dna.Append(value);
            return Append(dna);
        }

        public virtual Dna Prepend(Base value)
        {
            Dna dna = new ByteDna(1);
            dna.Prepend(value);
            return Prepend(dna);
        }

        public virtual Dna Sequence(int from, int tillExclusive)
        {
            return Sequence(from, tillExclusive, true);
        }

        public virtual Dna Sequence(int from, int tillExclusive, bool locked)
        {
            Require.True(from >= 0);
            Require.True(tillExclusive <= Length);
            if (from >= tillExclusive)
                return Dna.Epsilon;
            return new SequenceDna(this, from, tillExclusive, locked);
        }

        public virtual int Length { get { return 0; } }
        public virtual int Depth { get { return 0; } }

        public static Dna FromString(string text)
        {
            return new ByteDna(text);
        }

        public override string ToString()
        {
            StringBuilder sb = new StringBuilder();
            sb.EnsureCapacity(Length);
            Dna d = Sequence(0, Length); // else the debuggers evaluation might cause us to skip to the end :)
            while (d.Length > 0)
            {
                sb.Append(BaseConverter.ToChar(d.Get(0)));
                d = d.Skip(1);
            }
            return sb.ToString();
        }

        public string ToString2()
        {
            StringBuilder sb = new StringBuilder();
            sb.EnsureCapacity(Length);
            for (int i = 0; i< Length; ++i)
            {
                sb.Append(BaseConverter.ToChar(Get(i)));
            }
            return sb.ToString();
        }

        // optimizes the tree
        public Dna Flatten()
        {
            if (Depth > 500)
            {
                flatty = new ByteDna(Length);
                Visit(AddFlatty, 0, Length);
//                Require.Equ(flatty.ToString(), ToString());
                //Require.Equ(flatty.ToString(), ToString2());
                return flatty;
            }
            return this;
        }

        public Dna Copy()
        {
            if (Length > 0)
            {
                flatty = new ByteDna(Length);
                Visit(AddFlatty, 0, Length);
                return flatty;
            }
            return this;
        }

        private ByteDna flatty;

        private void AddFlatty(byte[] data, int offset, int count, int mask)
        {
            flatty.AppendBulk(data, offset, count, mask);
        }

        public virtual void Visit(Visitor x, int from, int tillExclusive)
        {
        }
    }

    public delegate void Visitor(byte[] data, int offset, int count, int mask);

    class SequenceDna : Dna
    {
        private int from;
        private int tillExclusive;
        private Dna parent;
        private bool locked;
        private int depth;
        private int reset;

        public SequenceDna(Dna parent, int from, int tillExclusive, bool locked)
        {
            this.parent = parent;
            this.from = from;
            this.tillExclusive = tillExclusive;
            this.locked = locked;
            this.depth = parent.Depth + 1;
            reset = -1;
            if (parent is ConcatDna)
                reset = ((ConcatDna)parent).leftLength;
            if (reset < from)
                reset = int.MaxValue;
        }

        public override Dna Skip(int count)
        {
            if (count == 0)
                return this;
            if ((from + count) >= tillExclusive)
                return Dna.Epsilon;
            if (locked)
                return new SequenceDna(parent, this.from + count, this.tillExclusive, false);
            else
            {
                from += count;
                if (from == reset)
                    return parent.Sequence(from, tillExclusive, false);
                else
                    return this;
            }
        }

        public override Dna Sequence(int from, int tillExclusive, bool locked)
        {
            Require.True(from >= 0);
            Require.True(tillExclusive <= Length);
            if (from >= tillExclusive)
                return Dna.Epsilon;
            return parent.Sequence(this.from + from, this.from + tillExclusive, locked);
        }

        public override void Visit(Visitor x, int from, int tillExclusive)
        {
            if (tillExclusive > Length)
                tillExclusive = Length;
            if (from < tillExclusive)
                parent.Visit(x, from + this.from, this.from + tillExclusive);
        }

        public override int Length { get { return tillExclusive - from; } }
        public override int Depth { get { return depth; } }

        public override Base Get(int index)
        {
            if ((from + index) >= tillExclusive)
                return Base.Nothing;
            return parent.Get(from + index);
        }
    }

    public class ConcatDna : Dna
    {
        private Dna left;
        private Dna right;
        public int leftLength;
        private int length;
        private int depth;

        public ConcatDna(Dna left, Dna right)
        {
            this.left = left;
            this.right = right;
            leftLength = left.Length;
            length = right.Length + leftLength;
            depth = left.Depth;
            int rdepth = right.Depth;
            if (rdepth > depth)
                depth = rdepth;
            depth++;
//            if (depth > 100)
                //Require.Impossible();
        }

        public override int Length { get { return length; } }
        public override int Depth { get { return depth; } }

        public override Base Get(int index)
        {
            if (index < leftLength)
                return left.Get(index);
            return right.Get(index - leftLength);
        }

        public override Dna Sequence(int from, int tillExclusive, bool locked)
        {
            Require.True(from >= 0);
            Require.True(tillExclusive <= Length);
            if (tillExclusive <= leftLength)
                return left.Sequence(from, tillExclusive, locked);
            if (from >= leftLength)
                return right.Sequence(from - leftLength, tillExclusive - leftLength, locked);
            return base.Sequence(from, tillExclusive, locked);
        }

        public override void Visit(Visitor x, int from, int tillExclusive)
        {
            if (from >= tillExclusive)
                return;
            if (from < leftLength)
                if (tillExclusive < leftLength)
                    left.Visit(x, from, tillExclusive);
                else
                    left.Visit(x, from, leftLength);
            from -= leftLength;
            if (from < 0)
                from = 0;
            tillExclusive -= leftLength;
            if (tillExclusive > 0)
                right.Visit(x, from, tillExclusive);
        }
    }

    public sealed class ByteDna: Dna
    {
        private byte[] data;
        private int length;
        private int capacity;
        private int offset;
        private int mask;
        private bool lockFront = false;

        public ByteDna(int ensure)
        {
            length = 0;
            capacity = 16;
            while (capacity < ensure)
                capacity = capacity << 1;
            mask = capacity - 1;
            offset = 0;
            data = new byte[capacity];
        }

        public ByteDna(string text)
        {
            length = text.Length;
            capacity = 16;
            while (capacity < length)
                capacity = capacity << 1;
            mask = capacity - 1;
            data = new byte[capacity];
            offset = 0;
            int l = text.Length;
            for (int i = 0; i < l; ++i)
                Set(i, BaseConverter.FromChar(text[i]));
        }

        public override int Length { get { return length; } }

        public override Base Get(int index)
        {
            if (index >= length)
                return Base.Nothing;
            return (Base)data[(index + offset) & mask];
        }

        private void Grow(int ensure)
        {
            int newCapacity = capacity << 1;
            while (newCapacity < ensure)
                newCapacity = newCapacity << 1;

            if (offset != 0)
            {
                byte[] newData = new byte[newCapacity];

                CopyData(data, offset, mask, newData, 0, newCapacity - 1, length); 
                data = newData;
            }
            else
                Array.Resize(ref data, newCapacity);

            offset = 0;
            capacity = newCapacity;
            mask = newCapacity - 1;
        }

        public override Dna Skip(int count)
        {
            lockFront = true;
            return base.Skip(count);
        }

        public override Dna Sequence(int from, int tillExclusive)
        {
            lockFront = true;
            return base.Sequence(from, tillExclusive);
        }


        private void Set(int index, Base value)
        {
            data[(index + offset) & mask] = (byte)value;
        }

        public override Dna Prepend(Base value)
        {
            if (lockFront)
                return base.Prepend(value);
            else
            {
                if (length < capacity)
                {
                    offset = (offset - 1) & mask;
                    ++length;
                    data[offset] = (byte)value;
                }
                else
                {
                    Grow(0);
                    Prepend(value);
                }
                return this;
            }
        }

        public override Dna Append(Base value)
        {
            if (length < capacity)
            {
                ++length;
                data[(length - 1 + offset) & mask] = (byte)value;
            }
            else
            {
                Grow(0);
                Append(value);
            }
            return this;
        }

        public void AppendBulk(byte[] data, int offset, int count, int mask)
        {
            if ((length+count) >= capacity)
                Grow(length+count);
            CopyData(data, offset, mask, this.data, this.offset+length, this.mask, count);
            length += count;
        }

        private void CopyData(byte[] sdata, int soffset, int smask, byte[] ddata, int doffset, int dmask, int count)
        {
            //if (count > 5000000)
            //System.Console.Write(".");
            while (count > 0)
            {
                soffset = soffset & smask;
                doffset = doffset & dmask;

                int scount = smask - soffset + 1;
                int dcount = dmask - doffset + 1;

                int l = scount;
                if (l > dcount)
                    l = dcount;
                if (l > count)
                    l = count;
                Array.Copy(sdata, soffset, ddata, doffset, l);
                soffset += l;
                doffset += l;
                count -= l;
            }
        }

        public override void Visit(Visitor x, int from, int tillExclusive)
        {
            int o = (offset+from) & mask;
            int c = tillExclusive - from;
            Require.True(tillExclusive <= length);
            x(data, o, c, mask);
        }

    }

    public class DnaTest
    {
        /*
            13 ‘ICFP’[0 . . 2] returns ‘IC’
            14 ‘ICFP’[2 . . 0] returns #
            15 ‘ICFP’[2 . . 2] returns #
            16 ‘ICFP’[2 . . 3] returns ‘F’
            17 ‘ICFP’[2] returns F
            18 ‘ICFP’[2 . . 6] returns ‘FP’
            19 ‘ICFP’[2 . . ] returns ‘FP’
            20 ‘ICFP’[6] returns #
        */

        public static void RunTests()
        {
            Dna c = Dna.FromString("C");
            Dna f = Dna.FromString("F");
            Dna ic = c.Prepend(Base.I);
            Dna fp = f.Append(Base.P);
            Dna icfp = ic.Append(fp);
            runTests(icfp);
        }

        private static void runTests(Dna dna)
        {
            Dna c = Dna.FromString("ICFPPFCI");
            Dna d = Dna.FromString(c.ToString());
            Require.Equ(c.ToString(), d.ToString());
            Require.Equ(c.ToString(), "ICFPPFCI");

            c = c.Flatten();
            Require.Equ(c.ToString(), "ICFPPFCI");

            d = Dna.FromString("F");
            d.Prepend(Base.I);
            d.Prepend(Base.I);
            d.Prepend(Base.I);
            d.Prepend(Base.I);
            d.Prepend(Base.I);
            d.Prepend(Base.I);

            Require.Equ(d.ToString(), "IIIIIIF");

            d = d.Flatten();
            Require.Equ(d.ToString(), "IIIIIIF");
            
            Require.Equ(dna.Sequence(0, 2).ToString(), "IC");
            Require.Equ(dna.Sequence(2, 0).Length, 0);
            Require.Equ(dna.Sequence(2, 2).Length, 0);
            Require.Equ(dna.Sequence(2, 3).ToString(), "F");
            Require.Equ(dna.Get(2), Base.F);
            Require.Equ(dna.Sequence(1, 3).Get(1), dna.Get(2));
            Require.Equ(BaseConverter.ToChar(dna.Get(2)), 'F');
//            Require.Equ(dna.Sequence(2, 6).ToString(), "FP");
            Require.Equ(dna.Sequence(2, dna.Length).ToString(), "FP");
            Require.Equ(dna.Get(6), Base.Nothing);
        }
    }
}