Find common directory path

From Rosetta Code
Revision as of 13:27, 18 August 2011 by 84.112.82.23 (talk) (Move GW-Basic example)
Task
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

Works with: ALGOL 68 version Revision 1 - no extensions to language used
Works with: ALGOL 68G version Any - tested with release 1.18.0-9h.tiny
Works with: ELLA ALGOL 68 version Any (with appropriate job cards) - tested with release 1.8-8d

<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]

);

  1. 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

);

  1. 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], ...,

  1. 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

Works with: QuickBASIC version 7
Works with: FreeBASIC

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>

  1. include <iostream>
  2. include <string>
  3. 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

Works with: GW-BASIC
Works with: Chipmunk 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

Works with: Java version 1.5+

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>

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)

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>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 = (reverse sort values %hash)[0];
   return  unless $max == @paths;
   my @res =  grep {$hash{$_} == $max} keys %hash;
   return $sep . (sort {length($b) <=> length($a)} @res)[0];

}

  1. 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

This example is incorrect. Please fix the code and remove this message.

Details: It only works when all paths contain the same number of directories.

<lang php><?php

function common_path($dirList) { 

 $dirList = array_unique($dirList);
 while (1 !== count($dirList)) {
   $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"

PowerShell

<lang PowerShell># Find Common Directory Path

  1. 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

}

  1. 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)

}

  1. 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>

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 it
  • map is the conventional mapping combinator, which takes a function operating on items of a list to a function operating pointwise on a whole list
  • gcp is a polymorphic greatest-common-prefix library function working on pairs of strings or lists of any type
  • reduce 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 result
  • mat 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'
Retrieved from "https://rosettacode.org/wiki/Find_common_directory_path?oldid=143976"