module coneneko.container;
import std.string, std.stdio;

void remove(T, U)(ref T[] array, U index) ///
{
	for (int i = index; i < array.length - 1; i++) array[i] = array[i + 1];
	array.length = array.length - 1;
}

int indexOf(T)(T[] array, T a) /// is
{
	foreach (i, v; array) if (v is a) return i;
	return -1;
}

int indexOf2(T)(T[] array, T a) /// ==
{
	foreach (i, v; array) if (v == a) return i;
	return -1;
}

T popFront(T)(ref T[] array) ///
{
	T result = array[0];
	array.remove(0);
	return result;
}

T popBack(T)(ref T[] array) ///
{
	T result = array[$ - 1];
	array.length = array.length - 1;
	return result;
}

class Link
{
	invariant()
	{
		assert(first !is null);
		assert(second !is null);
		assert(first !is second);
	}
	
	Object first, second;
	Link clone() { return new Link(first, second); }
	bool opIn_r(Object a) { return a is first || a is second; }
	bool opEquals(Link a) { return a.first in this && a.second in this; }
	this(Object a, Object b) { first = a; second = b; }
	
	void swap()
	{
		auto tmp = first;
		first = second;
		second = tmp;
	}
	
	string toString()
	{
		return format(
			"%s(%x) - %s(%x)",
			first.toString(),
			first.toHash(),
			second.toString(),
			second.toHash()
		);
	}
}

static Link[] extract(Link[] array, Object a) // first=aの形で
{
	Link[] result;
	foreach (v; array)
	{
		if (!(a in v)) continue;
		auto b = v.clone;
		if (a is b.second) b.swap();
		result ~= b;
	}
	return result;
}

///
class Nodes
{
	unittest
	{
		auto nodes = new Nodes();
		class Test { char a; this(char a) { this.a = a; } }
		auto root = new Test('0');
		nodes.link(
			root,
			nodes.linkParallel(
				new Test('1'),
					new Test('2'),
					new Test('3')
			)
		);
		assert(nodes.isTree(root));
		string result;
		nodes.callTree(
			root,
			delegate void(Object obj, bool into)
			{
				if (auto a = cast(Test)obj) result ~= (into ? "a" : "d") ~ a.a;
			}
		);
		assert("a0a1a2d2a3d3d1d0" == result);
	}
	
	private Link[] links;
	
	Object link(Object a, Object b) ///
	{
		auto l = new Link(a, b);
		foreach (v; links)
		{
			if (v == l) return a;
		}
		links ~= l;
		return a;
	}
	
	Object linkSerial(Object a, Object b, Object c, Object[] d ...) /// a-b-c-d ...
	{
		if (d.length >= 1) link(c, d[0]);
		for (int i = 0; i + 1 < d.length; i++) link(d[i], d[i + 1]);
		return link(a, link(b, c));
	}
	
	Object linkParallel(Object a, Object b, Object c, Object[] d ...) /// a-b, a-c, a-d, ...
	{
		link(link(a, b), c);
		for (int i = 0; i < d.length; i++) link(a, d[i]);
		return a;
	}
	
	Object[] nexts(Object a) ///
	{
		Object[] result;
		foreach (v; links.extract(a)) result ~= v.second;
		return result;
	}
	
	unittest
	{
		auto nodes = new Nodes();
		auto root = new Object();
		nodes.linkParallel(
			root,
				new Object(),
				nodes.link(new Object(), new Object())
		);
		assert(nodes.isTree(root));
	}
	
	bool isTree(Object a) ///
	{
		bool[Object] check;
		check[a] = true;
		Link[] tmp;
		tmp ~= links.extract(a);
		while (tmp.length != 0)
		{
			auto i = tmp.popBack();
			if (i.second in check) return false;
			check[i.second] = true;
			auto list = links.extract(i.second);
			.remove(list, list.indexOf2(i));
			tmp ~= list;
		}
		return true;
	}
	
	void callTree(Object a, void delegate(Object obj, bool into) dg) ///
	in
	{
		assert(isTree(a));
	}
	body
	{
		dg(a, true);
		foreach (v; links.extract(a)) callTree(v, dg);
		dg(a, false);
	}
	
	private void callTree(Link a, void delegate(Object obj, bool into) dg)
	{
		dg(a.second, true);
		foreach (v; links.extract(a.second))
		{
			if (a != v) callTree(v, dg);
		}
		dg(a.second, false);
	}
	
	unittest
	{
		auto nodes = new Nodes();
		class Foo { int n() { return 1; } }
		class Hoge : Foo { override int n() { return 2; } }
		nodes.link(new Foo(), new Hoge());
		int total;
		foreach (Hoge v; nodes) total += v.n;
		assert(2 == total);
		total = 0;
		foreach (Foo v; nodes) total += v.n;
		assert(3 == total);
	}
	
	int opApply(T)(int delegate(ref T) dg) /// foreach
	{
		bool[T] map;
		foreach (v; links)
		{
			auto f = cast(T)v.first;
			auto s = cast(T)v.second;
			if (f !is null) map[f] = true;
			if (s !is null) map[s] = true;
		}
		foreach (ref T v; map.keys)
		{
			if (auto r = dg(v)) return r;
		}
		return 0;
	}
	
	unittest
	{
		auto nodes = new Nodes();
		auto a = new Object();
		auto b = new Object();
		auto c = new Object();
		nodes.linkSerial(a, b, c);
		assert(nodes.isTree(a));
		nodes.link(c, a);
		assert(!nodes.isTree(a));
		assert(2 == nodes.nexts(b).length);
		nodes.remove(b);
		assert(0 == nodes.nexts(b).length);
		assert(nodes.isTree(c));
		assert(!(b in nodes));
		nodes.linkSerial(a, b, c);
		assert(!nodes.isTree(b));
		nodes.cut(a, c);
		assert(nodes.isTree(b));
	}
	
	void remove(Object a) ///
	{
		for (int i = links.length - 1; i >= 0; i--)
		{
			if (a in links[i]) .remove(links, i);
		}
	}
	
	void cut(Object a, Object b) ///
	{
		auto l = new Link(a, b);
		for (int i = links.length - 1; i >= 0; i--)
		{
			if (l == links[i]) .remove(links, i);
		}
	}
	
	string toString()
	{
		string result;
		foreach (v; links) result ~= v.toString() ~ '\n';
		return result;
	}
	
	bool opIn_r(Object a) ///
	{
		foreach (v; links)
		{
			if (a in v) return true;
		}
		return false;
	}
	
	void swap(Object a, Object b) ///
	{
		foreach (ref v; links)
		{
			if (v.first == a) v.first = b;
			else if (v.second == a) v.second = b;
			else if (v.first == b) v.first = a;
			else if (v.second == b) v.second = a;
		}
	}
	
	unittest
	{
		auto nodes = new Nodes();
		auto a = new Object();
		auto b = new Object();
		auto c = new Object();
		auto d = new Object();
		nodes.linkSerial(a, b, c, d);
		assert(4 == nodes.enumChain(a).length);
		nodes.cut(b, c);
		assert(2 == nodes.enumChain(b).length);
		assert(2 == nodes.enumChain(c).length);
		nodes.removeChain(d);
		nodes.link(a, d);
		assert(3 == nodes.enumChain(a).length);
	}
	
	Object[] enumChain(Object a) /// 繋がっているものを
	{
		Object[] result;
		Object[] tmp; // 未処理の
		tmp ~= a;
		while (tmp.length != 0)
		{
			auto b = tmp.popBack();
			foreach (v; nexts(b))
			{
				if (result.indexOf(v) == -1) tmp ~= v;
			}
			result ~= b;
		}
		return result;
	}
	
	void removeChain(Object a) /// 繋がっているものを
	{
		foreach (v; enumChain(a)) remove(v);
	}
	
	void merge(Nodes nodes) ///
	{
		foreach (v; nodes.links) link(v.first, v.second);
	}
	
	void clear() ///
	{
		links = null;
	}
}
