1 /*
2  * Copyright (C) 2017 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 package libcore;
18 
19 import java.io.BufferedReader;
20 import java.io.BufferedWriter;
21 import java.io.FileReader;
22 import java.io.FileWriter;
23 import java.io.IOException;
24 import java.io.PrintStream;
25 import java.io.PrintWriter;
26 import java.io.Reader;
27 import java.io.Writer;
28 import java.nio.file.Path;
29 import java.nio.file.Paths;
30 import java.util.ArrayList;
31 import java.util.List;
32 
33 /**
34  * Utilities for dealing with text file contents.
35  */
36 class Util {
Util()37     private Util() {
38     }
39 
pathFromEnvOrThrow(String name)40     public static Path pathFromEnvOrThrow(String name) {
41         String envValue = getEnvOrThrow(name);
42         Path result = Paths.get(envValue);
43         if (!result.toFile().exists()) {
44             throw new IllegalArgumentException("Path not found: " + result);
45         }
46         return result;
47     }
48 
getEnvOrThrow(String name)49     private static String getEnvOrThrow(String name) {
50         String result = System.getenv(name);
51         if (result == null) {
52             throw new IllegalStateException("Environment variable undefined: " + name);
53         }
54         return result;
55     }
56 
readLines(Reader reader)57     public static Lines readLines(Reader reader) throws IOException {
58         List<String> result = new ArrayList<>();
59         BufferedReader br = (reader instanceof BufferedReader)
60                 ? (BufferedReader) reader : new BufferedReader(reader);
61         String line;
62         while ((line = br.readLine()) != null) {
63             result.add(line);
64         }
65         return new Lines(result);
66     }
67 
readLines(Path path)68     public static Lines readLines(Path path) throws IOException {
69         try (Reader reader = new FileReader(path.toFile())) {
70             return readLines(reader);
71         }
72     }
73 
writeLines(Path path, Lines lines)74     public static void writeLines(Path path, Lines lines) throws IOException {
75         try (PrintStream printStream = new PrintStream(path.toFile())) {
76             for (String line : lines) {
77                 printStream.println(line);
78             }
79         }
80     }
81 
82     /**
83      * Computes the edit distance of two lists, i.e. the smallest number of list items to delete,
84      * insert or replace that would transform the content of one list into the other.
85      */
editDistance(List<T> a, List<T> b)86     public static <T> int editDistance(List<T> a, List<T> b) {
87         if (a.equals(b)) {
88             return 0;
89         }
90         int numB = b.size();
91         int[] prevCost = new int[numB + 1];
92         for (int i = 0; i <= numB; i++) {
93             prevCost[i] = i;
94         }
95         int[] curCost = new int[numB + 1];
96         for (int endA = 1; endA <= a.size(); endA++) {
97             // For each valid index i, prevCost[i] is the edit distance between
98             // a.subList(0, endA-1) and b.sublist(0, i).
99             // We now calculate curCost[end_b] as the edit distance between
100             // a.subList(0, endA) and b.subList(0, endB)
101             curCost[0] = endA;
102             for (int endB = 1; endB <= numB; endB++) {
103                 boolean endsMatch = a.get(endA - 1).equals(b.get(endB - 1));
104                 curCost[endB] = min(
105                         curCost[endB - 1] + 1, // append item from b
106                         prevCost[endB] + 1, // append item from a
107                         prevCost[endB - 1] + (endsMatch ? 0 : 1)); // match or replace item
108             }
109             int[] tmp = curCost;
110             curCost = prevCost;
111             prevCost = tmp;
112         }
113         return prevCost[numB];
114     }
115 
min(int a, int b, int c)116     private static int min(int a, int b, int c) {
117         if (a < b) {
118             return a < c ? a : c;
119         } else {
120             return b < c ? b : c;
121         }
122     }
123 
124 }
125