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