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, last; int size; public abstract void add(Object o); public void clear() { first = null; } public Iterator iterator() { return new ListIterator(); } public boolean remove(Object o) { 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 next, Link prev, Object data) { this.next = next; this.prev = prev; this.data = data; } } protected class ListIterator implements Iterator { Link next, current; public Object next() throws NoSuchElementException { if (!hasNext()) throw new NoSuchElementException(); return next.data; } public boolean hasNext() { if (next != null) return true; return false; } public void remove() throws IllegalStateException, UnsupportedOperationException { throw new UnsupportedOperationException(); } }}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(first, null, o); size++; // øker antall i lista. }}class OrderedLinkedList extends IfiLinkedList { public void add(Object o) { Link current = first; while (current != null) { if (((Comparable) o).compareTo(current.data) < 0) { Link l = new Link(current, current.prev, o); current.prev.next = l; // oppdaterer pekere current.next.prev = l; size++; // øker antall i lista. return; } current = current.next; } }}class UnorderedArrayList extends IfiArrayList { public void add(Object o) { checkIncSize(); list[size++] = o; } public boolean remove(Object o) { 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) { return false; }}