/*
 * This class will be used to work with searching salaries
 * @author Jeff Borland(change)
 * @updated 3-22-2012
 */
import java.io.*;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
public class Passwords
{
	private String[] allPasswords = new String[200000];


	/*
	 * The constructor below will automatically read in all of the passwords
	 */
	public Passwords() 
	{
		Scanner scan = null;
		//To reset your scanner:
		try
		{
			scan=new Scanner(new File("outSorted.txt"));
		}
		catch (IOException e){}
		int i=0;
		while (scan.hasNext() && i<200000)
		{
			String theLine=scan.nextLine(); //This reads in the next password                                       
			allPasswords[i]=theLine;
			i++;                       
		}


	}

	//using linear search, finds location of first time password was used
	public int linearSearch(String password)
	{
		for (int i=0;i<allPasswords.length; i++)
			if (allPasswords[i].equals(password))
				return i;
		return -1;
	}

	//using binary search, finds location of first time password was used
	public int binarySearch(String password)
	{
		//this is just like our Binary search from yesterday
		//but to compare we cant use < or > on strings
		//but we can use compareTo
		int low=0;
		int high=(allPasswords.length)-1;
		while (low<=high)
		{
			int mid=(low+high)/2;
			if(allPasswords[mid].compareTo(password)<0)
				low=mid+1;
			else if(allPasswords[mid].compareTo(password)>0)
				high=mid-1;
			else
			{
				//we found it, but I asked for you to return the location 
				// of the FIRST TIME it is in the list
				//so I will keep moving mid forward until it is not
				//pointing at password
				while (allPasswords[mid-1].equals(password))
					mid--;
				return mid;
			}
		}
		return -1;
	}  

	//using binary search, finds how many times password has been used
	public int findHowMany (String yourPassword)
	{
		//first I find when was the first time it occured
		int firstTime=binarySearch(yourPassword);
		//if yourPassword is not there return 0
		if (firstTime==-1)
			return 0;
		//otherwise lets keep track of how many times its there 
		int counter=1;  
		while (allPasswords[firstTime+counter].equals(yourPassword))			
			counter++;
		return counter;

	}


	//finds all passwords that have the word in them. 
	public void findAllDerivatives(String word)
	{
		//the only way to do this is with a linear search
		//we are going to look at every password and see
		//if word is in it
		//remember the String function indexOf
		// it will return -1 if something is not in our String
		// so that will be really useful.		
		for (int i=0;i<allPasswords.length; i++)
			if (allPasswords[i].indexOf(word)!=-1)
				System.out.println(allPasswords[i]);

	}

	public String[] findTop(int howMany)
	{
		//this is advanced - try it on your own.
		String[] topList=new String[0];
		return topList;
	}

	public static void main(String[] args) {
		Passwords p=new Passwords();
		System.out.println("testing linary "+p.binarySearch("peace"));
		System.out.println("testing binary "+p.binarySearch("whatever"));
		System.out.println("dude has been used "+p.findHowMany("dude"));

		System.out.println("Listing all passwords that have been used atleast 100 times:");


		p.findAllDerivatives("dude"); 

		for (String pw:p.findTop(100))
		{
			System.out.println(pw + " - "+p.findHowMany(pw)+"times");	
		}
	}

}