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