From 0df0340cbc0fd03a8d291f1c7b47078ecbf4d99b Mon Sep 17 00:00:00 2001
From: jjenista <jjenista>
Date: Wed, 25 Feb 2009 00:06:08 +0000
Subject: [PATCH] Quick-and-dirty LinkedList implementation with Iterators that
 other container-ish classes can make their own iterators from

---
 Robust/src/ClassLibrary/Iterator.java   |  11 ++
 Robust/src/ClassLibrary/LinkedList.java | 190 ++++++++++++++++++++++++
 Robust/src/Tests/LinkedListTest.java    |  17 +++
 3 files changed, 218 insertions(+)
 create mode 100644 Robust/src/ClassLibrary/Iterator.java
 create mode 100644 Robust/src/ClassLibrary/LinkedList.java
 create mode 100644 Robust/src/Tests/LinkedListTest.java

diff --git a/Robust/src/ClassLibrary/Iterator.java b/Robust/src/ClassLibrary/Iterator.java
new file mode 100644
index 00000000..0dd24e04
--- /dev/null
+++ b/Robust/src/ClassLibrary/Iterator.java
@@ -0,0 +1,11 @@
+public class Iterator {
+  boolean hasNext() {
+    System.out.println( "Iterator is an abstract class." );
+    System.exit(-1);
+  }
+
+  Object next() {
+    System.out.println( "Iterator is an abstract class." );
+    System.exit(-1);
+  }
+}
diff --git a/Robust/src/ClassLibrary/LinkedList.java b/Robust/src/ClassLibrary/LinkedList.java
new file mode 100644
index 00000000..69356870
--- /dev/null
+++ b/Robust/src/ClassLibrary/LinkedList.java
@@ -0,0 +1,190 @@
+public class LinkedListElement {
+  public LinkedListElement next;
+  public LinkedListElement prev;
+  public Object element;
+
+  public LinkedListElement( Object e,
+			    LinkedListElement n,
+			    LinkedListElement p ) {
+    element = e;
+    next = n;
+    prev = p;
+  }
+}
+
+public class LinkedList {
+  LinkedListElement head;
+  LinkedListElement tail;
+  int size;
+
+  public LinkedList() {
+    clear();
+  }
+
+  public add( Object o ) {
+    if( tail == null ) {
+      head = new LinkedListElement( o, null, null );
+      tail = head;
+
+    } else {
+      tail.next = new LinkedListElement( o, null, tail );
+      tail = tail.next;
+    }
+    size++;
+  }
+
+  public addFirst( Object o ) {
+    if( head == null ) {
+      head = new LinkedListElement( o, null, null );
+      tail = head;
+
+    } else {
+      head.prev = new LinkedListElement( o, head, null );
+      head = head.prev;
+    }
+    size++;
+  }
+
+  public addLast( Object o ) {
+    add( o );
+  }
+
+  public clear() {
+    head = null;
+    tail = null;
+    size = 0;
+  }
+
+  public int size() {
+    return size;
+  }
+
+  public Object clone() {
+    System.out.println( "LinkedList.clone() not implemented." );
+    System.exit(-1);
+  }
+
+  public boolean contains( Object o ) {
+    LinkedListElement e = head;
+    while( e != null ) {
+      if( e.element == o ) {
+	return true;
+      }
+      e = e.next;
+    }
+    return false;
+  }
+
+  public Object getFirst() {
+    if( head == null ) {
+      return null;
+    }
+    return head.element;
+  }
+
+  public Object getLast() {
+    if( tail == null ) {
+      return null;
+    }
+    return tail.element;    
+  }
+
+  public Object element() {
+    getFirst();
+  }
+
+  public Object peek() {
+    getFirst();
+  }
+
+  public Object peekFirst() {
+    getFirst();
+  }
+
+  public Object peekLast() {
+    getLast();
+  }
+
+  public void removeFirst() {
+    if( head == null ) {
+      System.out.println( "LinkedList: illegal removeFirst()" );
+      System.exit(-1);
+    }
+    head = head.next;
+    if( head != null ) {
+      head.prev = null;
+    }
+    size--;
+  }
+
+  public void removeLast() {
+    if( tail == null ) {
+      System.out.println( "LinkedList: illegal removeLast()" );
+      System.exit(-1);
+    }
+    tail = tail.prev;
+    if( tail != null ) {
+      tail.next = null;
+    }
+    size--;
+  }
+
+  public void remove( Object o ) {
+    if( head == null ) {
+      System.out.println( "LinkedList: illegal remove( Object o )" );
+      System.exit(-1);
+    }
+    LinkedListElement e = head;
+    while( e != null ) {
+      if( e.element == o ) {
+	if( e.prev != null ) {
+	  e.prev.next = e.next;
+	}
+	if( e.next != null ) {
+	  e.next.prev = e.prev;
+	}
+	size--;
+	return;
+      }
+      e = e.next;
+    }
+    System.out.println( "LinkedList: illegal remove( Object o ), "+o+" not found" );
+    System.exit(-1);    
+  }
+
+  public Object pop() {
+    Object o = getFirst();
+    removeFirst();
+    return o;
+  }
+
+  public void push( Object o ) {
+    addFirst( o );
+  }
+
+  public Iterator iterator() {
+    return new LinkedListIterator( this );
+  }
+}
+
+public class LinkedListIterator extends Iterator {
+  LinkedListElement itr;
+  
+  public LinkedListIterator( LinkedList ll ) {
+    itr = ll.head;
+  }
+
+  boolean hasNext() {
+    return itr != null;
+  }
+
+  Object next() {
+    if( itr == null ) {
+      System.out.println( "LinkedListIterator: illegal next()" );
+      System.exit(-1);
+    }
+    Object o = itr.element;
+    itr = itr.next;
+    return o;
+  }
+}
diff --git a/Robust/src/Tests/LinkedListTest.java b/Robust/src/Tests/LinkedListTest.java
new file mode 100644
index 00000000..fa3af9da
--- /dev/null
+++ b/Robust/src/Tests/LinkedListTest.java
@@ -0,0 +1,17 @@
+public class LinkedListTest {
+  public static main( String[] args ) {
+
+    LinkedList list = new LinkedList();
+    System.out.println( "list should have zero elements: "+list.size() );
+
+    list.push( (Object)new Integer( 3 ) );
+    list.push( (Object)new Integer( 4 ) );
+
+    System.out.println( "list should have two elements: "+list.size() );
+
+    Integer x = (Integer)list.pop();
+    x = (Integer)list.pop();
+
+    System.out.println( "should be a 3: "+x );
+  }
+}
\ No newline at end of file
-- 
2.34.1