/* 

  Find common directory path (Rosetta code) in Picat.

  http://rosettacode.org/wiki/Find_common_directory_path
  """
  Create a routine that, given a set of strings representing directory 
  paths and a single character directory separator, will return a string 
  representing that part of the directory tree that is common to all 
  the directories.

  Test your routine using the forward slash '/' character as the directory 
  separator and the following three strings as input paths:

    '/home/user1/tmp/coverage/test'
    '/home/user1/tmp/covert/operator'
    '/home/user1/tmp/coven/members'

  Note: The resultant path should be the valid directory '/home/user1/tmp' and 
  not the longest common string '/home/user1/tmp/cove'.
  If your language has a routine that performs this function (even if it does 
  not have a changeable separator character), then mention it as part of the task. 
  """

  This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Picat page: http://www.hakank.org/picat/

*/


import util.
% import cp.


main => go.


%
% Finds "/home/user1/tmp/" as it should.
%
go =>
  Dirs = [
          "/home/user1/tmp/coverage/test",
          "/home/user1/tmp/covert/operator",
          "/home/user1/tmp/coven/members"
          ],
  Path = find_common_directory_path(Dirs),
  println(path=Path),
  nl.

%
% The common directory path is "/" (different home dirs)
%
go2 => 
  Dirs = [
         "/home/user1/tmp/coverage/test",
          "/home/user1/tmp/covert/operator",
          "/home/user1/tmp/coven/members"
          ],
  Path = find_common_directory_path2(Dirs),
  println(path=Path),
  nl.

go3 => 
  Dirs = [
          "/home/user1/tmp/coverage/test",
          "/home/user1/tmp/covert/operator",
          "/home/user1/tmp/coven/members"
          ],

  Path = find_common_directory_path3(Dirs),
  println(path=Path),

  nl.

go4 => 
  Dirs = [
          "/home/user1/tmp/coverage/test",
          "/home/user1/tmp/covert/operator",
          "/home/user1/tmp/coven/members"
          ],

  Path = find_common_directory_path4(Dirs),
  println(path=Path),

  nl.


% plain common prefix
go5 => 
  Dirs = [
          "/home/user1/tmp/coverage/test",
          "/home/user1/tmp/covert/operator",
          "/home/user1/tmp/coven/members"
          ],

  common_prefix3(Dirs,Prefix,Len),
  println([prefix=Prefix,len=Len]),

  nl.


%
% Using maxof/2 to get the longest common prefix.
%
find_common_directory_path(Dirs) = Path =>
  maxof( (common_prefix(Dirs,  Path,Len), append(_,"/",Path)), Len).

%
% Find a common prefix of all lists/strings in Ls.
% Using append/3.
% 
common_prefix(Ls, Prefix,Len) => 
  foreach(L in Ls) 
    append(Prefix,_,L)
  end,
  Len = Prefix.length.

%
% Imperative version 
%
find_common_directory_path2(Dirs) = Path =>
  common_prefix2(Dirs,'/',  Path).

common_prefix2(Ls,Last,Prefix) =>
  Len = Ls.length,
  MinLen = min([length(Ls[I]) : I in 1..Len]),
  Same = [ [1 : J in 2..Len,Ls[J,I]==Ls[J-1,I]] : I in 1..MinLen],
  Len1 = Len - 1,
  Ix = max([I : I in 1..Same.length, length(Same[I]) == Len1]),
  Ls1 = Ls[1],
  Prefix1 = [Ls1[I] : I in 1..Ix],
  if Last != [] then
    Prefix = [Ls1[I] : I in 1..find_last_of(Prefix1,Last)]
  else 
    Prefix = Prefix1
  end.


% 
% Using tabling.
%
find_common_directory_path3(Dirs) = Path =>
  common_prefix3(Dirs,Path,'/',_Len).

table(+,-,max)
common_prefix3(Ls,Prefix,Len) => 
  common_prefix3(Ls,Prefix,[],Len).

table(+,-,+,max)
common_prefix3(Ls,Prefix,Last,Len) =>
  foreach(L in Ls) 
    append(Prefix,_,L)
  end,
  if Last != [], Prefix != [] then
    Prefix.last() == Last
  end,
  Len = Prefix.length.


%
% Imperative
%
find_common_directory_path4(Dirs) = Path =>
  Len = Dirs.length,
  Splits = [D.split("/") : D in Dirs],
  MinLen = min([S.length() : S in Splits]),
  Ix = 0,
  Ok = true,
  while (Ix <= MinLen, Ok == true)
    Ix := Ix + 1,
    foreach(I in 2..Len)
      if Splits[I,Ix] != Splits[I-1,Ix] then
        Ok := false
      end
    end
  end,
  if Ix > 0 then
    Path = "/" ++ [Splits[1,I] : I in 1..Ix-1].join("/") ++ "/"
  else 
    Path = ""
  end.