package basictype;

import java.util.Iterator;


/**
 * A stack which uses an array for storing its elements.
 * The array is resized dynamically when it becomes 
 * too small for holding the elements of the stack.
 * 
 * @author Frederic Boulanger frederic.boulanger@supelec.fr
 *
 * @param <T> the type of elements in the stack
 */
public class ArrayStack<T> extends Stack<T> {
  private static final int initCapacity = 5;
  private T[] elements;
  private int size;
  
  //* Create an empty stack
  public ArrayStack() {
    this.size = 0;
    resize(initCapacity);
  }
  
  //* Push an item onto the stack
  @Override
  public void push(T item) {
    if (this.size == this.elements.length) {
      grow();
    }
    this.elements[this.size++] = item;
  }
  
  @Override
  public T top() {
    return this.elements[this.size - 1];
  }
  
  //* Remove the item at the top of the stack and return it
  @Override
  public T pop() {
    T result = null;
    if (this.size > 0) {
      result = this.elements[--this.size];
      this.elements[this.size]= null;
      shrink();
      return result;
    } else {
      throw new RuntimeException("Error: pop on empty stack.");
    }
  }
  
  //* Get the number of items on the stack
  @Override
  public int size() {
    return this.size;
  }
  
  //* Get an iterator on the stack
  @Override
  public Iterator<T> iterator() {
    return new ArrayStackIterator();
  }

  //* Private class of the iterators on this kind of stacks
  private class ArrayStackIterator implements Iterator <T> {
    private int currentIndex = ArrayStack.this.size;
    
    @Override
    public boolean hasNext() {
      return this.currentIndex > 0 ;
    }
    
    @Override
    public T next() {
      return ArrayStack.this.elements[--this.currentIndex];
    }

    @Override
    public void remove() {
      // Don't do anything, removing items from a stack is for pop() only!
    }
  }
  
  //* Grow the array for storing the items on the stack
  private void grow() {
    resize(this.elements.length * 2);
  }
  
  //* Shrink the array for storing the items if its is wasting too much memory
  private void shrink() {
    if ((this.size >= initCapacity) && (this.elements.length >= (2*this.size))) {
      resize(this.size);
    }
  }
  
  //* Resize the array for storing the items on the stack
  private void resize(int newCapacity) {
    // Create a new array with the new capacity
    @SuppressWarnings("unchecked")
    T[] newElements = (T[])new Object[newCapacity];
    // Copy the elements from the old array to the new one
    for (int i = 0; i < this.size; i++) {
      newElements[i] = this.elements[i];
    }
    // Use the new array as storage
    this.elements = newElements;
  }
  
  private static final String[] defaultArgs = {
    "un", "deux", "trois", "quatre", "cinq",
    "six", "sept", "huit", "neuf", "dix",
    "onze", "douze", "treize", "quatorze", "quinze"
  };
  /**
   * Test program
   */
  public static void main(String[] args) {
    String[] test = args;
    if (test.length == 0) {
      test = defaultArgs;
    }
    Stack<String> s = new ArrayStack<String>();
    for(String arg: test) {
      s.push(arg);
    }
    
    System.out.println("Taille = " + s.size());
    System.out.println("# Iterate");
    System.out.println(s);
    
    System.out.println("# Pop");
    while (s.size() > 0) {
      System.out.println(s.pop());
    }
  }

}