import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Scanner;


/**
 * Hybrid list structure that utilizes a linked structure of ArrayLists
 *   @author Dave Reed
 *   @version 10/23/15
 */
public class HybridList<T> {
    private int defaultSize;
    private ArrayListNode front;
    private ArrayListNode back;
    private int numStored;
    
    /**
     * Constructs a HybridList with internal lists of specified default size.
     * @param defaultSize the default size for internal lists
     */
    public HybridList(int defaultSize) {
        this.defaultSize = defaultSize;
        this.front = null;
        this.back = null;
        this.numStored = 0;
    }
    
    /**
     * Accessor method for the list size.
     * @return the number of values stored in the list
     */
    public int size() {
        return this.numStored;
    }
    
    /**
     * Adds an item to the end of the HybridList.
     * @param item the item to be added
     */
    public void add(T item) {
        if (this.front == null) {
            this.front = new ArrayListNode();
            this.back = this.front;
        }
        else if (this.back.getList().size() >= this.defaultSize) {
            this.back.setNext(new ArrayListNode());
            this.back = this.back.getNext();
        }
        this.back.getList().add(item);
        this.numStored++;
    }
    
    /////////////////////////////////////////////////////////////////
    
    private class ArrayListNode<T> {
        private ArrayList<T> list;
        private ArrayListNode<T> next;
        
        public ArrayListNode() {
            this.list = new ArrayList<T>();
            this.next = null;
        }
        
        public ArrayList<T> getList() {
            return this.list;
        }
        
        public ArrayListNode<T> getNext() {
            return this.next;
        }
        
        public void setNext(ArrayListNode<T> newNext) {
            this.next = newNext;
        }
    }
    
    /////////////////////////////////////////////////////////////////
    
    public static void main(String[] args) {
        StopWatch timer = new StopWatch();        
        System.out.print("Enter list size: ");
        Scanner input = new Scanner(System.in);
        int size = input.nextInt();
        
        ArrayList<Integer> array = new ArrayList<Integer>();
        timer.start();
        for (int i = 0; i < size; i++) {
            array.add(999);
        }
        timer.stop();       
        System.out.println("create array: " + timer.getElapsedTime());   
        
        timer.reset();
        System.gc();      

        LinkedList<Integer> linked = new LinkedList<Integer>();
        timer.start();
        for (int i = 0; i < size; i++) {
            linked.add(999);
        }
        timer.stop();       
        System.out.println("create linked: " + timer.getElapsedTime());  
        
        timer.reset();
        System.gc(); 
        
        HybridList<Integer> hybrid = new HybridList<Integer>(20);
        timer.start();
        for (int i = 0; i < size; i++) {
            hybrid.add(999);
        }
        timer.stop();       
        System.out.println("create hybrid: " + timer.getElapsedTime());
    }
}