% Longest Common Subsequence, 04-feb-2014
				% LPImmes
				% Employ pragma declaration in order to memoize.

				%longCommSubseq 487>uname -a
				%Darwin luke-immess-imac-2.local 13.0.0 Darwin Kernel
				%Version 13.0.0: Thu Sep 19 22:22:27 PDT 2013;
				%root:xnu-2422.1.72~6/RELEASE_X86_64 x86_64

				%Make sure that  .bashrc has:
				%  MERCURY_GCC=/Developer-3.2/usr
				% ...
				% $MERCURY_GCC/bin:\
				% ...
				%
				% Comment out this path entry for compiling, e.g., python modules.
				%
				%longCommSubseq 485>gcc --version
				%i686-apple-darwin10-gcc-4.2.1 (GCC) 4.2.1 (Apple Inc. build 5646)
				%Copyright (C) 2007 Free Software Foundation, Inc.
				%This is free software; see the source for copying conditions.  There is NO
				%warranty; not even for MERCHANTABILITY
				%or FITNESS FOR A PARTICULAR PURPOSE.
				%

				%longCommSubseq 483>mmc -version
				%mercury_compile: invalid grade `ion'
				%Mercury Compiler, version 13.05, configured for x86_64-apple-darwin12.5.0
				%Copyright (C) 1993-2013 The University of Melbourne
				%Usage: mmc [<options>] <arguments>
				%Use `mmc --help' for more information.

				%BUILD, either one:
				% mmc --make --fully-strict -E -v -O 0 --use-subdirs longCommSubseq
				% mmc --grade none.gc.stseg --fully-strict -E -v -O 0 --use-subdirs longCommSubseq

				% RUN: 
				% longCommSubseq 507>./longCommSubseq


:- module longCommSubseq.		% name of file, for now
:- interface.
:- import_module io.

:- pred main(io, io).
:- mode main(di, uo) is det.

:- implementation.
:- import_module pair, char, int, list, array, string.

:- func   findLngCmnSubsq(pair(list(string), list(string)), string) = string.
:- mode findLngCmnSubsq(in, in) = out is det.
:- pragma memo(findLngCmnSubsq/2). % Cache old results;  no need to write additional code.
findLngCmnSubsq(Pair, CurLngCmn) = LngCmnSq :-
				% Don't use ';' even though a little easier to read, because this neccessites 'multi'.
				% And multi can be problematic with memo pragma.

	% Compare left to right, 1st element, rest...x
	First = fst(Pair),
	Second = snd(Pair),
	A = list.det_index0(First, 0),
	B = list.det_index0(Second, 0),
	
	(if (A = ""; B = "") % ; means or
	then
	LngCmnSq = CurLngCmn
	
	else
	% End char is =, split further...
	list.det_drop(1, First, First_remaining),
	 list.det_drop(1, Second, Second_remaining),
	(if A = B
	then

	LngCmnSq = findLngCmnSubsq(
				   pair(First_remaining, Second_remaining),
				   CurLngCmn ++ A)

	% Compare shorter one to a longer one, split further...
	else
	S1 = findLngCmnSubsq(
			pair(First, Second_remaining),
			CurLngCmn),
	 S2 = findLngCmnSubsq(
			pair(First_remaining, Second),
			CurLngCmn),
	(if string.length(S1) >= string.length(S2)
	then
	LngCmnSq = S1
	else
	LngCmnSq = S2
	) % S1 >= S2
	) % A = B
	). % empty test

:- pred charToStrLst(list(char), list(string), list(string)).
:- mode charToStrLst(in, in, out) is det.
charToStrLst([H | T], Accum, LstStr) :-  % [H|T] can fail
	(if list.is_empty([H|T]) 
	then
	LstStr = Accum
	else
	format("%c", [c(H)], Str),
	 charToStrLst(T, [Str | Accum], LstStr)
	).

:- func longestCommonSubsequence(int) = string.
:- mode longestCommonSubsequence(in) = out is det. % because of charToStrLst
longestCommonSubsequence(Indx) = LngCmnSubsq :-
				% Input test cases from tst/0: 0, 1, 2, 3, 4.
	PairsTst = array.lookup(tst, Indx),
	Apair =  list.det_index0(PairsTst, 0),
	charToStrLst(string.to_char_list(Apair), [], LstFrst),

	Bpair =  list.det_index0(PairsTst, 1),
	charToStrLst(string.to_char_list(Bpair), [], LstSnd),
	
	PairsLst = pair(LstFrst, LstSnd),
	LngCmnSubsq = findLngCmnSubsq(PairsLst, "").

:- func tst = array(list(string)).
:- mode tst = out is det.
				% When prompted for test index, use either: 0, 1, 2, 3, 4.
tst =  array.array([                
		    ["a", "" ]
		   ]
		  ).

main(In, Out) :-
	write_string("Input test case 0, 1, 2, 3, 4. Output longest common subsequence.\n^d to quit.\n", In, Out1),
	mainAux(Out1, Out).

:- pred mainAux(io, io).
:- mode mainAux(di, uo) is det.
mainAux(In, Out) :-
	read_line_as_string(Result, In, Out0), % blank line, wait for input from console
	(
	 Result = eof,		% c^d
	 write_string("хорошо́ EOF, Quit\n", Out0, Out)
	;
	 Result = error(Error),
	 format("IO error: %s\n", [s(io.error_message(Error))], Out0, Out) % IO error from readLine
	;
	 Result = ok(IndxStr),
	 Indx = string.det_to_int(string.strip(IndxStr)), % use det_ so func. is det
	 format("Longest Common Subsequence: '%s'\n",
		[ s(longestCommonSubsequence(Indx)) ], Out0, Out1),
	 mainAux(Out1, Out) % do it again
	).