<![CDATA[
CSE143 IntList Code handout #29
Interface Iterator<E> from java.util
------------------------------------
public interface Iterator<E> {
public boolean hasNext();
public E next();
public void remove();
}
Interface Iterable<E> from java.lang
------------------------------------
public interface Iterable<E> {
public Iterator<E> iterator();
}
Interface IntList.java
----------------------
// The IntList interface defines a set of operations for an ordered collection
// (sequence) of integers.
public interface IntList extends Iterable<Integer> {
public int size();
public int get(int index);
public int indexOf(int value);
public boolean isEmpty();
public boolean contains(int value);
public void add(int value);
public void add(int index, int value);
public void addAll(IntList other);
public void remove(int index);
public void removeAll(IntList other);
public void set(int index, int value);
public void clear();
}
Class AbstractIntList.java
--------------------------
// AbstractIntList provides a skeletal implementation of the IntList class.
// Many operations are defined in terms of the list iterator. Subclasses
// need to define size(), get(int index), add(int value), add(index, value),
// remove(index), set(index, value), clear(), ensureCapacity() and iterator().
import java.util.*;
public abstract class AbstractIntList implements IntList {
// post: returns a comma-separated, bracketed version of the list
public String toString() {
Iterator<Integer> i = iterator();
String result = "[";
if (i.hasNext()) {
result += i.next();
while (i.hasNext())
result += ", " + i.next();
}
result += "]";
return result;
}
// post : returns the position of the first occurence of the given
// value (-1 if not found)
public int indexOf(int value) {
int index = 0;
for (int i : this) {
if (i == value)
return index;
index++;
}
return -1;
}
// post: returns true if list is empty, false otherwise
public boolean isEmpty() {
return !iterator().hasNext();
}
// post: returns true if the given value is contained in the list,
// false otherwise
public boolean contains(int value) {
return indexOf(value) != -1;
}
// post: appends all values in the given list to the end of this list
public void addAll(IntList other) {
for (int i : other)
add(i);
}
// post: removes all occurrences of the values in the given list from
// this list
public void removeAll(IntList other) {
Iterator<Integer> i = iterator();
while (i.hasNext())
if (other.contains(i.next()))
i.remove();
}
// post: throws an exception if the given index is out of range
protected void checkIndex(int index) {
if (index < 0 || index >= size())
throw new IndexOutOfBoundsException("illegal index: " + index);
}
}
Class ArrayIntList.java
-----------------------
import java.util.*;
public class ArrayIntList extends AbstractIntList {
private int[] elementData; // list of integers
private int size; // current number of elements in the list
public static final int DEFAULT_CAPACITY = 100;
// post: constructs an empty list of default capacity
public ArrayIntList() {
this(DEFAULT_CAPACITY);
}
// pre : capacity >= 0
// post: constructs an empty list with the given capacity
public ArrayIntList(int capacity) {
if (capacity < 0)
throw new IllegalArgumentException("negative capacity");
elementData = new int[capacity];
size = 0;
}
// post: returns the current number of elements in the list
public int size() {
return size;
}
// pre : 0 <= index < size()
// post: returns the integer at the given index in the list
public int get(int index) {
checkIndex(index);
return elementData[index];
}
// post: appends the given value to the end of the list
public void add(int value) {
ensureCapacity(size + 1);
elementData[size] = value;
size++;
}
// pre: 0 <= index <= size()
// post: inserts the given value at the given index, shifting subsequent
// values right
public void add(int index, int value) {
ensureCapacity(size + 1);
for (int i = size; i > index; i--)
elementData[i] = elementData[i - 1];
elementData[index] = value;
size++;
}
// pre : 0 <= index < size()
// post: removes value at the given index, shifting subsequent values left
public void remove(int index) {
checkIndex(index);
for (int i = index; i < size - 1; i++)
elementData[i] = elementData[i + 1];
size--;
}
public void set(int index, int value) {
checkIndex(index);
elementData[index] = value;
}
public void clear() {
size = 0;
}
public void ensureCapacity(int capacity) {
if (capacity > elementData.length) {
int newCapacity = elementData.length * 2 + 1;
if (capacity > newCapacity)
newCapacity = capacity;
int[] newList = new int[newCapacity];
for (int i = 0; i < size; i++)
newList[i] = elementData[i];
elementData = newList;
}
}
public Iterator<Integer> iterator() {
return new ArrayIterator();
}
private class ArrayIterator implements Iterator<Integer> {
private int position; // current position within the list
private boolean removeOK; // whether it's okay to remove now
// post: constructs an iterator for the given list
public ArrayIterator() {
position = 0;
removeOK = false;
}
public boolean hasNext() {
return position < size();
}
public Integer next() {
if (!hasNext())
throw new NoSuchElementException();
int result = get(position);
position++;
removeOK = true;
return result;
}
public void remove() {
if (!removeOK)
throw new IllegalStateException();
ArrayIntList.this.remove(position - 1);
position--;
removeOK = false;
}
}
}
Class LinkedIntList.java
------------------------
// LinkedIntList provides an implementation of the IntList interface backed by
// a doubly-linked list. This will provide O(1) performance for adding at the
// front or back of the list and removing values while iterating over the list.
// All of the iterator's methods are O(1). Methods like get and set will
// be O(n) for values in the middle of the list.
import java.util.*;
public class LinkedIntList extends AbstractIntList {
private ListNode front; // first value in the list
private ListNode back; // last value in the list
private int size; // current number of elements
// post: constructs an empty list
public LinkedIntList() {
clear();
}
// post: returns the current number of elements in the list
public int size() {
return size;
}
// pre : 0 <= index < size()
// post: returns the integer at the given index in the list
public int get(int index) {
checkIndex(index);
ListNode current = gotoIndex(index);
return current.data;
}
// post: appends the given value to the end of the list
public void add(int value) {
if (front == null) {
front = new ListNode(value);
back = front;
} else {
back.next = new ListNode(value, null, back);
back = back.next;
}
size++;
}
// pre: 0 <= index <= size()
// post: inserts the given value at the given index, shifting subsequent
// values right
public void add(int index, int value) {
if (index < 0 || index > size)
throw new IndexOutOfBoundsException("illegal index");
if (index == 0)
addFirst(value);
else if (index == size)
add(value);
else {
ListNode current = gotoIndex(index - 1);
ListNode newNode = new ListNode(value, current.next, current);
current.next = newNode;
newNode.next.prev = newNode;
size++;
}
}
// add value as new first element of the list
private void addFirst(int value) {
front = new ListNode(value, front, null);
if (front.next != null)
front.next.prev = front;
if (back == null)
back = front;
size++;
}
// pre : 0 <= index < size()
// post: removes value at the given index, shifting subsequent values left
public void remove(int index) {
checkIndex(index);
if (index == 0)
removeFirst();
else if (index == size - 1)
removeLast();
else {
ListNode current = gotoIndex(index - 1);
current.next = current.next.next;
current.next.prev = current;
size--;
}
}
// pre : list is not empty
// post: removes the first value of the list
private void removeFirst() {
front = front.next;
if (front == null)
back = null;
else
front.prev = null;
size--;
}
// pre : list is not empty
// post: removes the last value of the list
private void removeLast() {
back = back.prev;
if (back == null)
front = null;
else
back.next = null;
size--;
}
// pre : 0 <= index < size()
// post: replaces the integer at the given index with the given value
public void set(int index, int value) {
checkIndex(index);
ListNode current = gotoIndex(index);
current.data = value;
}
// post: list is empty
public void clear() {
front = null;
back = null;
size = 0;
}
// post: returns an iterator for this list
public Iterator<Integer> iterator() {
return new LinkedIterator();
}
// pre : 0 <= index < size()
// post: returns the node at a specific index. Uses the fact that the list
// is doubly-linked to start from the front or the back, whichever
// is closer.
private ListNode gotoIndex(int index) {
ListNode current;
if (index < size / 2) {
current = front;
for (int i = 0; i < index; i++)
current = current.next;
} else {
current = back;
for (int i = size - 1; i > index; i--)
current = current.prev;
}
return current;
}
private static class ListNode {
public int data; // data stored in this node
public ListNode next; // link to next node in the list
public ListNode prev; // link to previous node in the list
// post: constructs a node with given data and null links
public ListNode(int data) {
this(data, null, null);
}
// post: constructs a node with given data and given links
public ListNode(int data, ListNode next, ListNode prev) {
this.data = data;
this.next = next;
this.prev = prev;
}
}
private class LinkedIterator implements Iterator<Integer> {
private ListNode current; // location of next value to return
private boolean removeOK; // whether it's okay to remove now
// post: constructs an iterator for the given list
public LinkedIterator() {
current = front;
removeOK = false;
}
// post: returns true if there are more elements left, false otherwise
public boolean hasNext() {
return current != null;
}
// pre : hasNext()
// post: returns the next element in the iteration
public Integer next() {
if (!hasNext())
throw new NoSuchElementException();
int result = current.data;
current = current.next;
removeOK = true;
return result;
}
// pre : next() has been called without a call on remove (i.e., at most
// one call per call on next)
// post: removes the last element returned by the iterator
public void remove() {
if (!removeOK)
throw new IllegalStateException();
// allow outer class to handle front/back cases
if (current == null)
removeLast();
else if (current.prev == front)
removeFirst();
else {
ListNode prev2 = current.prev.prev;
prev2.next = current;
current.prev = prev2;
size--;
}
removeOK = false;
}
}
}
]]>