19f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson/* 29f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Licensed to the Apache Software Foundation (ASF) under one 39f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * or more contributor license agreements. See the NOTICE file 49f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * distributed with this work for additional information 59f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * regarding copyright ownership. The ASF licenses this file 69f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * to you under the Apache License, Version 2.0 (the "License"); 79f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * you may not use this file except in compliance with the License. 89f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * You may obtain a copy of the License at 99f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 109f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * http://www.apache.org/licenses/LICENSE-2.0 119f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 129f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Unless required by applicable law or agreed to in writing, software 139f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * distributed under the License is distributed on an "AS IS" BASIS, 149f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 159f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * See the License for the specific language governing permissions and 169f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * limitations under the License. 179f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 189f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson/* 199f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * $Id: IntStack.java 468655 2006-10-28 07:12:06Z minchau $ 209f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 219f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilsonpackage org.apache.xml.utils; 229f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 239f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilsonimport java.util.EmptyStackException; 249f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 259f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson/** 269f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Implement a stack of simple integers. 279f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 289f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * %OPT% 299f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * This is currently based on IntVector, which permits fast acess but pays a 309f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * heavy recopying penalty if/when its size is increased. If we expect deep 319f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * stacks, we should consider a version based on ChunkedIntVector. 329f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @xsl.usage internal 339f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 349f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilsonpublic class IntStack extends IntVector 359f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson{ 369f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 379f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 389f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Default constructor. Note that the default 399f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * block size is very small, for small lists. 409f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 419f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public IntStack() 429f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 439f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson super(); 449f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 459f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 469f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 479f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Construct a IntVector, using the given block size. 489f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 499f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param blocksize Size of block to allocate 509f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 519f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public IntStack(int blocksize) 529f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 539f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson super(blocksize); 549f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 559f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 569f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 579f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Copy constructor for IntStack 589f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 599f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param v IntStack to copy 609f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 619f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public IntStack (IntStack v) 629f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 639f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson super(v); 649f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 659f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 669f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 679f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Pushes an item onto the top of this stack. 689f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 699f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param i the int to be pushed onto this stack. 709f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @return the <code>item</code> argument. 719f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 729f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public int push(int i) 739f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 749f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 759f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if ((m_firstFree + 1) >= m_mapSize) 769f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 779f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_mapSize += m_blocksize; 789f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 799f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int newMap[] = new int[m_mapSize]; 809f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 819f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson System.arraycopy(m_map, 0, newMap, 0, m_firstFree + 1); 829f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 839f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_map = newMap; 849f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 859f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 869f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_map[m_firstFree] = i; 879f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 889f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_firstFree++; 899f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 909f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson return i; 919f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 929f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 939f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 949f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Removes the object at the top of this stack and returns that 959f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * object as the value of this function. 969f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 979f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @return The object at the top of this stack. 989f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 999f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public final int pop() 1009f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 1019f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson return m_map[--m_firstFree]; 1029f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 1039f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1049f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 1059f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Quickly pops a number of items from the stack. 1069f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 1079f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1089f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public final void quickPop(int n) 1099f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 1109f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_firstFree -= n; 1119f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 1129f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1139f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 1149f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Looks at the object at the top of this stack without removing it 1159f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * from the stack. 1169f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 1179f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @return the object at the top of this stack. 1189f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @throws EmptyStackException if this stack is empty. 1199f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 1209f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public final int peek() 1219f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 1229f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson try { 1239f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson return m_map[m_firstFree - 1]; 1249f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 1259f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson catch (ArrayIndexOutOfBoundsException e) 1269f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 1279f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson throw new EmptyStackException(); 1289f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 1299f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 1309f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1319f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 1329f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Looks at the object at the position the stack counting down n items. 1339f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 1349f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param n The number of items down, indexed from zero. 1359f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @return the object at n items down. 1369f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @throws EmptyStackException if this stack is empty. 1379f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 1389f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public int peek(int n) 1399f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 1409f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson try { 1419f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson return m_map[m_firstFree-(1+n)]; 1429f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 1439f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson catch (ArrayIndexOutOfBoundsException e) 1449f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 1459f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson throw new EmptyStackException(); 1469f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 1479f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 1489f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1499f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 1509f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Sets an object at a the top of the statck 1519f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 1529f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 1539f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param val object to set at the top 1549f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @throws EmptyStackException if this stack is empty. 1559f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 1569f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public void setTop(int val) 1579f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 1589f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson try { 1599f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_map[m_firstFree - 1] = val; 1609f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 1619f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson catch (ArrayIndexOutOfBoundsException e) 1629f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 1639f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson throw new EmptyStackException(); 1649f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 1659f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 1669f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1679f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 1689f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Tests if this stack is empty. 1699f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 1709f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @return <code>true</code> if this stack is empty; 1719f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * <code>false</code> otherwise. 1729f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @since JDK1.0 1739f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 1749f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public boolean empty() 1759f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 1769f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson return m_firstFree == 0; 1779f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 1789f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1799f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 1809f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Returns where an object is on this stack. 1819f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 1829f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param o the desired object. 1839f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @return the distance from the top of the stack where the object is] 1849f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * located; the return value <code>-1</code> indicates that the 1859f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * object is not on the stack. 1869f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @since JDK1.0 1879f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 1889f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public int search(int o) 1899f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 1909f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1919f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int i = lastIndexOf(o); 1929f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1939f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if (i >= 0) 1949f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 1959f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson return size() - i; 1969f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 1979f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1989f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson return -1; 1999f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 2009f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 2019f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 2029f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Returns clone of current IntStack 2039f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 2049f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @return clone of current IntStack 2059f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 2069f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public Object clone() 2079f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson throws CloneNotSupportedException 2089f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 2099f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson return (IntStack) super.clone(); 2109f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 2119f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson} 212