//
// Problem 1
//
// Part A
// History - list: keeps track of things in an order (chronological in this case)
// Favorites - dictionary: most browsers let you choose a name to go along with the URL
//           - set: just keep URLs, with no repeats
// Search Results - list: sorted ordering of the most relevant URLs
//                  set: only unique URLs returned, still needs to be sorted by rank

// Part B
// Just about anything that makes sense was fine. But any algorithm described had 
// to work correctly and unambiguously.


//
// Problem 2
//
// Part A
public int indexOutOfOrder (List<Comparable> values, int start)
{
    for (int k = start; k < values.size() - 1; k++)
    {
        Comparable current = values.get(k);
        Comparable next = values.get(k + 1);
        if (current.compareTo(next) > 0)
        {
            return k + 1;
        }
    }

    // OR:
    // Comparable previous = values.get(start);
    // for (int k = start + 1; k < values.size(); k++)
    // {
    //     Comparable current = values.get(k);
    //     if (current.compareTo(previous) < 0)
    //     {
    //         return k;
    //     }
    //     previous = current;
    // }

    return -1;
}

// Part B
public void sortByRemoval (List<Comparable> values)
{
    int index = indexOutOfOrder(values, 0);

    while (index > 0)
    {
	values.remove(index);
 	index = indexOutOfOrder(values, index);
    }
}

// Part C
// No, not guaranteed. Best justification is to show a counter-example, such as [ 1, 4, 3, 2, 5 ]


//
// Problem 3
//
// Part A
public class Date implements Comparable<Date>
{
    private int myDay;
    private int myMonth;
    private int myYear;

    public Date (String data)
    {
        int firstIndex = data.indexOf("/");
        int lastIndex = data.lastIndexOf("/");
        myMonth = Integer.parseInt(data.substring(0, firstIndex));
        myDay = Integer.parseInt(data.substring(firstIndex + 1, lastIndex));
        myYear = Integer.parseInt(data.substring(lastIndex + 1));
        // OR:
        // String[] values = data.split("/");
        // myMonth = Integer.parseInt(values[0]);
        // myDay = Integer.parseInt(values[1]);
        // myYear = Integer.parseInt(values[2]);
        // OR:
        // Scanner line = new Scanner(data.replaceAll("/", " "));
        // myMonth = line.nextInt();
        // myDay = line.nextInt();
        // myYear = line.nextInt();
    }

    public int compareTo (Date other)
    {
        if (myYear < other.myYear)            return -1;
        else if (myYear > other.myYear)       return  1;
        else
        {
            if (myMonth < other.myMonth)      return -1;
            else if (myMonth > other.myMonth) return  1;
            else
            {
                if (myDay < other.myDay)      return -1;
                else if (myDay > other.myDay) return  1;
                else                          return  0;
            }
        }
        // OR:
        // int result = myYear - other.myYear;
        // if (result == 0)
        // {
        //     result = myMonth - other.myMonth;
        //     if (result == 0)
        //     {
        //         result = myDay - other.myDay;
        //     }
        // }
        // return result;
    }

    public boolean equals (Object o)
    {
        if (o instanceof Date)
        {
            Date other = (Date)o;
            return (myYear == other.myYear && 
                    myMonth == other.myMonth && 
                    myDay == other.myDay);
            // OR:
            // return (compareTo(other) == 0);
        }
        return false;
    }
}

// Part B
private Map<Date, Set<String>> readTodos (Scanner input)
{
    Map<Date, Set<String>> results = new TreeMap<Date, Set<String>>()
    while (input.hasNext())
    {
        Scanner line = new Scanner(input.nextLine());
        Date key = new Date(line.next());
        String todo = line.nextLine();
        Set<String> value = results.get(key);
        if (value == null)
	{
            value = new TreeSet<String>();
            results.put(key, value);
	}
        value.add(todo);
    }
    return results;
}

// Part C
public List<String> getTodos (Map<Date, Set<String>> dates, Date target)
{
    List<String> results = new ArrayList<String>();
    for (Date current : dates.keySet())
    {
        if (current.compareTo(target) < 0)
        {
            results.addAll(dates.get(current));
        }
    }
    Collections.sort(results);
    return results;
}

// Part D
// If dates was a TreeMap, then the keys traversed in the loop would be in 
// sorted order.  Thus, when a key date past the target date was found,
// you could break out of the loop.