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);
}
}
}