Homework: Map Implementation on Queue

This homework is necessary preparation for the lab. Make sure you type your answers in files you bring to the lab so that you will not have to waste time entering your code during the lab.

  1. Implement the following method that, given a queue of Map.Pair<K, V> and a key of type K, searches for a pair with the given key in the given queue and, if it finds it, moves that pair to the front of the queue. 
        /**
     * Finds pair with first component {@code key} and, if such exists, moves it
     * to the front of {@code q}.
     * 
     * @param <K>
     *            type of {@code Pair} key
     * @param <V>
     *            type of {@code Pair} value
     * @param q
     *            the {@code Queue} to be searched
     * @param key
     *            the key to be searched for
     * @updates q
     * @ensures <pre>
     * perms(q, #q)  and
     * if there exists value: V (<(key, value)> is substring of q)
     *  then there exists value: V (<(key, value)> is prefix of q)
     * </pre>
     */
    private static <K, V> void moveToFront(Queue<Pair<K, V>> q, K key) {...}

    Note that moveToFront is a static, generic method: it is parameterized by the types K and V of the Map.Pair<K, V> entries in the queue. You can use the types K, V, and Pair<K, V> wherever you need to declare a variable that refers to an object of any of these types.

    Pay attention to the contract. There is no requires clause. If you have trouble reading and understanding the ensures clause, be sure to ask for help.

    If you need to construct a Pair object in your code (it should not be necessary in moveToFront, but you will need it in the lab), just use the only available implementation of the Map.Pair interface called MapSecondary.SimplePair<K, V>. Inside the Map2 class, you will be able to declare and initialize a Pair variable with a statement like this: 

        Pair<K, V> p = new SimplePair<>(key, value);
    where key and value are some variables of type K and V, respectively.

  2. Develop a complete test plan for the Map constructor and kernel methods: add, remove, removeAny, value, hasKey, and size and enter them in MapTest.
  3. Complete (and print with your homework) the following tracing table. We care greatly that you use correct punctuation when you write objects' values; we care so much that we will dock you points on exams when you use wrong punctuation when supplying objects' values to our questions. We urge you to practice writing correctly the values of objects. For example, after the 4th statement one of the six correct ways of showing this value is: m = {("zero", 0), ("negative one", -1), ("one", 1)}. There are six (or three factorial, 3!) correct ways because the order in which we show the three elements of the set does not matter. Note the use of curly braces, rounded parentheses, commas, double quote marks, and the absence thereof. As another example, after the 5th statement the only correct value for p is: p = ("zero", 0). It is a good idea to consult the mathematical models for MapKernel and Map.Pair and make a connection between them and the notation used in the correct answers shown here just above. Of course, it is also a good idea to consult the contract for each method or constructor called.

    Statement Variable Values
    Map<String, Integer> m = new Map1L<>();
    m =
    m.add("one", 1);
    m =
    m.add("zero", 0);
    m =
    m.add("negative one", -1);
    m =
    Pair<String, Integer> p = m.remove("zero");
    m =
    p =
    m.remove("one");
    m =
    p =
    m.add("cipher", p.value());
    m =
    p =
    m.add(p.key(), p.value());
    m =
    p =
    m.remove("negative one");
    m =
    p =
    m.remove("cipher");
    m =
    p =
    p = m.removeAny();
    m =
    p =

For the homework, turn in your answer to the last question and, as answers to the other questions, printouts of your implementation of moveToFront and of the MapTest.java file.