Add searchable android.DirectorySortedPaths
Add an android.DirectorySortedPaths that stores paths sorted such
that all paths in a directory including subdirectories are in a
contiguous subslice. This will allow efficient O(log(N)) finding
of all paths in a directory using a binary search on the directory
prefix.
Test: TestDirectorySortedPaths in paths_test.go
Change-Id: I5a06a89351ae06e88c06526be54a6b79075361b7
diff --git a/android/paths_test.go b/android/paths_test.go
index 248f4d4..82ae4dc 100644
--- a/android/paths_test.go
+++ b/android/paths_test.go
@@ -340,3 +340,75 @@
})
}
}
+
+func TestDirectorySortedPaths(t *testing.T) {
+ makePaths := func() Paths {
+ return Paths{
+ PathForTesting("a.txt"),
+ PathForTesting("a/txt"),
+ PathForTesting("a/b/c"),
+ PathForTesting("a/b/d"),
+ PathForTesting("b"),
+ PathForTesting("b/b.txt"),
+ PathForTesting("a/a.txt"),
+ }
+ }
+
+ expected := []string{
+ "a.txt",
+ "a/a.txt",
+ "a/b/c",
+ "a/b/d",
+ "a/txt",
+ "b",
+ "b/b.txt",
+ }
+
+ paths := makePaths()
+ reversePaths := make(Paths, len(paths))
+ for i, v := range paths {
+ reversePaths[len(paths)-i-1] = v
+ }
+
+ sortedPaths := PathsToDirectorySortedPaths(paths)
+ reverseSortedPaths := PathsToDirectorySortedPaths(reversePaths)
+
+ if !reflect.DeepEqual(Paths(sortedPaths).Strings(), expected) {
+ t.Fatalf("sorted paths:\n %#v\n != \n %#v", paths.Strings(), expected)
+ }
+
+ if !reflect.DeepEqual(Paths(reverseSortedPaths).Strings(), expected) {
+ t.Fatalf("sorted reversed paths:\n %#v\n !=\n %#v", reversePaths.Strings(), expected)
+ }
+
+ expectedA := []string{
+ "a/a.txt",
+ "a/b/c",
+ "a/b/d",
+ "a/txt",
+ }
+
+ inA := sortedPaths.PathsInDirectory("a")
+ if !reflect.DeepEqual(inA.Strings(), expectedA) {
+ t.Errorf("FilesInDirectory(a):\n %#v\n != \n %#v", inA.Strings(), expectedA)
+ }
+
+ expectedA_B := []string{
+ "a/b/c",
+ "a/b/d",
+ }
+
+ inA_B := sortedPaths.PathsInDirectory("a/b")
+ if !reflect.DeepEqual(inA_B.Strings(), expectedA_B) {
+ t.Errorf("FilesInDirectory(a/b):\n %#v\n != \n %#v", inA_B.Strings(), expectedA_B)
+ }
+
+ expectedB := []string{
+ "b/b.txt",
+ }
+
+ inB := sortedPaths.PathsInDirectory("b")
+ if !reflect.DeepEqual(inB.Strings(), expectedB) {
+ t.Errorf("FilesInDirectory(b):\n %#v\n != \n %#v", inA.Strings(), expectedA)
+ }
+}