import java.io.*; import java.util.Scanner; public class ListTester { public static void main(String[] args) { System.out.println("List tester."); // Make the list manager. ListMan lm1 = new ListMan(); lm1.setName("Magic Items"); lm1.setDesc("These are some of my favorite things."); final String fileName = "magicitems.txt"; readMagicItemsFromFileToList(fileName, lm1); // Display the list of items. // System.out.println(lm1.toString()); // Declare an array for the items. ListItem[] items = new ListItem[lm1.getLength()]; readMagicItemsFromFileToArray(fileName, items); // Display the array of items. System.out.println("Items in the array BEFORE sorting:"); for (int i = 0; i < items.length; i++) { if (items[i] != null) { System.out.println(items[i].toString()); } } selectionSort(items); System.out.println("Items in the array AFTER sorting:"); for (int i = 0; i < items.length; i++) { if (items[i] != null) { System.out.println(items[i].toString()); } } // Ask player for an item. Scanner inputReader = new Scanner(System.in); System.out.print("What item would you like? "); String targetItem = new String(); targetItem = inputReader.nextLine(); System.out.println(); ListItem li = new ListItem(); li = sequentialSearchArray(items, targetItem); li = binarySearchArray(items, targetItem); } // // Private // private static ListItem sequentialSearchArray(ListItem[] items, String target) { ListItem retVal = null; System.out.println("Sequential Searching for " + target + "."); int counter = 0; ListItem currentItem = new ListItem(); boolean isFound = false; while ( (!isFound) && (counter < items.length) ) { currentItem = items[counter]; if (currentItem.getName().equalsIgnoreCase(target)) { // We found it! isFound = true; retVal = currentItem; } else { // Keep looking. counter = counter +1; } } if (isFound) { System.out.println("Found " + target + " after " + counter + " comparisons."); } else { System.out.println("Could not find " + target + " in " + counter + " comparisons."); } return retVal; } private static ListItem binarySearchArray(ListItem[] items, String target) { ListItem retVal = null; System.out.println("Binary Searching for " + target + "."); ListItem currentItem = new ListItem(); boolean isFound = false; int counter = 0; int low = 0; int high = items.length-1; // because 0-based arrays while ( (!isFound) && (low <= high)) { int mid = Math.round((high + low) / 2); currentItem = items[mid]; if (currentItem.getName().equalsIgnoreCase(target)) { // We found it! isFound = true; retVal = currentItem; } else { // Keep looking. counter++; if (currentItem.getName().compareToIgnoreCase(target) > 0) { // target is higher in the list than the currentItem (at mid) high = mid - 1; } else { // target is lower in the list than the currentItem (at mid) low = mid + 1; } } } if (isFound) { System.out.println("Found " + target + " after " + counter + " comparisons."); } else { System.out.println("Could not find " + target + " in " + counter + " comparisons."); } return retVal; } private static ListItem sequentialSearchList(ListMan lm, String target) { ListItem retVal = null; System.out.println("Searching for " + target + "."); int counter = 0; ListItem currentItem = new ListItem(); currentItem = lm.getHead(); boolean isFound = false; while ( (!isFound) && (currentItem != null) ) { counter = counter +1; if (currentItem.getName().equalsIgnoreCase(target)) { // We found it! isFound = true; retVal = currentItem; } else { // Keep looking. currentItem = currentItem.getNext(); } } if (isFound) { System.out.println("Found " + target + " after " + counter + " comparisons."); } else { System.out.println("Could not find " + target + " in " + counter + " comparisons."); } return retVal; } private static void readMagicItemsFromFileToList(String fileName, ListMan lm) { File myFile = new File(fileName); try { Scanner input = new Scanner(myFile); while (input.hasNext()) { // Read a line from the file. String itemName = input.nextLine(); // Construct a new list item and set its attributes. ListItem fileItem = new ListItem(); fileItem.setName(itemName); fileItem.setCost(Math.random() * 100); fileItem.setNext(null); // Still redundant. Still safe. // Add the newly constructed item to the list. lm.add(fileItem); } // Close the file. input.close(); } catch (FileNotFoundException ex) { System.out.println("File not found. " + ex.toString()); } } private static void readMagicItemsFromFileToArray(String fileName, ListItem[] items) { File myFile = new File(fileName); try { int itemCount = 0; Scanner input = new Scanner(myFile); while (input.hasNext() && itemCount < items.length) { // Read a line from the file. String itemName = input.nextLine(); // Construct a new list item and set its attributes. ListItem fileItem = new ListItem(); fileItem.setName(itemName); fileItem.setCost(Math.random() * 100); fileItem.setNext(null); // Still redundant. Still safe. // Add the newly constructed item to the array. items[itemCount] = fileItem; itemCount = itemCount + 1; } // Close the file. input.close(); } catch (FileNotFoundException ex) { System.out.println("File not found. " + ex.toString()); } } private static void selectionSort(ListItem[] items) { for (int pass = 0; pass < items.length-1; pass++) { // System.out.println(pass + "-" + items[pass]); int indexOfTarget = pass; int indexOfSmallest = indexOfTarget; for (int j = indexOfTarget+1; j < items.length; j++) { if (items[j].getName().compareToIgnoreCase(items[indexOfSmallest].getName()) < 0) { indexOfSmallest = j; } } ListItem temp = items[indexOfTarget]; items[indexOfTarget] = items[indexOfSmallest]; items[indexOfSmallest] = temp; } } }