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$ 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 ObjectVector, 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 ChunkedObjectVector. 329f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @xsl.usage internal 339f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 349f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilsonpublic class ObjectStack extends ObjectVector 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 ObjectStack() 429f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 439f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson super(); 449f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 459f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 469f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 479f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Construct a ObjectVector, using the given block size. 489f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 499f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param blocksize Size of block to allocate 509f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 519f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public ObjectStack(int blocksize) 529f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 539f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson super(blocksize); 549f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 559f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 569f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 579f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Copy constructor for ObjectStack 589f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 599f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param v ObjectStack to copy 609f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 619f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public ObjectStack (ObjectStack 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 Object push(Object 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 Object newMap[] = new Object[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 Object pop() 1009f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 1019f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson Object val = m_map[--m_firstFree]; 1029f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_map[m_firstFree] = null; 1039f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1049f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson return val; 1059f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 1069f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1079f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 1089f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Quickly pops a number of items from the stack. 1099f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 1109f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1119f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public void quickPop(int n) 1129f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 1139f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_firstFree -= n; 1149f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 1159f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1169f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 1179f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Looks at the object at the top of this stack without removing it 1189f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * from the stack. 1199f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 1209f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @return the object at the top of this stack. 1219f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @throws EmptyStackException if this stack is empty. 1229f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 1239f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public Object peek() 1249f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 1259f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson try { 1269f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson return m_map[m_firstFree - 1]; 1279f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 1289f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson catch (ArrayIndexOutOfBoundsException e) 1299f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 1309f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson throw new EmptyStackException(); 1319f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 1329f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 1339f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1349f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 1359f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Looks at the object at the position the stack counting down n items. 1369f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 1379f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param n The number of items down, indexed from zero. 1389f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @return the object at n items down. 1399f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @throws EmptyStackException if this stack is empty. 1409f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 1419f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public Object peek(int n) 1429f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 1439f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson try { 1449f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson return m_map[m_firstFree-(1+n)]; 1459f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 1469f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson catch (ArrayIndexOutOfBoundsException e) 1479f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 1489f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson throw new EmptyStackException(); 1499f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 1509f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 1519f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1529f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 1539f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Sets an object at a the top of the statck 1549f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 1559f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 1569f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param val object to set at the top 1579f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @throws EmptyStackException if this stack is empty. 1589f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 1599f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public void setTop(Object val) 1609f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 1619f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson try { 1629f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_map[m_firstFree - 1] = val; 1639f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 1649f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson catch (ArrayIndexOutOfBoundsException e) 1659f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 1669f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson throw new EmptyStackException(); 1679f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 1689f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 1699f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1709f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 1719f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Tests if this stack is empty. 1729f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 1739f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @return <code>true</code> if this stack is empty; 1749f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * <code>false</code> otherwise. 1759f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @since JDK1.0 1769f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 1779f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public boolean empty() 1789f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 1799f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson return m_firstFree == 0; 1809f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 1819f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1829f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 1839f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Returns where an object is on this stack. 1849f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 1859f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param o the desired object. 1869f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @return the distance from the top of the stack where the object is] 1879f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * located; the return value <code>-1</code> indicates that the 1889f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * object is not on the stack. 1899f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @since JDK1.0 1909f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 1919f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public int search(Object o) 1929f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 1939f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1949f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int i = lastIndexOf(o); 1959f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1969f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if (i >= 0) 1979f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 1989f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson return size() - i; 1999f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 2009f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 2019f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson return -1; 2029f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 2039f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 2049f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 2059f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Returns clone of current ObjectStack 2069f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 2079f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @return clone of current ObjectStack 2089f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 2099f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public Object clone() 2109f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson throws CloneNotSupportedException 2119f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 2129f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson return (ObjectStack) super.clone(); 2139f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 2149f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 2159f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson} 216