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: NodeVector.java 468655 2006-10-28 07:12:06Z minchau $ 209f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 219f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilsonpackage org.apache.xml.utils; 229f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 239f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilsonimport java.io.Serializable; 249f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 259f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilsonimport org.apache.xml.dtm.DTM; 269f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 279f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson/** 289f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * A very simple table that stores a list of Nodes. 299f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @xsl.usage internal 309f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 319f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilsonpublic class NodeVector implements Serializable, Cloneable 329f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson{ 339f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson static final long serialVersionUID = -713473092200731870L; 349f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 359f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 369f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Size of blocks to allocate. 379f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @serial 389f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 399f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson private int m_blocksize; 409f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 419f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 429f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Array of nodes this points to. 439f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @serial 449f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 459f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson private int m_map[]; 469f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 479f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 489f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Number of nodes in this NodeVector. 499f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @serial 509f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 519f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson protected int m_firstFree = 0; 529f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 539f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 549f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Size of the array this points to. 559f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @serial 569f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 579f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson private int m_mapSize; // lazy initialization 589f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 599f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 609f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Default constructor. 619f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 629f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public NodeVector() 639f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 649f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_blocksize = 32; 659f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_mapSize = 0; 669f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 679f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 689f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 699f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Construct a NodeVector, using the given block size. 709f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 719f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param blocksize Size of blocks to allocate 729f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 739f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public NodeVector(int blocksize) 749f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 759f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_blocksize = blocksize; 769f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_mapSize = 0; 779f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 789f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 799f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 809f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Get a cloned LocPathIterator. 819f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 829f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @return A clone of this 839f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 849f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @throws CloneNotSupportedException 859f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 869f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public Object clone() throws CloneNotSupportedException 879f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 889f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 899f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson NodeVector clone = (NodeVector) super.clone(); 909f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 919f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if ((null != this.m_map) && (this.m_map == clone.m_map)) 929f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 939f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson clone.m_map = new int[this.m_map.length]; 949f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 959f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson System.arraycopy(this.m_map, 0, clone.m_map, 0, this.m_map.length); 969f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 979f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 989f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson return clone; 999f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 1009f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1019f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 1029f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Get the length of the list. 1039f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 1049f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @return Number of nodes in this NodeVector 1059f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 1069f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public int size() 1079f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 1089f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson return m_firstFree; 1099f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 1109f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1119f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 1129f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Append a Node onto the vector. 1139f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 1149f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param value Node to add to the vector 1159f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 1169f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public void addElement(int value) 1179f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 1189f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1199f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if ((m_firstFree + 1) >= m_mapSize) 1209f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 1219f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if (null == m_map) 1229f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 1239f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_map = new int[m_blocksize]; 1249f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_mapSize = m_blocksize; 1259f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 1269f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson else 1279f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 1289f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_mapSize += m_blocksize; 1299f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1309f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int newMap[] = new int[m_mapSize]; 1319f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1329f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson System.arraycopy(m_map, 0, newMap, 0, m_firstFree + 1); 1339f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1349f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_map = newMap; 1359f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 1369f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 1379f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1389f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_map[m_firstFree] = value; 1399f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1409f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_firstFree++; 1419f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 1429f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1439f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 1449f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Append a Node onto the vector. 1459f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 1469f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param value Node to add to the vector 1479f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 1489f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public final void push(int value) 1499f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 1509f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1519f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int ff = m_firstFree; 1529f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1539f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if ((ff + 1) >= m_mapSize) 1549f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 1559f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if (null == m_map) 1569f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 1579f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_map = new int[m_blocksize]; 1589f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_mapSize = m_blocksize; 1599f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 1609f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson else 1619f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 1629f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_mapSize += m_blocksize; 1639f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1649f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int newMap[] = new int[m_mapSize]; 1659f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1669f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson System.arraycopy(m_map, 0, newMap, 0, ff + 1); 1679f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1689f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_map = newMap; 1699f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 1709f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 1719f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1729f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_map[ff] = value; 1739f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1749f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson ff++; 1759f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1769f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_firstFree = ff; 1779f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 1789f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1799f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 1809f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Pop a node from the tail of the vector and return the result. 1819f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 1829f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @return the node at the tail of the vector 1839f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 1849f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public final int pop() 1859f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 1869f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1879f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_firstFree--; 1889f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1899f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int n = m_map[m_firstFree]; 1909f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1919f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_map[m_firstFree] = DTM.NULL; 1929f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1939f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson return n; 1949f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 1959f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1969f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 1979f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Pop a node from the tail of the vector and return the 1989f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * top of the stack after the pop. 1999f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 2009f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @return The top of the stack after it's been popped 2019f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 2029f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public final int popAndTop() 2039f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 2049f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 2059f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_firstFree--; 2069f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 2079f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_map[m_firstFree] = DTM.NULL; 2089f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 2099f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson return (m_firstFree == 0) ? DTM.NULL : m_map[m_firstFree - 1]; 2109f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 2119f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 2129f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 2139f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Pop a node from the tail of the vector. 2149f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 2159f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public final void popQuick() 2169f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 2179f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 2189f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_firstFree--; 2199f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 2209f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_map[m_firstFree] = DTM.NULL; 2219f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 2229f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 2239f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 2249f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Return the node at the top of the stack without popping the stack. 2259f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Special purpose method for TransformerImpl, pushElemTemplateElement. 2269f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Performance critical. 2279f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 2289f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @return Node at the top of the stack or null if stack is empty. 2299f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 2309f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public final int peepOrNull() 2319f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 2329f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson return ((null != m_map) && (m_firstFree > 0)) 2339f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson ? m_map[m_firstFree - 1] : DTM.NULL; 2349f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 2359f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 2369f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 2379f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Push a pair of nodes into the stack. 2389f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Special purpose method for TransformerImpl, pushElemTemplateElement. 2399f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Performance critical. 2409f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 2419f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param v1 First node to add to vector 2429f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param v2 Second node to add to vector 2439f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 2449f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public final void pushPair(int v1, int v2) 2459f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 2469f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 2479f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if (null == m_map) 2489f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 2499f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_map = new int[m_blocksize]; 2509f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_mapSize = m_blocksize; 2519f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 2529f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson else 2539f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 2549f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if ((m_firstFree + 2) >= m_mapSize) 2559f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 2569f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_mapSize += m_blocksize; 2579f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 2589f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int newMap[] = new int[m_mapSize]; 2599f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 2609f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson System.arraycopy(m_map, 0, newMap, 0, m_firstFree); 2619f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 2629f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_map = newMap; 2639f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 2649f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 2659f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 2669f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_map[m_firstFree] = v1; 2679f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_map[m_firstFree + 1] = v2; 2689f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_firstFree += 2; 2699f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 2709f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 2719f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 2729f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Pop a pair of nodes from the tail of the stack. 2739f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Special purpose method for TransformerImpl, pushElemTemplateElement. 2749f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Performance critical. 2759f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 2769f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public final void popPair() 2779f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 2789f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 2799f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_firstFree -= 2; 2809f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_map[m_firstFree] = DTM.NULL; 2819f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_map[m_firstFree + 1] = DTM.NULL; 2829f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 2839f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 2849f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 2859f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Set the tail of the stack to the given node. 2869f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Special purpose method for TransformerImpl, pushElemTemplateElement. 2879f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Performance critical. 2889f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 2899f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param n Node to set at the tail of vector 2909f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 2919f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public final void setTail(int n) 2929f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 2939f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_map[m_firstFree - 1] = n; 2949f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 2959f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 2969f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 2979f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Set the given node one position from the tail. 2989f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Special purpose method for TransformerImpl, pushElemTemplateElement. 2999f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Performance critical. 3009f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 3019f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param n Node to set 3029f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 3039f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public final void setTailSub1(int n) 3049f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 3059f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_map[m_firstFree - 2] = n; 3069f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 3079f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 3089f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 3099f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Return the node at the tail of the vector without popping 3109f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Special purpose method for TransformerImpl, pushElemTemplateElement. 3119f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Performance critical. 3129f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 3139f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @return Node at the tail of the vector 3149f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 3159f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public final int peepTail() 3169f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 3179f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson return m_map[m_firstFree - 1]; 3189f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 3199f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 3209f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 3219f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Return the node one position from the tail without popping. 3229f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Special purpose method for TransformerImpl, pushElemTemplateElement. 3239f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Performance critical. 3249f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 3259f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @return Node one away from the tail 3269f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 3279f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public final int peepTailSub1() 3289f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 3299f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson return m_map[m_firstFree - 2]; 3309f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 3319f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 3329f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 3339f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Insert a node in order in the list. 3349f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 3359f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param value Node to insert 3369f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 3379f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public void insertInOrder(int value) 3389f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 3399f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 3409f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson for (int i = 0; i < m_firstFree; i++) 3419f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 3429f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if (value < m_map[i]) 3439f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 3449f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson insertElementAt(value, i); 3459f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 3469f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson return; 3479f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 3489f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 3499f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 3509f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson addElement(value); 3519f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 3529f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 3539f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 3549f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Inserts the specified node in this vector at the specified index. 3559f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Each component in this vector with an index greater or equal to 3569f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * the specified index is shifted upward to have an index one greater 3579f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * than the value it had previously. 3589f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 3599f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param value Node to insert 3609f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param at Position where to insert 3619f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 3629f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public void insertElementAt(int value, int at) 3639f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 3649f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 3659f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if (null == m_map) 3669f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 3679f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_map = new int[m_blocksize]; 3689f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_mapSize = m_blocksize; 3699f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 3709f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson else if ((m_firstFree + 1) >= m_mapSize) 3719f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 3729f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_mapSize += m_blocksize; 3739f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 3749f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int newMap[] = new int[m_mapSize]; 3759f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 3769f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson System.arraycopy(m_map, 0, newMap, 0, m_firstFree + 1); 3779f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 3789f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_map = newMap; 3799f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 3809f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 3819f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if (at <= (m_firstFree - 1)) 3829f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 3839f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson System.arraycopy(m_map, at, m_map, at + 1, m_firstFree - at); 3849f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 3859f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 3869f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_map[at] = value; 3879f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 3889f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_firstFree++; 3899f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 3909f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 3919f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 3929f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Append the nodes to the list. 3939f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 3949f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param nodes NodeVector to append to this list 3959f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 3969f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public void appendNodes(NodeVector nodes) 3979f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 3989f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 3999f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int nNodes = nodes.size(); 4009f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 4019f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if (null == m_map) 4029f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 4039f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_mapSize = nNodes + m_blocksize; 4049f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_map = new int[m_mapSize]; 4059f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 4069f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson else if ((m_firstFree + nNodes) >= m_mapSize) 4079f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 4089f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_mapSize += (nNodes + m_blocksize); 4099f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 4109f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int newMap[] = new int[m_mapSize]; 4119f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 4129f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson System.arraycopy(m_map, 0, newMap, 0, m_firstFree + nNodes); 4139f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 4149f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_map = newMap; 4159f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 4169f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 4179f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson System.arraycopy(nodes.m_map, 0, m_map, m_firstFree, nNodes); 4189f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 4199f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_firstFree += nNodes; 4209f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 4219f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 4229f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 4239f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Inserts the specified node in this vector at the specified index. 4249f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Each component in this vector with an index greater or equal to 4259f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * the specified index is shifted upward to have an index one greater 4269f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * than the value it had previously. 4279f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 4289f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public void removeAllElements() 4299f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 4309f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 4319f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if (null == m_map) 4329f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson return; 4339f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 4349f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson for (int i = 0; i < m_firstFree; i++) 4359f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 4369f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_map[i] = DTM.NULL; 4379f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 4389f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 4399f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_firstFree = 0; 4409f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 4419f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 4429f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 4439f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Set the length to zero, but don't clear the array. 4449f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 4459f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public void RemoveAllNoClear() 4469f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 4479f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 4489f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if (null == m_map) 4499f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson return; 4509f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 4519f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_firstFree = 0; 4529f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 4539f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 4549f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 4559f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Removes the first occurrence of the argument from this vector. 4569f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * If the object is found in this vector, each component in the vector 4579f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * with an index greater or equal to the object's index is shifted 4589f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * downward to have an index one smaller than the value it had 4599f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * previously. 4609f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 4619f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param s Node to remove from the list 4629f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 4639f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @return True if the node was successfully removed 4649f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 4659f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public boolean removeElement(int s) 4669f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 4679f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 4689f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if (null == m_map) 4699f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson return false; 4709f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 4719f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson for (int i = 0; i < m_firstFree; i++) 4729f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 4739f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int node = m_map[i]; 4749f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 4759f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if (node == s) 4769f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 4779f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if (i > m_firstFree) 4789f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson System.arraycopy(m_map, i + 1, m_map, i - 1, m_firstFree - i); 4799f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson else 4809f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_map[i] = DTM.NULL; 4819f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 4829f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_firstFree--; 4839f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 4849f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson return true; 4859f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 4869f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 4879f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 4889f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson return false; 4899f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 4909f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 4919f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 4929f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Deletes the component at the specified index. Each component in 4939f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * this vector with an index greater or equal to the specified 4949f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * index is shifted downward to have an index one smaller than 4959f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * the value it had previously. 4969f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 4979f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param i Index of node to remove 4989f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 4999f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public void removeElementAt(int i) 5009f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 5019f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 5029f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if (null == m_map) 5039f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson return; 5049f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 5059f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if (i > m_firstFree) 5069f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson System.arraycopy(m_map, i + 1, m_map, i - 1, m_firstFree - i); 5079f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson else 5089f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_map[i] = DTM.NULL; 5099f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 5109f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 5119f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 5129f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Sets the component at the specified index of this vector to be the 5139f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * specified object. The previous component at that position is discarded. 5149f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 5159f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * The index must be a value greater than or equal to 0 and less 5169f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * than the current size of the vector. 5179f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 5189f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param node Node to set 5199f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param index Index of where to set the node 5209f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 5219f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public void setElementAt(int node, int index) 5229f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 5239f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 5249f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if (null == m_map) 5259f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 5269f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_map = new int[m_blocksize]; 5279f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_mapSize = m_blocksize; 5289f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 5299f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 5309f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if(index == -1) 5319f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson addElement(node); 5329f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 5339f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_map[index] = node; 5349f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 5359f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 5369f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 5379f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Get the nth element. 5389f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 5399f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param i Index of node to get 5409f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 5419f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @return Node at specified index 5429f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 5439f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public int elementAt(int i) 5449f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 5459f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 5469f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if (null == m_map) 5479f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson return DTM.NULL; 5489f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 5499f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson return m_map[i]; 5509f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 5519f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 5529f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 5539f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Tell if the table contains the given node. 5549f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 5559f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param s Node to look for 5569f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 5579f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @return True if the given node was found. 5589f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 5599f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public boolean contains(int s) 5609f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 5619f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 5629f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if (null == m_map) 5639f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson return false; 5649f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 5659f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson for (int i = 0; i < m_firstFree; i++) 5669f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 5679f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int node = m_map[i]; 5689f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 5699f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if (node == s) 5709f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson return true; 5719f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 5729f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 5739f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson return false; 5749f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 5759f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 5769f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 5779f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Searches for the first occurence of the given argument, 5789f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * beginning the search at index, and testing for equality 5799f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * using the equals method. 5809f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 5819f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param elem Node to look for 5829f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param index Index of where to start the search 5839f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @return the index of the first occurrence of the object 5849f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * argument in this vector at position index or later in the 5859f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * vector; returns -1 if the object is not found. 5869f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 5879f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public int indexOf(int elem, int index) 5889f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 5899f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 5909f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if (null == m_map) 5919f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson return -1; 5929f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 5939f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson for (int i = index; i < m_firstFree; i++) 5949f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 5959f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int node = m_map[i]; 5969f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 5979f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if (node == elem) 5989f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson return i; 5999f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 6009f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 6019f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson return -1; 6029f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 6039f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 6049f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 6059f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Searches for the first occurence of the given argument, 6069f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * beginning the search at index, and testing for equality 6079f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * using the equals method. 6089f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 6099f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param elem Node to look for 6109f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @return the index of the first occurrence of the object 6119f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * argument in this vector at position index or later in the 6129f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * vector; returns -1 if the object is not found. 6139f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 6149f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public int indexOf(int elem) 6159f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 6169f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 6179f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if (null == m_map) 6189f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson return -1; 6199f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 6209f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson for (int i = 0; i < m_firstFree; i++) 6219f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 6229f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int node = m_map[i]; 6239f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 6249f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if (node == elem) 6259f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson return i; 6269f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 6279f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 6289f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson return -1; 6299f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 6309f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 6319f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 6329f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Sort an array using a quicksort algorithm. 6339f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 6349f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param a The array to be sorted. 6359f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param lo0 The low index. 6369f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param hi0 The high index. 6379f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 6389f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @throws Exception 6399f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 6409f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public void sort(int a[], int lo0, int hi0) throws Exception 6419f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 6429f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 6439f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int lo = lo0; 6449f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int hi = hi0; 6459f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 6469f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson // pause(lo, hi); 6479f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if (lo >= hi) 6489f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 6499f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson return; 6509f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 6519f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson else if (lo == hi - 1) 6529f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 6539f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 6549f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /* 6559f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * sort a two element list by swapping if necessary 6569f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 6579f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if (a[lo] > a[hi]) 6589f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 6599f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int T = a[lo]; 6609f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 6619f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson a[lo] = a[hi]; 6629f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson a[hi] = T; 6639f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 6649f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 6659f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson return; 6669f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 6679f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 6689f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /* 6699f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Pick a pivot and move it out of the way 6709f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 6719f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int pivot = a[(lo + hi) / 2]; 6729f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 6739f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson a[(lo + hi) / 2] = a[hi]; 6749f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson a[hi] = pivot; 6759f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 6769f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson while (lo < hi) 6779f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 6789f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 6799f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /* 6809f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Search forward from a[lo] until an element is found that 6819f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * is greater than the pivot or lo >= hi 6829f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 6839f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson while (a[lo] <= pivot && lo < hi) 6849f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 6859f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson lo++; 6869f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 6879f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 6889f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /* 6899f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Search backward from a[hi] until element is found that 6909f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * is less than the pivot, or lo >= hi 6919f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 6929f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson while (pivot <= a[hi] && lo < hi) 6939f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 6949f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson hi--; 6959f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 6969f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 6979f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /* 6989f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Swap elements a[lo] and a[hi] 6999f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 7009f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if (lo < hi) 7019f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 7029f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int T = a[lo]; 7039f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 7049f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson a[lo] = a[hi]; 7059f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson a[hi] = T; 7069f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 7079f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson // pause(); 7089f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 7099f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 7109f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson // if (stopRequested) { 7119f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson // return; 7129f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson // } 7139f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 7149f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 7159f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /* 7169f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Put the median in the "center" of the list 7179f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 7189f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson a[hi0] = a[hi]; 7199f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson a[hi] = pivot; 7209f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 7219f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /* 7229f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Recursive calls, elements a[lo0] to a[lo-1] are less than or 7239f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * equal to pivot, elements a[hi+1] to a[hi0] are greater than 7249f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * pivot. 7259f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 7269f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson sort(a, lo0, lo - 1); 7279f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson sort(a, hi + 1, hi0); 7289f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 7299f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 7309f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 7319f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Sort an array using a quicksort algorithm. 7329f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 7339f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @throws Exception 7349f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 7359f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public void sort() throws Exception 7369f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 7379f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson sort(m_map, 0, m_firstFree - 1); 7389f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 7399f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson} 740