CODEWITHSUNDEEP
javafile
Alex Spurling
Alex Spurling

Reputation: 55864

Find the longest Path common to two Paths in Java

If I have two Paths, how can I find the longest common Path of the two?

import java.nio.file.Path;
import java.nio.file.Paths;

Path common(Path pathA, Path pathB) {
    ...
}
...
common(Paths.get("/a/b/c/d/e"), Paths.get("/a/b/c/g/h"))

Expected output: 

Paths.get("/a/b/c")

Upvotes: 5

Views: 2068

Answers (6)

k314159
k314159

Reputation: 11110

Old question, but none of the answers seemed concise enough. Here's my one:

    public static Path common(Path a, Path b) {
        while (!a.startsWith(b))
            b = b.getParent();
        return b;
    }

Upvotes: 0

DuncG
DuncG

Reputation: 15136

Whatever the question, it's always fun trying to answer using streams:

public static Path commonPath(Path a, Path b) {
    Path other = b.normalize();
    return Stream.iterate(a.normalize(), Path::getParent)
        .takeWhile(Objects::nonNull)
        .filter(parent -> Stream.iterate(other, Path::getParent).takeWhile(Objects::nonNull)
                                .anyMatch(x -> Objects.equals(x, parent)))
        .findFirst().orElse(null);
}

This works on Windows / Linux, for example try the test data in @Michał Ziober answer. This just iterates up the parent hierarchy of first until it meets a parent of the other.

With the suggestion by Bass in comments, the common path check is more concise using the other version of Stream.iterate:

public static Path commonPath(Path a, Path b) {
    return Stream.iterate(a.normalize(), Objects::nonNull, Path::getParent)
        .filter(parent -> Stream.iterate(b.normalize(), Objects::nonNull, Path::getParent)
                                .anyMatch(parent::equals))
        .findFirst().orElse(null);
}

A small refactoring could pull out Stream.iterate(path.normalize(), Objects::nonNull, Path::getParent) to a utility method Stream<Path> parentsOf(Path path) as it is repeated twice above:

public static Path commonPath(Path a, Path b) {
    return parentsOf(a)
            .filter(parent -> parentsOf(b).anyMatch(parent::equals))
            .findFirst().orElse(null);
}
private static Stream<Path> parentsOf(Path a) {
    return Stream.iterate(a.normalize(), Objects::nonNull, Path::getParent);
}

Upvotes: 2

Bass
Bass

Reputation: 5318

While the answer by DuncG is definitely the most concise and probably the most efficient one, I'll add my solution, too.

Consider we have a function to transform a Path into a Stream of path entries:

@NonNull Stream<@NonNull Path> pathEntries(final @NonNull Path path) {
    return Stream.concat(Stream.ofNullable(path.getRoot()), StreamSupport.stream(path.spliterator(), false));
}

Now, consider we have another helper function that zips two streams together (e.g.: Streams.zip() from Guava):

<A, B, R> @NonNull Stream<R> zip(
        final @NonNull Stream<A> streamA,
        final @NonNull Stream<B> streamB,
        final BiFunction<? super A, ? super B, ? extends R> function
) {
    final Spliterator<A> splitrA = streamA.spliterator();
    final Spliterator<B> splitrB = streamB.spliterator();
    final int characteristics = splitrA.characteristics()
            & splitrB.characteristics()
            & (Spliterator.SIZED | Spliterator.ORDERED);
    final Iterator<A> itrA = Spliterators.iterator(splitrA);
    final Iterator<B> itrB = Spliterators.iterator(splitrB);
    return StreamSupport.stream(new AbstractSpliterator<R>(Math.min(splitrA.estimateSize(), splitrB.estimateSize()), characteristics) {
        @Override
        public boolean tryAdvance(final @NonNull Consumer<? super R> action) {
            if (itrA.hasNext() && itrB.hasNext()) {
                action.accept(function.apply(itrA.next(), itrB.next()));
                return true;
            }

            return false;
        }
    }, false)
            .onClose(streamA::close)
            .onClose(streamB::close);
}

Then, the solution will look like this:

@Nullable Path commonOrNull(final @NonNull Path left, final @NonNull Path right) {
    return zip(
            pathEntries(left.normalize()),
            pathEntries(right.normalize()),
            (l, r) -> l.equals(r) ? l : null
    )
            .takeWhile(Objects::nonNull)
            .reduce(Path::resolve)
            .orElse(null);
}

This will also work on Windows, returning null for any two paths that don't share a common file system root, like C:\foo and D:\foo.

Upvotes: 1

Michał Ziober
Michał Ziober

Reputation: 38655

We can generate all subpaths starting from the longest possible and check which two are equal:

private Path commonPath(Path path0, Path path1) {
    if (path0.equals(path1)) {
        return path0;
    }

    path0 = path0.normalize();
    path1 = path1.normalize();
    int minCount = Math.min(path0.getNameCount(), path1.getNameCount());
    for (int i = minCount; i > 0; i--) {
        Path sp0 = path0.subpath(0, i);
        if (sp0.equals(path1.subpath(0, i))) {
            String root = Objects.toString(path0.getRoot(), "");
            return Paths.get(root, sp0.toString());
        }
    }

    return path0.getRoot();
}

And usage:

Map<String, String> paths = new LinkedHashMap<>();
paths.put("/a/b/c", "/a/b/d");
paths.put("/a/", "/a/b/d");
paths.put("/f/b/c", "/a/b/d");
paths.put("/a/b/c/d/e", "/a/b/f/../c/g");
paths.put("C:/Winnt/System32", "C:/Winnt/System64");

paths.forEach((k, v) ->
        System.out.println(
                k + " = " + v + " => " + commonPath(Paths.get(k), Paths.get(v))));

Above code prints:

/a/b/c = /a/b/d => /a/b
/a/ = /a/b/d => /a
/f/b/c = /a/b/d => /
/a/b/c/d/e = /a/b/f/../c/g => /a/b/c
C:/Winnt/System32 = C:/Winnt/System64 => C:/Winnt

Upvotes: 2

mnesarco
mnesarco

Reputation: 2778

Try this simple idea

    Path a = Paths.get("a/b/c/d/e");
    Path b = Paths.get("a/b/c/g/h");

    // Normalize
    a = a.normalize();
    b = b.normalize();

    // Create common root
    Path common = null;
    if (a.isAbsolute() && b.isAbsolute() && a.getRoot().equals(b.getRoot())) {
            common = a.getRoot();
    }
    else if (!a.isAbsolute() && !b.isAbsolute()) {
            common = Paths.get("");
    }

    // Iterate from root until names differ
    if (common != null) {
            int n = Math.min(a.getNameCount(), b.getNameCount());
            for (int i=0; i<n; i++) {
                    if (a.getName(i).equals(b.getName(i))) {
                            common = common.resolve(a.getName(i));
                    }
                    else {
                            break;
                    }
            }
    }

    // Show
    System.out.println(common);

Upvotes: 3

Felk
Felk

Reputation: 8224

Path path1 = Paths.get("/a/b/c/d/e");
Path path2 = Paths.get("/a/b/c/g/h");

You can relativize the paths to one another:

Path relativePath = path1.relativize(path2).normalize();
// result: ../../g/h

and then go to the parent until the path ends in ..

while(relativePath != null && !relativePath.endsWith("..")) {
    relativePath = relativePath.getParent();
}
// result: ../.. (but may also be null)

the result can be applied back to any of the two paths:

Path result = path1.resolve(relativePath).normalize()
// result: /a/b/c

Upvotes: 5

Related Questions