/*
 * Mid2FavBeverage.java
 *
 * Solution and test code for the Midterm2 programming problem, 143-03su
 * For compactness of the solution, the Link and List classes are included
 * within this file instead of being separate public classes.
 *

 */
import java.util.*;

/*America's Favorite Beverage. A marketing agency wants to know what beverage is preferred by the largest number of people in a recent survey.  
 A program has been written which reads the survey data  into a linked list of Strings, one per person surveyed.  
 The strings are names of beverages: they are spelled and capitalized correctly, are already trimmed for spaces, and there are no nulls or empty strings.  
 The list is in no particular order.   Implement the findFavoriteBeverage method.  
 Use the SurveyList and Link class as given below (very similar to what was used in lecture, but with none of the list class methods implemented!  
 In particular, there is no get method or iterator method).

Hint: although the parameter of findFavoriteBeverage of of the weird SurveyList type, 
 you can use classes of the Java Collections framework elsewhere in your solution as desired.  
 For example, a Map might be handy...
*/
/**
 */
public class Mid2FavBeverage {
    
/** Return the name of the beverage chosen as "favorite" by the largest number of people. */
public static String findFavoriteBeverage(SurveyList bevNames) {
//IMPLEMENT THIS 
    //Solution using a Map
    Map uniqueNames = new HashMap();  //create an empty Map
    String favorite = "no favorite yet";
    int howManyOfFavorite = 0;
    Link currentLink = bevNames.first;
    while (currentLink != null) { //go through all the survey responses
        String currName = currentLink.item;
        Integer occurrences = (Integer) uniqueNames.get(currName);
        int howManySoFar;
        if (occurrences == null) {
            howManySoFar = 0;
        } else {
            howManySoFar = occurrences.intValue();
        }
        howManySoFar++;
        uniqueNames.put(currName, new Integer(howManySoFar+1));
        if (howManySoFar > howManyOfFavorite) {
            //got a new favorite
            favorite = currName;
            howManyOfFavorite = howManySoFar;
        }
        currentLink = currentLink.next;
    }
    return favorite;        
    }

/** Return the name of the beverage chosen as "favorite" by the largest number of people.
      Alternate solution not using Maps.
*/
public static String findFavoriteBeverage2(SurveyList bevNames) {
//IMPLEMENT THIS 
    //Solution using parallel Lists.
    //counts[i] will hold the number of people who prefer uniqueNames[i].
    List uniqueNames = new ArrayList();
    List counts = new ArrayList();
    String favorite = "no favorite yet";
    int howManyOfFavorite = 0;
    Link currentLink = bevNames.first;
    while (currentLink != null) { //go through all the survey responses
        String currName = currentLink.item;
        Integer occurrences = null;
        int arrayPosition = uniqueNames.size()-1; //last one; then count backwards
        while (arrayPosition >= 0) {
            String savedName = (String) uniqueNames.get(arrayPosition);
            if (savedName.equals(currName)) {
                //have found what we need
                occurrences = ((Integer) counts.get(arrayPosition));
                break; //not strictly necessary, but faster
            } else {
                arrayPosition--;
            }
        }
        int howManySoFar;
        if (occurrences == null) {
            //the name was not in the list, so add entries for it now.
            occurrences = new Integer(0);
            uniqueNames.add(currName);
            counts.add(occurrences);
            arrayPosition = uniqueNames.size()-1; //where we just added
        }
        howManySoFar = 1 + occurrences.intValue();
        counts.set(arrayPosition, new Integer(howManySoFar));
        if (howManySoFar > howManyOfFavorite) {
            //got a new favorite
            favorite = currName;
            howManyOfFavorite = howManySoFar;
        }
        currentLink = currentLink.next; //advance linked list
    }
    return favorite;        
    }

    
    /**test: Create a list, and then send it to findFavoriteBeverage
     */
    public static void main(String[] args) {
        SurveyList testList = new SurveyList();
        String[] names = new String[] { "Coke", "Coke", "Sprite", "Ovaltine",
                                "GatorAide", "Ovaltine", "Ovaltine", "Coke", "Coke"};
        testList.first = new Link(names[0], null);
        Link currLink = testList.first;
        for (int n = 1; n < names.length; n++) {
            currLink.next = new Link(names[n], null);
            currLink = currLink.next;
        }        
        String fav = findFavoriteBeverage(testList);       
        System.out.println("Favorite is " + fav);        
        String fav2 = findFavoriteBeverage(testList); //test the other version
        assert fav.equals(fav2);
        System.out.println("test finished.");
    }  
}

/** Link class for a linked  list of survey responses */
class Link {
    public String  item;
    public Link next;

    public Link(String data, Link nextLink) { // constructor
         this.item = data;
         this.next = nextLink;
    }
}

/** Linked list class for the survey */
class SurveyList {
     public Link first = null;
    
     // There are NO other methods!

}