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}