1. /*
  2. * Copyright 1999-2004 The Apache Software Foundation.
  3. *
  4. * Licensed under the Apache License, Version 2.0 (the "License");
  5. * you may not use this file except in compliance with the License.
  6. * You may obtain a copy of the License at
  7. *
  8. * http://www.apache.org/licenses/LICENSE-2.0
  9. *
  10. * Unless required by applicable law or agreed to in writing, software
  11. * distributed under the License is distributed on an "AS IS" BASIS,
  12. * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13. * See the License for the specific language governing permissions and
  14. * limitations under the License.
  15. */
  16. /*
  17. * $Id: IntStack.java,v 1.11 2004/02/17 04:21:14 minchau Exp $
  18. */
  19. package com.sun.org.apache.xml.internal.utils;
  20. import java.util.EmptyStackException;
  21. /**
  22. * Implement a stack of simple integers.
  23. *
  24. * %OPT%
  25. * This is currently based on IntVector, which permits fast acess but pays a
  26. * heavy recopying penalty if/when its size is increased. If we expect deep
  27. * stacks, we should consider a version based on ChunkedIntVector.
  28. * @xsl.usage internal
  29. */
  30. public class IntStack extends IntVector
  31. {
  32. /**
  33. * Default constructor. Note that the default
  34. * block size is very small, for small lists.
  35. */
  36. public IntStack()
  37. {
  38. super();
  39. }
  40. /**
  41. * Construct a IntVector, using the given block size.
  42. *
  43. * @param blocksize Size of block to allocate
  44. */
  45. public IntStack(int blocksize)
  46. {
  47. super(blocksize);
  48. }
  49. /**
  50. * Copy constructor for IntStack
  51. *
  52. * @param v IntStack to copy
  53. */
  54. public IntStack (IntStack v)
  55. {
  56. super(v);
  57. }
  58. /**
  59. * Pushes an item onto the top of this stack.
  60. *
  61. * @param i the int to be pushed onto this stack.
  62. * @return the <code>item</code> argument.
  63. */
  64. public int push(int i)
  65. {
  66. if ((m_firstFree + 1) >= m_mapSize)
  67. {
  68. m_mapSize += m_blocksize;
  69. int newMap[] = new int[m_mapSize];
  70. System.arraycopy(m_map, 0, newMap, 0, m_firstFree + 1);
  71. m_map = newMap;
  72. }
  73. m_map[m_firstFree] = i;
  74. m_firstFree++;
  75. return i;
  76. }
  77. /**
  78. * Removes the object at the top of this stack and returns that
  79. * object as the value of this function.
  80. *
  81. * @return The object at the top of this stack.
  82. */
  83. public final int pop()
  84. {
  85. return m_map[--m_firstFree];
  86. }
  87. /**
  88. * Quickly pops a number of items from the stack.
  89. */
  90. public final void quickPop(int n)
  91. {
  92. m_firstFree -= n;
  93. }
  94. /**
  95. * Looks at the object at the top of this stack without removing it
  96. * from the stack.
  97. *
  98. * @return the object at the top of this stack.
  99. * @throws EmptyStackException if this stack is empty.
  100. */
  101. public final int peek()
  102. {
  103. try {
  104. return m_map[m_firstFree - 1];
  105. }
  106. catch (ArrayIndexOutOfBoundsException e)
  107. {
  108. throw new EmptyStackException();
  109. }
  110. }
  111. /**
  112. * Looks at the object at the position the stack counting down n items.
  113. *
  114. * @param n The number of items down, indexed from zero.
  115. * @return the object at n items down.
  116. * @throws EmptyStackException if this stack is empty.
  117. */
  118. public int peek(int n)
  119. {
  120. try {
  121. return m_map[m_firstFree-(1+n)];
  122. }
  123. catch (ArrayIndexOutOfBoundsException e)
  124. {
  125. throw new EmptyStackException();
  126. }
  127. }
  128. /**
  129. * Sets an object at a the top of the statck
  130. *
  131. *
  132. * @param val object to set at the top
  133. * @throws EmptyStackException if this stack is empty.
  134. */
  135. public void setTop(int val)
  136. {
  137. try {
  138. m_map[m_firstFree - 1] = val;
  139. }
  140. catch (ArrayIndexOutOfBoundsException e)
  141. {
  142. throw new EmptyStackException();
  143. }
  144. }
  145. /**
  146. * Tests if this stack is empty.
  147. *
  148. * @return <code>true</code> if this stack is empty;
  149. * <code>false</code> otherwise.
  150. * @since JDK1.0
  151. */
  152. public boolean empty()
  153. {
  154. return m_firstFree == 0;
  155. }
  156. /**
  157. * Returns where an object is on this stack.
  158. *
  159. * @param o the desired object.
  160. * @return the distance from the top of the stack where the object is]
  161. * located; the return value <code>-1</code> indicates that the
  162. * object is not on the stack.
  163. * @since JDK1.0
  164. */
  165. public int search(int o)
  166. {
  167. int i = lastIndexOf(o);
  168. if (i >= 0)
  169. {
  170. return size() - i;
  171. }
  172. return -1;
  173. }
  174. /**
  175. * Returns clone of current IntStack
  176. *
  177. * @return clone of current IntStack
  178. */
  179. public Object clone()
  180. throws CloneNotSupportedException
  181. {
  182. return (IntStack) super.clone();
  183. }
  184. }