// SortableLinkedList.java

import java.util.Arrays;

@SuppressWarnings("unchecked")
public class SortableLinkedList {

   public static void main(String[] args) {
      testLinkedList();
      testLinkedListSpeed();
   }

   public static void testAbstractListSpeed(java.util.AbstractList list, int n) {
      long time0 = System.currentTimeMillis();
      java.util.Random random = new java.util.Random();
      for (int i=0; i<n; i++)
         list.add(random.nextInt());
      java.util.Collections.sort(list);
      long time1 = System.currentTimeMillis();
      System.out.println("Time = " + (time1 - time0) + "ms");
   }

   public static void testLinkedListSpeed() {
      int n = 1000*10;
      System.out.print("Testing speed using ArrayLists:  ");
      testAbstractListSpeed(new java.util.ArrayList(), n);
      System.out.print("Testing speed using LinkedLists:  ");
      testAbstractListSpeed(new LinkedList(), n);
   }

   public static void testLinkedList() {
      LinkedList a = new LinkedList();
      assert(a.size() == 0);

      try { a.get(-1); assert(false); }
      catch (Exception e1) { assert(e1 instanceof IndexOutOfBoundsException); }

      try { a.set(-1,"foo"); assert(false); }
      catch (IndexOutOfBoundsException e) { /* do nothing */ }
      catch (Exception e1) { assert(false); }

      a.add("foo");
      assert(a.size() == 1);
      assert(a.get(0).equals("foo"));
      assert(a.toString().equals("[foo]"));

      try { a.get(1); assert(false); }
      catch (Exception e1) { assert(e1 instanceof IndexOutOfBoundsException); }

      a.add("bar");
      assert(a.size() == 2);
      assert(a.get(0).equals("foo"));
      assert(a.get(1).equals("bar"));
      assert(a.toString().equals("[foo, bar]"));

      Object oldValue = a.set(1,"blat");
      assert(oldValue.equals("bar"));
      assert(a.size() == 2);
      assert(a.get(0).equals("foo"));
      assert(a.get(1).equals("blat"));
      assert(a.toString().equals("[foo, blat]"));

      java.util.Collections.sort(a);
      assert(a.size() == 2);
      assert(a.get(0).equals("blat"));
      assert(a.get(1).equals("foo"));
      assert(a.toString().equals("[blat, foo]"));
      System.out.println("Passed all LinkedList tests");
   }
}

class LinkedList extends java.util.AbstractList {
   private Node head;

   private Node getLastNode() {
      if (head == null) return null;
      Node node = head;
      while (node.next != null)
         node = node.next;
      return node;
   }

   // add to the end
   public boolean add(Object obj) {
      Node newNode = new Node();
      newNode.value = obj;
      if (head == null)
         head = newNode;
      else {
         Node lastNode = getLastNode();
         lastNode.next = newNode;
      }
      return true; // to abide by the API contract
   }

   public Object get(int index) {
      if (index < 0) throw new IndexOutOfBoundsException("Index out of bounds: " + index);
      int counter = 0;
      for (Node node=head; node!=null; node=node.next) {
         if (counter == index)
            return node.value;
         counter++;
      }
      throw new IndexOutOfBoundsException("Index out of bounds: " + index);
   }

   public Object set(int index, Object newValue) {
      if (index < 0) throw new IndexOutOfBoundsException("Index out of bounds: " + index);
      int counter = 0;
      for (Node node=head; node!=null; node=node.next) {
         if (counter == index) {
            Object oldValue = node.value;
            node.value = newValue;
            return oldValue;
         }
         counter++;
      }
      throw new IndexOutOfBoundsException("Index out of bounds: " + index);
   }

   public int size() {
      int counter = 0;
      for (Node node=head; node!=null; node=node.next)
         counter++;
      return counter;
   }

   public String toString() {
      StringBuffer sb = new StringBuffer("[");
      int counter = 0;
      for (Node node=head; node!=null; node=node.next) {
         if (counter > 0) sb.append(", ");
         counter++;
         sb.append(node.value);
      }
      sb.append("]");
      return sb.toString();
   }
}

class Node {
   public Object value;
   public Node next;
}