Find common directory path
You are encouraged to solve this task according to the task description, using any language you may know.
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)
Ada
<lang ada> with Ada.Text_IO; use Ada.Text_IO;
procedure Test_Common_Path is
function "rem" (A, B : String) return String is Slash : Integer := A'First; -- At the last slash seen in A At_A : Integer := A'first; At_B : Integer := B'first; begin loop if At_A > A'Last then if At_B > B'Last or else B (At_B) = '/' then return A; else return A (A'First..Slash - 1); end if; elsif At_B > B'Last then if A (At_A) = '/' then -- A cannot be shorter than B here return B; else return A (A'First..Slash - 1); end if; elsif A (At_A) /= B (At_B) then return A (A'First..Slash - 1); elsif A (At_A) = '/' then Slash := At_A; end if; At_A := At_A + 1; At_B := At_B + 1; end loop; end "rem";
begin
Put_Line ( "/home/user1/tmp/coverage/test" rem "/home/user1/tmp/covert/operator" rem "/home/user1/tmp/coven/members" );
end Test_Common_Path; </lang> Output:
/home/user1/tmp
ALGOL 68
<lang algol68># Utilities code #
CHAR dir sep = "/"; # Assume POSIX #
PROC dir name = (STRING dir)STRING: (
STRING out; FOR pos FROM UPB dir BY -1 TO LWB dir DO IF dir[pos] = dir sep THEN out := dir[:pos-1]; GO TO out exit FI OD; # else: # out:=""; out exit: out
);
PROC shortest = ([]STRING string list)STRING: (
INT min := max int; INT min key := LWB string list - 1; FOR key FROM LWB string list TO UPB string list DO IF UPB string list[key][@1] < min THEN min := UPB string list[key][@1]; min key := key FI OD; string list[min key]
);
- Actual code #
PROC common prefix = ([]STRING strings)STRING: (
IF LWB strings EQ UPB strings THEN # exit: # strings[LWB strings] ELSE STRING prefix := shortest(strings); FOR pos FROM LWB prefix TO UPB prefix DO CHAR first = prefix[pos]; FOR key FROM LWB strings+1 TO UPB strings DO IF strings[key][@1][pos] NE first THEN prefix := prefix[:pos-1]; GO TO prefix exit FI OD OD; prefix exit: prefix FI
);
- Test code #
test:(
[]STRING dir list = ( "/home/user1/tmp/coverage/test", "/home/user1/tmp/covert/operator", "/home/user1/tmp/coven/members" ); print((dir name(common prefix(dir list)), new line))
)</lang> Output:
/home/user1/tmp
AutoHotkey
<lang autohotkey>Dir1 := "/home/user1/tmp/coverage/test" Dir2 := "/home/user1/tmp/covert/operator" Dir3 := "/home/user1/tmp/coven/members"
StringSplit, Dir1_, Dir1, / StringSplit, Dir2_, Dir2, / StringSplit, Dir3_, Dir3, /
Loop
If (Dir1_%A_Index% = Dir2_%A_Index%) And (Dir1_%A_Index% = Dir3_%A_Index%) Result .= (A_Index=1 ? "" : "/") Dir1_%A_Index% Else Break
MsgBox, % Result</lang> Message box shows:
/home/user1/tmp
AWK
<lang awk># Finds the longest common directory of paths[1], paths[2], ...,
- paths[count], where sep is a single-character directory separator.
function common_dir(paths, count, sep, b, c, f, i, j, p) { if (count < 1) return ""
p = "" # Longest common prefix f = 0 # Final index before last sep
# Loop for c = each character of paths[1]. for (i = 1; i <= length(paths[1]); i++) { c = substr(paths[1], i, 1)
# If c is not the same in paths[2], ..., paths[count] # then break both loops. b = 0 for (j = 2; j <= count; j++) { if (c != substr(paths[j], i, 1)) { b = 1 break } } if (b) break
# Append c to prefix. Update f. p = p c if (c == sep) f = i - 1 }
# Return only f characters of prefix. return substr(p, 1, f) }
BEGIN { a[1] = "/home/user1/tmp/coverage/test" a[2] = "/home/user1/tmp/covert/operator" a[3] = "/home/user1/tmp/coven/members" print common_dir(a, 3, "/") }</lang>
Prints /home/user1/tmp.
BASIC
This version is a little smarter than the one above... but not much. This version could be turned into an actual useful utility by changing it to compare command-line parameters, instead of built-in data.
Also, under FreeBASIC, the pathSep
arg to commonPath$
could be made optional, or even system-dependent.
<lang qbasic>DECLARE FUNCTION commonPath$ (paths() AS STRING, pathSep AS STRING)
DATA "/home/user2", "/home/user1/tmp/covert/operator", "/home/user1/tmp/coven/members"
DIM x(0 TO 2) AS STRING, n AS INTEGER FOR n = 0 TO 2
READ x(n)
NEXT
PRINT "Common path is '"; commonPath$(x(), "/"); "'"
FUNCTION commonPath$ (paths() AS STRING, pathSep AS STRING)
DIM tmpint1 AS INTEGER, tmpint2 AS INTEGER, tmpstr1 AS STRING, tmpstr2 AS STRING DIM L0 AS INTEGER, L1 AS INTEGER, lowerbound AS INTEGER, upperbound AS INTEGER lowerbound = LBOUND(paths): upperbound = UBOUND(paths)
IF (lowerbound) = upperbound THEN 'Some quick error checking... commonPath$ = paths(lowerbound) ELSEIF lowerbound > upperbound THEN 'How in the...? commonPath$ = "" ELSE tmpstr1 = paths(lowerbound)
FOR L0 = (lowerbound + 1) TO upperbound 'Find common strings. tmpstr2 = paths(L0) tmpint1 = LEN(tmpstr1) tmpint2 = LEN(tmpstr2) IF tmpint1 > tmpint2 THEN tmpint1 = tmpint2 FOR L1 = 1 TO tmpint1 IF MID$(tmpstr1, L1, 1) <> MID$(tmpstr2, L1, 1) THEN tmpint1 = L1 - 1 EXIT FOR END IF NEXT tmpstr1 = LEFT$(tmpstr1, tmpint1) NEXT
IF RIGHT$(tmpstr1, 1) <> pathSep THEN FOR L1 = tmpint1 TO 2 STEP -1 IF (pathSep) = MID$(tmpstr1, L1, 1) THEN tmpstr1 = LEFT$(tmpstr1, L1 - 1) EXIT FOR END IF NEXT IF LEN(tmpstr1) = tmpint1 THEN tmpstr1 = "" ELSEIF tmpint1 > 1 THEN tmpstr1 = LEFT$(tmpstr1, tmpint1 - 1) END IF
commonPath$ = tmpstr1 END IF
END FUNCTION</lang>
BBC BASIC
<lang bbcbasic> DIM path$(3)
path$(1) = "/home/user1/tmp/coverage/test" path$(2) = "/home/user1/tmp/covert/operator" path$(3) = "/home/user1/tmp/coven/members" PRINT FNcommonpath(path$(), "/") END DEF FNcommonpath(p$(), s$) LOCAL I%, J%, O% REPEAT O% = I% I% = INSTR(p$(1), s$, I%+1) FOR J% = 2 TO DIM(p$(), 1) IF LEFT$(p$(1), I%) <> LEFT$(p$(J%), I%) EXIT REPEAT NEXT J% UNTIL I% = 0 = LEFT$(p$(1), O%-1)</lang>
C
<lang C>#include <stdio.h>
int common_len(char **names, int n, char sep) { int i, pos; for (pos = 0; ; pos++) { for (i = 0; i < n; i++) { if (names[i][pos] != '\0' && names[i][pos] == names[0][pos]) continue;
/* backtrack */ while (pos > 0 && names[0][--pos] != sep); return pos; } }
return 0; }
int main() { char *names[] = { "/home/user1/tmp/coverage/test", "/home/user1/tmp/covert/operator", "/home/user1/tmp/coven/members", }; int len = common_len(names, sizeof(names) / sizeof(char*), '/');
if (!len) printf("No common path\n"); else printf("Common path: %.*s\n", len, names[0]);
return 0; }</lang>output:<lang>Common path: /home/user1/tmp</lang>
C++
<lang cpp>#include <algorithm>
- include <iostream>
- include <string>
- include <vector>
std::string longestPath( const std::vector<std::string> & , char ) ;
int main( ) {
std::string dirs[ ] = { "/home/user1/tmp/coverage/test" , "/home/user1/tmp/covert/operator" , "/home/user1/tmp/coven/members" } ; std::vector<std::string> myDirs ( dirs , dirs + 3 ) ; std::cout << "The longest common path of the given directories is " << longestPath( myDirs ,
'/' ) << "!\n" ;
return 0 ;
}
std::string longestPath( const std::vector<std::string> & dirs , char separator ) {
std::vector<std::string>::const_iterator vsi = dirs.begin( ) ; int maxCharactersCommon = vsi->length( ) ; std::string compareString = *vsi ; for ( vsi = dirs.begin( ) + 1 ; vsi != dirs.end( ) ; vsi++ ) { std::pair<std::string::const_iterator , std::string::const_iterator> p =
std::mismatch( compareString.begin( ) , compareString.end( ) , vsi->begin( ) ) ;
if (( p.first - compareString.begin( ) ) < maxCharactersCommon )
maxCharactersCommon = p.first - compareString.begin( ) ;
} std::string::size_type found = compareString.rfind( separator , maxCharactersCommon ) ; return compareString.substr( 0 , found ) ;
}</lang> Output:
The longest common path of the given directories is /home/user1/tmp!
Clojure
<lang clojure>(use '[clojure.string :only [join,split]])
(defn common-prefix [sep paths]
(let [parts-per-path (map #(split % (re-pattern sep)) paths) parts-per-position (apply map vector parts-per-path)] (join sep (for [parts parts-per-position :while (apply = parts)] (first parts)))))
(println
(common-prefix "/" ["/home/user1/tmp/coverage/test" "/home/user1/tmp/covert/operator" "/home/user1/tmp/coven/members"]))</lang>
C#
<lang csharp> using System; using System.Collections.Generic; using System.Linq; using System.Text;
namespace RosettaCodeTasks {
class Program { static void Main ( string[ ] args ) { FindCommonDirectoryPath.Test ( ); }
}
class FindCommonDirectoryPath { public static void Test ( ) { Console.WriteLine ( "Find Common Directory Path" ); Console.WriteLine ( ); List<string> PathSet1 = new List<string> ( ); PathSet1.Add ( "/home/user1/tmp/coverage/test" ); PathSet1.Add ( "/home/user1/tmp/covert/operator" ); PathSet1.Add ( "/home/user1/tmp/coven/members" ); Console.WriteLine("Path Set 1 (All Absolute Paths):"); foreach ( string path in PathSet1 ) { Console.WriteLine ( path ); } Console.WriteLine ( "Path Set 1 Common Path: {0}", FindCommonPath ( "/", PathSet1 ) ); } public static string FindCommonPath ( string Separator, List<string> Paths ) { string CommonPath = String.Empty; List<string> SeparatedPath = Paths .First ( str => str.Length == Paths.Max ( st2 => st2.Length ) ) .Split ( new string[ ] { Separator }, StringSplitOptions.RemoveEmptyEntries ) .ToList ( );
foreach ( string PathSegment in SeparatedPath.AsEnumerable ( ) ) { if ( CommonPath.Length == 0 && Paths.All ( str => str.StartsWith ( PathSegment ) ) ) { CommonPath = PathSegment; } else if ( Paths.All ( str => str.StartsWith ( CommonPath + Separator + PathSegment ) ) ) { CommonPath += Separator + PathSegment; } else { break; } }
return CommonPath; } } }
</lang>
D
<lang d>import std.stdio, std.string, std.algorithm, std.path;
string commonDirPath(string[] paths, char sep = '/') {
if (paths.length) { auto res = "", tmp = ""; sort!q{a.length < b.length}(paths); foreach (i, c ; paths[0]) { for (int j = 1; j < paths.length; j++) if (c != paths[j][i]) goto done; tmp ~= c; if (c == sep) { res ~= tmp; tmp = ""; } } if (res == "" && tmp != "") res = curdir; done: while(res.length > 1 && res[$-1] == sep) res = res.chop(); return res; } return null;
}
void main() {
string[] paths = ["/home/user1/tmp/coverage/test", "/home/user1/tmp/covert/operator", "/home/user1/tmp/coven/members"]; writeln("Common path is ", commonDirPath(paths, '/'));
}</lang>
Common path is /home/user1/tmp
Factor
<lang factor>: take-shorter ( seq1 seq2 -- shorter )
[ shorter? ] 2keep ? ;
- common-head ( seq1 seq2 -- head )
2dup mismatch [ nip head ] [ take-shorter ] if* ;
- common-prefix-1 ( file1 file2 separator -- prefix )
[ common-head ] dip '[ _ = not ] trim-tail ;
- common-prefix ( seq separator -- prefix )
[ ] swap '[ _ common-prefix-1 ] map-reduce ;</lang>
( scratchpad ) { "/home/user1/tmp/coverage/test" "/home/user1/tmp/covert/operator" "/home/user1/tmp/coven/members" } CHAR: / common-prefix . "/home/user1/tmp/"
Go
If the common path that would otherwise have been found ('/home/user1/tmp') is prepended to the list of paths in the C++ solution (and possibly some of the others; I didn't test them), then the final part of the path is removed. This solution also includes a correction for that.
<lang go>package main
import( "fmt" "path" "strings" )
func CommonPrefix(sep string, paths ...string) (string) { // Handle special cases. switch len(paths) { case 0: return "" case 1: return path.Clean(paths[0]) }
c := []byte(path.Clean(paths[0]))
// Ignore the first path since it's already in c. for _, v := range(paths[1:]) { // Clean up each path before testing it. v = path.Clean(v)
// Get the length of the shorter slice. shorter := len(v) if len(v) > len(c) { shorter = len(c) }
// Find the first non-common character and copy up to it into c. for i := 0; i < shorter; i++ { if v[i] != c[i] { c = c[0:i] break } } }
// Correct for problem caused by prepending the actual common path to the // list of paths searched through. for _, v := range(paths) { if len(v) > len(c) { if strings.HasPrefix(v, string(c)) { if len(v) > len(c) + len(sep) { if v[len(c):len(c)+len(sep)] == sep { c = append(c, []byte(sep)...) break } } } } }
// Remove trailing non-seperator characters. for i := len(c)-1; i >= 0; i-- { if i + len(sep) > len(c) { continue }
if string(c[i:i+len(sep)]) == sep { c = c[0:i] break } }
return string(c) }
func main() { c := CommonPrefix("/", "/home/user1/tmp/coverage/test", "/home/user1/tmp/covert/operator", "/home/user1/tmp/coven/members", ) fmt.Printf("%v\n", c) }</lang>
Groovy
Solution: <lang groovy>def commonPath = { delim, Object[] paths ->
def pathParts = paths.collect { it.split(delim) } pathParts.transpose().inject([match:true, commonParts:[]]) { aggregator, part -> aggregator.match = aggregator.match && part.every { it == part [0] } if (aggregator.match) { aggregator.commonParts << part[0] } aggregator }.commonParts.join(delim)
}</lang>
Test: <lang groovy>println commonPath('/',
'/home/user1/tmp/coverage/test', '/home/user1/tmp/covert/operator', '/home/user1/tmp/coven/members')
println commonPath('/',
'/home/user1/tmp/coverage/test', '/home/user1/tmp/covert/test', '/home/user1/tmp/coven/test', '/home/user1/tmp/covers/test')</lang>
Output:
/home/user1/tmp /home/user1/tmp
GW-BASIC
Because most BASICs don't have any sort of parsing functions built in, we have to deal with the entire string (rather than checking one level at a time).
Note that if the root directory is the common path, this reports the same as no match found (i.e. blank result).
<lang qbasic>10 REM All GOTO statements can be replaced with EXIT FOR in newer BASICs.
110 X$ = "/home/user1/tmp/coverage/test" 120 Y$ = "/home/user1/tmp/covert/operator" 130 Z$ = "/home/user1/tmp/coven/members"
150 A = LEN(X$) 160 IF A > LEN(Y$) THEN A = LEN(Y$) 170 IF A > LEN(Z$) THEN A = LEN(Z$) 180 FOR L0 = 1 TO A 190 IF MID$(X$, L0, 1) <> MID$(Y$, L0, 1) THEN GOTO 210 200 NEXT 210 A = L0 - 1
230 FOR L0 = 1 TO A 240 IF MID$(X$, L0, 1) <> MID$(Z$, L0, 1) THEN GOTO 260 250 NEXT 260 A = L0 - 1
280 IF MID$(X$, L0, 1) <> "/" THEN 290 FOR L0 = A TO 1 STEP -1 300 IF "/" = MID$(X$, L0, 1) THEN GOTO 340 310 NEXT 320 END IF
340 REM Task description says no trailing slash, so... 350 A = L0 - 1 360 P$ = LEFT$(X$, A) 370 PRINT "Common path is '"; P$; "'"</lang>
Output:
Common path is '/home/user1/tmp'
Haskell
<lang haskell> import Data.List
-- Return the common prefix of two lists. commonPrefix2 (x:xs) (y:ys) | x == y = x : commonPrefix2 xs ys commonPrefix2 _ _ = []
-- Return the common prefix of zero or more lists. commonPrefix (xs:xss) = foldr commonPrefix2 xs xss commonPrefix _ = []
-- Split a string into path components. splitPath = groupBy (\_ c -> c /= '/')
-- Return the common prefix of zero or more paths. -- Note that '/' by itself is not considered a path component, -- so "/" and "/foo" are treated as having nothing in common. commonDirPath = concat . commonPrefix . map splitPath
main = putStrLn $ commonDirPath [
"/home/user1/tmp/coverage/test", "/home/user1/tmp/covert/operator", "/home/user1/tmp/coven/members" ]
</lang>
HicEst
<lang HicEst>CHARACTER a='/home/user1/tmp/coverage/test', b='/home/user1/tmp/covert/operator', c='/home/user1/tmp/coven/members'
minLength = MIN( LEN(a), LEN(b), LEN(c) ) lastSlash = 0
DO i = 1, minLength
IF( (a(i) == b(i)) * (b(i) == c(i)) ) THEN IF(a(i) == "/") lastSlash = i ELSEIF( lastSlash ) THEN WRITE(Messagebox) "Common Directory = ", a(1:lastSlash-1) ELSE WRITE(Messagebox, Name) "No common directory for", a, b, c ENDIF
ENDDO</lang>
Icon and Unicon
<lang Icon>procedure main() write(lcdsubstr(["/home/user1/tmp/coverage/test","/home/user1/tmp/covert/operator","/home/user1/tmp/coven/members"])) end
procedure lcdsubstr(sL,d) #: return the longest common sub-string of strings in the list sL delimited by d local ss
/d := "/" reverse(sL[1]) ? {
if tab(find(d)+*d) || allmatch(ss := reverse(tab(0)),sL) then return ss }
end
procedure allmatch(s,L) #: retrun s if it matches all strings in L local x every x := !L do
if not match(s,x) then fail
return s end</lang>
J
Solution: <lang j>parseDirs =: = <;.2 ] getCommonPrefix =: {. ;@{.~ 0 i.~ *./@(="1 {.)
getCommonDirPath=: [: getCommonPrefix parseDirs&></lang>
Example: <lang j> paths=: '/home/user1/tmp/coverage/test';'/home/user1/tmp/covert/operator';'/home/user1/tmp/coven/members'
getCommonPrefix >paths
/home/user1/tmp/cove
'/' getCommonDirPath paths
/home/user1/tmp/</lang>
Note: This alternative formulation of parseDirs provides cross-platform support, without the need to specify the path separator. <lang j>parseDirs =: (PATHSEP_j_&= <;.2 ])@jhostpath</lang>
Java
This example is case-sensitive. <lang java5>public class CommonPath { public static String commonPath(String... paths){ String commonPath = ""; String[][] folders = new String[paths.length][]; for(int i = 0; i < paths.length; i++){ folders[i] = paths[i].split("/"); //split on file separator } for(int j = 0; j < folders[0].length; j++){ String thisFolder = folders[0][j]; //grab the next folder name in the first path boolean allMatched = true; //assume all have matched in case there are no more paths for(int i = 1; i < folders.length && allMatched; i++){ //look at the other paths if(folders[i].length < j){ //if there is no folder here allMatched = false; //no match break; //stop looking because we've gone as far as we can } //otherwise allMatched &= folders[i][j].equals(thisFolder); //check if it matched } if(allMatched){ //if they all matched this folder name commonPath += thisFolder + "/"; //add it to the answer }else{//otherwise break;//stop looking } } return commonPath; }
public static void main(String[] args){ String[] paths = { "/home/user1/tmp/coverage/test", "/home/user1/tmp/covert/operator", "/home/user1/tmp/coven/members"}; System.out.println(commonPath(paths));
String[] paths2 = { "/hame/user1/tmp/coverage/test", "/home/user1/tmp/covert/operator", "/home/user1/tmp/coven/members"}; System.out.println(commonPath(paths2)); } }</lang> Output:
/home/user1/tmp/ /
Change folders[i] = paths[i].split("/");
to add more separators. Ex: to add "\" and "." as separators, change the line to folders[i] = paths[i].split("[/\\\\.]");
(adding square brackets makes the regex choose one character out of the group inside, adding all of the extra backslashes escapes the backslash character). After making this change, all separators will be changed to "/" in the result, but they can be mixed in the path (e.g. "/home.user1/tmp\\coverage/test" (escaped backslash) will act the same as "/home/user1/tmp/coverage/test").
Liberty BASIC
<lang lb>path$(1) = "/home/user1/tmp/coverage/test" path$(2) = "/home/user1/tmp/covert/operator" path$(3) = "/home/user1/tmp/coven/members"
print samepath$(3,"/")
end
function samepath$(paths,sep$)
d = 1 'directory depth n = 2 'path$(number) while 1 if word$(path$(1),d,sep$) <> word$(path$(n),d,sep$) or word$(path$(1),d,sep$) = "" then exit while n = n + 1 if n > paths then if right$(samepath$,1) <> sep$ and d<>1 then samepath$ = samepath$ + sep$ + word$(path$(1),d,sep$) else samepath$ = samepath$ + word$(path$(1),d,sep$) end if n = 2 d = d + 1 end if wend
end function</lang>
Mathematica
<lang Mathematica>FindCommonDirectory[x_] := If[StringTake[#, -1] != "/", StringTake[#, Max[StringPosition[#, "/"]]], #] &
[Fold[LongestCommonSubsequence, First[x] , Rest[x]]]
FindCommonDirectory[{"/home/user1/tmp/coverage/test", "/home/user1/tmp/covert/operator", "/home/user1/tmp/coven/members"}] ->"/home/user1/tmp/"</lang>
MUMPS
<lang MUMPS>FCD
NEW D,SEP,EQ,LONG,DONE,I,J,K,RETURN SET D(1)="/home/user1/tmp/coverage/test" SET D(2)="/home/user1/tmp/covert/operator" SET D(3)="/home/user1/tmp/coven/members" SET SEP="/" SET LONG=D(1) SET DONE=0 FOR I=1:1:$LENGTH(LONG,SEP) QUIT:DONE SET EQ(I)=1 FOR J=2:1:3 SET EQ(I)=($PIECE(D(J),SEP,I)=$PIECE(LONG,SEP,I))&EQ(I) SET DONE='EQ(I) QUIT:'EQ(I) SET RETURN="" FOR K=1:1:I-1 Q:'EQ(K) SET:EQ(K) $PIECE(RETURN,SEP,K)=$PIECE(LONG,SEP,K) WRITE !,"For the paths:" FOR I=1:1:3 WRITE !,D(I) WRITE !,"The longest common directory is: ",RETURN KILL D,SEP,EQ,LONG,DONE,I,J,K,RETURN QUIT</lang>
Usage:
USER>D FCD^ROSETTA For the paths: /home/user1/tmp/coverage/test /home/user1/tmp/covert/operator /home/user1/tmp/coven/members The longest common directory is: /home/user1/tmp
OCaml
<lang ocaml>let rec aux acc paths =
if List.mem [] paths then (List.rev acc) else let heads = List.map List.hd paths in let item = List.hd heads in let all_the_same = List.for_all ((=) item) (List.tl heads) in if all_the_same then aux (item::acc) (List.map List.tl paths) else (List.rev acc)
let common_prefix sep = function
| [] -> invalid_arg "common_prefix" | dirs -> let paths = List.map (Str.split (Str.regexp_string sep)) dirs in let res = aux [] paths in (sep ^ (String.concat sep res))
let () =
let dirs = [ "/home/user1/tmp/coverage/test"; "/home/user1/tmp/covert/operator"; "/home/user1/tmp/coven/members"; ] in print_endline (common_prefix "/" dirs);
- </lang>
(uses the module Str
, str.cma)
OpenEdge/Progress
<lang progress>FUNCTION findCommonDir RETURNS CHAR(
i_cdirs AS CHAR, i_cseparator AS CHAR
):
DEF VAR idir AS INT. DEF VAR idepth AS INT. DEF VAR cdir AS CHAR EXTENT. DEF VAR lsame AS LOGICAL INITIAL TRUE. DEF VAR cresult AS CHAR.
EXTENT( cdir ) = NUM-ENTRIES( i_cdirs, '~n' ).
DO idir = 1 TO NUM-ENTRIES( i_cdirs, '~n' ): cdir[ idir ] = ENTRY( idir, i_cdirs, '~n' ). END.
DO idepth = 2 TO NUM-ENTRIES( cdir [ 1 ], i_cseparator ) WHILE lsame: DO idir = 1 TO EXTENT( cdir ) - 1 WHILE lsame: lsame = ( ENTRY( idepth, cdir [ idir ], i_cseparator ) = ENTRY( idepth, cdir [ idir + 1 ], i_cseparator ) ). END. IF lsame THEN cresult = cresult + i_cseparator + ENTRY( idepth, cdir [ 1 ], i_cseparator ). END.
RETURN cresult.
END FUNCTION.</lang>
<lang progress>MESSAGE
findCommonDir( '/home/user1/tmp/coverage/test' + '~n' + '/home/user1/tmp/covert/operator' + '~n' + '/home/user1/tmp/coven/members', '/' )
VIEW-AS ALERT-BOX</lang>
Output
--------------------------- Message (Press HELP to view stack trace) --------------------------- /home/user1/tmp --------------------------- OK Help ---------------------------
Oz
With a few helper functions, we can express the solution like this in Oz: <lang oz>declare
fun {CommonPrefix Sep Paths} fun {GetParts P} {String.tokens P Sep} end Parts = {ZipN {Map Paths GetParts}} EqualParts = {List.takeWhile Parts fun {$ X|Xr} {All Xr {Equals X}} end} in {Join Sep {Map EqualParts Head}} end
fun {ZipN Xs} if {Some Xs {Equals nil}} then nil else {Map Xs Head} | {ZipN {Map Xs Tail}} end end
fun {Join Sep Xs} {FoldR Xs fun {$ X Z} {Append X Sep|Z} end nil} end
fun {Equals C} fun {$ X} X == C end end
fun {Head X|_} X end
fun {Tail _|Xr} Xr end
in
{System.showInfo {CommonPrefix &/ ["/home/user1/tmp/coverage/test" "/home/user1/tmp/covert/operator" "/home/user1/tmp/coven/members"]}}</lang>
PARI/GP
<lang parigp>cdp(v)={
my(s=""); v=apply(t->Vec(t),v); for(i=1,vecmin(apply(length,v)), for(j=2,#v, if(v[j][i]!=v[1][i],return(s))); if(i>1&v[1][i]=="/",s=concat(vecextract(v[1],1<<(i-1)-1)) ) ); if(vecmax(apply(length,v))==vecmin(apply(length,v)),concat(v[1]),s)
}; cdp(["/home/user1/tmp/coverage/test","/home/user1/tmp/covert/operator","/home/user1/tmp/coven/members"])</lang>
Perl
Assuming all paths begin at root.
<lang Perl>use List::Util qw(max reduce); sub compath {
my ($sep, @paths, %hash) = @_; # Tokenize and tally subpaths foreach (@paths) { my @tok = split $sep, substr($_,1); ++$hash{join $sep, @tok[0..$_]} for (0..$#tok); } # Return max length subpath or null my $max = max values %hash; return unless $max == @paths; my @res = grep {$hash{$_} == $max} keys %hash; return $sep . reduce { length $a > length $b ? $a : $b } @res;
}
- Test and display
my @paths = qw(/home/user1/tmp/coverage/test
/home/user1/tmp/covert/operator /home/user1/tmp/coven/members);
print compath('/', @paths), "\n";</lang>
Output:
/home/user1/tmp
Perl 6
<lang Perl 6>my $sep = '/'; my @dirs = </home/user1/tmp/coverage/test
/home/user1/tmp/covert/operator /home/user1/tmp/coven/members>;
my @comps = @dirs.map: { [ .comb(/ $sep [ <!before $sep> . ]* /) ] };
my $prefix = ;
while all(@comps[*]»[0]) eq @comps[0][0] {
$prefix ~= @comps[0][0] // last; @comps».shift;
}
say "The longest common path is $prefix"; </lang> Output:
The longest common path is /home/user1/tmp
If you'd prefer a pure FP solution without side effects, you can use this: <lang perl6>my $sep := '/'; my @dirs := </home/user1/tmp/coverage/test
/home/user1/tmp/covert/operator /home/user1/tmp/coven/members>;
my @comps := @dirs.map: { [ .comb(/ $sep [ <!before $sep> . ]* /) ] };
say "The longest common path is ",
gather for 0..* -> $column { last unless all(@comps[*]»[$column]) eq @comps[0][$column]; take @comps[0][$column] // last; }</lang>
PHP
<lang php><?php
/*
This works with dirs and files in any number of combinations.
- /
function _commonPath($dirList) { $arr = array(); foreach($dirList as $i => $path) { $dirList[$i] = explode('/', $path); unset($dirList[$i][0]);
$arr[$i] = count($dirList[$i]); }
$min = min($arr);
for($i = 0; $i < count($dirList); $i++) { while(count($dirList[$i]) > $min) { array_pop($dirList[$i]); }
$dirList[$i] = '/' . implode('/' , $dirList[$i]); }
$dirList = array_unique($dirList); while(count($dirList) !== 1) { $dirList = array_map('dirname', $dirList); $dirList = array_unique($dirList); } reset($dirList);
return current($dirList); }
/* TEST */
$dirs = array(
'/home/user1/tmp/coverage/test', '/home/user1/tmp/covert/operator', '/home/user1/tmp/coven/members',
);
if('/home/user1/tmp' !== common_path($dirs))
{
echo 'test fail';
} else {
echo 'test success';
}
?></lang>
PicoLisp
<lang PicoLisp>(de commonPath (Lst Chr)
(glue Chr (make (apply find (mapcar '((L) (split (chop L) Chr)) Lst) '(@ (or (pass <>) (nil (link (next))))) ) ) ) )</lang>
Output:
(commonPath (quote "/home/user1/tmp/coverage/test" "/home/user1/tmp/covert/operator" "/home/user1/tmp/coven/members" ) "/" ) -> "/home/user1/tmp"
Pike
<lang Pike>array paths = ({ "/home/user1/tmp/coverage/test",
"/home/user1/tmp/covert/operator", "/home/user1/tmp/coven/members" });
// append a / to each entry, so that a path like "/home/user1/tmp" will be recognized as a prefix // without it the prefix would end up being "/home/user1/" paths = paths[*]+"/";
string cp = String.common_prefix(paths); cp = cp[..sizeof(cp)-search(reverse(cp), "/")-2]; Result: "/home/user1/tmp"</lang>
PowerShell
<lang PowerShell># Find Common Directory Path
- Input is an array of strings holding the paths
function Get-CommonDirectoryPath($paths){
# Convert each path into array of tokens (i.e. convert array into jagged array) for($i=0; $i -lt $paths.Count; $i++) { $paths[$i] = ($paths[$i].TrimStart('/').Split('/')) }
# Loop through tokens $c = -1 $found = $false do { # Do Until loop used to handle paths with different number of directories $t = $paths[0][++$c] for($r = 1; $r -lt $paths.Count; $r++) { if ($t -ne $paths[$r][$c]) { $found=$true; break } } } until ($found)
# Return the answer for($i=0; $i -lt $c; $i++) {$s += "/"+$paths[0][$i]} return $s
}
- Main Entry Point
"The common directory path is " + (Get-CommonDirectoryPath ("/home/user1/tmp/coverage/test", "/home/user1/tmp/covert/operator", "/home/user1/tmp/coven/members"))</lang>
Output: <lang>The common directory path is /home/user1/tmp</lang>
PureBasic
PureBasic don't have a path comparator directly but instead have powerful string tools.
Simply by checking the catalog names until they mismatch and add up the correct parts, the task is accomplished. <lang PureBasic>Procedure.s CommonPath(Array InPaths.s(1),separator.s="/")
Protected SOut$="" Protected i, j, toggle If ArraySize(InPaths())=0 ProcedureReturn InPaths(0) ; Special case, only one path EndIf Repeat i+1 toggle=#False For j=1 To ArraySize(InPaths()) If (StringField(InPaths(j-1),i,separator)=StringField(InPaths(j),i,separator)) If Not toggle SOut$+StringField(InPaths(j-1),i,separator)+separator toggle=#True EndIf Else ProcedureReturn SOut$ EndIf Next ForEver
EndProcedure</lang>
Example of implementation <lang PureBasic>Dim t.s(2) t(0)="/home/user1/tmp/coverage/test" t(1)="/home/user1/tmp/covert/operator" t(2)="/home/user1/tmp/coven/members"
Debug CommonPath(t(),"/"))</lang>
Python
The Python os.path.commonprefix function is broken as it returns common characters that may not form a valid directory path: <lang python>>>> import os >>> os.path.commonprefix(['/home/user1/tmp/coverage/test',
'/home/user1/tmp/covert/operator', '/home/user1/tmp/coven/members'])
'/home/user1/tmp/cove'</lang>
This result can be fixed: <lang python>>>> def commonprefix(*args, sep='/'): return os.path.commonprefix(*args).rpartition(sep)[0]
>>> commonprefix(['/home/user1/tmp/coverage/test',
'/home/user1/tmp/covert/operator', '/home/user1/tmp/coven/members'])
'/home/user1/tmp'</lang>
But it may be better to not rely on the faulty implementation at all: <lang python>>>> from itertools import takewhile >>> def allnamesequal(name): return all(n==name[0] for n in name[1:])
>>> def commonprefix(paths, sep='/'): bydirectorylevels = zip(*[p.split(sep) for p in paths]) return sep.join(x[0] for x in takewhile(allnamesequal, bydirectorylevels))
>>> commonprefix(['/home/user1/tmp/coverage/test',
'/home/user1/tmp/covert/operator', '/home/user1/tmp/coven/members'])
'/home/user1/tmp' >>> # And also >>> commonprefix(['/home/user1/tmp', '/home/user1/tmp/coverage/test',
'/home/user1/tmp/covert/operator', '/home/user1/tmp/coven/members'])
'/home/user1/tmp' >>> </lang>
R
<lang r> get_common_dir <- function(paths, delim = "/") {
path_chunks <- strsplit(paths, delim) i <- 1 repeat({ current_chunk <- sapply(path_chunks, function(x) x[i]) if(any(current_chunk != current_chunk[1])) break i <- i + 1 }) paste(path_chunks1[seq_len(i - 1)], collapse = delim)
}
- Example Usage:
paths <- c(
'/home/user1/tmp/coverage/test', '/home/user1/tmp/covert/operator', '/home/user1/tmp/coven/members')
get_common_dir(paths) # "/home/user1/tmp"
</lang>
Ruby
Uses the standard library abbrev
module: Given a set of strings, calculate the set of unambiguous abbreviations for those strings, and return a hash where the keys are all the possible abbreviations and the values are the full strings.
<lang ruby>require 'abbrev'
dirs = %w( /home/user1/tmp/coverage/test /home/user1/tmp/covert/operator /home/user1/tmp/coven/members )
common_prefix = dirs.abbrev.keys.min_by {|key| key.length}.chop # => "/home/user1/tmp/cove" common_directory = common_prefix.sub(%r{/[^/]*$}, ) # => "/home/user1/tmp"</lang>
Implementing without that module: <lang ruby>separator = '/' paths = dirs.collect {|dir| dir.split(separator)} uncommon_idx = paths.transpose.each_with_index.find {|dirnames, idx| dirnames.uniq.length > 1}.last common_directory = paths[0][0 ... uncommon_idx].join(separator) # => "/home/user1/tmp"</lang>
Run BASIC
<lang runbasic>' ------------------------------------------
' Find common directory to all directories
' and directories common with other Paths
' ------------------------------------------
print word$(word$(httpget$("http://tycho.usno.navy.mil/cgi-bin/timer.pl"),1,"UTC"),2,"
") ' Universal time
dim path$(20) path$(1) = "/home/user1/tmp/coverage/test" path$(2) = "/home/user1/tmp/covert/operator" path$(3) = "/home/user1/tmp/coven/members"
path$(4) = "/home/user1/tmp1/coverage/test" path$(5) = "/home/user1/tmp1/covert/operator" path$(6) = "/home/user1/tmp1/coven/members"
path$(7) = "/home/user1/tmp2/coverage/test" path$(8) = "/home/user1/tmp2/covert/operator" path$(9) = "/home/user1/tmp2/coven/members"
path$(10) = "/home/user1/tmp3/coverage/test" path$(11) = "/home/user1/tmp3/covert/operator" path$(12) = "/home/user1/tmp3/coven/members"
sqliteconnect #mem, ":memory:"
- mem execute("CREATE TABLE dirTree (seq,pos,dir)")
for i = 1 to 12 j = 1 [loop] j = instr(path$(i),"/",j + 1) if j > 0 then dir$ = mid$(path$(i),1,j) mem$ = "INSERT INTO dirTree VALUES (";i;",";j;",'";dir$;"')" #mem execute(mem$) goto [loop] end if next i
mem$ = "SELECT dir FROM dirTree GROUP BY dir HAVING count(*) = pos ORDER BY pos desc LIMIT 1"
- mem execute(mem$)
rows = #mem ROWCOUNT() 'Get the number of rows if rows > 0 then #row = #mem #nextrow() print "====== Largest Directory Common to all Paths =========" print #row dir$()
else
print "No common Directory" end if
html "
"
print "========= Common paths ================"
mem$ = "SELECT t.seq as seq,t.pos as pos,t.dir as dir,t1.seq as t1Seq ,t1.dir as t1Dir FROM dirTree as t JOIN dirTree as t1 ON t1.dir = t.dir AND t1.seq > t.seq GROUP BY t.dir,t1.seq"
html "
"- mem execute(mem$)
WHILE #mem hasanswer() #row = #mem #nextrow() seq = #row seq() t1Seq = #row t1Seq() pos = #row pos() dir$ = #row dir$() t1Dir$ = #row t1Dir$()
html "" html "" html "" html "" html "" html "" html "" WEND html "Seq | Path | Common Dir | Seq | With Path |
";seq;" | ";path$(seq);" | ";dir$;" | ";t1Seq;" | ";path$(t1Seq);" |
"
wait
end</lang>
========= Common paths ================
shows only the first few common paths..
Seq | Path | Common Dir | Seq | With Path |
1 | /home/user1/tmp/coverage/test | /home/ | 2 | /home/user1/tmp/covert/operator |
2 | /home/user1/tmp/covert/operator | /home/ | 3 | /home/user1/tmp/coven/members |
3 | /home/user1/tmp/coven/members | /home/ | 4 | /home/user1/tmp1/coverage/test |
4 | /home/user1/tmp1/coverage/test | /home/ | 5 | /home/user1/tmp1/covert/operator |
5 | /home/user1/tmp1/covert/operator | /home/ | 6 | /home/user1/tmp1/coven/members |
6 | /home/user1/tmp1/coven/members | /home/ | 7 | /home/user1/tmp2/coverage/test |
7 | /home/user1/tmp2/coverage/test | /home/ | 8 | /home/user1/tmp2/covert/operator |
8 | /home/user1/tmp2/covert/operator | /home/ | 9 | /home/user1/tmp2/coven/members |
9 | /home/user1/tmp2/coven/members | /home/ | 10 | /home/user1/tmp3/coverage/test |
10 | /home/user1/tmp3/coverage/test | /home/ | 11 | /home/user1/tmp3/covert/operator |
11 | /home/user1/tmp3/covert/operator | /home/ | 12 | /home/user1/tmp3/coven/members |
1 | /home/user1/tmp/coverage/test | /home/user1/ | 2 | /home/user1/tmp/covert/operator |
2 | /home/user1/tmp/covert/operator | /home/user1/ | 3 | /home/user1/tmp/coven/members |
3 | /home/user1/tmp/coven/members | /home/user1/ | 4 | /home/user1/tmp1/coverage/test |
4 | /home/user1/tmp1/coverage/test | /home/user1/ | 5 | /home/user1/tmp1/covert/operator |
5 | /home/user1/tmp1/covert/operator | /home/user1/ | 6 | /home/user1/tmp1/coven/members |
6 | /home/user1/tmp1/coven/members | /home/user1/ | 7 | /home/user1/tmp2/coverage/test |
7 | /home/user1/tmp2/coverage/test | /home/user1/ | 8 | /home/user1/tmp2/covert/operator |
8 | /home/user1/tmp2/covert/operator | /home/user1/ | 9 | /home/user1/tmp2/coven/members |
9 | /home/user1/tmp2/coven/members | /home/user1/ | 10 | /home/user1/tmp3/coverage/test |
10 | /home/user1/tmp3/coverage/test | /home/user1/ | 11 | /home/user1/tmp3/covert/operator |
11 | /home/user1/tmp3/covert/operator | /home/user1/ | 12 | /home/user1/tmp3/coven/members |
1 | /home/user1/tmp/coverage/test | /home/user1/tmp/ | 2 | /home/user1/tmp/covert/operator |
2 | /home/user1/tmp/covert/operator | /home/user1/tmp/ | 3 | /home/user1/tmp/coven/members |
4 | /home/user1/tmp1/coverage/test | /home/user1/tmp1/ | 5 | /home/user1/tmp1/covert/operator |
5 | /home/user1/tmp1/covert/operator | /home/user1/tmp1/ | 6 | /home/user1/tmp1/coven/members |
7 | /home/user1/tmp2/coverage/test | /home/user1/tmp2/ | 8 | /home/user1/tmp2/covert/operator |
8 | /home/user1/tmp2/covert/operator | /home/user1/tmp2/ | 9 | /home/user1/tmp2/coven/members |
10 | /home/user1/tmp3/coverage/test | /home/user1/tmp3/ | 11 | /home/user1/tmp3/covert/operator |
11 | /home/user1/tmp3/covert/operator | /home/user1/tmp3/ | 12 | /home/user1/tmp3/coven/members |
Seed7
Seed7 has a standard path representation:
- The slash ('/') is used as path delimiter.
- Drive letters are not allowed, but there is a solution to replace them.
- Except for the path "/" a standard path is not allowed to end with a slash.
Therefore Seed7 programs do not need to consider varying path delimiters, but they need to make sure that a path does not end with a slash.
<lang seed7>$ include "seed7_05.s7i";
const func integer: commonLen (in array string: names, in char: sep) is func
result var integer: result is -1; local var integer: index is 0; var integer: pos is 1; begin if length(names) <> 0 then repeat for index range 1 to length(names) do if pos > length(names[index]) or names[index][pos] <> names[1][pos] then decr(pos); while pos >= 1 and names[1][pos] <> sep do decr(pos); end while; if pos > 1 then decr(pos); end if; result := pos; end if; end for; incr(pos); until result <> -1; end if; end func;
const proc: main is func
local var integer: length is 0; const array string: names is [] ("/home/user1/tmp/coverage/test", "/home/user1/tmp/covert/operator", "/home/user1/tmp/coven/members") begin length := commonLen(names, '/'); if length = 0 then writeln("No common path"); else writeln("Common path: " <& names[1][.. length]); end if; end func;</lang>
Output:
Common path: /home/user1/tmp
Tcl
<lang tcl>package require Tcl 8.5 proc pop {varname} {
upvar 1 $varname var set var [lassign $var head] return $head
}
proc common_prefix {dirs {separator "/"}} {
set parts [split [pop dirs] $separator] while {[llength $dirs]} { set r {} foreach cmp $parts elt [split [pop dirs] $separator] { if {$cmp ne $elt} break lappend r $cmp } set parts $r } return [join $parts $separator]
}</lang>
% common_prefix {/home/user1/tmp/coverage/test /home/user1/tmp/covert/operator /home/user1/tmp/coven/members} /home/user1/tmp
TUSCRIPT
<lang tuscript> $$ MODE TUSCRIPT common="" dir1="/home/user1/tmp/coverage/test" dir2="/home/user1/tmp/covert/operator" dir3="/home/user1/tmp/coven/members" dir1=SPLIT (dir1,":/:"),dir2=SPLIT (dir2,":/:"), dir3=SPLIT (dir3,":/:") LOOP d1=dir1,d2=dir2,d3=dir3
IF (d1==d2,d3) THEN common=APPEND(common,d1,"/") ELSE PRINT common EXIT ENDIF
ENDLOOP </lang> Output:
/home/user1/tmp/
Ursala
The algorithm is to lex the paths into component directory names, and then find the greatest common prefix of those. <lang Ursala>#import std
comdir"s" "p" = mat"s" reduce(gcp,0) (map sep "s") "p"</lang>
where "s"
is a dummy variable representing the separator, "p"
is a dummy variable representing the list of paths, and
sep
is second order function in the standard library that takes a separator character and returns a lexer mapping a string containing the separator to a list of the substrings found between occurrences of itmap
is the conventional mapping combinator, which takes a function operating on items of a list to a function operating pointwise on a whole listgcp
is a polymorphic greatest-common-prefix library function working on pairs of strings or lists of any typereduce
is the standard functional programming reduction combinator, which cumulatively applies a binary operator to a list of operands given the operator and the vacuous case resultmat
is a second order function in the standard library that takes a separator character and returns a function that flattens a list of strings into a single string with copies of the separator inserted between them
Here is a version using operators instead of mnemonics for map
and reduce
.
<lang Ursala>comdir"s" "p" = mat"s" gcp:-0 sep"s"* "p"</lang>
Here is one in partly point-free form, using the composition operator (+
).
<lang Ursala>comdir"s" = mat"s"+ gcp:-0+ sep"s"*</lang>
Here it is in point-free form.
<lang Ursala>comdir = +^/mat gcp:-0++ *+ sep</lang>
test program:
<lang Ursala>#cast %s
test =
comdir`/ <
'/home/user1/tmp/coverage/test', '/home/user1/tmp/covert/operator', '/home/user1/tmp/coven/members'></lang>
output:
'/home/user1/tmp'
- Programming Tasks
- Solutions by Programming Task
- Ada
- ALGOL 68
- AutoHotkey
- AWK
- BASIC
- BBC BASIC
- C
- C++
- Clojure
- C sharp
- D
- Factor
- Go
- Groovy
- GW-BASIC
- Haskell
- HicEst
- Icon
- Unicon
- J
- Java
- Liberty BASIC
- Mathematica
- MUMPS
- OCaml
- OpenEdge/Progress
- Oz
- PARI/GP
- Perl
- Perl 6
- PHP
- PicoLisp
- Pike
- PowerShell
- PureBasic
- Python
- R
- Ruby
- Run BASIC
- Seed7
- Tcl
- TUSCRIPT
- Ursala
- GUISS/Omit