Skip to content

Instantly share code, notes, and snippets.

@stanio
Created December 16, 2019 22:43
Show Gist options
  • Save stanio/59904a4ee5213c52647e11793fb54b3f to your computer and use it in GitHub Desktop.
Save stanio/59904a4ee5213c52647e11793fb54b3f to your computer and use it in GitHub Desktop.
Find the common base path of a list of file paths
//package ;
import java.nio.file.Path;
import java.nio.file.Paths;
import java.util.List;
/**
* @see <a href="https://www.geeksforgeeks.org/longest-common-prefix-using-binary-search/">Longest
* Common Prefix using Binary Search</a>
*/
public class BasePath {
private List<Path> list = new java.util.ArrayList<>();
private int minLength = Integer.MAX_VALUE;
public void add(String first, String... more) {
add(Paths.get(first, more));
}
public void add(Path path) {
list.add(path);
if (path.getNameCount() < minLength) {
minLength = path.getNameCount();
}
}
public String find() {
if (list.isEmpty()) {
return "";
}
Path[] paths = list.toArray(new Path[list.size()]);
int low = minLength, high = paths.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (startWith(paths, low, mid)) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return (low == 0) ? "" : paths[0].subpath(0, low).toString();
}
private static boolean startWith(Path[] paths, int start, int end) {
Path prefix = paths[0];
for (int i = 1, n = paths.length; i < n; i++) {
Path str = paths[i];
for (int j = start; j <= end; j++) {
if (!str.getName(j).equals(prefix.getName(j))) {
return false;
}
}
}
return true;
}
public void clear() {
list.clear();
minLength = Integer.MAX_VALUE;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment