Please answer this multi part question. At the bottom is the Dlist.java source code file and the DlistTest.java source code files. Thanks!

1 (Include your modified DList.java source code file in your homework solution zip archive) Using whatever Java IDE you prefer, create a project and add DList.java and DListTest.java to it (these files are provided in the Week 6 Source zip archive). Modify DList to implement a method that removes all occurrences of a specific integer from the list. Here is the pseudocode:

Method removeAll(In: Integer pData) Returns Nothing Define index variable i and initialize i to 0 While i < the size of this Dlist Do

If get(i) equals pData Then remove(i)

Else Increment i

End If

End While

End Method removeAll

Next, modify DListTest() to add test case 21 which tests that removeAll() works correctly.

Part b. (Include DList.java in your solution zip archive) Here is the Java implementation of three useful methods (which are not currently in Dlist).

/**

* Removes the head node from this DList. It would be inadvisable to call this method on an

* empty list because we do not check for that condition. Returns the data stored in the head

* node.

*/

protected Integer removeHead() {

Integer data = getHead().getData();

if (getSize() == 1) {

setHead(null);

setTail(null);

} else {

getHead().getNext().setPrev(null);

setHead(getHead().getNext());

}

setSize(getSize() - 1);

return data;

}

/**

* Removes an interior node pNode from this DList. It would be inadvisable to call this method

* when pNode is null because we do not check for that condition. Returns the data stored in

* pNode.

*/

protected Integer removeInterior(Node pNode) {

Integer data = pNode.getData();

pNode.getPrev().setNext(pNode.getNext());

pNode.getNext().setPrev(pNode.getPrev());

setSize(getSize() - 1);

return data;

}

/**

* Removes the tail node from this DList. It would be inadvisable to call this method on an

* empty list because we do not check for that condition. Returns the data stored in the tail

* node.

*/

protected Integer removeTail() {

Integer data = getTail().getData();

if (getSize() == 1) {

setHead(null);

setTail(null);

} else {

getTail().getPrev().setNext(null);

setTail(getTail().getPrev());

}

setSize(getSize() - 1);

return data;

}

Using these three methods, rewrite the provided remove(index) method to make the code in that method simpler and more readable (my new and improved remove() method is half-a-dozen lines of code). Be sure to run the test cases in DListTest to ensure that your new remove() method still works correctly. Also, make sure remove() throws an IndexOutOfBoundsException if pIndex is less than 0 or greater than or equal to getSize().

Part c. (Include DList.java in your solution zip archive) Using the new add methods, rewrite append(data) and prepend(data).

Part d. (Include DList.java in your solution zip archive) Write a method void orderedAdd (Integer pData) that will insert Integers into a DList such that ascending sort order is maintained. For example,

DList list = new DList(); // list = { } 

list.orderedAdd(5); 

list.orderedAdd(3); 

list.orderedAdd(1); 

list.orderedAdd(7); 

list.orderedAdd(9); 

list.orderedAdd(-5); 

// list = { 5 } // list = { 3 5 } // list = { 1 3 5} // list = { 1 3 5 7} // list = { 1 3 5 79 } // list = { -5 1 3 5 7 9 }

Part e. Write a method void split(int pIndex, DList pLeft, DList pRight) that will "split" this DList (the one on which the method is invoked) into a left sublist pLeft and a right sublist pRight. The elements of pLeft will consist of list elements at indices 0, 1, 2, ..., pIndex - 1. The elements of pRight will consist of list elements at indices pIndex, pIndex + 1, ..., getSize() - 1. Note that pLeft and pRight must be created (and are assumed to be empty) before calling split(). For example:

 DList list = new DList(); // list = { } 

 list.append(3); list.append(5); list.append(7); list.append(11); 

 list.append(13); list.append(17); list.append(19); list.append(29); 

 // list = { 3, 5, 7, 11, 13, 17, 19, 29 } 

 DList left = new DList, right = new DList(); 

 list.split(5, left, right); 

 // left = { 3, 5, 7, 11, 13 }, right = { 17, 19, 29 } 

Dlist.java Source Code File

//************************************************************************************************** // CLASS: DList (DList.java) // // DESCRIPTION // Implements a doubly linked list data structure where each element is an Integer. // // AUTHOR //**************************************************************************************************

/** * Implements a doubly linked list of Integers. */ public class DList {

//============================================================================================== // DList Instance Variables //==============================================================================================

/** * For a nonempty DList, mHead is a reference to the first Node in the DList. For an empty * DList, mHead will be null. */ private Node mHead;

/** * The number of Nodes containing data in this DList. For an empty DList, mSize is 0. */ private int mSize;

/** * For a nonempty DList, mTail is a reference to the last Node in the DList. For an empty DList, * mTail will be null. */ private Node mTail;

//============================================================================================== // DList Instance Methods //==============================================================================================

/** * Creates an empty DList. For an empty DList, mHead = null, mTail = null, and mSize = 0. */ public DList() { setHead(null); setTail(null); setSize(0); }

/** * Creates a new DList with one element containing pData. */ public DList(Integer pData) { // Create a new Node storing pData. The ctor makes the mPrev and mNext references null. Node newNode = new Node(pData);

// Make the mHead reference refer to the new node. setHead(newNode);

// Make the mTail reference refer to the new node. setTail(newNode);

// The size of the list is now 1. setSize(1); }

/** * Inserts a new Node containing pData into this DList at index pIndex. Shifts the element * currently at that index (if it exists) and succeeding elements to the right (i.e., adds * one to their indices). * * Note that if pIndex == getSize() the new element is appended to the list. * * Throws an IndexOutOfBoundsException if pIndex < 0 or pIndex > size of the DList. */ public void add(int pIndex, Integer pData) throws IndexOutOfBoundsException { // Check for pIndex out of bounds. if (pIndex < 0 || pIndex > getSize()) throw new IndexOutOfBoundsException();

// Are we appending? if (pIndex == getSize()) { // Create a new Node storing pData. The mNext reference is initialized to null because // the new Node will become the tail Node of the DList and the mNext reference of the // tail Node is always null. The mPrev reference is initialized to mTail so it will // refer to the Node preceding the new Node. Node newNode = new Node(pData, getTail(), null);

// If this DList is empty the new Node becomes the head Node. Otherwise change mNext of // the tail Node to refer to the new Node. if (isEmpty()) setHead(newNode); else getTail().setNext(newNode);

// In any case, we must change mTail to refer to the new Node that is now at the tail. setTail(newNode); }

// We are not appending. else { // Get a reference to the Node at pIndex. We are inserting a new Node before 'node'. Node node = getNodeAt(pIndex);

// Create a new Node storing pData. Set the mPrev reference of the new Node to refer to // the Node preceding 'node'. Set the mNext reference of the new Node to refer to // 'node'. Node newNode = new Node(pData, node.getPrev(), node);

// If we are not inserting at pIndex = 0 then we need to change the mNext reference of // the Node preceding 'node' to refer to the new Node. if (pIndex != 0) node.getPrev().setNext(newNode);

// Make the mPrev reference of 'node' refer to the new Node. The result of these three // operations is to "link" the the new Node into the DList. node.setPrev(newNode);

// Are we inserting at index 0? If so, we need to change the head to refer to the new // Node because the new Node is now at head. if (pIndex == 0) setHead(newNode); }

// We have added a new Node to the DList. Increment the size of the DList. setSize(getSize() + 1); }

/** * Appends a new Node storing pData to this DList. Note that passing an index of getSize() to * add(int pIndex, Integer pData) will cause add() to perform an append operation. */ public void append(Integer pData) { add(getSize(), pData); }

/** * Removes all of the elements from the DList. After this operation the DList will be empty. */ public void clear() { // To clear the list is simple. Simply remove the node at index 0 until the list becomes // empty. while (!isEmpty()) { remove(0); } }

/** * Returns the element at index pIndex. * * Thows IndexOutOfBoundsException if pIndex < 0 or pIndex >= mSize. */ public Integer get(int pIndex) throws IndexOutOfBoundsException { return getNodeAt(pIndex).getData(); }

/** * Accessor method for the mHead field. */ protected Node getHead() { return mHead; }

/** * Returns a reference to the Node at index pIndex. * * Thows IndexOutOfBoundsException if pIndex < 0 or pIndex >= getSize() */ protected Node getNodeAt(int pIndex) throws IndexOutOfBoundsException { // Check for pIndex out of bounds and throw exception is necessary. if (pIndex < 0 || pIndex >= getSize()) throw new IndexOutOfBoundsException();

// Since accessing the head and tail nodes is a common operation we check for those cases // first. if (pIndex == 0) return getHead(); else if (pIndex == getSize() - 1) return getTail();

// Otherwise, start at the node at index 1 and walk forward until the node at index pIndex // is reached and then return it. Node node = getHead().getNext(); for (int index = 1; index < pIndex; ++index) node = node.getNext(); return node; }

/** * Accessor method for the mSize field. */ public int getSize() { return mSize; }

/** * Accessor method for the mTail field. */ protected Node getTail() { return mTail; }

/** * Returns true if this DList is empty. */ public boolean isEmpty() { return getSize() == 0; }

/** * Prepends a new Node storing pData to this DList. */ public void prepend(Integer pData) { add(0, pData); }

/** * Removes the element at index pIndex from this DList. Shifts any succeeding elements to * the left (i.e., subtracts one from their indices). Returns the element that was removed from * the list. * * Throws an IndexOutOfBoundsException is pIndex < 0 || pIndex >= getSize(). */ public Integer remove(int pIndex) throws IndexOutOfBoundsException { Node node = getNodeAt(pIndex);

// Are we removing the only element in a list with one element? if (getSize() == 1) { setHead(null); setTail(null); }

// Else are we removing the head node in a list with more than one element (note: we will // not get here if the list has only one element)? else if (pIndex == 0) { // Change the prev reference of the next node to null because the next node will now // be the head node in the list. node.getNext().setPrev(null);

// Since we removed the head node, we have to change the head reference to refer to the // next node succeeding the one that was just removed. setHead(node.getNext()); }

// Else are we removing the tail node in a list with more than one element (note: we will // not get here if the list has only one element)? else if (pIndex == getSize() - 1) { // Change the next reference of the previous node to null because the previous node will // now be the tail node in the list. node.getPrev().setNext(null);

// Since we removed the tail node, we have to change the tail reference to refer to the // previous node preceding the one that was just removed. setTail(node.getPrev()); }

// We are not removing the head or tail node. else { node.getPrev().setNext(node.getNext()); node.getNext().setPrev(node.getPrev()); }

// We have removed a Node so decrement the size of the list. setSize(getSize() - 1);

// Return the data stored at the removed Node. return node.getData(); }

/** * Replaces the element at the specified position in this list with the specified element. * Returns the element that was previously stored at pIndex. */ public Integer set(int pIndex, Integer pData) throws IndexOutOfBoundsException { Node node = getNodeAt(pIndex); Integer original = node.getData(); node.setData(pData); return original; }

/** * Mutator method for the mHead field. */ protected void setHead(Node pHead) { mHead = pHead; }

/** * Mutator method for the mSize field. */ protected void setSize(int pSize) { mSize = pSize; }

/** * Mutator method for the mTail field. */ protected void setTail(Node pTail) { mTail = pTail; }

/** * Returns a string representation of this DList where we define string representation be the * string representation of each of the Nodes. */ @Override public String toString() { String string = ""; for (int i = 0; i < getSize(); ++i) string += get(i) + " "; return string; }

//********************************************************************************************** // Static Nested Class: Node //**********************************************************************************************

/** * The data for each element of the DList is stored in a Node object. A Node object contains * three instance variables: (1) mData is a reference to the data stored in the Node; (2) mNext * is a reference to the succeeding Node in the DList; and (3) mPrev is a reference to the * preceding Node in the DList. * * Note that Node is declared as protected so it is not visible to other classes but it is * accessible to subclasses of DList. */ protected static class Node {

//========================================================================================== // Node Instance Variables //==========================================================================================

/** * The data stored in this Node. */ Integer mData;

/** * A reference to the succeeding Node in the DList. */ Node mNext;

/** * A reference to the preceding Node in the DList. */ Node mPrev;

//========================================================================================== // Node Instance Methods //==========================================================================================

/** * Creates a new Node storing no data and with mNext and mPrev set to null. */ public Node() { this(null); }

/** * Creates a new Node storing pData as the data and with mNext and mPrev set to null. */ public Node(Integer pData) { setData(pData); setNext(null); setPrev(null); }

/** * Creates a new Node storing pData as the data, mPrev initialized to pPrev, and mNext * initialized to pNext. */ public Node(Integer pData, Node pPrev, Node pNext) { setData(pData); setPrev(pPrev); setNext(pNext); }

/** * Returns true if this Node and pNode are equal to each other where equal is defined as: * * 1. If pNode is null, returns false. * 2. If mNode == pNode is true, returns true. * 3. If the instance variables of this Node are equal to the instance variables of pNode * returns true. * 4. Otherwise, returns false. */ @Override public boolean equals(Object pNode) { Node node = (Node)pNode; if (node == null) return false; if (this == node) return true; if (getData() == node.getData() && getNext() == node.getNext() && getPrev() == node.getPrev()) return true; return false; }

/** * Accessor method for the mData instance variable. */ public Integer getData() { return mData; }

/** * Accessor method for the mNext instance variable. */ public Node getNext() { return mNext; }

/** * Accessor method for the mPrev instance variable. */ public Node getPrev() { return mPrev; }

/** * Mutator method for the mData instance variable. */ public void setData(Integer pData) { mData = pData; }

/** * Mutator method for the mNext instance variable. */ public void setNext(Node pNext) { mNext = pNext; }

/** * Mutator method for the mPrev instance variable. */ public void setPrev(Node pPrev) { mPrev = pPrev; }

/** * Returns a string representation of this Node where we define the string representation * to be the string representation of the data stored in this Node. */ @Override public String toString() { return "" + getData(); } } }

DlistTest.java Source Code File

//************************************************************************************************** // CLASS: DListTest (DListTest.java) // // DESCRIPTION // Tests the DList class. // // AUTHOR ***********************************************************

/** * Tests the DList class. */ public class DListTest {

public static void main(String[] pArgs) { new DListTest().run(); }

private DListTest() { }

private void passOrFail(int pCase, DList list, String pExpected) { String listAsString = list.toString(); if (!listAsString.equals(pExpected)) { System.out.println("failed [" + listAsString + "]"); } else { System.out.println("passed"); } }

private void run() { testCase1(); testCase2(); testCase3(); testCase4(); testCase5(); testCase6(); testCase7(); testCase8(); testCase9(); testCase10(); testCase11(); testCase12(); testCase13(); testCase14(); testCase15(); testCase16(); testCase17(); testCase18(); testCase19(); }

/** * Test Case 1: tests appending of one element to an empty list. */ private void testCase1() { System.out.print("Running test case 1... "); DList list = new DList(); list.append(1); passOrFail(1, list, "1 "); }

/** * Test Case 2: tests appending of multiple elements. */ private void testCase2() { System.out.print("Running test case 2... "); DList list = new DList(); list.append(1); list.append(2); list.append(3); list.append(4); list.append(5); list.append(6); passOrFail(2, list, "1 2 3 4 5 6 "); }

/** * Test Case 3: test adding one element to an empty list (at pIndex = 0). */ private void testCase3() { System.out.print("Running test case 3... "); DList list = new DList(); list.add(0, 1); passOrFail(3, list, "1 "); }

/** * Test Case 4: test adding multiple elements to the head of a list (at pIndex = 0). */ private void testCase4() { System.out.print("Running test case 4... "); DList list = new DList(); list.add(0, 1); list.add(0, 2); list.add(0, 3); list.add(0, 4); list.add(0, 5); passOrFail(4, list, "5 4 3 2 1 "); }

/** * Test Case 5: test adding multiple elements to the tail of a nonempty list (at * pIndex = list.getSize()). */ private void testCase5() { System.out.print("Running test case 5... "); DList list = new DList(); list.add(0, 1); list.add(list.getSize(), 2); list.add(list.getSize(), 3); list.add(list.getSize(), 4); list.add(list.getSize(), 5); passOrFail(5, list, "1 2 3 4 5 "); }

/** * Test Case 6: test adding multiple elements to the middle of a nonempty list. */ private void testCase6() { System.out.print("Running test case 6... "); DList list = new DList(); list.add(0, 1); list.add(1, 2); list.add(1, 3); list.add(1, 4); list.add(1, 5); list.add(1, 6); passOrFail(6, list, "1 6 5 4 3 2 "); }

/** * Test Case 7: tests prepending of one element to an empty list. */ private void testCase7() { System.out.print("Running test case 7... "); DList list = new DList(); list.prepend(1); passOrFail(7, list, "1 "); }

/** * Test Case 8: tests prepending of multiple elements to a nonempty list. */ private void testCase8() { System.out.print("Running test case 8... "); DList list = new DList(); list.prepend(1); list.prepend(2); list.prepend(3); list.prepend(4); list.prepend(5); list.prepend(6); passOrFail(8, list, "6 5 4 3 2 1 "); }

/** * Test Case 9: tests that get(index) throws an IndexOutOfBoundsException when an invalid * index is passed on an empty list. */ private void testCase9() { System.out.print("Running test case 9... "); DList list = new DList(); try { Integer i = list.get(0); } catch (IndexOutOfBoundsException pExcept) { System.out.println("passed"); } }

/** * Test Case 10: tests that get(index) throws an IndexOutOfBoundsException when an invalid * index < 0 is passed on a nonempty list. */ private void testCase10() { System.out.print("Running test case 10... "); DList list = new DList(); list.append(1); list.append(2); list.append(3); try { Integer i = list.get(-1); } catch (IndexOutOfBoundsException pExcept) { System.out.println("passed"); } }

/** * Test Case 11: tests that get(index) throws an IndexOutOfBoundsException when an invalid * index >= list.getSize() is passed on a nonempty list. */ private void testCase11() { System.out.print("Running test case 11... "); DList list = new DList(); list.append(1); list.append(2); list.append(3); try { Integer i = list.get(3); } catch (IndexOutOfBoundsException pExcept) { System.out.println("passed"); } }

/** * Test Case 12: tests that remove(index) throws an IndexOutOfBoundsException when an invalid * index is passed on a empty list. */ private void testCase12() { System.out.print("Running test case 12... "); DList list = new DList(); try { Integer i = list.remove(0); } catch (IndexOutOfBoundsException pExcept) { System.out.println("passed"); } }

/** * Test Case 13: tests that remove(index) throws an IndexOutOfBoundsException when an invalid * index < 0 is passed on a nonempty list. */ private void testCase13() { System.out.print("Running test case 13... "); DList list = new DList(); list.append(1); list.append(2); list.append(3); try { Integer i = list.remove(-1); } catch (IndexOutOfBoundsException pExcept) { System.out.println("passed"); } }

/** * Test Case 14: tests that remove(index) throws an IndexOutOfBoundsException when an invalid * index >= list.getSize() is passed on a nonempty list. */ private void testCase14() { System.out.print("Running test case 14... "); DList list = new DList(); list.append(1); list.append(2); list.append(3); try { Integer i = list.remove(3); } catch (IndexOutOfBoundsException pExcept) { System.out.println("passed"); } }

/** * Test Case 15: tests that remove(index) removes the element at index 0 in a list of size 1. */ private void testCase15() { System.out.print("Running test case 15... "); DList list = new DList(); list.append(1); Integer i = list.remove(0); if (i != 1) System.out.println("failed"); passOrFail(15, list, ""); }

/** * Test Case 16: tests that remove(index) removes the element at index 0 in a nonempty list. */ private void testCase16() { System.out.print("Running test case 16... "); DList list = new DList(); list.append(1); list.append(2); list.append(3); list.append(4); Integer i = list.remove(0); if (i != 1) System.out.println("failed"); passOrFail(16, list, "2 3 4 "); }

/** * Test Case 17: tests that remove(index) removes the element at the end of a nonempty list. */ private void testCase17() { System.out.print("Running test case 17... "); DList list = new DList(); list.append(1); list.append(2); list.append(3); list.append(4); Integer i = list.remove(3); if (i != 4) System.out.println("failed"); passOrFail(17, list, "1 2 3 "); }

/** * Test Case 18: tests that remove(index) removes the elements from the middle of a nonempty * list. */ private void testCase18() { System.out.print("Running test case 18... "); DList list = new DList(); list.append(1); list.append(2); list.append(3); list.append(4); list.append(5); list.append(6); list.append(7); list.append(8); list.append(9); Integer i = list.remove(2); if (i != 3) System.out.println("failed"); i = list.remove(4); if (i != 6) System.out.println("failed"); i = list.remove(5); if (i != 8) System.out.println("failed"); passOrFail(18, list, "1 2 4 5 7 9 "); }

/** * Test Case 19/20: tests that clear erases the list. */ private void testCase19() { System.out.print("Running test case 19... "); DList list = new DList(); list.append(1); list.append(2); list.append(3); list.append(4); list.append(5); list.append(6); list.append(7); list.append(8); list.append(9); list.clear(); passOrFail(19, list, ""); System.out.print("Running test case 20... "); list.add(0, 8); list.append(9); list.append(9); list.append(9); passOrFail(20, list, "8 9 9 9 "); } }