// Solutions to Test 2 CompSci 6 Fall 2005


//------------------------------------------------------------
// Question 1
//

// Given:
//  Object -> Pet -> Dog
//                -> Cat -> Persian
//                       -> Siamese

// legal
// legal
// illegal - Siamese is not a sub-class of Dog
// legal
// illegal - Pet is abstract, cannot be created
// legal
// legal
// illegal - Siamese is not a sub-class of Persian 
// illegal - cast doesn't help
// legal


//------------------------------------------------------------
// Question 2
//

// Part A
public String getIP (String s)
{
    return s.substring(s.indexOf(" ") + 1);
    // OR:
    // Scanner input = new Scanner(s);
    // input.next();        // skip url entry
    // return input.next();
}

// Part B
public String findIPAddress (String[] addresses, String url)
{
    final String NO_IPADDRESS = "0.0.0.0";

    for (String current : addresses)
    {
        String location = current.substring(0, current.indexOf(" "));
        // OR:
        // String location = new Scanner(current).next();
        if (location.equals(url))
        {
            return getIP(current);
        }
    }

    return NO_IPADDRESS;
}


//------------------------------------------------------------
// Question 3
//
public int indexOutOfOrder (List<Comparable> values)
{
    // loop invariant:
    //   list elements 0 .. k-1 are in order,
    //   others yet to be checked 

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

    // OR:
    // for (int k = 0; 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:
    // Iterator<Comparable> iter = values.iterator();
    // Comparable previous = iter.next();
    // while (iter.hasNext())
    // {
    //     Comparable current = iter.next();
    //     if (current.compareTo(previous) < 0)
    //     {
    //         return k;
    //     }
    //     previous = current;
    // }

    return -1;
}


//------------------------------------------------------------
// Question 4
//

// Part A
public ArrayList<ArrayList<Double>> readData (Scanner input)
{
    ArrayList<ArrayList<Double>> results = new ArrayList<ArrayList<Double>>();
    
    input.useDelimiter("\n");
    while (input.hasNext())
    {
        ArrayList<Double> year = new ArrayList<Double>();
        Scanner line = new Scanner(input.next());
        while (line.hasNext())
        {
            year.add(line.next());
        }
        results.add(year);
    }

    return results;
}


// Part B
public double mostRain (double[][] data)
{
    double most = 0;

    for (double[] year : data)
    {
        for (double current : year)
        {
            most = Math.max(most, current);
        }
    }
    // OR:
    // for (int year = 0; year < data.length; year++)
    // {
    //     for (int month = 0; month < data[year].length; month++)
    //     {
    //         double current = data[year][month];
    //         if (current > most)
    //         {
    //             most = current;
    //         }
    //     }
    // }

    return most;
}

// Part C
public double totalForYear (double[] data, int year)
{
    double total = 0;

    int row = (year - 1) * 12;
    for (int k = 0; k < 12; k++)
    {
        total += data[row + k];
    }

    return total;
}


//------------------------------------------------------------
// Question 5
//

public class CountedSet
{
    class CountedItem
    {
       public Object value;
       public int count;
    }
    private ArrayList<CountedItem> myItems;

    public CountedSet ()
    {
        myItems = new ArrayList<CountedItem>();
    }

    public int size ()
    {
        return myItems.size();
    }

    public int count ()
    {
        int result = 0;
        for (CountedItem current : myItems)
        {
            result += current.count;
        }
        return result;
    }

    public void add (Object toAdd)
    {
        for (CountedItem current : myItems)
        {
            if (current.value.equals(toAdd))
            {
                current.count++;
                return;
            }
        }
        // not found
        myItems.add(new CountedItem(toAdd, 1));
    }

    public void remove (Object toRemove)
    {
        for (int k = 0; k < myItems.size(); k++)
        {
            if (myItems.get(k).value.equals(toRemove))
            {
                myItems.remove(k);
                return;
            }
        }
    }
}

// OR:
public class CountedSet
{
    private TreeSet<Object> mySet;
    private ArrayList<Object> myAdded;

    public CountedSet ()
    {
        mySet = new TreeSet<Object>();
        myAdded = new ArrayList<Object>();
    }

    public int size ()
    {
        return mySet.size();
    }

    public int count ()
    {
        return myAdded.size();
    }

    public void add (Object toAdd)
    {
        mySet.add(toAdd);
        myAdded.add(toAdd);
    }

    public void remove (Object toRemove)
    {
        mySet.remove(toRemove);
        while (myAdded.remove(toRemove))
            // do nothing else
    }
}

// OR:
public class CountedSet
{
    private ArrayList<Object> myValues;
    private ArrayList<Integer> myCounts;

    public CountedSet ()
    {
        myValues = new ArrayList<Object>();
        myCounts = new ArrayList<Integer>();
    }

    public int size ()
    {
        return myValues.size();
    }

    public int count ()
    {
        int result = 0;
        for (Integer current : myCounts)
        {
            result += current.intValue();
        }
        return result;
    }

    public void add (Object toAdd)
    {
        int index = myValues.indexOf(toAdd);
        if (index < 0)   // not found
        {
            myValues.add(toAdd);
            myCounts.add(1);
        }
        else
        {
            myCounts.set(index, myCounts.get(index) + 1);
        }
    }

    public void remove (Object toRemove)
    {
        int index = myValues.indexOf(toRemove);
        if (index >= 0)
        {
            myValues.remove(index);
            myCounts.remove(index);
        }
    }
}