2008/05/09 – CS235

Sing, Prayer

Announcements

•	Review schedule
o	Project 1 was due yesterday
o	Project 2 is assigned today
•	Grades posted on:  http://byuspring.blackboard.com
•	Projects 
o	103 for 3 or more days early, 102 for 2 days, 101 for one day, 100 on the day that it is due
o	80 for up to one week late, 60 for up to 2 weeks late, 0 after that. 
o	The TAs do not use timestamps. 
o	The projects must be submitted and passed off before the last TA leaves on the day that it is due.

Review
Lists
ArrayList (good for get/set)
LinkedList (good for insert/remove in within the list)
Sets
HashSet (fastest)
TreeSet (ordered by comparator)
LinkedHashSet (ordered by insertion)

Q: What is a factory method?
A: a method that creates new concrete instances but returns them using a reference to an abstract class

Group work

•	Write a program that takes a list of Map<String, String> objects and combines them into a single Map<String, List<String>> object.

•	Write a program that takes in a dictionary of words and prints out a list of the anagrams (i.e., a word or phrase spelled by rearranging the letters of another word or phrase).   Hint:  create a simulated multi-map using Map<String, List<String>>

•	Discuss how you might extend an AbstractList to implement a Stack 

•	Discuss how you implement a PriorityQueue

Lecture

Maps

Map Interface:

public interface Map<K,V> {

    // Basic operations
    V put(K key, V value);
    V get(Object key);
    V remove(Object key);
    boolean containsKey(Object key);
    boolean containsValue(Object value);
    int size();
    boolean isEmpty();

    // Bulk operations
    void putAll(Map<? extends K, ? extends V> m);
    void clear();

    // Collection Views
    public Set<K> keySet();
    public Collection<V> values();
    public Set<Map.Entry<K,V>> entrySet();

    // Interface for entrySet elements
    public interface Entry {
        K getKey();
        V getValue();
        V setValue(V value);
    }
}

Show << Freq.java >>
•	Get and put
•	Conditional expression
•	What if we wanted the words ordered?

Map Implementations
•	HashMap
•	TreeMap
•	LinkedHashMap

•	Compare to PHP arrays

Show << MapOperations.java >>
•	Why use generic Object as key and value?  Is that OK?

Show << MapMore.java >>
•	Find common keys

Show << Anagrams.java >>
•	Multi-map example (multiple values per key)
•	What is an anagram? a word or phrase spelled by rearranging the letters of another word or phrase (e.g., steal, stale, and slate)
•	Input:  Dictionary.txt

Show << MultiMap.java .>>

STACK

<< StackBasics.java >>

<< Balanced.java >>

import java.util.*;
import java.io.*;

public class AnagramFinder {
    public static void main(String[] args) {
        int minGroupSizeThreshold = Integer.parseInt(args[1]);

        // INITIALIZE YOUR CHOSEN DATA STRUCTURE HERE

        try {
            Scanner s = new Scanner(new File(args[0]));
            while (s.hasNext()) {
                //ADD CODE HERE

                

            }
        } catch (IOException e) {
            System.err.println(e);
            System.exit(1);
        }

        // Print all permutation groups above size threshold
        
    }

    // you may wish to use this function
    private static String alphabetize(String s) {
        char[] a = s.toCharArray();
        Arrays.sort(a);
        return new String(a);
    }

    
}