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.util.ArrayList; 30 import java.util.List; 31 32 /** 33 * Utilities for dealing with text file contents. 34 */ 35 class Util { Util()36 private Util() { 37 } 38 readLines(Reader reader)39 public static Lines readLines(Reader reader) throws IOException { 40 List<String> result = new ArrayList<>(); 41 BufferedReader br = (reader instanceof BufferedReader) 42 ? (BufferedReader) reader : new BufferedReader(reader); 43 String line; 44 while ((line = br.readLine()) != null) { 45 result.add(line); 46 } 47 return new Lines(result); 48 } 49 readLines(Path path)50 public static Lines readLines(Path path) throws IOException { 51 try (Reader reader = new FileReader(path.toFile())) { 52 return readLines(reader); 53 } 54 } 55 writeLines(Path path, Lines lines)56 public static void writeLines(Path path, Lines lines) throws IOException { 57 try (PrintStream printStream = new PrintStream(path.toFile())) { 58 for (String line : lines) { 59 printStream.println(line); 60 } 61 } 62 } 63 64 /** 65 * Computes the edit distance of two lists, i.e. the smallest number of list items to delete, 66 * insert or replace that would transform the content of one list into the other. 67 */ editDistance(List<T> a, List<T> b)68 public static <T> int editDistance(List<T> a, List<T> b) { 69 if (a.equals(b)) { 70 return 0; 71 } 72 int numB = b.size(); 73 int[] prevCost = new int[numB + 1]; 74 for (int i = 0; i <= numB; i++) { 75 prevCost[i] = i; 76 } 77 int[] curCost = new int[numB + 1]; 78 for (int endA = 1; endA <= a.size(); endA++) { 79 // For each valid index i, prevCost[i] is the edit distance between 80 // a.subList(0, endA-1) and b.sublist(0, i). 81 // We now calculate curCost[end_b] as the edit distance between 82 // a.subList(0, endA) and b.subList(0, endB) 83 curCost[0] = endA; 84 for (int endB = 1; endB <= numB; endB++) { 85 boolean endsMatch = a.get(endA - 1).equals(b.get(endB - 1)); 86 curCost[endB] = min( 87 curCost[endB - 1] + 1, // append item from b 88 prevCost[endB] + 1, // append item from a 89 prevCost[endB - 1] + (endsMatch ? 0 : 1)); // match or replace item 90 } 91 int[] tmp = curCost; 92 curCost = prevCost; 93 prevCost = tmp; 94 } 95 return prevCost[numB]; 96 } 97 min(int a, int b, int c)98 private static int min(int a, int b, int c) { 99 if (a < b) { 100 return a < c ? a : c; 101 } else { 102 return b < c ? b : c; 103 } 104 } 105 106 } 107