public class LinkedSet implements Set { protected Node head; protected Node tail; protected int numElements; @Override public void insert(T t) { if (has(t)) { return; } append(t); numElements++; } // Adds to the end of this linked-list in O(1) // Pre: t != null && has(t) == false // Post: has(t) == true && tail.data == t protected void append(T t) { if (tail == null) { tail = new Node(t); head = tail; } else { Node node = new Node<>(t); node.prev = tail; tail.next = node; tail = node; } } // Performs linear search. // Returns the target node containing t or null if t was not found. // Pre: t != null protected Node find(T t) { for (Node n = head; n != null; n = n.next) { if (n.data.equals(t)) { return n; } } return null; } @Override public void remove(T t) { Node target = find(t); if (target == null) { return; } remove(target); numElements--; } // Removes the given target node in O(1) // Pre: target != null // Post: has(target.data) == false protected void remove(Node target) { Node prevNode = target.prev; Node nextNode = target.next; if (prevNode != null) { prevNode.next = nextNode; } if (nextNode != null) { nextNode.prev = prevNode; } if (head == target) { head = target.next; } if (tail == target) { tail = target.prev; } } @Override public boolean has(T t) { return find(t) != null; } @Override public int size() { return numElements; } @Override public Iterator iterator() { return new SetIterator(); } // Doubly linked-list Node with 'next' and 'prev' reference variables protected static class Node { T data; Node next; Node prev; Node(T data) { this.data = data; } } // Iterate from head to tail; all operations O(1) private class SetIterator implements Iterator { private Node current; SetIterator() { current = LinkedSet.this.head; } @Override public boolean hasNext() { return current != null; } @Override public T next() { if (!hasNext()) { throw new NoSuchElementException(); } T t = current.data; current = current.next; return t; } } } public class ArraySet implements Set { protected int numElements; protected T[] data; /** * Make a set. 

public class TransposeArraySet extends ArraySet { // TODO: incorporate the transpose-sequential-search heuristic // each time a value is accessed. Override the relevant method(s) from ArraySet. }

public class MoveToFrontLinkedSet extends LinkedSet { // TODO: incorporate move-to-front heuristic each time a value is accessed. // Override the relevant method(s) from LinkedSet. } */ public ArraySet() { data = (T[]) new Object[1]; numElements = 0; } @Override public void insert(T t) { if (full()) { grow(); } if (!has(t)) { data[numElements++] = t; } } private boolean full() { return numElements >= data.length; } // Double the capacity of data array. private void grow() { T[] bigger = (T[]) new Object[2 * numElements]; System.arraycopy(data, 0, bigger, 0, numElements); data = bigger; } // Returns the index of t in data or -1 if it is not found. // Pre: t != null protected int find(T t) { for (int i = 0; i < numElements; i++) { if (t.equals(data[i])) { return i; } } return -1; } @Override public void remove(T t) { int i = find(t); if (i != -1) { data[i] = data[numElements - 1]; data[numElements - 1] = null; numElements--; } } @Override public boolean has(T t) { return find(t) != -1; } @Override public int size() { return numElements; } @Override public Iterator iterator() { return new SetIterator(); } // Iterate from element at position 0 to numElements private class SetIterator implements Iterator { private int current; SetIterator() { current = 0; } @Override public boolean hasNext() { return current < numElements; } @Override public T next() { if (!hasNext()) { throw new NoSuchElementException(); } return data[current++]; } } }

you will implement the move-to-front heuristic in MoveToFrontLinkedSet.java and transpose-sequential-search heuristic in TransposeArraySet.java. These hurestics are described in Chapter 15 (Set ADT).

MoveToFrontLinkedSet: A heuristic that moves the target of a search to the head of a list so it is found faster next time.

transpose-sequential-search heuristic: Search an array or list by checking items one at a time. If the value is found, swap it with its predecessor so it is found faster next time.

Note the MoveToFrontLinkedSet and TransposeArraySet classes extend the corresponding implementations LinkedSet and ArraySet of the Set ADT.

• You will need to override relevant method(s) from LinkedSet/ArraySet respectively. (The changes must be kept as minimal as possible.)
• You many not make any changes to Set.java, LinkedSet.java and ArraySet.java files.
• You may add as many private members as you need to MoveToFrontLinkedSet and TransposeArraySet. However, you may not add any public members in there.

Once you are done. run the tests in SetTest for MoveToFrontLinkedSet and TransposeArraySet. Make sure they all pass. This gives you a minimal assurance that your implementation does not break the code contract of the Set ADT.

Next, add a main method to each of MoveToFrontLinkedSet and TransposeArraySet. Inside the main method, add a sequence of operations to "insert", "remove" and "search" (use has operation) for some sample values. It is entirely up to you what values and what sequence of operations you use.

Run each main method in debug mode and execute the sequence of operations step by step. Use the debugger tool (or jGRASP/Java Visualizer plugins) to observe the state of the underlying array/linked list for each implementation. Make sure your implementation works as expected of each heuristic.

In the README.md file, please note if you encounter any issues, unexpected/surprising, or interesting observations as you execute the main method step by step. Hint: look more carefully at the values after removal!