template FingerTreeImpl(E)
{
static private:

	//-----------------------------------------------------
	// 2-3木
	//-----------------------------------------------------

	abstract class Tree
	{
		E[] toList();
	}

	class Leaf : Tree
	{
		E elem;
		this( E e ) { elem = e; }

		E[] toList() { return [elem] ;}
	}

	class Node(int N) : Tree
	{
		Tree[N] child;
		this( Tree[] c... ) { child[] = c; }

		E[] toList() { E[] a; foreach(c;child) a~=c.toList; return a; }
	}

	//-----------------------------------------------------
	// FingerTreeのようなもの本体
	//-----------------------------------------------------

	class Block
	{
		Tree[] l; // 左端何個か
		Block  c; // まんなからへん（ほんとはここLazyにしないとダメ）
		Tree[] r; // 右端何個か

		//※ cを1個たどるごとに1段深いTreeでlとrを保持するようにする
		//※ 1個しかTreeがないときは、とりあえずlに入れてrは空に

		this(Tree s_) { l=[s_]; }
		this(Tree[] l_, Block c_, Tree[] r_) {l=l_; c=c_; r=r_;}

		E[] toList() {
			E[] a;
			foreach(ll;l) a~=ll.toList;
			if(c) a~=c.toList;
			foreach(rr;r) a~=rr.toList;
			return a;
		}
	}

	//-----------------------------------------------------
	// 結合演算
	//-----------------------------------------------------

	Block catl( Tree x, Block b )
	{
		     if( !b )           return new Block(x);
		else if( !b.r )         return new Block(   [x], null, b.l );
		else if( b.l.length<4 ) return new Block( x~b.l,  b.c, b.r );
		else return new Block( x~b.l[0..1], catl(new Node!(3)(b.l[1..4]),b.c), b.r );
	}

	Block catr( Block b, Tree x )
	{
			 if( !b )           return new Block(x);
		else if( !b.r )         return new Block( b.l, null,   [x] );
		else if( b.r.length<4 ) return new Block( b.l,  b.c, b.r~x );
		else return new Block( b.l, catr(b.c,new Node!(3)(b.r[0..3])), b.r[3..4]~x );
	}

	Block cat( Block lhs, Tree[] cc, Block rhs )
	{
		if( !lhs || !lhs.r ) {
			if(lhs)               rhs = catl(lhs.l[0], rhs);
			foreach_reverse(c;cc) rhs = catl(       c, rhs);
			return rhs;
		} else if( !rhs || !rhs.r ) {
			foreach(c;cc) lhs = catr(lhs,        c);
			if(rhs)       lhs = catr(lhs, rhs.l[0]);
			return lhs;
		} else {
			Tree[] nodes;
			for(cc=lhs.r~cc~rhs.l; cc.length; )
				if( cc.length==2 || cc.length==4 ) {
					nodes ~= new Node!(2)(cc[0..2]);
					cc = cc[2..$];
				} else {
					nodes ~= new Node!(3)(cc[0..3]);
					cc = cc[3..$];
				}
			return new Block(lhs.l, cat(lhs.c, nodes, rhs.c), rhs.r);
		}
	}
}

struct Seq(E)
{
	mixin FingerTreeImpl!(E);
	private Block b;

	Seq opCat_r(E e) { return Seq( catl(new Leaf(e),b) );  }
	Seq opCat  (E e) { return Seq( catr(b, new Leaf(e)) ); }
	Seq opCat(Seq r) { return Seq( cat(b,[],r.b) ); }
	void opCatAssign(E e)   { b=catr(b, new Leaf(e)); }
	void opCatAssign(Seq r) { b=cat(b, [], r.b); }

	E[] toList() { return b.toList; }
}

import std.stdio;
void main()
{
	Seq!(int) x;
	x ~= 7;
	x ~= 8;
	x ~= 9;
	x = 6~x;
	x = 5~x;
	x = 4~x;
	x = 3~x;
	x = 2~x;
	x = 1~x;
	x = 0~x;
	x ~= x;
	x ~= 10;
	x ~= 11;
	x ~= 12;
	x ~= 13;
	writefln( x.toList );
}