    001// Copyright 2007, 2008, 2011 The Apache Software Foundation
    002//
    003// Licensed under the Apache License, Version 2.0 (the "License");
    004// you may not use this file except in compliance with the License.
    005// You may obtain a copy of the License at
    006//
    007//     http://www.apache.org/licenses/LICENSE-2.0
    008//
    009// Unless required by applicable law or agreed to in writing, software
    010// distributed under the License is distributed on an "AS IS" BASIS,
    011// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    012// See the License for the specific language governing permissions and
    013// limitations under the License.
    014
    015package org.apache.tapestry5.commons.util;
    016
    017/**
    018 * A simple, streamlined implementation of {@link java.util.Stack}. The implementation is <em>not</em> threadsafe.
    019 *
    020 * @param <E> the type of elements stored in the map
    021 * @see CollectionFactory#newStack()
    022 */
    023public class Stack<E>
    024{
    025    private static final int MINIMUM_SIZE = 3;
    026
    027    private static final int DEFAULT_ARRAY_SIZE = 20;
    028
    029    private Object[] items;
    030
    031    private int index = -1;
    032
    033    /**
    034     * Normal constructor supporting an initial size of 20.
    035     */
    036    public Stack()
    037    {
    038        this(DEFAULT_ARRAY_SIZE);
    039    }
    040
    041    /**
    042     * @param initialSize the initial size of the internal array (which will be expanded as necessary). For best
    043     *                    efficiency, set this to the maximum depth of the stack.
    044     */
    045    public Stack(int initialSize)
    046    {
    047        items = new Object[Math.max(initialSize, MINIMUM_SIZE)];
    048    }
    049
    050    /**
    051     * Returns true if the stack is empty.
    052     */
    053    public boolean isEmpty()
    054    {
    055        return index < 0;
    056    }
    057
    058    /**
    059     * Returns the number of items currently in the stack.
    060     */
    061    public int getDepth()
    062    {
    063        return index + 1;
    064    }
    065
    066    /**
    067     * Clears the stack, the same as popping off all elements.
    068     */
    069    public void clear()
    070    {
    071        for (int i = 0; i <= index; i++) items[i] = null;
    072
    073        index = -1;
    074    }
    075
    076    /**
    077     * Pushes a new item onto the stack.
    078     */
    079    public void push(E item)
    080    {
    081        index++;
    082
    083        if (index == items.length)
    084        {
    085            int newCapacity = (items.length * 3) / 2 + 1;
    086            Object[] newItems = new Object[newCapacity];
    087            System.arraycopy(items, 0, newItems, 0, items.length);
    088
    089            items = newItems;
    090        }
    091
    092        items[index] = item;
    093    }
    094
    095    /**
    096     * Pops the top element off the stack and returns it.
    097     *
    098     * @return the top element of the stack
    099     * @throws IllegalStateException if the stack is empty
    100     */
    101    @SuppressWarnings("unchecked")
    102    public E pop()
    103    {
    104        checkIfEmpty();
    105
    106        Object result = items[index];
    107
    108        items[index] = null;
    109
    110        index--;
    111
    112        return (E) result;
    113    }
    114
    115    private void checkIfEmpty()
    116    {
    117        if (index < 0) throw new IllegalStateException("Stack is empty.");
    118    }
    119
    120    /**
    121     * Returns the top element of the stack without affecting the stack.
    122     *
    123     * @return top element on the stack
    124     * @throws IllegalStateException if the stack is empty
    125     */
    126    @SuppressWarnings("unchecked")
    127    public E peek()
    128    {
    129        checkIfEmpty();
    130
    131        return (E) items[index];
    132    }
    133
    134    /**
    135     * Describes the stack, listing the element in order of depth (top element first).
    136     *
    137     * @return string description of the stack
    138     */
    139    @Override
    140    public String toString()
    141    {
    142        StringBuilder builder = new StringBuilder("Stack[");
    143
    144        for (int i = index; i >= 0; i--)
    145        {
    146            if (i != index) builder.append(", ");
    147
    148            builder.append(String.valueOf(items[i]));
    149        }
    150
    151        builder.append(']');
    152
    153        return builder.toString();
    154    }
    155
    156    /**
    157     * Returns a snapshot of the current state of the stack as an array of objects. The first object is the deepest in
    158     * the stack, the last object is the most shallowest (most recently pushed onto the stack).  The returned array may
    159     * be manipulated (it is a copy).
    160     *
    161     * @return the stack as an object array
    162     */
    163    public Object[] getSnapshot()
    164    {
    165        Object[] result = new Object[index + 1];
    166
    167        System.arraycopy(items, 0, result, 0, index + 1);
    168
    169        return result;
    170    }
    171}