import java.util.*;/** * An interface for the lists for Oblig4. All 4 lists are implementing this interface, and must * implement all the listed functions. */public interface IfiCollection extends Iterable { /** * Adds the specified element to the list. <p> * Where in the list the element is inserted depends on the type of list, i.e * for the sorted lists the new list has to remain sorted after insertion. For an * unsorted list, the location is unspecified. * * @param o element to be appended to this list. */ public void add(Object o); /** * Clears the list of elements. */ public void clear(); /** * Returns an iterator over the elements in this list in proper sequence. * @see <a href="http://java.sun.com/j2se/1.5.0/docs/api/java/util/Iterator.html">Iterator</a> * * @return an iterator over the elements in this list in proper sequence. */ public Iterator iterator(); /** Removes the first occurrence in this list of the specified element * (optional operation). If this list does not contain the element, it is * unchanged. * * @param o element to be removed from this list, if present. * @return <tt>true</tt> if this list contained the specified element. * @throws UnsupportedOperationException if the <tt>remove</tt> method is * not supported by this list. */ public boolean remove(Object o); /** * Returns the number of elements in this list. * * @return the number of elements in this list. */ public int size(); /** * * Returns <tt>true</tt> if this list contains the specified element. * * @param o element whose presence in this list is to be tested. * @return <tt>true</tt> if this list contains the specified element. */ public boolean contains(Object o); /** * Returns <tt>true</tt> if this list contains no elements. * * @return <tt>true</tt> if this list contains no elements. */ public boolean isEmpty();}abstract class IfiLinkedList implements IfiCollection { Link first; int size; public abstract void add(Object o); public void clear() { first = null; size = 0; } public Iterator iterator() { return new ListIterator(); } public boolean remove(Object o) { Link current = first; while (current != null) { if (current.data.equals(o)) { if (current.next != null) current.next.prev = current.prev; if (current.prev != null) current.prev.next = current.next; size--; return true; } current = current.next; } return false; } public int size() { return size; } public boolean contains(Object o) { Link current = first; while (current != null) { if (current.data.equals(o)) return true; current = current.next; } return false; } public boolean isEmpty() { if (first == null) return true; return false; } protected class Link { Link next, prev; Object data; Link(Link prev, Link next, Object data) { this.next = next; this.prev = prev; this.data = data; } } protected class ListIterator implements Iterator { Link currentLink, nextLink = first; public Object next() throws NoSuchElementException { if (!hasNext()) throw new NoSuchElementException(); currentLink = nextLink; nextLink = nextLink.next; return currentLink.data; } public boolean hasNext() { if (nextLink != null) return true; return false; } public void remove() throws IllegalStateException { if (currentLink == null) throw new IllegalStateException(); if (currentLink == first) { first = currentLink.next; } else { currentLink.prev.next = nextLink; currentLink.next.prev = currentLink.prev; currentLink = null; } size--; } }}abstract class IfiArrayList implements IfiCollection, Iterable { Object[] list; int size = 0; IfiArrayList() { clear(); } public void checkIncSize() { if (list.length == size) { Object[] newList = new Object[list.length*2]; for (int i = 0; i < size; i++) newList[i] = list[i]; list = newList; } } public void clear() { list = new Object[5000]; size = 0; } public Iterator iterator() { return new ArrayIterator(); } public abstract boolean remove(Object o); public int size() { return size; } public boolean contains(Object o) { for (int i = 0; i < size; i++) if (list[i].equals(o)) return true; return false; } public boolean isEmpty() { if (size > 0) return false; return true; } protected class ArrayIterator implements Iterator { int place = 0; public Object next() throws NoSuchElementException { if (!hasNext()) throw new NoSuchElementException(); return list[place++]; } public boolean hasNext() { if (place == size) return false; return true; } public void remove() throws IllegalStateException, UnsupportedOperationException { throw new UnsupportedOperationException(); } }}class UnorderedLinkedList extends IfiLinkedList { public void add(Object o) { first = new Link(null, first, o); size++; }}class OrderedLinkedList extends IfiLinkedList { public void add(Object o) { // Add the first element if the list is empty. if (isEmpty()) { first = new Link(null, null, o); size++; return; } // Iterate through, add the link at the correct place. Link current = first, last; while (current != null) { int compare = ((Comparable) o).compareTo(current.data); if (compare == -1) { Link newLink = new Link(current, current.next, o); if (current != first) current.prev.next = newLink; if (current.next != null) current.next.prev = newLink; size++; return; } if (current.next == null) { last = new Link(current, null, o); if (current != first) current.prev.next = last; size++; return; } current = current.next; } }}class UnorderedArrayList extends IfiArrayList { public void add(Object o) { checkIncSize(); list[size++] = o; } public boolean remove(Object o) { for (int i = 0; i < size; i++) { if (list[i].equals(o)) { list[i] = list[size-1]; list[--size] = null; return true; } } return false; }}class OrderedArrayList extends IfiArrayList { public void add(Object o) { checkIncSize(); for (int i = 0; i < size; i++) { if (((Comparable) o).compareTo(list[i]) < 0) { for (int j = size-1; j >= i; j--) list[j+1] = list[j]; list[i] = o; size++; return; } } list[size++] = o; } public boolean remove(Object o) { for (int i = 0; i < size; i++) { if (list[i].equals(o)) { for (int j = i; j < size; j++) list[j] = list[j+1]; size--; return true; } } return false; }}