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: SuballocatedIntVector.java 468655 2006-10-28 07:12:06Z minchau $ 209f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 219f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilsonpackage org.apache.xml.utils; 229f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 239f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson/** 249f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * A very simple table that stores a list of int. Very similar API to our 259f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * IntVector class (same API); different internal storage. 269f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 279f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * This version uses an array-of-arrays solution. Read/write access is thus 289f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * a bit slower than the simple IntVector, and basic storage is a trifle 299f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * higher due to the top-level array -- but appending is O(1) fast rather 309f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * than O(N**2) slow, which will swamp those costs in situations where 319f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * long vectors are being built up. 329f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 339f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Known issues: 349f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 359f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Some methods are private because they haven't yet been tested properly. 369f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 379f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Retrieval performance is critical, since this is used at the core 389f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * of the DTM model. (Append performance is almost as important.) 399f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * That's pushing me toward just letting reads from unset indices 409f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * throw exceptions or return stale data; safer behavior would have 419f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * performance costs. 429f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * */ 439f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilsonpublic class SuballocatedIntVector 449f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson{ 459f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** Size of blocks to allocate */ 469f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson protected int m_blocksize; 479f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 489f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** Bitwise addressing (much faster than div/remainder */ 499f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson protected int m_SHIFT, m_MASK; 509f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 519f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** The default number of blocks to (over)allocate by */ 529f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson protected static final int NUMBLOCKS_DEFAULT = 32; 539f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 549f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** The number of blocks to (over)allocate by */ 559f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson protected int m_numblocks = NUMBLOCKS_DEFAULT; 569f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 579f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** Array of arrays of ints */ 589f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson protected int m_map[][]; 599f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 609f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** Number of ints in array */ 619f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson protected int m_firstFree = 0; 629f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 639f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** "Shortcut" handle to m_map[0]. Surprisingly helpful for short vectors. */ 649f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson protected int m_map0[]; 659f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 669f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** "Shortcut" handle to most recently added row of m_map. 679f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Very helpful during construction. 689f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @xsl.usage internal 699f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 709f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson protected int m_buildCache[]; 719f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson protected int m_buildCacheStartIndex; 729f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 739f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 749f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 759f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Default constructor. Note that the default 769f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * block size is currently 2K, which may be overkill for 779f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * small lists and undershootng for large ones. 789f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 799f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public SuballocatedIntVector() 809f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 819f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson this(2048); 829f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 839f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 849f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 859f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Construct a IntVector, using the given block size and number 869f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * of blocks. For efficiency, we will round the requested size 879f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * off to a power of two. 889f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 899f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param blocksize Size of block to allocate 909f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param numblocks Number of blocks to allocate 919f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * */ 929f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public SuballocatedIntVector(int blocksize, int numblocks) 939f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 949f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson //m_blocksize = blocksize; 959f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson for(m_SHIFT=0;0!=(blocksize>>>=1);++m_SHIFT) 969f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson ; 979f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_blocksize=1<<m_SHIFT; 989f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_MASK=m_blocksize-1; 999f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_numblocks = numblocks; 1009f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1019f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_map0=new int[m_blocksize]; 1029f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_map = new int[numblocks][]; 1039f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_map[0]=m_map0; 1049f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_buildCache = m_map0; 1059f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_buildCacheStartIndex = 0; 1069f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 1079f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1089f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** Construct a IntVector, using the given block size and 1099f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * the default number of blocks (32). 1109f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 1119f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param blocksize Size of block to allocate 1129f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * */ 1139f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public SuballocatedIntVector(int blocksize) 1149f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 1159f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson this(blocksize, NUMBLOCKS_DEFAULT); 1169f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 1179f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1189f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 1199f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Get the length of the list. 1209f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 1219f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @return length of the list 1229f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 1239f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public int size() 1249f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 1259f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson return m_firstFree; 1269f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 1279f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1289f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 1299f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Set the length of the list. This will only work to truncate the list, and 1309f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * even then it has not been heavily tested and may not be trustworthy. 1319f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 1329f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @return length of the list 1339f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 1349f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public void setSize(int sz) 1359f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 1369f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if(m_firstFree>sz) // Whups; had that backward! 1379f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_firstFree = sz; 1389f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 1399f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1409f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 1419f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Append a int onto the vector. 1429f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 1439f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param value Int to add to the list 1449f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 1459f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public void addElement(int value) 1469f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 1479f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int indexRelativeToCache = m_firstFree - m_buildCacheStartIndex; 1489f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1499f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson // Is the new index an index into the cache row of m_map? 1509f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if(indexRelativeToCache >= 0 && indexRelativeToCache < m_blocksize) { 1519f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_buildCache[indexRelativeToCache]=value; 1529f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson ++m_firstFree; 1539f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } else { 1549f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson // Growing the outer array should be rare. We initialize to a 1559f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson // total of m_blocksize squared elements, which at the default 1569f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson // size is 4M integers... and we grow by at least that much each 1579f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson // time. However, attempts to microoptimize for this (assume 1589f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson // long enough and catch exceptions) yield no noticable 1599f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson // improvement. 1609f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1619f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int index=m_firstFree>>>m_SHIFT; 1629f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int offset=m_firstFree&m_MASK; 1639f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1649f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if(index>=m_map.length) 1659f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 1669f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int newsize=index+m_numblocks; 1679f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int[][] newMap=new int[newsize][]; 1689f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson System.arraycopy(m_map, 0, newMap, 0, m_map.length); 1699f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_map=newMap; 1709f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 1719f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int[] block=m_map[index]; 1729f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if(null==block) 1739f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson block=m_map[index]=new int[m_blocksize]; 1749f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson block[offset]=value; 1759f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1769f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson // Cache the current row of m_map. Next m_blocksize-1 1779f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson // values added will go to this row. 1789f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_buildCache = block; 1799f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_buildCacheStartIndex = m_firstFree-offset; 1809f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1819f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson ++m_firstFree; 1829f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 1839f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 1849f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1859f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 1869f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Append several int values onto the vector. 1879f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 1889f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param value Int to add to the list 1899f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 1909f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson private void addElements(int value, int numberOfElements) 1919f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 1929f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if(m_firstFree+numberOfElements<m_blocksize) 1939f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson for (int i = 0; i < numberOfElements; i++) 1949f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 1959f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_map0[m_firstFree++]=value; 1969f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 1979f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson else 1989f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 1999f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int index=m_firstFree>>>m_SHIFT; 2009f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int offset=m_firstFree&m_MASK; 2019f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_firstFree+=numberOfElements; 2029f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson while( numberOfElements>0) 2039f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 2049f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if(index>=m_map.length) 2059f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 2069f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int newsize=index+m_numblocks; 2079f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int[][] newMap=new int[newsize][]; 2089f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson System.arraycopy(m_map, 0, newMap, 0, m_map.length); 2099f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_map=newMap; 2109f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 2119f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int[] block=m_map[index]; 2129f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if(null==block) 2139f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson block=m_map[index]=new int[m_blocksize]; 2149f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int copied=(m_blocksize-offset < numberOfElements) 2159f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson ? m_blocksize-offset : numberOfElements; 2169f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson numberOfElements-=copied; 2179f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson while(copied-- > 0) 2189f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson block[offset++]=value; 2199f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 2209f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson ++index;offset=0; 2219f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 2229f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 2239f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 2249f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 2259f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 2269f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Append several slots onto the vector, but do not set the values. 2279f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Note: "Not Set" means the value is unspecified. 2289f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 2299f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param numberOfElements Int to add to the list 2309f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 2319f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson private void addElements(int numberOfElements) 2329f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 2339f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int newlen=m_firstFree+numberOfElements; 2349f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if(newlen>m_blocksize) 2359f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 2369f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int index=m_firstFree>>>m_SHIFT; 2379f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int newindex=(m_firstFree+numberOfElements)>>>m_SHIFT; 2389f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson for(int i=index+1;i<=newindex;++i) 2399f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_map[i]=new int[m_blocksize]; 2409f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 2419f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_firstFree=newlen; 2429f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 2439f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 2449f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 2459f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Inserts the specified node in this vector at the specified index. 2469f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Each component in this vector with an index greater or equal to 2479f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * the specified index is shifted upward to have an index one greater 2489f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * than the value it had previously. 2499f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 2509f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Insertion may be an EXPENSIVE operation! 2519f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 2529f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param value Int to insert 2539f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param at Index of where to insert 2549f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 2559f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson private void insertElementAt(int value, int at) 2569f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 2579f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if(at==m_firstFree) 2589f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson addElement(value); 2599f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson else if (at>m_firstFree) 2609f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 2619f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int index=at>>>m_SHIFT; 2629f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if(index>=m_map.length) 2639f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 2649f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int newsize=index+m_numblocks; 2659f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int[][] newMap=new int[newsize][]; 2669f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson System.arraycopy(m_map, 0, newMap, 0, m_map.length); 2679f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_map=newMap; 2689f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 2699f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int[] block=m_map[index]; 2709f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if(null==block) 2719f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson block=m_map[index]=new int[m_blocksize]; 2729f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int offset=at&m_MASK; 2739f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson block[offset]=value; 2749f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_firstFree=offset+1; 2759f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 2769f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson else 2779f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 2789f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int index=at>>>m_SHIFT; 2799f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int maxindex=m_firstFree>>>m_SHIFT; // %REVIEW% (m_firstFree+1?) 2809f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson ++m_firstFree; 2819f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int offset=at&m_MASK; 2829f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int push; 2839f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 2849f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson // ***** Easier to work down from top? 2859f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson while(index<=maxindex) 2869f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 2879f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int copylen=m_blocksize-offset-1; 2889f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int[] block=m_map[index]; 2899f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if(null==block) 2909f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 2919f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson push=0; 2929f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson block=m_map[index]=new int[m_blocksize]; 2939f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 2949f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson else 2959f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 2969f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson push=block[m_blocksize-1]; 2979f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson System.arraycopy(block, offset , block, offset+1, copylen); 2989f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 2999f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson block[offset]=value; 3009f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson value=push; 3019f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson offset=0; 3029f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson ++index; 3039f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 3049f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 3059f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 3069f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 3079f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 3089f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Wipe it out. Currently defined as equivalent to setSize(0). 3099f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 3109f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public void removeAllElements() 3119f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 3129f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_firstFree = 0; 3139f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_buildCache = m_map0; 3149f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_buildCacheStartIndex = 0; 3159f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 3169f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 3179f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 3189f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Removes the first occurrence of the argument from this vector. 3199f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * If the object is found in this vector, each component in the vector 3209f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * with an index greater or equal to the object's index is shifted 3219f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * downward to have an index one smaller than the value it had 3229f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * previously. 3239f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 3249f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param s Int to remove from array 3259f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 3269f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @return True if the int was removed, false if it was not found 3279f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 3289f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson private boolean removeElement(int s) 3299f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 3309f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int at=indexOf(s,0); 3319f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if(at<0) 3329f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson return false; 3339f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson removeElementAt(at); 3349f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson return true; 3359f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 3369f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 3379f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 3389f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Deletes the component at the specified index. Each component in 3399f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * this vector with an index greater or equal to the specified 3409f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * index is shifted downward to have an index one smaller than 3419f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * the value it had previously. 3429f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 3439f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param i index of where to remove and int 3449f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 3459f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson private void removeElementAt(int at) 3469f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 3479f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson // No point in removing elements that "don't exist"... 3489f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if(at<m_firstFree) 3499f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 3509f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int index=at>>>m_SHIFT; 3519f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int maxindex=m_firstFree>>>m_SHIFT; 3529f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int offset=at&m_MASK; 3539f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 3549f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson while(index<=maxindex) 3559f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 3569f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int copylen=m_blocksize-offset-1; 3579f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int[] block=m_map[index]; 3589f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if(null==block) 3599f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson block=m_map[index]=new int[m_blocksize]; 3609f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson else 3619f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson System.arraycopy(block, offset+1, block, offset, copylen); 3629f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if(index<maxindex) 3639f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 3649f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int[] next=m_map[index+1]; 3659f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if(next!=null) 3669f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson block[m_blocksize-1]=(next!=null) ? next[0] : 0; 3679f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 3689f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson else 3699f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson block[m_blocksize-1]=0; 3709f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson offset=0; 3719f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson ++index; 3729f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 3739f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 3749f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson --m_firstFree; 3759f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 3769f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 3779f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 3789f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Sets the component at the specified index of this vector to be the 3799f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * specified object. The previous component at that position is discarded. 3809f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 3819f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * The index must be a value greater than or equal to 0 and less 3829f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * than the current size of the vector. 3839f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 3849f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param value object to set 3859f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param at Index of where to set the object 3869f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 3879f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public void setElementAt(int value, int at) 3889f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 3899f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if(at<m_blocksize) 3909f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_map0[at]=value; 3919f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson else 3929f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 3939f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int index=at>>>m_SHIFT; 3949f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int offset=at&m_MASK; 3959f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 3969f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if(index>=m_map.length) 3979f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 3989f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int newsize=index+m_numblocks; 3999f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int[][] newMap=new int[newsize][]; 4009f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson System.arraycopy(m_map, 0, newMap, 0, m_map.length); 4019f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_map=newMap; 4029f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 4039f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 4049f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int[] block=m_map[index]; 4059f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if(null==block) 4069f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson block=m_map[index]=new int[m_blocksize]; 4079f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson block[offset]=value; 4089f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 4099f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 4109f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if(at>=m_firstFree) 4119f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_firstFree=at+1; 4129f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 4139f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 4149f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 4159f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 4169f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Get the nth element. This is often at the innermost loop of an 4179f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * application, so performance is critical. 4189f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 4199f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param i index of value to get 4209f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 4219f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @return value at given index. If that value wasn't previously set, 4229f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * the result is undefined for performance reasons. It may throw an 4239f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * exception (see below), may return zero, or (if setSize has previously 4249f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * been used) may return stale data. 4259f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 4269f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @throws ArrayIndexOutOfBoundsException if the index was _clearly_ 4279f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * unreasonable (negative, or past the highest block). 4289f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 4299f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @throws NullPointerException if the index points to a block that could 4309f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * have existed (based on the highest index used) but has never had anything 4319f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * set into it. 4329f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * %REVIEW% Could add a catch to create the block in that case, or return 0. 4339f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Try/Catch is _supposed_ to be nearly free when not thrown to. Do we 4349f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * believe that? Should we have a separate safeElementAt? 4359f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 4369f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public int elementAt(int i) 4379f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 4389f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson // This is actually a significant optimization! 4399f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if(i<m_blocksize) 4409f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson return m_map0[i]; 4419f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 4429f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson return m_map[i>>>m_SHIFT][i&m_MASK]; 4439f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 4449f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 4459f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 4469f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Tell if the table contains the given node. 4479f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 4489f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param s object to look for 4499f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 4509f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @return true if the object is in the list 4519f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 4529f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson private boolean contains(int s) 4539f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 4549f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson return (indexOf(s,0) >= 0); 4559f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 4569f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 4579f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 4589f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Searches for the first occurence of the given argument, 4599f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * beginning the search at index, and testing for equality 4609f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * using the equals method. 4619f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 4629f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param elem object to look for 4639f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param index Index of where to begin search 4649f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @return the index of the first occurrence of the object 4659f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * argument in this vector at position index or later in the 4669f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * vector; returns -1 if the object is not found. 4679f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 4689f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public int indexOf(int elem, int index) 4699f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 4709f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if(index>=m_firstFree) 4719f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson return -1; 4729f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 4739f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int bindex=index>>>m_SHIFT; 4749f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int boffset=index&m_MASK; 4759f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int maxindex=m_firstFree>>>m_SHIFT; 4769f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int[] block; 4779f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 4789f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson for(;bindex<maxindex;++bindex) 4799f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 4809f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson block=m_map[bindex]; 4819f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if(block!=null) 4829f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson for(int offset=boffset;offset<m_blocksize;++offset) 4839f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if(block[offset]==elem) 4849f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson return offset+bindex*m_blocksize; 4859f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson boffset=0; // after first 4869f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 4879f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson // Last block may need to stop before end 4889f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int maxoffset=m_firstFree&m_MASK; 4899f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson block=m_map[maxindex]; 4909f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson for(int offset=boffset;offset<maxoffset;++offset) 4919f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if(block[offset]==elem) 4929f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson return offset+maxindex*m_blocksize; 4939f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 4949f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson return -1; 4959f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 4969f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 4979f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 4989f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Searches for the first occurence of the given argument, 4999f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * beginning the search at index, and testing for equality 5009f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * using the equals method. 5019f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 5029f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param elem object to look for 5039f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @return the index of the first occurrence of the object 5049f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * argument in this vector at position index or later in the 5059f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * vector; returns -1 if the object is not found. 5069f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 5079f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public int indexOf(int elem) 5089f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 5099f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson return indexOf(elem,0); 5109f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 5119f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 5129f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 5139f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Searches for the first occurence of the given argument, 5149f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * beginning the search at index, and testing for equality 5159f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * using the equals method. 5169f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 5179f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param elem Object to look for 5189f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @return the index of the first occurrence of the object 5199f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * argument in this vector at position index or later in the 5209f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * vector; returns -1 if the object is not found. 5219f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 5229f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson private int lastIndexOf(int elem) 5239f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 5249f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int boffset=m_firstFree&m_MASK; 5259f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson for(int index=m_firstFree>>>m_SHIFT; 5269f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson index>=0; 5279f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson --index) 5289f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 5299f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int[] block=m_map[index]; 5309f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if(block!=null) 5319f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson for(int offset=boffset; offset>=0; --offset) 5329f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if(block[offset]==elem) 5339f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson return offset+index*m_blocksize; 5349f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson boffset=0; // after first 5359f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 5369f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson return -1; 5379f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 5389f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 5399f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 5409f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Return the internal m_map0 array 5419f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @return the m_map0 array 5429f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 5439f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public final int[] getMap0() 5449f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 5459f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson return m_map0; 5469f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 5479f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 5489f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 5499f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Return the m_map double array 5509f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @return the internal map of array of arrays 5519f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 5529f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public final int[][] getMap() 5539f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 5549f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson return m_map; 5559f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 5569f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 5579f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson} 558