001: /*
002: * Copyright 1999-2004 The Apache Software Foundation.
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: /*
017: * $Id: IntStack.java,v 1.11 2004/02/17 04:21:14 minchau Exp $
018: */
019: package org.apache.xml.utils;
020:
021: import java.util.EmptyStackException;
022:
023: /**
024: * Implement a stack of simple integers.
025: *
026: * %OPT%
027: * This is currently based on IntVector, which permits fast acess but pays a
028: * heavy recopying penalty if/when its size is increased. If we expect deep
029: * stacks, we should consider a version based on ChunkedIntVector.
030: * @xsl.usage internal
031: */
032: public class IntStack extends IntVector {
033:
034: /**
035: * Default constructor. Note that the default
036: * block size is very small, for small lists.
037: */
038: public IntStack() {
039: super ();
040: }
041:
042: /**
043: * Construct a IntVector, using the given block size.
044: *
045: * @param blocksize Size of block to allocate
046: */
047: public IntStack(int blocksize) {
048: super (blocksize);
049: }
050:
051: /**
052: * Copy constructor for IntStack
053: *
054: * @param v IntStack to copy
055: */
056: public IntStack(IntStack v) {
057: super (v);
058: }
059:
060: /**
061: * Pushes an item onto the top of this stack.
062: *
063: * @param i the int to be pushed onto this stack.
064: * @return the <code>item</code> argument.
065: */
066: public int push(int i) {
067:
068: if ((m_firstFree + 1) >= m_mapSize) {
069: m_mapSize += m_blocksize;
070:
071: int newMap[] = new int[m_mapSize];
072:
073: System.arraycopy(m_map, 0, newMap, 0, m_firstFree + 1);
074:
075: m_map = newMap;
076: }
077:
078: m_map[m_firstFree] = i;
079:
080: m_firstFree++;
081:
082: return i;
083: }
084:
085: /**
086: * Removes the object at the top of this stack and returns that
087: * object as the value of this function.
088: *
089: * @return The object at the top of this stack.
090: */
091: public final int pop() {
092: return m_map[--m_firstFree];
093: }
094:
095: /**
096: * Quickly pops a number of items from the stack.
097: */
098:
099: public final void quickPop(int n) {
100: m_firstFree -= n;
101: }
102:
103: /**
104: * Looks at the object at the top of this stack without removing it
105: * from the stack.
106: *
107: * @return the object at the top of this stack.
108: * @throws EmptyStackException if this stack is empty.
109: */
110: public final int peek() {
111: try {
112: return m_map[m_firstFree - 1];
113: } catch (ArrayIndexOutOfBoundsException e) {
114: throw new EmptyStackException();
115: }
116: }
117:
118: /**
119: * Looks at the object at the position the stack counting down n items.
120: *
121: * @param n The number of items down, indexed from zero.
122: * @return the object at n items down.
123: * @throws EmptyStackException if this stack is empty.
124: */
125: public int peek(int n) {
126: try {
127: return m_map[m_firstFree - (1 + n)];
128: } catch (ArrayIndexOutOfBoundsException e) {
129: throw new EmptyStackException();
130: }
131: }
132:
133: /**
134: * Sets an object at a the top of the statck
135: *
136: *
137: * @param val object to set at the top
138: * @throws EmptyStackException if this stack is empty.
139: */
140: public void setTop(int val) {
141: try {
142: m_map[m_firstFree - 1] = val;
143: } catch (ArrayIndexOutOfBoundsException e) {
144: throw new EmptyStackException();
145: }
146: }
147:
148: /**
149: * Tests if this stack is empty.
150: *
151: * @return <code>true</code> if this stack is empty;
152: * <code>false</code> otherwise.
153: * @since JDK1.0
154: */
155: public boolean empty() {
156: return m_firstFree == 0;
157: }
158:
159: /**
160: * Returns where an object is on this stack.
161: *
162: * @param o the desired object.
163: * @return the distance from the top of the stack where the object is]
164: * located; the return value <code>-1</code> indicates that the
165: * object is not on the stack.
166: * @since JDK1.0
167: */
168: public int search(int o) {
169:
170: int i = lastIndexOf(o);
171:
172: if (i >= 0) {
173: return size() - i;
174: }
175:
176: return -1;
177: }
178:
179: /**
180: * Returns clone of current IntStack
181: *
182: * @return clone of current IntStack
183: */
184: public Object clone() throws CloneNotSupportedException {
185: return (IntStack) super.clone();
186: }
187: }
|