/***********************************************************************
 *
 * Copyright (C) 2014 Avaneesh Rastogi (rastogi.avaneesh (at) gmail (dot) com)
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see (http://www.gnu.org/licenses/).
 *
 ***********************************************************************/

package Miscellaneous;

import java.lang.reflect.Array;

/**
 * {@code Stack} implements a generic array-based stack.
 *
 * @author Avaneesh Rastogi
 * @version 1.0
 * @param <T> type of {@code Stack} elements
 */
public class Stack<T> {

    /**
     * Generic Array for Stack object elements
     */
    private final T m_array[];
    /**
     * Size of Stack array
     */
    private final int m_size;
    /**
     * top pointer of Stack object
     */
    private int m_top;

//-----------------------------------------------------------------------
    /**
     * Constructor for initializing {@code Stack} object without a given size.
     * <br> The size of {@code Stack} array defaults to 100.
     *
     * @param stackType type of {@code Stack} elements
     */
    public Stack(Class<T> stackType) {
        this(stackType, 100);
    }
//-----------------------------------------------------------------------

    /**
     * Constructor for initializing {@code Stack} object with given size.
     *
     * @param stackType type of {@code Stack} elements
     * @param stackSize size of {@code Stack} array
     */
    public Stack(Class<T> stackType, int stackSize) {
        m_array = (T[]) Array.newInstance(stackType, stackSize);
        m_top = -1;
        m_size = stackSize;

        /* Set array elements to null values */
        for (T i : m_array) {
            i = null;
        }
    }
//-----------------------------------------------------------------------

    /**
     * Copy constructor for copying {@code Stack} objects.
     * <br> This method is invoked with the destination {@code Stack}.
     * <br> The source {@code Stack} is passed as argument.
     *
     * @param sourceStack {@code Stack} object to be copied
     */
    public Stack(Stack<T> sourceStack) {
        this.m_top = sourceStack.m_top;
        this.m_array = sourceStack.m_array;
        this.m_size = sourceStack.m_size;
    }
//-----------------------------------------------------------------------

    /**
     * Gets the size of the invoking {@code Stack}.
     *
     * @return size of the {@code Stack}
     */
    public int getSize() {
        return m_size;
    }
//-----------------------------------------------------------------------

    /**
     * Gets the value of {@code top} for the invoking {@code Stack}.
     *
     * @return value of {@code m_top}
     */
    public int getTop() {
        return m_top;
    }
//-----------------------------------------------------------------------

    /**
     * Indicates if the invoking {@code Stack} is empty.
     *
     * @return {@code true} if {@code Stack} is empty, {@code false} otherwise.
     */
    public boolean isEmpty() {
        return (this.numberOfElements() == 0);
    }
//-----------------------------------------------------------------------

    /**
     * Returns the number of elements present in {@code Stack}.
     *
     * @return number of elements in invoking {@code Stack} object or -1 if
     * empty
     */
    public int numberOfElements() {
        return (m_top + 1);
    }
//-----------------------------------------------------------------------

    /**
     * Returns the top element of the invoking {@code Stack} object,
     * {@code null} if {@code Stack} empty.
     * <br> If the {@code Stack} object contains no elements, then {@code null}
     * is returned.
     *
     * @return {@code Stack} array element of type {@code T} at the top of stack
     * or {@code null} if {@code Stack} empty
     */
    public T front() {
        if (m_top >= 0) {
            return m_array[m_top];
        } else {
            return null;
        }
    }
//-----------------------------------------------------------------------

    /**
     * Pushes the argument {@code stackElement} to the top of the invoking
     * {@code Stack}.
     *
     * @param stackElement {@code Stack} element of type {@code T} to push in
     * the {@code Stack}
     * @return element pushed in the {@code Stack}, {@code null} if
     * {@code Stack} full.
     */
    public T push(T stackElement) {
        if (this.numberOfElements() == m_size) {
            return null;
        }

        m_array[++m_top] = stackElement;
        return m_array[m_top];
    }
//-----------------------------------------------------------------------

    /**
     * Removes an element from the top of the invoking {@code Stack} and returns
     * the popped element.
     * <br> In case the {@code Stack} is empty, {@code null} is returned.
     *
     * @return popped element from the {@code Stack}, {@code null} if
     * {@code Stack} is empty
     */
    public T pop() {
        /* Stack is empty */
        if (this.isEmpty()) {
            return null;
        }

        T var = m_array[m_top--];
        return var;
    }
//-----------------------------------------------------------------------

    /**
     * Clears all the elements of the invoking {@code Stack}.
     */
    public void clear() {
        m_top = -1;
        for (int i = 0; i < m_array.length; i++) {
            m_array[i] = null;
        }
    }
//-----------------------------------------------------------------------

    /**
     * Reverse all the elements of the invoking {@code Stack}.
     */
    public void reverse() {
        /* Stack is empty */
        if (m_top == -1) {
            return;
        }

        /* Reverse Stack elements */
        for (int i = 0; i < m_top / 2; i++) {
            T var = m_array[i];
            m_array[i] = m_array[m_top - i];
            m_array[m_top - i] = var;
        }
    }
//-----------------------------------------------------------------------

    /**
     * Method for debugging purposes.
     * <br> Displays all the elements of {@code m_array} in the order of
     * indices.
     */
    public void debug() {
        System.out.println("DEBUG: Printing Stack ... m_array[0] -> m_array[size-1]");
        for (T i : m_array) {
            System.out.print(i + " ");
        }
        System.out.println();
    }
//-----------------------------------------------------------------------
}
