    001    /*
    002     * Licensed to the Apache Software Foundation (ASF) under one or more
    003     * contributor license agreements.  See the NOTICE file distributed with
    004     * this work for additional information regarding copyright ownership.
    005     * The ASF licenses this file to You under the Apache License, Version 2.0
    006     * (the "License"); you may not use this file except in compliance with
    007     * the License.  You may obtain a copy of the License at
    008     *
    009     *      http://www.apache.org/licenses/LICENSE-2.0
    010     *
    011     * Unless required by applicable law or agreed to in writing, software
    012     * distributed under the License is distributed on an "AS IS" BASIS,
    013     * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    014     * See the License for the specific language governing permissions and
    015     * limitations under the License.
    016     */
    017    package org.apache.commons.collections;
    018
    019    import java.util.ArrayList;
    020    import java.util.EmptyStackException;
    021
    022    /**
    023     * An implementation of the {@link java.util.Stack} API that is based on an
    024     * <code>ArrayList</code> instead of a <code>Vector</code>, so it is not
    025     * synchronized to protect against multi-threaded access.  The implementation
    026     * is therefore operates faster in environments where you do not need to
    027     * worry about multiple thread contention.
    028     * <p>
    029     * The removal order of an <code>ArrayStack</code> is based on insertion
    030     * order: The most recently added element is removed first.  The iteration
    031     * order is <i>not</i> the same as the removal order.  The iterator returns
    032     * elements from the bottom up, whereas the {@link #remove()} method removes
    033     * them from the top down.
    034     * <p>
    035     * Unlike <code>Stack</code>, <code>ArrayStack</code> accepts null entries.
    036     * <p>
    037     * <strong>Note:</strong> this class should be bytecode-identical to the
    038     * version in commons collections. This is required to allow backwards
    039     * compability with both previous versions of BeanUtils and also allow
    040     * coexistance with both collections 2.1 and 3.0.
    041     *
    042     * @see java.util.Stack
    043     * @since Commons Collections 1.0
    044     * @version $Revision: 555824 $ $Date: 2007-07-13 01:27:15 +0100 (Fri, 13 Jul 2007) $
    045     *
    046     * @author Craig R. McClanahan
    047     * @author Paul Jack
    048     * @author Stephen Colebourne
    049     */
    050    public class ArrayStack extends ArrayList implements Buffer {
    051
    052        /** Ensure serialization compatibility */
    053        private static final long serialVersionUID = 2130079159931574599L;
    054
    055        /**
    056         * Constructs a new empty <code>ArrayStack</code>. The initial size
    057         * is controlled by <code>ArrayList</code> and is currently 10.
    058         */
    059        public ArrayStack() {
    060            super();
    061        }
    062
    063        /**
    064         * Constructs a new empty <code>ArrayStack</code> with an initial size.
    065         *
    066         * @param initialSize  the initial size to use
    067         * @throws IllegalArgumentException  if the specified initial size
    068         *  is negative
    069         */
    070        public ArrayStack(int initialSize) {
    071            super(initialSize);
    072        }
    073
    074        /**
    075         * Return <code>true</code> if this stack is currently empty.
    076         * <p>
    077         * This method exists for compatibility with <code>java.util.Stack</code>.
    078         * New users of this class should use <code>isEmpty</code> instead.
    079         *
    080         * @return true if the stack is currently empty
    081         */
    082        public boolean empty() {
    083            return isEmpty();
    084        }
    085
    086        /**
    087         * Returns the top item off of this stack without removing it.
    088         *
    089         * @return the top item on the stack
    090         * @throws EmptyStackException  if the stack is empty
    091         */
    092        public Object peek() throws EmptyStackException {
    093            int n = size();
    094            if (n <= 0) {
    095                throw new EmptyStackException();
    096            } else {
    097                return get(n - 1);
    098            }
    099        }
    100
    101        /**
    102         * Returns the n'th item down (zero-relative) from the top of this
    103         * stack without removing it.
    104         *
    105         * @param n  the number of items down to go
    106         * @return the n'th item on the stack, zero relative
    107         * @throws EmptyStackException  if there are not enough items on the
    108         *  stack to satisfy this request
    109         */
    110        public Object peek(int n) throws EmptyStackException {
    111            int m = (size() - n) - 1;
    112            if (m < 0) {
    113                throw new EmptyStackException();
    114            } else {
    115                return get(m);
    116            }
    117        }
    118
    119        /**
    120         * Pops the top item off of this stack and return it.
    121         *
    122         * @return the top item on the stack
    123         * @throws EmptyStackException  if the stack is empty
    124         */
    125        public Object pop() throws EmptyStackException {
    126            int n = size();
    127            if (n <= 0) {
    128                throw new EmptyStackException();
    129            } else {
    130                return remove(n - 1);
    131            }
    132        }
    133
    134        /**
    135         * Pushes a new item onto the top of this stack. The pushed item is also
    136         * returned. This is equivalent to calling <code>add</code>.
    137         *
    138         * @param item  the item to be added
    139         * @return the item just pushed
    140         */
    141        public Object push(Object item) {
    142            add(item);
    143            return item;
    144        }
    145
    146        /**
    147         * Returns the one-based position of the distance from the top that the
    148         * specified object exists on this stack, where the top-most element is
    149         * considered to be at distance <code>1</code>.  If the object is not
    150         * present on the stack, return <code>-1</code> instead.  The
    151         * <code>equals()</code> method is used to compare to the items
    152         * in this stack.
    153         *
    154         * @param object  the object to be searched for
    155         * @return the 1-based depth into the stack of the object, or -1 if not found
    156         */
    157        public int search(Object object) {
    158            int i = size() - 1;        // Current index
    159            int n = 1;                 // Current distance
    160            while (i >= 0) {
    161                Object current = get(i);
    162                if ((object == null && current == null) ||
    163                    (object != null && object.equals(current))) {
    164                    return n;
    165                }
    166                i--;
    167                n++;
    168            }
    169            return -1;
    170        }
    171
    172        /**
    173         * Returns the element on the top of the stack.
    174         *
    175         * @return the element on the top of the stack
    176         * @throws BufferUnderflowException  if the stack is empty
    177         */
    178        public Object get() {
    179            int size = size();
    180            if (size == 0) {
    181                throw new BufferUnderflowException();
    182            }
    183            return get(size - 1);
    184        }
    185
    186        /**
    187         * Removes the element on the top of the stack.
    188         *
    189         * @return the removed element
    190         * @throws BufferUnderflowException  if the stack is empty
    191         */
    192        public Object remove() {
    193            int size = size();
    194            if (size == 0) {
    195                throw new BufferUnderflowException();
    196            }
    197            return remove(size - 1);
    198        }
    199
    200    }