Description

This problem gives you an opportunity to work with a linked data structure by implementing the java.util.List and java.util.ListIterator interfaces through an adaptive list. This adaptive list is a doubly linked list complemented by an array for indexed read operations (like get(int pos)) and indexed write operations (like set(int pos, E obj)). The adaptive list is much more efficient than the doubly linked list for supporting a long sequence of indexed read/write operations flanked by add() and remove() operations.

Requirements of the AdaptiveList class

Write a generic linked list class named AdaptiveList. Your class must implement the java.util.List interface. You may find it helpful to read the Javadoc for the interface along with its iterator subinterface. All the methods except subList method in the interface as well as a few additional methods must be implemented with throwing throwing an UnsupportedOperationException, i.e., you may throw an UnsupportedOperationExceptionfor the subList method. Note that for some of the methods, we provide their implementations as examples for you to study or for showing the list/array created by your code; you just need to implement the other methods with the comment line // TODO in the body. You are not allowed to use any Collection class in your implementation.

The AdaptiveList class has a non-static inner class named ListNode whose instances serve as nodes in the doubly linked list. The inner class has three member variables: data of generic type E, link of typeListNode, and prev of type ListNode. No additional member variables in the ListNode class are allowed. The link data field of a node refers to its successor node in the list if the successor node exists and isnullotherwise. The prev data field of a node refers to its predecessor node in the list if the predecessor node exists and is null otherwise. Every AdaptiveList list must have two dummy nodes named head and tailalong with normal nodes. The list is empty if it has no normal nodes. If the list is empty, then head is the predecessor of tail and tail is the successor of head. Otherwise, head is the predecessor of the first normal node and the first normal node is the successor node of head; tail is the successor of the last normal node and the last normal node is the predecessor of tail. The data fields of head and tail are always null. The prev data field of head and the link data field of tail are always null.

Below figure shows the case when AdaptiveList list is empty, i.e., there is no normal nodes.

Write a private inner class named AdaptiveListIterator to implement the ListIterator interface. You should implement all methods in the ListIterator interface without throwing anyUnsupportedOperationException. There is no need to keep a coherent list if there is concurrent modifiction to the list. In other words, there iterator does not have to be a fail-fast iterator.

In addition to the doubly linked list, the AdaptiveList class keeps an array of type E elements for implementing the get(int pos), set(int pos, E obj), and reverse() methods efficiently. Note thatreverse()method swaps the elements at indices 0 and n-1, at indices 1 and n-2, and so on, so that the order of the elements in the array of length n is reversed. The method returns false if n

The doubly linked list and the array are alternately used as follows. The class keeps two boolean data fields named linkedUTD and arrayUTD, where UTD stands for Up To Date: linkedUTD is true if the doubly linked list is used to represent the current sequence of data items and false otherwise; arrayUTD is true if the array is used to represent the current sequence of data items and false otherwise. At any time, the current sequence of data items is represented either by doubly linked list or by the array; so at least one oflinkedUTD and arrayUTD is true. The doubly linked list is used to implement all methods except for the get(int pos), set(int pos, E obj), and reverse() methods, which are implemented by using the array. These implementations are facilitated by using two helper methods: The updateLinked() method creates a new doubly linked list with numItems normal nodes by copying the current sequence of data items from the array to the doubly linked list and setting linkedUTD to true, whereas the updateArray() method creates a new array of length numItems by copying the current sequence of data items from the doubly linked list to the array and setting arrayUTD to true. If a method is to be implemented by using the doubly linked list but linkedUTD is false, then updateLinked() needs to be called before the implementation and at the endarrayUTD needs to be set to false if the doubly linked list is modified by the method so that the array is no longer up to date. Similarly, if a method is to be implemented by using the array but arrayUTD is false, then updateArray() needs to be called before the implementation and at the end linkedUTD needs to be set to false if the array is to be modified by the set(int pos, E obj) or reverse() method. For example, if following code fragment runs:

public static void main(String[] args) { AdaptiveList seq = new AdaptiveList(); seq.add("B"); seq.add("A"); seq.add("C"); System.out.println("After the three seq.add() operations:"); System.out.println("linkedUTD: " + seq.getlinkedUTD()); System.out.println("arrayUTD: " + seq.getarrayUTD()); System.out.println(seq.toString()); System.out.println( seq.get(1) ); System.out.println("After the seq.get(1) operation:"); System.out.println("linkedUTD: " + seq.getlinkedUTD()); System.out.println("arrayUTD: " + seq.getarrayUTD()); System.out.println(seq.toString()); System.out.println( seq.set(1, "D") ); System.out.println("After the seq.set(1, 'D') operation:"); System.out.println("linkedUTD: " + seq.getlinkedUTD()); System.out.println("arrayUTD: " + seq.getarrayUTD()); System.out.println(seq.toString()); seq.add("E"); System.out.println("After the seq.add('E') operation:"); System.out.println("linkedUTD: " + seq.getlinkedUTD()); System.out.println("arrayUTD: " + seq.getarrayUTD()); System.out.println(seq.toString()); System.out.println("Any change in array: "+seq.reverse()); System.out.println("linkedUTD: " + seq.getlinkedUTD()); System.out.println("arrayUTD: " + seq.getarrayUTD()); System.out.println(seq.toString()); }

we would get the following output:

After the three seq.add() operations: linkedUTD: true arrayUTD: false A sequence of items from the most recent array: [] A sequence of items from the most recent linked list: (B, A, C) A After the seq.get(1) operation: linkedUTD: true arrayUTD: true A sequence of items from the most recent array: [B, A, C] A sequence of items from the most recent linked list: (B, A, C) A After the seq.set(1, 'D') operation: linkedUTD: false arrayUTD: true A sequence of items from the most recent array: [B, D, C] A sequence of items from the most recent linked list: (B, A, C) After the seq.add('E') operation: linkedUTD: true arrayUTD: false A sequence of items from the most recent array: [B, D, C] A sequence of items from the most recent linked list: (B, D, C, E) Any change in array: true linkedUTD: false arrayUTD: true A sequence of items from the most recent array: [E, C, D, B] A sequence of items from the most recent linked list: (B, D, C, E)

you need to use the following short template, AdaptiveList.java, to get started.

package edu.iastate.summer18.cs228.hw5; /* * @author * * An implementation of List based on a doubly-linked list * with an array for indexed reads/writes * */

import java.util.Arrays;

import java.util.Collection; import java.util.Iterator; import java.util.List; import java.util.ListIterator; import java.util.NoSuchElementException;

public class AdaptiveList implements List { public class ListNode // private member of outer class { public E data; // public members: public ListNode link; // used outside the inner class public ListNode prev; // used outside the inner class public ListNode(E item) { data = item; link = prev = null; } } public ListNode head; // dummy node made public for testing. public ListNode tail; // dummy node made public for testing. private int numItems; // number of data items private boolean linkedUTD; // true if the linked list is up-to-date.

public E[] theArray; // the array for storing elements private boolean arrayUTD; // true if the array is up-to-date.

public AdaptiveList() { clear(); }

@Override public void clear() { head = new ListNode(null); tail = new ListNode(null); head.link = tail; tail.prev = head; numItems = 0; linkedUTD = true; arrayUTD = false; theArray = null; }

public boolean getlinkedUTD() { return linkedUTD; }

public boolean getarrayUTD() { return arrayUTD; }

public AdaptiveList(Collection extends E> c) { // TODO }

// Removes the node from the linked list. // This method should be used to remove a node from the linked list. private void unlink(ListNode toRemove) { if ( toRemove == head || toRemove == tail ) throw new RuntimeException("An attempt to remove head or tail"); toRemove.prev.link = toRemove.link; toRemove.link.prev = toRemove.prev; }

// Inserts new node toAdd right after old node current. // This method should be used to add a node to the linked list. private void link(ListNode current, ListNode toAdd) { if ( current == tail ) throw new RuntimeException("An attempt to link after tail"); if ( toAdd == head || toAdd == tail ) throw new RuntimeException("An attempt to add head/tail as a new node"); toAdd.link = current.link; toAdd.link.prev = toAdd; toAdd.prev = current; current.link = toAdd; }

private void updateArray() // makes theArray up-to-date. { if ( numItems

private void updateLinked() // makes the linked list up-to-date. { if ( numItems

if ( theArray == null || theArray.length

// TODO }

@Override public int size() { // TODO return -1; // may need to be revised. }

@Override public boolean isEmpty() { // TODO return true; // may need to be revised. }

@Override public boolean add(E obj) { // TODO return true; // may need to be revised. }

@Override public boolean addAll(Collection c) { // TODO return true; // may need to be revised. } // addAll 1

@Override public boolean remove(Object obj) { // TODO return true; // may need to be revised. }

private void checkIndex(int pos) // a helper method { if ( pos >= numItems || pos

private void checkIndex2(int pos) // a helper method { if ( pos > numItems || pos

private void checkNode(ListNode cur) // a helper method { if ( cur == null || cur == tail ) throw new RuntimeException( "numItems: " + numItems + " is too large"); }

private ListNode findNode(int pos) // a helper method { ListNode cur = head; for ( int i = 0; i

@Override public void add(int pos, E obj) { // TODO }

@Override public boolean addAll(int pos, Collection c) { // TODO return true; // may need to be revised. } // addAll 2

@Override public E remove(int pos) { // TODO return null; // may need to be revised. }

@Override public E get(int pos) { // TODO return null; // may need to be revised. }

@Override public E set(int pos, E obj) { // TODO return null; // may need to be revised. }

// If the number of elements is at most 1, the method returns false. // Otherwise, it reverses the order of the elements in the array // without using any additional array, and returns true. // Note that if the array is modified, then linkedUTD needs to be set to false. public boolean reverse() { // TODO return true; // may need to be revised. }

@Override public boolean contains(Object obj) { // TODO return true; // may need to be revised. }

@Override public boolean containsAll(Collection c) { // TODO return true; // may need to be revised. } // containsAll

@Override public int indexOf(Object obj) { // TODO return -1; // may need to be revised. }

@Override public int lastIndexOf(Object obj) { // TODO return -1; // may need to be revised. }

@Override public boolean removeAll(Collection> c) { // TODO return true; // may need to be revised. }

@Override public boolean retainAll(Collection> c) { // TODO return true; // may need to be revised. }

@Override public Object[] toArray() { // TODO return null; // may need to be revised. } @Override public T[] toArray(T[] arr) { // TODO return null; // may need to be revised. }

@Override public List subList(int fromPos, int toPos) { throw new UnsupportedOperationException(); }

private class AdaptiveListIterator implements ListIterator { private int index; // index of next node; private ListNode cur; // node at index - 1 private ListNode last; // node last visited by next() or previous()

public AdaptiveListIterator() { if ( ! linkedUTD ) updateLinked(); // TODO } public AdaptiveListIterator(int pos) { if ( ! linkedUTD ) updateLinked(); // TODO }

@Override public boolean hasNext() { // TODO return true; // may need to be revised. }

@Override public E next() { // TODO return null; // may need to be revised. }

@Override public boolean hasPrevious() { // TODO return true; // may need to be revised. }

@Override public E previous() { // TODO return null; // may need to be revised. } @Override public int nextIndex() { // TODO return -1; // may need to be revised. }

@Override public int previousIndex() { // TODO return -1; // may need to be revised. }

public void remove() { // TODO }

public void add(E obj) { // TODO } // add

@Override public void set(E obj) { // TODO } // set } // AdaptiveListIterator @Override public boolean equals(Object obj) { if ( ! linkedUTD ) updateLinked(); if ( (obj == null) || ! ( obj instanceof List> ) ) return false; List> list = (List>) obj; if ( list.size() != numItems ) return false; Iterator> iter = list.iterator(); for ( ListNode tmp = head.link; tmp != tail; tmp = tmp.link ) { if ( ! iter.hasNext() ) return false; Object t = iter.next(); if ( ! (t == tmp.data || t != null && t.equals(tmp.data) ) ) return false; } if ( iter.hasNext() ) return false; return true; } // equals

@Override public Iterator iterator() { return new AdaptiveListIterator(); }

@Override public ListIterator listIterator() { return new AdaptiveListIterator(); }

@Override public ListIterator listIterator(int pos) { checkIndex2(pos); return new AdaptiveListIterator(pos); }

// Adopted from the List interface. @Override public int hashCode() { if ( ! linkedUTD ) updateLinked(); int hashCode = 1; for ( E e : this ) hashCode = 31 * hashCode + ( e == null ? 0 : e.hashCode() ); return hashCode; }

// You should use the toString*() methods to see if your code works as expected. @Override public String toString() { String eol = System.getProperty("line.separator"); return toStringArray() + eol + toStringLinked(); }

public String toStringArray() { String eol = System.getProperty("line.separator"); StringBuilder strb = new StringBuilder(); strb.append("A sequence of items from the most recent array:" + eol ); strb.append('['); if ( theArray != null ) for ( int j = 0; j

public String toStringLinked() { return toStringLinked(null); }

// iter can be null. public String toStringLinked(ListIterator iter) { int cnt = 0; int loc = iter == null? -1 : iter.nextIndex();

String eol = System.getProperty("line.separator"); StringBuilder strb = new StringBuilder(); strb.append("A sequence of items from the most recent linked list:" + eol ); strb.append('('); for ( ListNode cur = head.link; cur != tail; ) { if ( cur.data != null ) { if ( loc == cnt ) { strb.append("| "); loc = -1; } strb.append(cur.data.toString()); cnt++;

if ( loc == numItems && cnt == numItems ) { strb.append(" |"); loc = -1; } } else strb.append("-"); cur = cur.link; if ( cur != tail ) strb.append(", "); } strb.append(')'); return strb.toString(); } }

Below figure shows the case when (Adaptivelist list is empty, i.e., there is no normal nodes. head tail link link NULL NULL prev prev Whereas following figure shows (Adaptivelist list with two normal nodes. head tail link link link link A NULL NULL prev prev prev prev Write a private inner class named AdaptiveListIterator to implement the ListIterator interface. You should implement all methods in the ListIterator interface without throwing any UnsupportedoperationException There is no need to keen a coherent list if there is concurrent modifiction to the list, In other words, there