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