1. /*
  2. * The Apache Software License, Version 1.1
  3. *
  4. *
  5. * Copyright (c) 1999 The Apache Software Foundation. All rights
  6. * reserved.
  7. *
  8. * Redistribution and use in source and binary forms, with or without
  9. * modification, are permitted provided that the following conditions
  10. * are met:
  11. *
  12. * 1. Redistributions of source code must retain the above copyright
  13. * notice, this list of conditions and the following disclaimer.
  14. *
  15. * 2. Redistributions in binary form must reproduce the above copyright
  16. * notice, this list of conditions and the following disclaimer in
  17. * the documentation and/or other materials provided with the
  18. * distribution.
  19. *
  20. * 3. The end-user documentation included with the redistribution,
  21. * if any, must include the following acknowledgment:
  22. * "This product includes software developed by the
  23. * Apache Software Foundation (http://www.apache.org/)."
  24. * Alternately, this acknowledgment may appear in the software itself,
  25. * if and wherever such third-party acknowledgments normally appear.
  26. *
  27. * 4. The names "Xalan" and "Apache Software Foundation" must
  28. * not be used to endorse or promote products derived from this
  29. * software without prior written permission. For written
  30. * permission, please contact apache@apache.org.
  31. *
  32. * 5. Products derived from this software may not be called "Apache",
  33. * nor may "Apache" appear in their name, without prior written
  34. * permission of the Apache Software Foundation.
  35. *
  36. * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
  37. * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  38. * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  39. * DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
  40. * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  41. * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  42. * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
  43. * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
  44. * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  45. * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
  46. * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  47. * SUCH DAMAGE.
  48. * ====================================================================
  49. *
  50. * This software consists of voluntary contributions made by many
  51. * individuals on behalf of the Apache Software Foundation and was
  52. * originally based on software copyright (c) 1999, Lotus
  53. * Development Corporation., http://www.lotus.com. For more
  54. * information on the Apache Software Foundation, please see
  55. * <http://www.apache.org/>.
  56. */
  57. package org.apache.xml.utils;
  58. import java.util.EmptyStackException;
  59. /**
  60. * <meta name="usage" content="internal"/>
  61. * Implement a stack of simple integers.
  62. *
  63. * %OPT%
  64. * This is currently based on IntVector, which permits fast acess but pays a
  65. * heavy recopying penalty if/when its size is increased. If we expect deep
  66. * stacks, we should consider a version based on ChunkedIntVector.
  67. */
  68. public class IntStack extends IntVector
  69. {
  70. /**
  71. * Default constructor. Note that the default
  72. * block size is very small, for small lists.
  73. */
  74. public IntStack()
  75. {
  76. super();
  77. }
  78. /**
  79. * Construct a IntVector, using the given block size.
  80. *
  81. * @param blocksize Size of block to allocate
  82. */
  83. public IntStack(int blocksize)
  84. {
  85. super(blocksize);
  86. }
  87. /**
  88. * Copy constructor for IntStack
  89. *
  90. * @param v IntStack to copy
  91. */
  92. public IntStack (IntStack v)
  93. {
  94. super(v);
  95. }
  96. /**
  97. * Pushes an item onto the top of this stack.
  98. *
  99. * @param i the int to be pushed onto this stack.
  100. * @return the <code>item</code> argument.
  101. */
  102. public int push(int i)
  103. {
  104. if ((m_firstFree + 1) >= m_mapSize)
  105. {
  106. m_mapSize += m_blocksize;
  107. int newMap[] = new int[m_mapSize];
  108. System.arraycopy(m_map, 0, newMap, 0, m_firstFree + 1);
  109. m_map = newMap;
  110. }
  111. m_map[m_firstFree] = i;
  112. m_firstFree++;
  113. return i;
  114. }
  115. /**
  116. * Removes the object at the top of this stack and returns that
  117. * object as the value of this function.
  118. *
  119. * @return The object at the top of this stack.
  120. */
  121. public int pop()
  122. {
  123. return m_map[--m_firstFree];
  124. }
  125. /**
  126. * Quickly pops a number of items from the stack.
  127. */
  128. public void quickPop(int n)
  129. {
  130. m_firstFree -= n;
  131. }
  132. /**
  133. * Looks at the object at the top of this stack without removing it
  134. * from the stack.
  135. *
  136. * @return the object at the top of this stack.
  137. * @throws EmptyStackException if this stack is empty.
  138. */
  139. public int peek()
  140. {
  141. try {
  142. return m_map[m_firstFree - 1];
  143. }
  144. catch (ArrayIndexOutOfBoundsException e)
  145. {
  146. throw new EmptyStackException();
  147. }
  148. }
  149. /**
  150. * Looks at the object at the position the stack counting down n items.
  151. *
  152. * @param n The number of items down, indexed from zero.
  153. * @return the object at n items down.
  154. * @throws EmptyStackException if this stack is empty.
  155. */
  156. public int peek(int n)
  157. {
  158. try {
  159. return m_map[m_firstFree-(1+n)];
  160. }
  161. catch (ArrayIndexOutOfBoundsException e)
  162. {
  163. throw new EmptyStackException();
  164. }
  165. }
  166. /**
  167. * Sets an object at a the top of the statck
  168. *
  169. *
  170. * @param val object to set at the top
  171. * @throws EmptyStackException if this stack is empty.
  172. */
  173. public void setTop(int val)
  174. {
  175. try {
  176. m_map[m_firstFree - 1] = val;
  177. }
  178. catch (ArrayIndexOutOfBoundsException e)
  179. {
  180. throw new EmptyStackException();
  181. }
  182. }
  183. /**
  184. * Tests if this stack is empty.
  185. *
  186. * @return <code>true</code> if this stack is empty;
  187. * <code>false</code> otherwise.
  188. * @since JDK1.0
  189. */
  190. public boolean empty()
  191. {
  192. return m_firstFree == 0;
  193. }
  194. /**
  195. * Returns where an object is on this stack.
  196. *
  197. * @param o the desired object.
  198. * @return the distance from the top of the stack where the object is]
  199. * located; the return value <code>-1</code> indicates that the
  200. * object is not on the stack.
  201. * @since JDK1.0
  202. */
  203. public int search(int o)
  204. {
  205. int i = lastIndexOf(o);
  206. if (i >= 0)
  207. {
  208. return size() - i;
  209. }
  210. return -1;
  211. }
  212. /**
  213. * Returns clone of current IntStack
  214. *
  215. * @return clone of current IntStack
  216. */
  217. public Object clone()
  218. throws CloneNotSupportedException
  219. {
  220. return (IntStack) super.clone();
  221. }
  222. }