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 22package com.sun.org.apache.xml.internal.utils; 23 24/** 25 * A very simple table that stores a list of objects. 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. 32 * @xsl.usage internal 33 */ 34public class ObjectVector implements Cloneable 35{ 36 37 /** Size of blocks to allocate */ 38 protected int m_blocksize; 39 40 /** Array of objects */ 41 protected Object m_map[]; 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 */ 53 public ObjectVector() 54 { 55 56 m_blocksize = 32; 57 m_mapSize = m_blocksize; 58 m_map = new Object[m_blocksize]; 59 } 60 61 /** 62 * Construct a IntVector, using the given block size. 63 * 64 * @param blocksize Size of block to allocate 65 */ 66 public ObjectVector(int blocksize) 67 { 68 69 m_blocksize = blocksize; 70 m_mapSize = blocksize; 71 m_map = new Object[blocksize]; 72 } 73 74 /** 75 * Construct a IntVector, using the given block size. 76 * 77 * @param blocksize Size of block to allocate 78 */ 79 public ObjectVector(int blocksize, int increaseSize) 80 { 81 82 m_blocksize = increaseSize; 83 m_mapSize = blocksize; 84 m_map = new Object[blocksize]; 85 } 86 87 /** 88 * Copy constructor for ObjectVector 89 * 90 * @param v Existing ObjectVector to copy 91 */ 92 public ObjectVector(ObjectVector v) 93 { 94 m_map = new Object[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 */ 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 */ 116 public final void setSize(int sz) 117 { 118 m_firstFree = sz; 119 } 120 121 122 /** 123 * Append an object onto the vector. 124 * 125 * @param value Object to add to the list 126 */ 127 public final void addElement(Object value) 128 { 129 130 if ((m_firstFree + 1) >= m_mapSize) 131 { 132 m_mapSize += m_blocksize; 133 134 Object newMap[] = new Object[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 Object values onto the vector. 148 * 149 * @param value Object to add to the list 150 */ 151 public final void addElements(Object value, int numberOfElements) 152 { 153 154 if ((m_firstFree + numberOfElements) >= m_mapSize) 155 { 156 m_mapSize += (m_blocksize+numberOfElements); 157 158 Object newMap[] = new Object[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 number of slots to append 176 */ 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 Object newMap[] = new Object[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 object 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 Object to insert 202 * @param at Index of where to insert 203 */ 204 public final void insertElementAt(Object value, int at) 205 { 206 207 if ((m_firstFree + 1) >= m_mapSize) 208 { 209 m_mapSize += m_blocksize; 210 211 Object newMap[] = new Object[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 * Remove all elements objects from the list. 230 */ 231 public final void removeAllElements() 232 { 233 234 for (int i = 0; i < m_firstFree; i++) 235 { 236 m_map[i] = null; 237 } 238 239 m_firstFree = 0; 240 } 241 242 /** 243 * Removes the first occurrence of the argument from this vector. 244 * If the object is found in this vector, each component in the vector 245 * with an index greater or equal to the object's index is shifted 246 * downward to have an index one smaller than the value it had 247 * previously. 248 * 249 * @param s Object to remove from array 250 * 251 * @return True if the object was removed, false if it was not found 252 */ 253 public final boolean removeElement(Object s) 254 { 255 256 for (int i = 0; i < m_firstFree; i++) 257 { 258 if (m_map[i] == s) 259 { 260 if ((i + 1) < m_firstFree) 261 System.arraycopy(m_map, i + 1, m_map, i - 1, m_firstFree - i); 262 else 263 m_map[i] = null; 264 265 m_firstFree--; 266 267 return true; 268 } 269 } 270 271 return false; 272 } 273 274 /** 275 * Deletes the component at the specified index. Each component in 276 * this vector with an index greater or equal to the specified 277 * index is shifted downward to have an index one smaller than 278 * the value it had previously. 279 * 280 * @param i index of where to remove an object 281 */ 282 public final void removeElementAt(int i) 283 { 284 285 if (i > m_firstFree) 286 System.arraycopy(m_map, i + 1, m_map, i, m_firstFree); 287 else 288 m_map[i] = null; 289 290 m_firstFree--; 291 } 292 293 /** 294 * Sets the component at the specified index of this vector to be the 295 * specified object. The previous component at that position is discarded. 296 * 297 * The index must be a value greater than or equal to 0 and less 298 * than the current size of the vector. 299 * 300 * @param value object to set 301 * @param index Index of where to set the object 302 */ 303 public final void setElementAt(Object value, int index) 304 { 305 m_map[index] = value; 306 } 307 308 /** 309 * Get the nth element. 310 * 311 * @param i index of object to get 312 * 313 * @return object at given index 314 */ 315 public final Object elementAt(int i) 316 { 317 return m_map[i]; 318 } 319 320 /** 321 * Tell if the table contains the given Object. 322 * 323 * @param s object to look for 324 * 325 * @return true if the object is in the list 326 */ 327 public final boolean contains(Object s) 328 { 329 330 for (int i = 0; i < m_firstFree; i++) 331 { 332 if (m_map[i] == s) 333 return true; 334 } 335 336 return false; 337 } 338 339 /** 340 * Searches for the first occurence of the given argument, 341 * beginning the search at index, and testing for equality 342 * using the equals method. 343 * 344 * @param elem object to look for 345 * @param index Index of where to begin search 346 * @return the index of the first occurrence of the object 347 * argument in this vector at position index or later in the 348 * vector; returns -1 if the object is not found. 349 */ 350 public final int indexOf(Object elem, int index) 351 { 352 353 for (int i = index; i < m_firstFree; i++) 354 { 355 if (m_map[i] == elem) 356 return i; 357 } 358 359 return java.lang.Integer.MIN_VALUE; 360 } 361 362 /** 363 * Searches for the first occurence of the given argument, 364 * beginning the search at index, and testing for equality 365 * using the equals method. 366 * 367 * @param elem object to look for 368 * @return the index of the first occurrence of the object 369 * argument in this vector at position index or later in the 370 * vector; returns -1 if the object is not found. 371 */ 372 public final int indexOf(Object elem) 373 { 374 375 for (int i = 0; i < m_firstFree; i++) 376 { 377 if (m_map[i] == elem) 378 return i; 379 } 380 381 return java.lang.Integer.MIN_VALUE; 382 } 383 384 /** 385 * Searches for the first occurence of the given argument, 386 * beginning the search at index, and testing for equality 387 * using the equals method. 388 * 389 * @param elem Object to look for 390 * @return the index of the first occurrence of the object 391 * argument in this vector at position index or later in the 392 * vector; returns -1 if the object is not found. 393 */ 394 public final int lastIndexOf(Object elem) 395 { 396 397 for (int i = (m_firstFree - 1); i >= 0; i--) 398 { 399 if (m_map[i] == elem) 400 return i; 401 } 402 403 return java.lang.Integer.MIN_VALUE; 404 } 405 406 /* 407 * Reset the array to the supplied size. 408 * 409 * @param size 410 */ 411 public final void setToSize(int size) { 412 413 Object newMap[] = new Object[size]; 414 415 System.arraycopy(m_map, 0, newMap, 0, m_firstFree); 416 m_mapSize = size; 417 418 m_map = newMap; 419 420 } 421 422 /** 423 * Returns clone of current ObjectVector 424 * 425 * @return clone of current ObjectVector 426 */ 427 public Object clone() 428 throws CloneNotSupportedException 429 { 430 return new ObjectVector(this); 431 } 432} 433