    001    // Copyright 2007, 2008 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
    015    package org.apache.tapestry5.ioc.util;
    016
    017    import 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     */
    025    public 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(UtilMessages.stackIsEmpty());
    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    }