/*
 * @author Ranides Atterwim <ranides@gmail.com>
 * @copyright Ranides Atterwim
 * @license WTFPL
 * @url http://ranides.net/projects/assira
 */
package net.ranides.assira.collection;

import java.io.Serializable;
import java.util.*;

/**
 * <p>Niesynchronizowana implementacja stosu wydajniejsza (jako stos) od standardowych
 * kolekcji. Poniżej szybkie podsumowanie, dlaczego rezygnujemy ze standardowych
 * możliwości:</p>
 * <p>
 * {@link java.util.Vector} - można optymalnie zarządzać rozmiarem, ale jest synchronizowany.
 * </p>
 * <p>
 * {@link java.util.ArrayList} - nie jest synchronizowana, ale nie da się zarządzać rozmiarem.
 * Puchnie jak licho nawet do rozmiaru o 50% większego, dla dużych stosów to horror)
 * </p>
 * <p>
 * {@link java.util.LinkedList} - niby wygodne, rozmiarem idealnie zarządza i
 * nie jest synchronizowane, ale totalnie niewydajne pamięciowo: w końcu do
 * podwójnie linkowana lista. 4x większy rozmiar to ma, niż zwykła tablica
 * </p>
 *
 * @param <T>
 * @author ranides
 */
@SuppressWarnings("unchecked")
public class Stack<T> extends AbstractList<T> implements RandomAccess, Serializable  {

    private static final long serialVersionUID = 1L;
    
    private static final Object[] EMPTY = new Object[0];

    private Object items[];
    private int pointer;

    /**
     * Tworzy pusty stos, niczego nie alokuje
     */
    public Stack() {
        items = EMPTY;
    }

    /**
     * Tworzy stos o podanym rozmiarze.
     * @param capacity
     */
    public Stack(int capacity) {
        items = new Object[capacity];
    }

    @Override
    public final T get(int index) {
        return (T)items[index];
    }

    @Override
    public final int size() {
        return pointer;
    }

    /**
     * Wstawia element na stos.
     * @param value
     */
    public final void push(T value) {
        allocator(items.length, pointer+1);
        items[pointer++] = value;
    }

    /**
     * Zdejmuje element ze stosu.
     * @return
     */
    public final T pop() {
        if( pointer < 1 ) {
            throw new EmptyStackException();
        }
        return (T)items[--pointer];
    }

    /**
     * Zwraca wartość elementu ze szczytu stosu bez zdejmowania.
     * @return
     */
    public final T peek() {
        if( pointer < 1 ) {
            throw new EmptyStackException();
        }
        return (T)items[pointer-1];
    }

    /**
     * Zwraca wartość n-tego elementu, licząc od szczytu stosu bez zdejmowania.
     * @param index
     * @return
     */
    public final T peek(int index) {
        return (T)items[pointer-index-1];
    }

    /**
     * Metoda alokująca pamięć dla stosu.
     * @param size
     */
    protected final void allocate(int size) {
        Object[] next = new Object[size];
        System.arraycopy(items, 0, next, 0, items.length);
        items = next;
    }


    /**
     * Metoda zarządzająca rozmiarem stosu. Przeładowana metoda powinna
     * ustawiać rozmiar stosu za pomocą metody {@link #allocate}
     * @param size
     * @param request
     */
    protected void allocator(int size, int request) {
        if( request >= size ) {
            allocate(size + 8);
        }
    }

    @Override
    public void clear() {
        pointer = 0;
    }

}
