001/*
002 * Copyright (C) 2009-2011 Mathias Doenitz
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License");
005 * you may not use this file except in compliance with the License.
006 * You may obtain a copy of the License at
007 *
008 * http://www.apache.org/licenses/LICENSE-2.0
009 *
010 * Unless required by applicable law or agreed to in writing, software
011 * distributed under the License is distributed on an "AS IS" BASIS,
012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013 * See the License for the specific language governing permissions and
014 * limitations under the License.
015 */
016
017package org.parboiled.common;
018
019public class IntArrayStack {
020
021    public static class UnderflowException extends RuntimeException {
022        public UnderflowException(String message) {
023            super(message);
024        }
025    }
026
027    private static final int INITIAL_CAPACITY = 16;
028    private int[] array;
029    private int top;
030
031    public IntArrayStack() {
032        array = new int[INITIAL_CAPACITY];
033        top = -1;
034    }
035
036    /**
037     * Tests if the stack is empty.
038     *
039     * @return true if empty, false otherwise.
040     */
041    public boolean isEmpty() {
042        return top == -1;
043    }
044
045    /**
046     * Returns the number of element currently on the stack.
047     *
048     * @return the number of element currently on the stack
049     */
050    public int size() {
051        return top + 1;
052    }
053
054    /**
055     * Copies all elements currently on the stack into the given array.
056     *
057     * @param destArray the array
058     * @param destStartIndex the index to start copying into
059     */
060    public void getElements(int[] destArray, int destStartIndex) {
061        System.arraycopy(array, 0, destArray, destStartIndex, size());
062    }
063
064    /**
065     * @return all elements in a new array.
066     */
067    public int[] toArray() {
068        int[] array = new int[size()];
069        getElements(array, 0);
070        return array;
071    }
072
073    /**
074     * Empties the stack.
075     */
076    public void clear() {
077        top = -1;
078    }
079
080    /**
081     * Returns the item at the top of the stack without removing it.
082     *
083     * @return the most recently inserted item in the stack.
084     * @throws UnderflowException if the stack is empty.
085     */
086    public int peek() {
087        if (isEmpty()) {
088            throw new UnderflowException("IntArrayStack peek");
089        }
090        return array[top];
091    }
092
093    /**
094     * Removes the most recently inserted item from the stack.
095     *
096     * @return the top stack item
097     * @throws UnderflowException if the stack is empty.
098     */
099    public int pop() {
100        if (isEmpty()) {
101            throw new UnderflowException("IntArrayStack pop");
102        }
103        return array[top--];
104    }
105
106    /**
107     * Pushes a new item onto the stack.
108     *
109     * @param x the item to add.
110     */
111    public void push(int x) {
112        if (top == array.length - 1) {
113            expandCapacity();
114        }
115        array[++top] = x;
116    }
117
118    private void expandCapacity() {
119        int[] newArray = new int[array.length * 2];
120        System.arraycopy(array, 0, newArray, 0, array.length);
121        array = newArray;
122    }
123}