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: IntVector.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. 259f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 269f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * This version is based on a "realloc" strategy -- a simle array is 279f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * used, and when more storage is needed, a larger array is obtained 289f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * and all existing data is recopied into it. As a result, read/write 299f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * access to existing nodes is O(1) fast but appending may be O(N**2) 309f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * slow. See also SuballocatedIntVector. 319f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @xsl.usage internal 329f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 339f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilsonpublic class IntVector implements Cloneable 349f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson{ 359f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 369f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** Size of blocks to allocate */ 379f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson protected int m_blocksize; 389f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 399f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** Array of ints */ 409f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson protected int m_map[]; // IntStack is trying to see this directly 419f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 429f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** Number of ints in array */ 439f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson protected int m_firstFree = 0; 449f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 459f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** Size of array */ 469f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson protected int m_mapSize; 479f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 489f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 499f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Default constructor. Note that the default 509f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * block size is very small, for small lists. 519f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 529f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public IntVector() 539f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 549f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 559f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_blocksize = 32; 569f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_mapSize = m_blocksize; 579f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_map = new int[m_blocksize]; 589f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 599f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 609f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 619f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Construct a IntVector, using the given block size. 629f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 639f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param blocksize Size of block to allocate 649f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 659f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public IntVector(int blocksize) 669f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 679f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 689f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_blocksize = blocksize; 699f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_mapSize = blocksize; 709f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_map = new int[blocksize]; 719f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 729f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 739f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 749f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Construct a IntVector, using the given block size. 759f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 769f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param blocksize Size of block to allocate 779f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 789f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public IntVector(int blocksize, int increaseSize) 799f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 809f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 819f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_blocksize = increaseSize; 829f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_mapSize = blocksize; 839f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_map = new int[blocksize]; 849f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 859f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 869f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 879f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Copy constructor for IntVector 889f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 899f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param v Existing IntVector to copy 909f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 919f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public IntVector(IntVector v) 929f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 939f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_map = new int[v.m_mapSize]; 949f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_mapSize = v.m_mapSize; 959f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_firstFree = v.m_firstFree; 969f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_blocksize = v.m_blocksize; 979f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson System.arraycopy(v.m_map, 0, m_map, 0, m_firstFree); 989f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 999f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1009f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 1019f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Get the length of the list. 1029f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 1039f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @return length of the list 1049f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 1059f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public final int size() 1069f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 1079f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson return m_firstFree; 1089f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 1099f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1109f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 1119f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Get the length of the list. 1129f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 1139f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @return length of the list 1149f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 1159f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public final void setSize(int sz) 1169f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 1179f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_firstFree = sz; 1189f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 1199f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1209f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1219f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 1229f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Append a int onto the vector. 1239f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 1249f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param value Int to add to the list 1259f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 1269f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public final void addElement(int value) 1279f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 1289f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1299f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if ((m_firstFree + 1) >= m_mapSize) 1309f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 1319f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_mapSize += m_blocksize; 1329f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1339f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int newMap[] = new int[m_mapSize]; 1349f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1359f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson System.arraycopy(m_map, 0, newMap, 0, m_firstFree + 1); 1369f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1379f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_map = newMap; 1389f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 1399f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1409f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_map[m_firstFree] = value; 1419f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1429f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_firstFree++; 1439f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 1449f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1459f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 1469f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Append several int values onto the vector. 1479f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 1489f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param value Int to add to the list 1499f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 1509f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public final void addElements(int value, int numberOfElements) 1519f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 1529f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1539f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if ((m_firstFree + numberOfElements) >= m_mapSize) 1549f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 1559f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_mapSize += (m_blocksize+numberOfElements); 1569f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1579f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int newMap[] = new int[m_mapSize]; 1589f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1599f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson System.arraycopy(m_map, 0, newMap, 0, m_firstFree + 1); 1609f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1619f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_map = newMap; 1629f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 1639f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1649f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson for (int i = 0; i < numberOfElements; i++) 1659f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 1669f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_map[m_firstFree] = value; 1679f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_firstFree++; 1689f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 1699f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 1709f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1719f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 1729f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Append several slots onto the vector, but do not set the values. 1739f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 1749f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param numberOfElements Int to add to the list 1759f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 1769f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public final void addElements(int numberOfElements) 1779f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 1789f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1799f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if ((m_firstFree + numberOfElements) >= m_mapSize) 1809f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 1819f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_mapSize += (m_blocksize+numberOfElements); 1829f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1839f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int newMap[] = new int[m_mapSize]; 1849f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1859f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson System.arraycopy(m_map, 0, newMap, 0, m_firstFree + 1); 1869f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1879f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_map = newMap; 1889f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 1899f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1909f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_firstFree += numberOfElements; 1919f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 1929f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1939f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 1949f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 1959f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Inserts the specified node in this vector at the specified index. 1969f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Each component in this vector with an index greater or equal to 1979f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * the specified index is shifted upward to have an index one greater 1989f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * than the value it had previously. 1999f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 2009f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param value Int to insert 2019f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param at Index of where to insert 2029f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 2039f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public final void insertElementAt(int value, int at) 2049f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 2059f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 2069f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if ((m_firstFree + 1) >= m_mapSize) 2079f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 2089f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_mapSize += m_blocksize; 2099f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 2109f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson int newMap[] = new int[m_mapSize]; 2119f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 2129f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson System.arraycopy(m_map, 0, newMap, 0, m_firstFree + 1); 2139f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 2149f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_map = newMap; 2159f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 2169f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 2179f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if (at <= (m_firstFree - 1)) 2189f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 2199f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson System.arraycopy(m_map, at, m_map, at + 1, m_firstFree - at); 2209f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 2219f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 2229f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_map[at] = value; 2239f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 2249f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_firstFree++; 2259f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 2269f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 2279f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 2289f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Inserts the specified node in this vector at the specified index. 2299f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Each component in this vector with an index greater or equal to 2309f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * the specified index is shifted upward to have an index one greater 2319f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * than the value it had previously. 2329f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 2339f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public final void removeAllElements() 2349f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 2359f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 2369f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson for (int i = 0; i < m_firstFree; i++) 2379f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 2389f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_map[i] = java.lang.Integer.MIN_VALUE; 2399f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 2409f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 2419f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_firstFree = 0; 2429f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 2439f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 2449f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 2459f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Removes the first occurrence of the argument from this vector. 2469f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * If the object is found in this vector, each component in the vector 2479f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * with an index greater or equal to the object's index is shifted 2489f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * downward to have an index one smaller than the value it had 2499f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * previously. 2509f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 2519f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param s Int to remove from array 2529f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 2539f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @return True if the int was removed, false if it was not found 2549f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 2559f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public final boolean removeElement(int s) 2569f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 2579f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 2589f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson for (int i = 0; i < m_firstFree; i++) 2599f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 2609f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if (m_map[i] == s) 2619f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 2629f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if ((i + 1) < m_firstFree) 2639f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson System.arraycopy(m_map, i + 1, m_map, i - 1, m_firstFree - i); 2649f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson else 2659f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_map[i] = java.lang.Integer.MIN_VALUE; 2669f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 2679f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_firstFree--; 2689f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 2699f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson return true; 2709f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 2719f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 2729f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 2739f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson return false; 2749f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 2759f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 2769f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 2779f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Deletes the component at the specified index. Each component in 2789f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * this vector with an index greater or equal to the specified 2799f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * index is shifted downward to have an index one smaller than 2809f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * the value it had previously. 2819f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 2829f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param i index of where to remove and int 2839f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 2849f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public final void removeElementAt(int i) 2859f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 2869f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 2879f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if (i > m_firstFree) 2889f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson System.arraycopy(m_map, i + 1, m_map, i, m_firstFree); 2899f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson else 2909f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_map[i] = java.lang.Integer.MIN_VALUE; 2919f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 2929f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_firstFree--; 2939f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 2949f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 2959f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 2969f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Sets the component at the specified index of this vector to be the 2979f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * specified object. The previous component at that position is discarded. 2989f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 2999f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * The index must be a value greater than or equal to 0 and less 3009f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * than the current size of the vector. 3019f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 3029f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param value object to set 3039f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param index Index of where to set the object 3049f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 3059f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public final void setElementAt(int value, int index) 3069f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 3079f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson m_map[index] = value; 3089f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 3099f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 3109f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 3119f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Get the nth element. 3129f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 3139f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param i index of object to get 3149f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 3159f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @return object at given index 3169f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 3179f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public final int elementAt(int i) 3189f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 3199f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson return m_map[i]; 3209f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 3219f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 3229f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 3239f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Tell if the table contains the given node. 3249f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 3259f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param s object to look for 3269f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 3279f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @return true if the object is in the list 3289f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 3299f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public final boolean contains(int s) 3309f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 3319f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 3329f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson for (int i = 0; i < m_firstFree; i++) 3339f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 3349f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if (m_map[i] == s) 3359f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson return true; 3369f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 3379f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 3389f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson return false; 3399f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 3409f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 3419f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 3429f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Searches for the first occurence of the given argument, 3439f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * beginning the search at index, and testing for equality 3449f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * using the equals method. 3459f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 3469f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param elem object to look for 3479f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param index Index of where to begin search 3489f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @return the index of the first occurrence of the object 3499f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * argument in this vector at position index or later in the 3509f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * vector; returns -1 if the object is not found. 3519f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 3529f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public final int indexOf(int elem, int index) 3539f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 3549f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 3559f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson for (int i = index; i < m_firstFree; i++) 3569f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 3579f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if (m_map[i] == elem) 3589f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson return i; 3599f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 3609f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 3619f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson return java.lang.Integer.MIN_VALUE; 3629f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 3639f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 3649f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 3659f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Searches for the first occurence of the given argument, 3669f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * beginning the search at index, and testing for equality 3679f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * using the equals method. 3689f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 3699f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param elem object to look for 3709f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @return the index of the first occurrence of the object 3719f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * argument in this vector at position index or later in the 3729f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * vector; returns -1 if the object is not found. 3739f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 3749f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public final int indexOf(int elem) 3759f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 3769f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 3779f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson for (int i = 0; i < m_firstFree; i++) 3789f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 3799f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if (m_map[i] == elem) 3809f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson return i; 3819f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 3829f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 3839f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson return java.lang.Integer.MIN_VALUE; 3849f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 3859f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 3869f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 3879f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Searches for the first occurence of the given argument, 3889f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * beginning the search at index, and testing for equality 3899f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * using the equals method. 3909f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 3919f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @param elem Object to look for 3929f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @return the index of the first occurrence of the object 3939f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * argument in this vector at position index or later in the 3949f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * vector; returns -1 if the object is not found. 3959f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 3969f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public final int lastIndexOf(int elem) 3979f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 3989f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 3999f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson for (int i = (m_firstFree - 1); i >= 0; i--) 4009f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 4019f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson if (m_map[i] == elem) 4029f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson return i; 4039f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 4049f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 4059f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson return java.lang.Integer.MIN_VALUE; 4069f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 4079f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 4089f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson /** 4099f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * Returns clone of current IntVector 4109f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * 4119f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson * @return clone of current IntVector 4129f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson */ 4139f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson public Object clone() 4149f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson throws CloneNotSupportedException 4159f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson { 4169f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson return new IntVector(this); 4179f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson } 4189f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson 4199f8118474e9513f7a5b7d2a05e4a0fb15d1a6569Jesse Wilson} 420