Lab 5 Feedback
Marking scheme:
--------------------
1.2 / 2 -some unit tests failed; TAs, please check for errors
--------------------
TA Comments:
-why is there a loop in removeFirst? all you need to do is remove the
head node of the list
-in removeLast, if the size of the list is 1 then after removing the
node this.head and this.tail should both be null
-in remove there are 3 cases to consider:
1. is index == 0?
-if so then use removeFirst
2. is index == this.size - 1?
-if so then use removeLast
3. is index > 0 && index < this.size - 1?
-if so then use getNode(index - 1) to get the get the
node before the one that you need to remove and set
that node so that its next link is the node after
the one that you want to remove
-in shiftRight you should perform the following steps:
1. compute the index of the new tail node; this is equal to:
int newTailIndex = this.size() - n - 1;
2. join the current tail to the current head:
this.tail.setNext(this.head);
3. set the new tail:
this.tail = this.getNode(newTailIndex);
4. set the new head:
this.head = this.tail.getNext();
5. make sure the new tail has no next link:
this.tail.setNext(null);
--------------------
Style checker output:
No style errors found by checkstyle; TAs, please check for poorly named
variables, unusual programming constructs, and other style errors.
--------------------
Unit tester output:
YOUR SUMBISSION FAILED SOME UNIT TESTS
Here is the test output:
java -classpath .:/home/burton/work/teaching/2017F/2030/marking/lab5/_jar/* org.junit.runner.JUnitCore eecs2030.lab5.Lab5Suite
JUnit version 4.12
.............E.E.E.E.E.E.E
Time: 0.04
There were 7 failures:
1) test12_removeFirst(eecs2030.lab5.LinkedIntListTest)
java.lang.AssertionError: list has the wrong size; expected size: 9, got size: 0
2) test13_removeLast(eecs2030.lab5.LinkedIntListTest)
java.lang.AssertionError: expected an empty list; got a list with a non-null head node
3) test14_remove(eecs2030.lab5.LinkedIntListTest)
java.lang.AssertionError: remove(0) should have thrown an exception for the empty list
4) test15_remove(eecs2030.lab5.LinkedIntListTest)
java.lang.AssertionError: remove(4) should have thrown an exception for a list of size 4
5) test16_remove(eecs2030.lab5.LinkedIntListTest)
java.lang.AssertionError: expected an empty list; got a list of size: 1
6) test17_remove(eecs2030.lab5.LinkedIntListTest)
java.lang.AssertionError: list has the wrong size; expected size: 19, got size: 20
7) test18_shiftRight(eecs2030.lab5.LinkedIntListTest)
java.lang.AssertionError: list has the wrong size; expected size: 5, got size: 6
FAILURES!!!
Tests run: 19, Failures: 7
--------------------
Your submission:
package eecs2030.lab5;
import java.util.NoSuchElementException;
/**
* A linked list of int values. Students should use the eecs2030.lab5.Node class
* to represent nodes of this list.
*
* <p>
* This implementation keeps track of the first (head) and last (tail) node of
* the linked list. All methods that add or remove nodes from the list may have
* to update the fields this.head, this.tail, and this.size
*/
public class LinkedIntList {
private int size;
private Node head;
private Node tail;
/**
* Initializes this linked list to an empty list.
*/
public LinkedIntList() {
this.size = 0;
this.head = null;
this.tail = null;
}
/**
* Returns a reference to the first node of the list (the head node).
*
* <p>
* NOTE: This method causes a privacy leak and would not normally be part of the
* public API; however, it is useful for testing purposes.
*
* @return a reference to the first node of the list
*/
public Node head() {
return this.head;
}
/**
* Returns a reference to the last node of the list (the tail node).
*
* <p>
* NOTE: This method causes a privacy leak and would not normally be part of the
* public API; however, it is useful for testing purposes.
*
* @return a reference to the last node of the list
*/
public Node tail() {
return this.tail;
}
/**
* Throws an IndexOutOfBoundsException exception if idx is less than zero or
* greater than (this.size - 1)
*
* @param idx
* an index to check
* @throws IndexOutOfBoundsException
* exception if idx is less than zero or greater than (this.size -
* 1)
*/
private void checkIndex(int idx) {
if (idx < 0 || idx > this.size - 1) {
throw new IndexOutOfBoundsException(String.format("index: %d, size: %d", idx, this.size));
}
}
/**
* Throws a NoSuchElementException if the list is empty.
*
* @throws NoSuchElementException
* if the list is empty
*/
private void checkNotEmpty() {
if (this.isEmpty()) {
throw new NoSuchElementException();
}
}
/**
* Returns a string representation of this list similar to the string returned
* by java.util.List.toString.
*
* @return a string representation of this list
*/
public String toString() {
StringBuilder b = new StringBuilder("[");
if (this.size > 0) {
Node n = this.head;
b.append(n.getData());
n = n.getNext();
while (n != null) {
b.append(", ");
b.append(n.getData());
n = n.getNext();
}
} else {
b.append("empty");
}
b.append("]");
return b.toString();
}
/**
* Returns the number of elements in this list.
*
* @return the number of elements in this list
*/
public int size() {
return this.size;
}
/**
* Returns true if the size of this list is zero, and false otherwise.
*
* @return true if the size of this list is zero, and false otherwise
*/
public boolean isEmpty() {
if (this.size == 0) {
return true;
}
return false;
}
/**
* Add an element to the end of this linked list.
*
* @param elem
* the element to add to the end of this linked list
* @return true (to be consistent with java.util.Collection)
*/
public boolean add(int elem) {
Node p = new Node(elem, null);
if (this.head == null) {
this.head = p;
this.tail = p;
this.size++;
return true;
} else {
Node n = this.head;
// n = n.getNext();
while (n.getNext() != null) {
n = n.getNext();
}
n.setNext(p);
this.size++;
this.tail = p;
return true;
}
}
/**
* Returns the node at the given index.
*
* <p>
* NOTE: This method is extremely useful for implementing many of the methods of
* this class, but students should try to use this method only once in each
* method.
*
* <p>
* NOTE: This method causes a privacy leak and would not normally be part of the
* public API; however, it is useful for testing purposes.
*
* @param index
* the index of the node
* @return the node at the given index
* @throws IndexOutOfBoundsException
* if index is less than 0 or greater than or equal the size of this
* list
*/
public Node getNode(int index) throws java.lang.IndexOutOfBoundsException {
if (index < 0 || this.size <= index) {
throw new java.lang.IndexOutOfBoundsException();
}
Node p = this.head;
int i;
for (i = 0; i < index; i++) {
p = p.getNext();
}
return p;
}
/**
* Get the element stored at the given index in this linked list.
*
* @param index
* the index of the element to get
* @return the element stored at the given index in this linked list
* @throws IndexOutOfBoundsException
* if (index < 0) || (index > size - 1)
*/
public int get(int index) {
Node m = this.getNode(index);
return m.getData();
}
/**
* Sets the element stored at the given index in this linked list. Returns the
* old element that was stored at the given index.
*
* @param index
* the index of the element to set
* @param elem
* the element to store in this linked list
* @return the old element that was stored at the given index
* @throws IndexOutOfBoundsException
* if (index < 0) || (index > size - 1)
*/
public int set(int index, int elem) {
Node p = this.getNode(index);
int i = p.getData();
p.setData(elem);
return i;
}
/**
* Insert an element to the front of this list.
*
* @param elem
* the element to insert at the front of this list
*/
public void addFirst(int elem) {
this.add(elem);
int i = 0;
int j = elem;
while (i < this.size) {
j = this.set(i, j);
i++;
}
}
/**
* Inserts the specified element at the specified position in this list. Shifts
* the element currently at that position (if any) and any subsequent elements
* to the right (adds one to their indices).
*
* <p>
* <code>t.add(0, elem)</code> is equivalent to <code>t.addFront(elem)</code>.
*
* <p>
* <code>t.add(t.size(), elem)</code> is equivalent to <code>t.add(elem)</code>.
*
* @param index
* index at which the specified element is to be inserted
* @param elem
* the element to be inserted
* @throws IndexOutOfBoundsException
* if the index is out of range (index < 0 || index > size())
*/
public void add(int index, int elem) throws IndexOutOfBoundsException {
if (index < 0 || index > this.size) {
throw new IndexOutOfBoundsException();
}
this.add(elem);
int i = index;
int j = elem;
while (i < this.size) {
j = this.set(i, j);
i++;
}
}
/**
* Removes and returns the first element from this list.
*
* @return the first element from this list
* @throws NoSuchElementException
* if this list is empty
*/
public int removeFirst() throws NoSuchElementException {
int i = this.size - 1;
if (i < 0) {
throw new NoSuchElementException();
}
if (i < 1) {
int l = this.head.getData();
i--;
this.size = i + 1;
return l;
}
else {
int j = 0;
while (i >= 0) {
j = this.set(i, j);
i--;
}
Node p = this.getNode(this.size - 2);
p.setNext(null);
this.tail = p;
this.head = this.getNode(0);
this.size = i + 1;
return j;
}
}
/**
* Removes and returns the last element from this list.
*
* @return the last element from this list
* @throws NoSuchElementException
* if this list is empty
*/
public int removeLast() throws NoSuchElementException {
if (this.size == 0) {
throw new NoSuchElementException();
}
if (this.size == 1) {
int j = this.getNode(0).getData();
this.tail = this.head;
this.size--;
return j;
}
else {
Node p = this.getNode(this.size - 2);
Node i = this.getNode(this.size - 1);
int k = i.getData();
p.setNext(null);
this.tail = p;
this.size--;
return k;
}
}
/**
* Removes the element at the specified position in this list. Shifts any
* subsequent elements to the left (subtracts one from their indices). Returns
* the element that was removed from the list.
*
* <p>
* <code>t.remove(0)</code> is equivalent to <code>t.removeFirst()</code> except
* that a different exception might be thrown.
*
* <p>
* <code>t.remove(t.size() - 1)</code> is equivalent to
* <code>t.removeLast()</code> except that a different exception might be
* thrown.
*
* @param index
* the index of the element to be removed
* @return the removed element
* @throws IndexOutOfBoundsException
* if the index is out of range (index < 0 || index >= size())
*/
public int remove(int index) {
return 0;
}
/**
* Circularly shifts the elements of this list to the right by n positions
* causing the n elements at the end of the original list to appear at the front
* of the resulting list. For example, if <code>t</code> is the list:
*
* <pre>
* [0, 1, 2, 3, 4, 5]
* </pre>
*
* <p>
* then <code>t.shiftRight(2)</code> results in <code>t</code> being equal to:
*
* <pre>
* [4, 5, 0, 1, 2, 3]
* </pre>
*
* <p>
* <code>t.shiftRight(0)</code> and <code>t.shiftRight(t.size())</code> both
* leave <code>t</code> unchanged.
*
* @param n
* the number of positions to shift the elements
* @throws IllegalArgumentException
* if n is out of range (n < 0 || n > size())
*/
public void shiftRight(int n) throws IllegalArgumentException {
if (n < 0 || n > size()) {
throw new IllegalArgumentException();
}
int i = this.size;
for (int j = i - 1; j >= (i - n); j--) {
int t = i;
int k = this.get(j);
this.addFirst(k);
Node p = this.head;
while (t > 1) {
p = p.getNext();
t--;
}
p.setNext(null);
}
}
}