1 /* 2 * reserved comment block 3 * DO NOT REMOVE OR ALTER! 4 */ 5 /* 6 * Licensed to the Apache Software Foundation (ASF) under one or more 7 * contributor license agreements. See the NOTICE file distributed with 8 * this work for additional information regarding copyright ownership. 9 * The ASF licenses this file to You under the Apache License, Version 2.0 10 * (the "License"); you may not use this file except in compliance with 11 * the License. You may obtain a copy of the License at 12 * 13 * http://www.apache.org/licenses/LICENSE-2.0 14 * 15 * Unless required by applicable law or agreed to in writing, software 16 * distributed under the License is distributed on an "AS IS" BASIS, 17 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 18 * See the License for the specific language governing permissions and 19 * limitations under the License. 20 */ 21 22 package com.sun.org.apache.xml.internal.utils; 23 24 /** 25 * A very simple table that stores a list of int. 26 * 27 * This version is based on a "realloc" strategy -- a simle array is 28 * used, and when more storage is needed, a larger array is obtained 29 * and all existing data is recopied into it. As a result, read/write 30 * access to existing nodes is O(1) fast but appending may be O(N**2) 31 * slow. See also SuballocatedIntVector. 32 * @xsl.usage internal 33 */ 34 public class IntVector implements Cloneable 35 { 36 37 /** Size of blocks to allocate */ 38 protected int m_blocksize; 39 40 /** Array of ints */ 41 protected int m_map[]; // IntStack is trying to see this directly 42 43 /** Number of ints in array */ 44 protected int m_firstFree = 0; 45 46 /** Size of array */ 47 protected int m_mapSize; 48 49 /** 50 * Default constructor. Note that the default 51 * block size is very small, for small lists. 52 */ IntVector()53 public IntVector() 54 { 55 56 m_blocksize = 32; 57 m_mapSize = m_blocksize; 58 m_map = new int[m_blocksize]; 59 } 60 61 /** 62 * Construct a IntVector, using the given block size. 63 * 64 * @param blocksize Size of block to allocate 65 */ IntVector(int blocksize)66 public IntVector(int blocksize) 67 { 68 69 m_blocksize = blocksize; 70 m_mapSize = blocksize; 71 m_map = new int[blocksize]; 72 } 73 74 /** 75 * Construct a IntVector, using the given block size. 76 * 77 * @param blocksize Size of block to allocate 78 */ IntVector(int blocksize, int increaseSize)79 public IntVector(int blocksize, int increaseSize) 80 { 81 82 m_blocksize = increaseSize; 83 m_mapSize = blocksize; 84 m_map = new int[blocksize]; 85 } 86 87 /** 88 * Copy constructor for IntVector 89 * 90 * @param v Existing IntVector to copy 91 */ IntVector(IntVector v)92 public IntVector(IntVector v) 93 { 94 m_map = new int[v.m_mapSize]; 95 m_mapSize = v.m_mapSize; 96 m_firstFree = v.m_firstFree; 97 m_blocksize = v.m_blocksize; 98 System.arraycopy(v.m_map, 0, m_map, 0, m_firstFree); 99 } 100 101 /** 102 * Get the length of the list. 103 * 104 * @return length of the list 105 */ size()106 public final int size() 107 { 108 return m_firstFree; 109 } 110 111 /** 112 * Get the length of the list. 113 * 114 * @return length of the list 115 */ setSize(int sz)116 public final void setSize(int sz) 117 { 118 m_firstFree = sz; 119 } 120 121 122 /** 123 * Append a int onto the vector. 124 * 125 * @param value Int to add to the list 126 */ addElement(int value)127 public final void addElement(int value) 128 { 129 130 if ((m_firstFree + 1) >= m_mapSize) 131 { 132 m_mapSize += m_blocksize; 133 134 int newMap[] = new int[m_mapSize]; 135 136 System.arraycopy(m_map, 0, newMap, 0, m_firstFree + 1); 137 138 m_map = newMap; 139 } 140 141 m_map[m_firstFree] = value; 142 143 m_firstFree++; 144 } 145 146 /** 147 * Append several int values onto the vector. 148 * 149 * @param value Int to add to the list 150 */ addElements(int value, int numberOfElements)151 public final void addElements(int value, int numberOfElements) 152 { 153 154 if ((m_firstFree + numberOfElements) >= m_mapSize) 155 { 156 m_mapSize += (m_blocksize+numberOfElements); 157 158 int newMap[] = new int[m_mapSize]; 159 160 System.arraycopy(m_map, 0, newMap, 0, m_firstFree + 1); 161 162 m_map = newMap; 163 } 164 165 for (int i = 0; i < numberOfElements; i++) 166 { 167 m_map[m_firstFree] = value; 168 m_firstFree++; 169 } 170 } 171 172 /** 173 * Append several slots onto the vector, but do not set the values. 174 * 175 * @param numberOfElements Int to add to the list 176 */ addElements(int numberOfElements)177 public final void addElements(int numberOfElements) 178 { 179 180 if ((m_firstFree + numberOfElements) >= m_mapSize) 181 { 182 m_mapSize += (m_blocksize+numberOfElements); 183 184 int newMap[] = new int[m_mapSize]; 185 186 System.arraycopy(m_map, 0, newMap, 0, m_firstFree + 1); 187 188 m_map = newMap; 189 } 190 191 m_firstFree += numberOfElements; 192 } 193 194 195 /** 196 * Inserts the specified node in this vector at the specified index. 197 * Each component in this vector with an index greater or equal to 198 * the specified index is shifted upward to have an index one greater 199 * than the value it had previously. 200 * 201 * @param value Int to insert 202 * @param at Index of where to insert 203 */ insertElementAt(int value, int at)204 public final void insertElementAt(int value, int at) 205 { 206 207 if ((m_firstFree + 1) >= m_mapSize) 208 { 209 m_mapSize += m_blocksize; 210 211 int newMap[] = new int[m_mapSize]; 212 213 System.arraycopy(m_map, 0, newMap, 0, m_firstFree + 1); 214 215 m_map = newMap; 216 } 217 218 if (at <= (m_firstFree - 1)) 219 { 220 System.arraycopy(m_map, at, m_map, at + 1, m_firstFree - at); 221 } 222 223 m_map[at] = value; 224 225 m_firstFree++; 226 } 227 228 /** 229 * Inserts the specified node in this vector at the specified index. 230 * Each component in this vector with an index greater or equal to 231 * the specified index is shifted upward to have an index one greater 232 * than the value it had previously. 233 */ removeAllElements()234 public final void removeAllElements() 235 { 236 237 for (int i = 0; i < m_firstFree; i++) 238 { 239 m_map[i] = java.lang.Integer.MIN_VALUE; 240 } 241 242 m_firstFree = 0; 243 } 244 245 /** 246 * Removes the first occurrence of the argument from this vector. 247 * If the object is found in this vector, each component in the vector 248 * with an index greater or equal to the object's index is shifted 249 * downward to have an index one smaller than the value it had 250 * previously. 251 * 252 * @param s Int to remove from array 253 * 254 * @return True if the int was removed, false if it was not found 255 */ removeElement(int s)256 public final boolean removeElement(int s) 257 { 258 259 for (int i = 0; i < m_firstFree; i++) 260 { 261 if (m_map[i] == s) 262 { 263 if ((i + 1) < m_firstFree) 264 System.arraycopy(m_map, i + 1, m_map, i - 1, m_firstFree - i); 265 else 266 m_map[i] = java.lang.Integer.MIN_VALUE; 267 268 m_firstFree--; 269 270 return true; 271 } 272 } 273 274 return false; 275 } 276 277 /** 278 * Deletes the component at the specified index. Each component in 279 * this vector with an index greater or equal to the specified 280 * index is shifted downward to have an index one smaller than 281 * the value it had previously. 282 * 283 * @param i index of where to remove and int 284 */ removeElementAt(int i)285 public final void removeElementAt(int i) 286 { 287 288 if (i > m_firstFree) 289 System.arraycopy(m_map, i + 1, m_map, i, m_firstFree); 290 else 291 m_map[i] = java.lang.Integer.MIN_VALUE; 292 293 m_firstFree--; 294 } 295 296 /** 297 * Sets the component at the specified index of this vector to be the 298 * specified object. The previous component at that position is discarded. 299 * 300 * The index must be a value greater than or equal to 0 and less 301 * than the current size of the vector. 302 * 303 * @param value object to set 304 * @param index Index of where to set the object 305 */ setElementAt(int value, int index)306 public final void setElementAt(int value, int index) 307 { 308 m_map[index] = value; 309 } 310 311 /** 312 * Get the nth element. 313 * 314 * @param i index of object to get 315 * 316 * @return object at given index 317 */ elementAt(int i)318 public final int elementAt(int i) 319 { 320 return m_map[i]; 321 } 322 323 /** 324 * Tell if the table contains the given node. 325 * 326 * @param s object to look for 327 * 328 * @return true if the object is in the list 329 */ contains(int s)330 public final boolean contains(int s) 331 { 332 333 for (int i = 0; i < m_firstFree; i++) 334 { 335 if (m_map[i] == s) 336 return true; 337 } 338 339 return false; 340 } 341 342 /** 343 * Searches for the first occurence of the given argument, 344 * beginning the search at index, and testing for equality 345 * using the equals method. 346 * 347 * @param elem object to look for 348 * @param index Index of where to begin search 349 * @return the index of the first occurrence of the object 350 * argument in this vector at position index or later in the 351 * vector; returns -1 if the object is not found. 352 */ indexOf(int elem, int index)353 public final int indexOf(int elem, int index) 354 { 355 356 for (int i = index; i < m_firstFree; i++) 357 { 358 if (m_map[i] == elem) 359 return i; 360 } 361 362 return java.lang.Integer.MIN_VALUE; 363 } 364 365 /** 366 * Searches for the first occurence of the given argument, 367 * beginning the search at index, and testing for equality 368 * using the equals method. 369 * 370 * @param elem object to look for 371 * @return the index of the first occurrence of the object 372 * argument in this vector at position index or later in the 373 * vector; returns -1 if the object is not found. 374 */ indexOf(int elem)375 public final int indexOf(int elem) 376 { 377 378 for (int i = 0; i < m_firstFree; i++) 379 { 380 if (m_map[i] == elem) 381 return i; 382 } 383 384 return java.lang.Integer.MIN_VALUE; 385 } 386 387 /** 388 * Searches for the first occurence of the given argument, 389 * beginning the search at index, and testing for equality 390 * using the equals method. 391 * 392 * @param elem Object to look for 393 * @return the index of the first occurrence of the object 394 * argument in this vector at position index or later in the 395 * vector; returns -1 if the object is not found. 396 */ lastIndexOf(int elem)397 public final int lastIndexOf(int elem) 398 { 399 400 for (int i = (m_firstFree - 1); i >= 0; i--) 401 { 402 if (m_map[i] == elem) 403 return i; 404 } 405 406 return java.lang.Integer.MIN_VALUE; 407 } 408 409 /** 410 * Returns clone of current IntVector 411 * 412 * @return clone of current IntVector 413 */ clone()414 public Object clone() 415 throws CloneNotSupportedException 416 { 417 return new IntVector(this); 418 } 419 420 } 421