/** * 2018/2019 Regional ICPC * Problem ? * Orphan Backups * * @author M. K. Furon * @version 1.0 * @since 2018-10-18 */ import java.io.*; import java.util.*; class Backupfile implements Comparable { // Class for file names and base image names. This is done so the // file name sort can be done on base image names. String filename; String imagename; Backupfile (String inputname) { // Extract the base image name from a file name. int underpos; filename = inputname; underpos = filename.lastIndexOf ('_'); underpos = filename.lastIndexOf ('_', (underpos - 1)); imagename = filename.substring (0, underpos); } public int compareTo (Backupfile secondfile) { return ((this.imagename).compareTo (secondfile.imagename)); } } class orphanbackups { public static void main (String args[]) throws IOException { int comparison, filecount, i, indexcount, j; String lineimage; ArrayList backupindex = new ArrayList (); ArrayList filelist = new ArrayList (); ArrayList orphanfile = new ArrayList (); ArrayList orphanindex = new ArrayList (); BufferedReader stdin = new BufferedReader (new InputStreamReader (System.in)); // Load the list of backup catalog entries. lineimage = stdin.readLine (); while (lineimage.length () > 0) { backupindex.add (lineimage); lineimage = stdin.readLine (); } // The remaining entries are the file names. These are created as // "Backupfile" entries that contain both the full file name and // the base name of the backup image. while ((lineimage = stdin.readLine ()) != null) filelist.add (new Backupfile (lineimage)); // Sort the backup index into ascending order. backupindex.sort (Comparator.naturalOrder ()); // Sort the file list into ascending order. This has to be sorted // by the base name to deal with conditions where the base name // might end in an underscore followed by digits. Collections.sort (filelist); // The backup index and the file list are both now in natural // order. Check each entry in the backup index against the file // list. Build two lists of mis-matches, one for index entries // with no files, the other for files with no index entry. indexcount = backupindex.size (); filecount = filelist.size (); String backupentry[] = new String[indexcount]; Backupfile fileentry[] = new Backupfile[filecount]; backupentry = backupindex.toArray (backupentry); fileentry = filelist.toArray (fileentry); i = j = 0; while ((i < indexcount) && (j < filecount)) { // Compare the sorted index and file name lists. comparison = backupentry[i].compareTo (fileentry[j].imagename); if (comparison < 0) // If index entry comes first orphanindex.add (backupentry[i++]); else if (comparison > 0) // If file name comes first orphanfile.add (fileentry[j++].filename); else { // The two entries are equal. j++; while ((j < filecount) && (backupentry[i].compareTo (fileentry[j].imagename) == 0)) j++; i++; } } // We have reached the end of at least one list. Anything remaining // in the other list is an orphan. while (i < indexcount) orphanindex.add (backupentry[i++]); while (j < filecount) orphanfile.add (fileentry[j++].filename); // Print the results. if (orphanfile.size () > 0) { for (String orphan: orphanfile) { System.out.print ("F "); System.out.println (orphan); } } if (orphanindex.size () > 0) { for (String orphan: orphanindex) { System.out.print ("I "); System.out.println (orphan); } } if ((orphanindex.size () == 0) && (orphanfile.size () == 0)) System.out.println ("No mismatches."); return; } }