import java.util.List;
/** This will create a list of contacts and then proceed to search for contacts that have matching
 * criteria using first a linear search algorithm and then a binary search algorithm.
 * Then we'll discuss the advantages and limitations of each search algorithm.
 * 
 * This class uses the ContactLib library to quickly generate large lists of contacts in
 * alphabetical (ascending or descending) or unsorted (random) order.
 * @author Braskin, Aaron
 * @version April 8th, 2015
 */
public class SearchRunner {
	public static void main(String[] args) {
		List<Contact> people=ContactLib.makeContacts(ContactLib.ORDER_DESCENDING, 20);
		printContacts("Contacts:",people);
		String search="Yanofsky, Milan";
		linearSearch(search,people);
		binarySearch(search,people);
	}
	public static int binarySearch(String findName, List<Contact> contacts) {
		int matchingIndex=-1, lowIndex=0, highIndex=contacts.size()-1;
		int iterations=0;
		while(lowIndex<=highIndex) {
			iterations++;
			matchingIndex=(highIndex-lowIndex)/2+lowIndex; // Picking the halfway-point between low and high indexes
			Contact aPerson=contacts.get(matchingIndex);
			String lastFirst=aPerson.getLastNameFirst();
			int compareResult=lastFirst.compareTo(findName);
			if (compareResult>0) {
				lowIndex=matchingIndex+1;
			} else if (compareResult<0) {
				highIndex=matchingIndex-1;
			} else {
				break;
			}
		}
		if (lowIndex>highIndex) matchingIndex=-1;
		System.out.println("Binary search for "+findName);
		if (matchingIndex==-1) {
			System.out.println("found no match");
		} else {
			System.out.println("found "+contacts.get(matchingIndex)+"\nAt index "+matchingIndex);
		}
		System.out.println("The search took "+iterations+" iterations");
		return matchingIndex;
	}
	public static int linearSearch(String findName, List<Contact> contacts) {
		int matchingIndex=-1;
		int iterations=0;
		for (int i=0; i<contacts.size(); i++) {
			iterations++;
			Contact aPerson=contacts.get(i);
			String lastFirst=aPerson.getLastNameFirst();
			if (lastFirst.equals(findName)) {
				matchingIndex=i;
				i=contacts.size();
			}
		}
		System.out.println("Linear search for "+findName);
		if (matchingIndex==-1) {
			System.out.println("found no match");
		} else {
			System.out.println("found "+contacts.get(matchingIndex)+"\nAt index "+matchingIndex);
		}
		System.out.println("The search took "+iterations+" iterations");
		return matchingIndex;
	}
	public static void printContacts(String title, List<Contact> contacts) {
		System.out.println(title);
		for (int i=0; i<contacts.size(); i++) {
			System.out.println("["+i+"]\t"+contacts.get(i).getLastNameFirst());
		}
	}
}