% Longest Common Subsequence, 06-feb-2014
				% Redo this code, use just strings, easier for user to understand.
				% LPImmes
				% Employ pragma declaration in order to memoize-- makes a huge difference,
				% see test cases 9.
				% Future, show argument calls to findLngCmnSubsq/2, with and without
				% pragma declaration.

				%lngCommSubseq 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.
				%
				%lngCommSubseq 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.
				%

				%lngCommSubseq 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 lngCommonSubseqStck
				% mmc --grade none.gc.stseg --fully-strict -E -v -O 0 --use-subdirs lngCommSubseqStck

				%With logging: try to run
				% lngCommSubsq 503>./lngCommSubseqStck.bash
				% Working, and predicates found in module, but not sure of semantics of his logging.

				% RUN: 
% lngCommSubseqStck 495>./lngCommonSubseqStck 
% Input test case 0, 1, 2, 3, 4, ... Output longest common subsequence.
% ^d to quit.
% 	Caching really speeds up execution, but same number of calls.
% 0
% LongestCommonSubsequence('a', 'a')='a',
% 	a length: 1, b length: 1, findLngCmnSubsqStck calls: 2.
% 1
% LongestCommonSubsequence('aa', 'bb')='',
% 	a length: 2, b length: 2, findLngCmnSubsqStck calls: 4.
% 2
% LongestCommonSubsequence('aaa', 'bbb')='',
% 	a length: 3, b length: 3, findLngCmnSubsqStck calls: 7.
% 3
% LongestCommonSubsequence('aaaa', 'bbbb')='',
% 	a length: 4, b length: 4, findLngCmnSubsqStck calls: 11.
% 4
% LongestCommonSubsequence('aaaaa', 'bbbbb')='',
% 	a length: 5, b length: 5, findLngCmnSubsqStck calls: 16.
% 5
% LongestCommonSubsequence('aaaaaa', 'bbbbbb')='',
% 	a length: 6, b length: 6, findLngCmnSubsqStck calls: 22.
% 6
% LongestCommonSubsequence('aaaaaaa', 'bbbbbbb')='',
% 	a length: 7, b length: 7, findLngCmnSubsqStck calls: 29.
% 7
% LongestCommonSubsequence('aaaaaaaa', 'bbbbbbbb')='',
% 	a length: 8, b length: 8, findLngCmnSubsqStck calls: 37.
% 9
% LongestCommonSubsequence('aaaaaaaaaa', 'bbbbbbbbbb')='',
% 	a length: 10, b length: 10, findLngCmnSubsqStck calls: 56.
% 10
% LongestCommonSubsequence('aaaaaaaaaaa', 'bbbbbbbbbbb')='',
% 	a length: 11, b length: 11, findLngCmnSubsqStck calls: 67.
% 11
% LongestCommonSubsequence('aaaaaaaaaaaa', 'bbbbbbbbbbbb')='',
% 	a length: 12, b length: 12, findLngCmnSubsqStck calls: 79.
% 12
% LongestCommonSubsequence('aaaaaaaaaaaaa', 'bbbbbbbbbbbbb')='',
% 	a length: 13, b length: 13, findLngCmnSubsqStck calls: 92.
% 13
% LongestCommonSubsequence('aaaaaaaaaaaaaa', 'bbbbbbbbbbbbbb')='',
% 	a length: 14, b length: 14, findLngCmnSubsqStck calls: 106.
% 14
% LongestCommonSubsequence('aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa', 'bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb')='',
% 	a length: 61, b length: 61, findLngCmnSubsqStck calls: 1892.
% 15
% LongestCommonSubsequence('a', '')='',
% 	a length: 1, b length: 0, findLngCmnSubsqStck calls: 1.
% 16
% LongestCommonSubsequence('abcbdab', 'bdcaba')='bcba',
% 	a length: 7, b length: 6, findLngCmnSubsqStck calls: 37.
% хорошо́ EOF, Quit
% lngCommSubseqStck 495>

:- module lngCommonSubseqStck.		% 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. % io. %log4m.

% Analysis
% Following author uses longest length, versus, longest common sequence, as an output:
%   http://www.ics.uci.edu/~eppstein/161/960229.html
%    Time analysis for his code: each call to subproblem takes constant time. We call it once from the main routine,
%    and at most twice every time we fill in an entry of array L. There are (m+1)(n+1) entries, so the
%    total number of calls is at most 2(m+1)(n+1)+1 and the time is O(mn).
%
% Comment pragma out, and run test case: 9, aaaa..., bbb..., and we wait forever.
% Using pragma, i.e, caching, we solve same problem very quickly.
% Work out by hand: (aaaa, bbbb); some caching does occur, e.g., (aaa, bb). For this small example it does not
% seem that the amount of caching is significant.

% See mercury IO: http://dbpatterson.tumblr.com/post/10101986648
% Calling java:
% http://www.mercurylang.org/information/doc-release/mercury_ref/Using-pragma-foreign_005fexport-for-Java.html

% Pragma, i.e., caching really speeds up execution, but number of calls is the same in either case.
% I would be expecting much fewer calls if caching, i.e., no repeat recursion.
:- func   findLngCmnSubsqStck(int, string, string) = pair(int, string).
:- mode findLngCmnSubsqStck(in, in, in) = out is det.
:- pragma memo(findLngCmnSubsqStck/3). % Cache old results;  no need to write additional code.
findLngCmnSubsqStck(Cnt, First, Second) = LngCmnSq :-
				% Don't use ';' even though a little easier to read, because this neccessites 'multi'.
				% And multi can be problematic with memo pragma.
				% Compare these two strings left to right.
	string.split(First, 1, A, FirstRest),
	string.split(Second, 1, B, SecondRest),
	
	(if (A = ""; B = "")	% ';' means or; base case
	then
	LngCmnSq = pair(Cnt+1, "")
	
	else			% recursive cases
	(if A = B		% initial char =
	then
	P = findLngCmnSubsqStck(Cnt+1, FirstRest, SecondRest),
	 NewCnt = fst(P), LngCm = snd(P),
	 LngCmnSq = pair(NewCnt + Cnt, A ++ LngCm) 
	
	else % initial char is != , so shorten size of the other string
	P1 = findLngCmnSubsqStck(Cnt+1, First, SecondRest),
	 NewCnt1 = fst(P1), LngCm1 = snd(P1),
	 P2 =  findLngCmnSubsqStck(Cnt+1, FirstRest, Second),
	 NewCnt2 = fst(P2), LngCm2 = snd(P2),
	 
	 (if string.length(LngCm1) >= string.length(LngCm2)
	 then
	 LngCmnSq = pair(NewCnt1 + Cnt, LngCm1) 
	 else
	 LngCmnSq = pair(NewCnt2 + Cnt, LngCm2) 
	 )			% S1 >= S2
	
	)			% A = B
	).			% empty string test

:- func longestCommonSubsequence(int) = string.
:- mode longestCommonSubsequence(in) = out is det. 
longestCommonSubsequence(Indx) = LngCmnSubsq :-
				% Input test cases from tst/0: 0, 1, 2, 3, 4 ,...
	PairsTst = array.lookup(tst, Indx),
	A = list.det_index0(PairsTst, 0), LenA = string.length(A),
	B = list.det_index0(PairsTst, 1), LenB = string.length(B),
	P = findLngCmnSubsqStck(0, A, B),
	Cnt = fst(P), LngCm = snd(P),
	format("LongestCommonSubsequence('%s', '%s')='%s',\n\ta length: %i, b length: %i, findLngCmnSubsqStck calls: %i.",
	      [s(A), s(B), s(LngCm), i(LenA), i(LenB), i(Cnt)], LngCmnSubsq).

:- 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([                
				   % Worst case analysis, if strings are != in every position
				    % length a string = length of b string
				    ["a",        "a"],	      
				    ["aa",        "bb"],    
				    ["aaa",       "bbb"],  
				    ["aaaa",     "bbbb"],  
				    ["aaaaa",    "bbbbb"], 
				    ["aaaaaa",  "bbbbbb"], 
				    ["aaaaaaa", "bbbbbbb"],
				    ["aaaaaaaa", "bbbbbbbb"],
				    ["aaaaaaaaa", "bbbbbbbbb"],
				    ["aaaaaaaaaa", "bbbbbbbbbb"], 
				    ["aaaaaaaaaaa", "bbbbbbbbbbb"], 
				    ["aaaaaaaaaaaa", "bbbbbbbbbbbb"], 
				    ["aaaaaaaaaaaaa", "bbbbbbbbbbbbb"], % starts to slow up here without caching
				    ["aaaaaaaaaaaaaa", "bbbbbbbbbbbbbb"], 

				    % go forever if no caching; careful on proportional fonts! Lengths can be deceiving.
				    [
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
"bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb"],
				    
				    % typical cases
				    ["a", "" ],	% 0  ''
				    ["abcbdab", "bdcaba"], % 8 'bcba' Cormen text, p391, 36 calls
				    ["a", "b"],	 % 4 ''
				    ["a", "ab"],     % 5 'a'
				    ["ab", "a"],     % 6 'a'
				    ["ba", "a"],     % 5 'a'
				    ["bac", "cab"],  % 6 'b'
				    ["bac", "abc"]   % 7 'bc'
	
		   ]
		  ).

main(In, Out) :-
	write_string("Input test case 0, 1, 2, 3, 4, ... Output longest common subsequence.\n^d to quit.\n\tCaching really speeds up execution, but same number of calls.\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("%s\n",	[ s(longestCommonSubsequence(Indx)) ], Out0, Out1),
	 mainAux(Out1, Out) % do it again
	).