/* RetroLinkedList.java provides a 1.1 version of LinkedList
 *  it implements some of the Java 1.2 List interface
 * Author: Charles Hoot, for Hands On Java.
 * Date:   July 2000
 *
 */

import java.util.*;

public class RetroLinkedList extends Object {
	
	private Node first, last;
	private int mySize;
	
	public RetroLinkedList() {
		first = null;
		last = null;
		mySize = 0;
	}
	
	public void add(int index, Object element) {
		Node scout = first;
		
		if(mySize == 0){						//special case empty
			Node newNode = new Node(element, null, null);
			first = newNode;
			last = newNode;
		}
		
		if(index == 0) {						// special case at front
			Node newNode = new Node(element, null, first);
			first.prev = newNode;
			first = newNode;
			return;
		}

		if(index == mySize) {					// special case at end
			Node newNode = new Node(element, last, null);
			last.next = newNode;
			last = newNode;
			return;
		}
		
		// find node before
		for(int i=0; i<index-1; i++)
			scout = scout.next;
			
		Node newNode = new Node(element, scout, scout.next);
		scout.next.prev = newNode;
		scout.next = newNode;
		mySize++;
	}
	
	// add at end of list
	public boolean add(Object o) {
		add(mySize, o);
		return true;
	}
	
	public void clear() {
		first = null;
		last = null;
		mySize = 0;
	}
	
	public Object clone () {
		RetroLinkedList aCopy = new RetroLinkedList();
		//This is not an efficient implementation
		for(int i=0; i<mySize; i++) {
			add(get(i));
		}
		return aCopy;
			
	}
	
	public boolean contains(Object elem){
		Node scout = first;
		for(int i=0; i<mySize; i++){
			if(scout.data.equals(elem)) return true;
			scout = scout.next;
		}
		return false;
	}
		
	
	public int indexOf(Object elem){
		Node scout = first;
		for(int i=0; i<mySize; i++){
			if(scout.data.equals(elem)) return i;
			scout = scout.next;
		}
		return -1;
	}
	
	public int lastIndexOf(Object elem){
		int lastWas = -1;
		Node scout = last;
		for(int i=mySize-1; i>=0; i++){
			if(scout.data.equals(elem)) return i;
			scout = scout.prev;
		}
		return -1;
	}
	
			
	public int size(){
		return mySize;
	}
	
	public boolean isEmpty(){
		return mySize == 0;
	}
	
	public Object get(int index){
		Node scout = first;
		for(int i=0; i<index; i++){
			scout = scout.next;
		}
		return scout.data;
	}
	
	public Object set(int index, Object element){
		Node scout = first;
		for(int i=0; i<index; i++){
			scout = scout.next;
		}

		Object previous = scout.data;
		scout.data = element;
		return previous;
	}
                  
    public Object remove(int index){
		Node scout = first;
		
		if(mySize == 1){						//special case singleton
			Node toRemove = first;
			first = null;
			last = null;
			return toRemove;
		}
		
		if(index == 0) {				// special case at front
			Node toRemove = first;
			first = toRemove.next;
			first.prev = null;
			return toRemove;
		}

		if(index == mySize-1) {				// special case at end
			Node toRemove = last;
			last = toRemove.prev;
			last.next = null;
			return toRemove;
		}
		
		// find node before
		for(int i=0; i<index-1; i++)
			scout = scout.next;
			
		Node toRemove = scout.next;
		scout.next = toRemove.next;
		scout.next.prev = scout;
		mySize--;
		return toRemove;
	}
	
}

/* he following is a private class that defines a doubly linked node in
 * our linked list.
 * We will grant RetroLinkedList access to the attributes since no other class
 * will be allowed access to us
 */
 
 class Node {
 	public Object data;
 	public Node next, prev;
 	
 	
 	public Node(Object value, Node prevLink, Node nextLink){
 		data = value;
 		prev = prevLink;
 		next = nextLink;
 	}
}