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; }
}