Homework: Set 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 and an entry of type T, searches for the given entry in the given queue and, if it finds it, moves that entry to the front of the queue.
        /**
         * Finds {@code x} in {@code q} and, if such exists, moves it to the front
         * of {@code q}.
         * 
         * @param <T>
         *            type of {@code Queue} entries
         * @param q
         *            the {@code Queue} to be searched
         * @param x
         *            the entry to be searched for
         * @updates q
         * @ensures <pre>
         * perms(q, #q)  and
         * if <x> is substring of q
         *  then <x> is prefix of q
         * </pre>
         */
        private static <T> void moveToFront(Queue<T> q, T x) {...}
    

    Note that moveToFront is a static, generic method: it is parameterized by the type T of the entries in the queue. You can use the type T wherever you need to declare a variable that refers to an object of type T.

    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.

  2. Develop a complete test plan for the Set constructor and kernel methods: add, remove, removeAny, contains, and size and enter them in SetTest. You can find some more information on how to effectively test removeAny here.

For the homework, turn in printouts of your implementation of moveToFront and of the SetTest.java file.