//---------------------------------------------------------------------------
// Learning Regular Expression from postiive/negative training sets.
//
// author:  k.inaba     (http://www.kmonos.net/)
// license: NYSL 0.9982 (http://www.kmonos.net/nysl/)
//
// Outcome from PRML Hackathon #1
//   http://atnd.org/events/1422
// Thank you for organizing such a great event! > naoya_t
//---------------------------------------------------------------------------

import std.stdio;
import std.conv;
import std.numeric;
import std.algorithm;
import std.array;
import std.random;
import std.range;

version = ZLearn;

//---------------------------------------------------------------------------
// ユーティリティ
//---------------------------------------------------------------------------

auto array(Range)(Range r) // なぜ標準ライブラリにないのか...
{
	ElementType!(Range)[] arr;
	foreach(e; r)
		arr ~= e;
	return arr;
}

template Set(T) // すごい適当極まりないひどさの固まりのSetのような何か
{
	alias T[] Set;
}

T[] set_add(T)( T[] set, T[] t... )
{
	set = set ~ t;
	set.sort;
	return array(uniq(set));
}

void destructive_add(T)( ref T[] set, T t )
{
	set = set ~ t;
	set.sort;
	set = array(uniq(set));
}

bool set_has(T)( T[] set, T[] t... )
{
	return !empty( findAmongSorted(set, t) );
}


//---------------------------------------------------------------------------
// 非決定性オートマトン
//---------------------------------------------------------------------------

class NFA
{
	unittest
	{
		auto A = NFA.from_string("Hello");
		assert(  A.accept("Hello") );
		assert( !A.accept("Hell") );
		assert( !A.accept("Helloo") );

		auto B = NFA.from_string("World");
		assert(  B.accept("World") );
		assert( !B.accept("Worl") );
		assert( !B.accept("WorldW") );

		auto C = NFA.merge(A,B);
		assert(  C.accept("Hello") );
		assert( !C.accept("Hell") );
		assert( !C.accept("Helloo") );
		assert(  C.accept("World") );
		assert( !C.accept("Worl") );
		assert( !C.accept("WorldW") );

		C = NFA.randomize(C);
		assert(  C.accept("Hello") );
		assert( !C.accept("Hell") );
		assert( !C.accept("Helloo") );
		assert(  C.accept("World") );
		assert( !C.accept("Worl") );
		assert( !C.accept("WorldW") );

		auto D = NFA.mergeState(B, 0, 5);
		assert(  D.accept("World") );
		assert( !D.accept("Worl") );
		assert( !B.accept("WorldWorld") );
		assert(  D.accept("WorldWorld") );
		assert(  D.accept("WorldWorldWorld") );

		auto E = NFA.mergeState(A, 1, 3);
		assert(  E.accept("Hello") );
		assert( !E.accept("Hell") );
		assert( !E.accept("Helloo") );
		assert(  E.accept("Hlo") );
		assert( !A.accept("Hlo") );

		version(ZLearn) {
			auto F = NFA.from_string("xzz");
			assert( F.accept("xzz") );
			assert( F.accept("xab") );
			assert( !F.accept("xzzz") );
		}
	}

	alias int State;
	int stateNum;                   // 状態の総数
	Set!(State)              ini;   // 開始状態
	Set!(State)[char][State] delta; // 遷移関数
	Set!(State)              fin;   // 受理状態

	string toString()
	{
		return
			"<< #st: " ~ to!(string)(stateNum) ~ "\n"
			"   ini: " ~ to!(string)(ini) ~ "\n"
			"   fin: " ~ to!(string)(fin) ~ "\n"
			"   dlt: " ~ to!(string)(delta) ~ " >>";
	}

	bool accept_none( string[] ss )
	{
		foreach(s; ss)
			if( accept(s) )
				return false;
		return true;
	}

	bool accept( string s )
	{
		Set!(State) qs = ini; // 初期状態
		foreach(c; s) // 一文字読んで
		{
			Set!(State) ps;
			foreach(q; qs)
				if( q in delta && c in delta[q] )
					ps = ps.set_add( delta[q][c] );
			qs = ps; // 次の状態に遷移
		}
		foreach(q; qs)
			if( fin.set_has(q) )
				return true; // 受理状態にあればaccept
		return false;
	}

	// 空のオートマトンを作る

	static NFA empty() { return new NFA; }
	private this() {}

	// 文字列からそれだけacceptするオートマトンを作る

	static NFA from_string( string s )
	{
		NFA C = NFA.empty;
		
		C.stateNum = s.length+1;
		for(int q=0; q<s.length; ++q)
		{
			version(ZLearn) {
				if( s[q]=='z' ) // z は [a-z] 扱いという私はウルトラアドホック
					foreach(c; 'a'..'z'+1)
						C.delta[q][c] = [q+1];
				else
					C.delta[q] = [s[q]: [q+1]];
			} else {
				C.delta[q] = [s[q]: [q+1]];
			}
		}
		C.ini = [0];
		C.fin = [s.length];

		return C;
	}

	// 別のオートマトンの状態番号をランダマイズして作る

	static NFA randomize( NFA A )
	{
		int[] ix;
		foreach(i; 0..A.stateNum)
			ix ~= i;
		ix = array(randomCover(ix, rndGen));

		NFA C = NFA.empty;
		C.stateNum = A.stateNum;
		foreach(q; A.ini) C.ini = C.ini.set_add(ix[q]);
		foreach(q; A.fin) C.fin = C.fin.set_add(ix[q]);
		foreach(q; A.delta.keys)
			foreach(c; A.delta[q].keys)
				foreach(p; A.delta[q][c])
					C.delta[ix[q]][c] = C.delta[ix[q]][c].set_add(ix[p]);
		return C;
	}

	// 二つのオートマトンを合併

	static NFA merge( NFA A, NFA B )
	{
		NFA C = NFA.empty;
		addToFrom(C, A);
		addToFrom(C, B);
		assert(C.stateNum == A.stateNum + B.stateNum);
		return C;
	}

	private static void addToFrom( NFA C, NFA A )
	{
		int offset = C.stateNum;

		C.stateNum += A.stateNum;
		foreach(q; A.ini) C.ini = C.ini.set_add(q+offset);
		foreach(q; A.fin) C.fin = C.fin.set_add(q+offset);
		foreach(q; A.delta.keys)
			foreach(c; A.delta[q].keys)
				foreach(p; A.delta[q][c])
					C.delta[q+offset][c] = C.delta[q+offset][c].set_add(p+offset);
	}

	// オートマトンA の状態 Q と P をマージしたオートマトンを作る

	static NFA mergeState(NFA A, State Q, State P)
	in
	{
		assert( 0 <= Q );
		assert( Q < P );
		assert( P < A.stateNum );
	}
	out(r)
	{
		assert( r.stateNum == A.stateNum-1 );
	}
	body
	{
		NFA C = NFA.empty;

		C.stateNum = A.stateNum - 1;
		foreach(q; A.ini)
			if( q!=Q && q<P ) C.ini = C.ini.set_add(q);
			else if( P<q )    C.ini = C.ini.set_add(q-1);
		if( A.ini.set_has(Q, P) ) C.ini = C.ini.set_add(Q);

		foreach(q; A.fin)
			if( q!=Q && q<P ) C.fin = C.fin.set_add(q);
			else if( P<q )    C.fin = C.fin.set_add(q-1);
		if( A.fin.set_has(Q, P) ) C.fin = C.fin.set_add(Q);

		foreach(q; A.delta.keys)
			foreach(c; A.delta[q].keys)
				foreach(p; A.delta[q][c]) {
					auto q2 = (q<P ? q : q==P ? Q : q-1);
					auto p2 = (p<P ? p : p==P ? Q : p-1);
					C.delta[q2][c] = C.delta[q2][c].set_add(p2);
				}
		return C;
	}
}

//---------------------------------------------------------------------------
// MOIL アルゴリズムによる学習
//    Pedro García; Manuel Vázquez de Parga; Gloria I. Álvarez & José Ruiz
//    "Learning Regular Languages Using Nondeterministic Finite Automata"
//    Conference on Implementation and Application of Automata (CIAA), 2008
//
// 正の例（マッチして欲しい例）と負の例（マッチして欲しくない例）を
// それっぽく与えたらそれっぽいNFAを返す
//---------------------------------------------------------------------------

NFA learn_regex( string[] positive, string[] negative )
{
	// メインの学習ルーチン moil を適当に10回くらい呼んでみて
	// でてきた一番小さい NFA を採用する。
	// 
	// moil は必ず訓練データと矛盾しないNFAを返すので、
	// あとは NFA が小さければ小さい方が過学習してなさそうでよい

	NFA A = moil( positive, negative );
	foreach(_; 0..10) {
		NFA B = moil( positive, negative );
		if( A.stateNum > B.stateNum )
			A = B;
	}
	return A;
}



NFA moil( string[] Dp, string[] Dn )
{
	NFA A = NFA.empty;

	// 正の例を受理するように（負の例にマッチしないように気をつけつつ）１個ずつ増やしてく
	for(int i=0; i<Dp.length; ++i)
		if( !A.accept(Dp[i]) )
		{
			A = moil_merge(A, Dp[i], Dp, Dn);
			assert( A.accept(Dp[i]) );
			assert( A.accept_none(Dn) );
		}

	return A;
}

NFA moil_merge( NFA A, string x, string[] Dp, string[] Dn )
{
	NFA B = NFA.from_string(x);
	NFA C = NFA.merge(A, B);

	for(int q=A.stateNum; q<C.stateNum; ++q)
	{
		NFA bestM  = null;
		int bestMC = 0;

		// マージすると一番多く正の例を受理できるようになるところをマージする
		foreach(p; 0..q)
		{
			NFA M = NFA.mergeState(C, p, q);
			if( !M.accept_none(Dn) )
				continue;

			int MC = count!( (string s){return M.accept(s);} )(Dp);
			if( bestM is null || bestMC < MC )
			{
				bestM  = M;
				bestMC = MC;
			}
		}

		if( bestM !is null ) {
			C = bestM;
			--q;
		}
	}

	return C;
}



//---------------------------------------------------------------------------
// てすてす
//---------------------------------------------------------------------------

void main()
{
	{
		string[] Dp = ["aaa", "abb", "aaaabbbb",  "abbbbb", "bbb"];
		string[] Dn = ["baa", "bab", "bbbbbaaaaaa", "abba"];

		string[] DpX = ["ab", "aaaaab","aab"];
		string[] DnX = ["bbbbbbaa", "babababa", "bbbbba","ba", "aba"];

		NFA A = learn_regex(Dp, Dn);

		foreach(s; Dp) writeln("LEARN(+): ", (A.accept(s) ? "ok" : "bad") );
		foreach(s; Dn) writeln("LEARN(-): ", (A.accept(s) ? "bad" : "ok") );
		foreach(s; DpX) writeln("EVAL(+): ", (A.accept(s) ? "ok" : "bad") );
		foreach(s; DnX) writeln("EVAL(-): ", (A.accept(s) ? "bad" : "ok") );

		writeln(A);
	}
	{
		string[] Dp = ["zzz@zzz.zzz", "bbb@ccc.aaa", "ccc@bbb.aaa", "prml@example.com"];
		string[] Dn = ["aaabbbccc", "aaabbb.ccc", "aaa@bbbccc", "aaa.bbb@ccc"];

		string[] DpX = ["hello@be.com", "kiki@kmnos.net", "good@mail.address"];
		string[] DnX = ["bbbbbbaa", "babababa", "bbbbba","ba", "aba", "bad@mailaddress"];

		NFA A = learn_regex(Dp, Dn);

		foreach(s; Dp) writeln("LEARN(+): ", (A.accept(s) ? "ok" : "bad") );
		foreach(s; Dn) writeln("LEARN(-): ", (A.accept(s) ? "bad" : "ok") );
		foreach(s; DpX) writeln("EVAL(+): ", (A.accept(s) ? "ok" : "bad") );
		foreach(s; DnX) writeln("EVAL(-): ", (A.accept(s) ? "bad" : "ok") );

		writeln(A);
	}
}