001 /*
002 * Licensed to the Apache Software Foundation (ASF) under one
003 * or more contributor license agreements. See the NOTICE file
004 * distributed with this work for additional information
005 * regarding copyright ownership. The ASF licenses this file
006 * to you under the Apache License, Version 2.0 (the "License");
007 * you may not use this file except in compliance with the License.
008 * You may obtain a copy of the License at
009 *
010 * http://www.apache.org/licenses/LICENSE-2.0
011 *
012 * Unless required by applicable law or agreed to in writing, software
013 * distributed under the License is distributed on an "AS IS" BASIS,
014 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
015 * See the License for the specific language governing permissions and
016 * limitations under the License.
017 */
018 /*
019 * $Id: IntStack.java 468655 2006-10-28 07:12:06Z minchau $
020 */
021 package org.apache.xml.utils;
022
023 import java.util.EmptyStackException;
024
025 /**
026 * Implement a stack of simple integers.
027 *
028 * %OPT%
029 * This is currently based on IntVector, which permits fast acess but pays a
030 * heavy recopying penalty if/when its size is increased. If we expect deep
031 * stacks, we should consider a version based on ChunkedIntVector.
032 * @xsl.usage internal
033 */
034 public class IntStack extends IntVector
035 {
036
037 /**
038 * Default constructor. Note that the default
039 * block size is very small, for small lists.
040 */
041 public IntStack()
042 {
043 super();
044 }
045
046 /**
047 * Construct a IntVector, using the given block size.
048 *
049 * @param blocksize Size of block to allocate
050 */
051 public IntStack(int blocksize)
052 {
053 super(blocksize);
054 }
055
056 /**
057 * Copy constructor for IntStack
058 *
059 * @param v IntStack to copy
060 */
061 public IntStack (IntStack v)
062 {
063 super(v);
064 }
065
066 /**
067 * Pushes an item onto the top of this stack.
068 *
069 * @param i the int to be pushed onto this stack.
070 * @return the <code>item</code> argument.
071 */
072 public int push(int i)
073 {
074
075 if ((m_firstFree + 1) >= m_mapSize)
076 {
077 m_mapSize += m_blocksize;
078
079 int newMap[] = new int[m_mapSize];
080
081 System.arraycopy(m_map, 0, newMap, 0, m_firstFree + 1);
082
083 m_map = newMap;
084 }
085
086 m_map[m_firstFree] = i;
087
088 m_firstFree++;
089
090 return i;
091 }
092
093 /**
094 * Removes the object at the top of this stack and returns that
095 * object as the value of this function.
096 *
097 * @return The object at the top of this stack.
098 */
099 public final int pop()
100 {
101 return m_map[--m_firstFree];
102 }
103
104 /**
105 * Quickly pops a number of items from the stack.
106 */
107
108 public final void quickPop(int n)
109 {
110 m_firstFree -= n;
111 }
112
113 /**
114 * Looks at the object at the top of this stack without removing it
115 * from the stack.
116 *
117 * @return the object at the top of this stack.
118 * @throws EmptyStackException if this stack is empty.
119 */
120 public final int peek()
121 {
122 try {
123 return m_map[m_firstFree - 1];
124 }
125 catch (ArrayIndexOutOfBoundsException e)
126 {
127 throw new EmptyStackException();
128 }
129 }
130
131 /**
132 * Looks at the object at the position the stack counting down n items.
133 *
134 * @param n The number of items down, indexed from zero.
135 * @return the object at n items down.
136 * @throws EmptyStackException if this stack is empty.
137 */
138 public int peek(int n)
139 {
140 try {
141 return m_map[m_firstFree-(1+n)];
142 }
143 catch (ArrayIndexOutOfBoundsException e)
144 {
145 throw new EmptyStackException();
146 }
147 }
148
149 /**
150 * Sets an object at a the top of the statck
151 *
152 *
153 * @param val object to set at the top
154 * @throws EmptyStackException if this stack is empty.
155 */
156 public void setTop(int val)
157 {
158 try {
159 m_map[m_firstFree - 1] = val;
160 }
161 catch (ArrayIndexOutOfBoundsException e)
162 {
163 throw new EmptyStackException();
164 }
165 }
166
167 /**
168 * Tests if this stack is empty.
169 *
170 * @return <code>true</code> if this stack is empty;
171 * <code>false</code> otherwise.
172 * @since JDK1.0
173 */
174 public boolean empty()
175 {
176 return m_firstFree == 0;
177 }
178
179 /**
180 * Returns where an object is on this stack.
181 *
182 * @param o the desired object.
183 * @return the distance from the top of the stack where the object is]
184 * located; the return value <code>-1</code> indicates that the
185 * object is not on the stack.
186 * @since JDK1.0
187 */
188 public int search(int o)
189 {
190
191 int i = lastIndexOf(o);
192
193 if (i >= 0)
194 {
195 return size() - i;
196 }
197
198 return -1;
199 }
200
201 /**
202 * Returns clone of current IntStack
203 *
204 * @return clone of current IntStack
205 */
206 public Object clone()
207 throws CloneNotSupportedException
208 {
209 return (IntStack) super.clone();
210 }
211 }