1 2 /* ==================================================================== 3 * The Apache Software License, Version 1.1 4 * 5 * Copyright (c) 2002 The Apache Software Foundation. All rights 6 * reserved. 7 * 8 * Redistribution and use in source and binary forms, with or without 9 * modification, are permitted provided that the following conditions 10 * are met: 11 * 12 * 1. Redistributions of source code must retain the above copyright 13 * notice, this list of conditions and the following disclaimer. 14 * 15 * 2. Redistributions in binary form must reproduce the above copyright 16 * notice, this list of conditions and the following disclaimer in 17 * the documentation and/or other materials provided with the 18 * distribution. 19 * 20 * 3. The end-user documentation included with the redistribution, 21 * if any, must include the following acknowledgment: 22 * "This product includes software developed by the 23 * Apache Software Foundation (http://www.apache.org/)." 24 * Alternately, this acknowledgment may appear in the software itself, 25 * if and wherever such third-party acknowledgments normally appear. 26 * 27 * 4. The names "Apache" and "Apache Software Foundation" and 28 * "Apache POI" must not be used to endorse or promote products 29 * derived from this software without prior written permission. For 30 * written permission, please contact apache@apache.org. 31 * 32 * 5. Products derived from this software may not be called "Apache", 33 * "Apache POI", nor may "Apache" appear in their name, without 34 * prior written permission of the Apache Software Foundation. 35 * 36 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED 37 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 38 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 39 * DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR 40 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 41 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 42 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF 43 * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND 44 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, 45 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT 46 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 47 * SUCH DAMAGE. 48 * ==================================================================== 49 * 50 * This software consists of voluntary contributions made by many 51 * individuals on behalf of the Apache Software Foundation. For more 52 * information on the Apache Software Foundation, please see 53 * <http://www.apache.org/>. 54 */ 55 56 package org.apache.poi.util; 57 58 import java.util.*; 59 60 /** 61 * A List of short's; as full an implementation of the java.util.List 62 * interface as possible, with an eye toward minimal creation of 63 * objects 64 * 65 * the mimicry of List is as follows: 66 * <ul> 67 * <li> if possible, operations designated 'optional' in the List 68 * interface are attempted 69 * <li> wherever the List interface refers to an Object, substitute 70 * short 71 * <li> wherever the List interface refers to a Collection or List, 72 * substitute ShortList 73 * </ul> 74 * 75 * the mimicry is not perfect, however: 76 * <ul> 77 * <li> operations involving Iterators or ListIterators are not 78 * supported 79 * <li> remove(Object) becomes removeValue to distinguish it from 80 * remove(short index) 81 * <li> subList is not supported 82 * </ul> 83 * 84 * @author Marc Johnson 85 */ 86 87 public class ShortList 88 { 89 private short[] _array; 90 private int _limit; 91 private static final int _default_size = 128; 92 93 /** 94 * create an ShortList of default size 95 */ 96 97 public ShortList() 98 { 99 this(_default_size); 100 } 101 102 /** 103 * create a copy of an existing ShortList 104 * 105 * @param list the existing ShortList 106 */ 107 108 public ShortList(final ShortList list) 109 { 110 this(list._array.length); 111 System.arraycopy(list._array, 0, _array, 0, _array.length); 112 _limit = list._limit; 113 } 114 115 /** 116 * create an ShortList with a predefined initial size 117 * 118 * @param initialCapacity the size for the internal array 119 */ 120 121 public ShortList(final int initialCapacity) 122 { 123 _array = new short[ initialCapacity ]; 124 _limit = 0; 125 } 126 127 /** 128 * add the specfied value at the specified index 129 * 130 * @param index the index where the new value is to be added 131 * @param value the new value 132 * 133 * @exception IndexOutOfBoundsException if the index is out of 134 * range (index < 0 || index > size()). 135 */ 136 137 public void add(final int index, final short value) 138 { 139 if (index > _limit) 140 { 141 throw new IndexOutOfBoundsException(); 142 } 143 else if (index == _limit) 144 { 145 add(value); 146 } 147 else 148 { 149 150 // index < limit -- insert into the middle 151 if (_limit == _array.length) 152 { 153 growArray(_limit * 2); 154 } 155 System.arraycopy(_array, index, _array, index + 1, 156 _limit - index); 157 _array[ index ] = value; 158 _limit++; 159 } 160 } 161 162 /** 163 * Appends the specified element to the end of this list 164 * 165 * @param value element to be appended to this list. 166 * 167 * @return true (as per the general contract of the Collection.add 168 * method). 169 */ 170 171 public boolean add(final short value) 172 { 173 if (_limit == _array.length) 174 { 175 growArray(_limit * 2); 176 } 177 _array[ _limit++ ] = value; 178 return true; 179 } 180 181 /** 182 * Appends all of the elements in the specified collection to the 183 * end of this list, in the order that they are returned by the 184 * specified collection's iterator. The behavior of this 185 * operation is unspecified if the specified collection is 186 * modified while the operation is in progress. (Note that this 187 * will occur if the specified collection is this list, and it's 188 * nonempty.) 189 * 190 * @param c collection whose elements are to be added to this 191 * list. 192 * 193 * @return true if this list changed as a result of the call. 194 */ 195 196 public boolean addAll(final ShortList c) 197 { 198 if (c._limit != 0) 199 { 200 if ((_limit + c._limit) > _array.length) 201 { 202 growArray(_limit + c._limit); 203 } 204 System.arraycopy(c._array, 0, _array, _limit, c._limit); 205 _limit += c._limit; 206 } 207 return true; 208 } 209 210 /** 211 * Inserts all of the elements in the specified collection into 212 * this list at the specified position. Shifts the element 213 * currently at that position (if any) and any subsequent elements 214 * to the right (increases their indices). The new elements will 215 * appear in this list in the order that they are returned by the 216 * specified collection's iterator. The behavior of this 217 * operation is unspecified if the specified collection is 218 * modified while the operation is in progress. (Note that this 219 * will occur if the specified collection is this list, and it's 220 * nonempty.) 221 * 222 * @param index index at which to insert first element from the 223 * specified collection. 224 * @param c elements to be inserted into this list. 225 * 226 * @return true if this list changed as a result of the call. 227 * 228 * @exception IndexOutOfBoundsException if the index is out of 229 * range (index < 0 || index > size()) 230 */ 231 232 public boolean addAll(final int index, final ShortList c) 233 { 234 if (index > _limit) 235 { 236 throw new IndexOutOfBoundsException(); 237 } 238 if (c._limit != 0) 239 { 240 if ((_limit + c._limit) > _array.length) 241 { 242 growArray(_limit + c._limit); 243 } 244 245 // make a hole 246 System.arraycopy(_array, index, _array, index + c._limit, 247 _limit - index); 248 249 // fill it in 250 System.arraycopy(c._array, 0, _array, index, c._limit); 251 _limit += c._limit; 252 } 253 return true; 254 } 255 256 /** 257 * Removes all of the elements from this list. This list will be 258 * empty after this call returns (unless it throws an exception). 259 */ 260 261 public void clear() 262 { 263 _limit = 0; 264 } 265 266 /** 267 * Returns true if this list contains the specified element. More 268 * formally, returns true if and only if this list contains at 269 * least one element e such that o == e 270 * 271 * @param o element whose presence in this list is to be tested. 272 * 273 * @return true if this list contains the specified element. 274 */ 275 276 public boolean contains(final short o) 277 { 278 boolean rval = false; 279 280 for (int j = 0; !rval && (j < _limit); j++) 281 { 282 if (_array[ j ] == o) 283 { 284 rval = true; 285 } 286 } 287 return rval; 288 } 289 290 /** 291 * Returns true if this list contains all of the elements of the 292 * specified collection. 293 * 294 * @param c collection to be checked for containment in this list. 295 * 296 * @return true if this list contains all of the elements of the 297 * specified collection. 298 */ 299 300 public boolean containsAll(final ShortList c) 301 { 302 boolean rval = true; 303 304 if (this != c) 305 { 306 for (int j = 0; rval && (j < c._limit); j++) 307 { 308 if (!contains(c._array[ j ])) 309 { 310 rval = false; 311 } 312 } 313 } 314 return rval; 315 } 316 317 /** 318 * Compares the specified object with this list for equality. 319 * Returns true if and only if the specified object is also a 320 * list, both lists have the same size, and all corresponding 321 * pairs of elements in the two lists are equal. (Two elements e1 322 * and e2 are equal if e1 == e2.) In other words, two lists are 323 * defined to be equal if they contain the same elements in the 324 * same order. This definition ensures that the equals method 325 * works properly across different implementations of the List 326 * interface. 327 * 328 * @param o the object to be compared for equality with this list. 329 * 330 * @return true if the specified object is equal to this list. 331 */ 332 333 public boolean equals(final Object o) 334 { 335 boolean rval = this == o; 336 337 if (!rval && (o != null) && (o.getClass() == this.getClass())) 338 { 339 ShortList other = ( ShortList ) o; 340 341 if (other._limit == _limit) 342 { 343 344 // assume match 345 rval = true; 346 for (int j = 0; rval && (j < _limit); j++) 347 { 348 rval = _array[ j ] == other._array[ j ]; 349 } 350 } 351 } 352 return rval; 353 } 354 355 /** 356 * Returns the element at the specified position in this list. 357 * 358 * @param index index of element to return. 359 * 360 * @return the element at the specified position in this list. 361 * 362 * @exception IndexOutOfBoundsException if the index is out of 363 * range (index < 0 || index >= size()). 364 */ 365 366 public short get(final int index) 367 { 368 if (index >= _limit) 369 { 370 throw new IndexOutOfBoundsException(); 371 } 372 return _array[ index ]; 373 } 374 375 /** 376 * Returns the hash code value for this list. The hash code of a 377 * list is defined to be the result of the following calculation: 378 * 379 * <code> 380 * hashCode = 1; 381 * Iterator i = list.iterator(); 382 * while (i.hasNext()) { 383 * Object obj = i.next(); 384 * hashCode = 31*hashCode + (obj==null ? 0 : obj.hashCode()); 385 * } 386 * </code> 387 * 388 * This ensures that list1.equals(list2) implies that 389 * list1.hashCode()==list2.hashCode() for any two lists, list1 and 390 * list2, as required by the general contract of Object.hashCode. 391 * 392 * @return the hash code value for this list. 393 */ 394 395 public int hashCode() 396 { 397 int hash = 0; 398 399 for (int j = 0; j < _limit; j++) 400 { 401 hash = (31 * hash) + _array[ j ]; 402 } 403 return hash; 404 } 405 406 /** 407 * Returns the index in this list of the first occurrence of the 408 * specified element, or -1 if this list does not contain this 409 * element. More formally, returns the lowest index i such that 410 * (o == get(i)), or -1 if there is no such index. 411 * 412 * @param o element to search for. 413 * 414 * @return the index in this list of the first occurrence of the 415 * specified element, or -1 if this list does not contain 416 * this element. 417 */ 418 419 public int indexOf(final short o) 420 { 421 int rval = 0; 422 423 for (; rval < _limit; rval++) 424 { 425 if (o == _array[ rval ]) 426 { 427 break; 428 } 429 } 430 if (rval == _limit) 431 { 432 rval = -1; // didn't find it 433 } 434 return rval; 435 } 436 437 /** 438 * Returns true if this list contains no elements. 439 * 440 * @return true if this list contains no elements. 441 */ 442 443 public boolean isEmpty() 444 { 445 return _limit == 0; 446 } 447 448 /** 449 * Returns the index in this list of the last occurrence of the 450 * specified element, or -1 if this list does not contain this 451 * element. More formally, returns the highest index i such that 452 * (o == get(i)), or -1 if there is no such index. 453 * 454 * @param o element to search for. 455 * 456 * @return the index in this list of the last occurrence of the 457 * specified element, or -1 if this list does not contain 458 * this element. 459 */ 460 461 public int lastIndexOf(final short o) 462 { 463 int rval = _limit - 1; 464 465 for (; rval >= 0; rval--) 466 { 467 if (o == _array[ rval ]) 468 { 469 break; 470 } 471 } 472 return rval; 473 } 474 475 /** 476 * Removes the element at the specified position in this list. 477 * Shifts any subsequent elements to the left (subtracts one from 478 * their indices). Returns the element that was removed from the 479 * list. 480 * 481 * @param index the index of the element to removed. 482 * 483 * @return the element previously at the specified position. 484 * 485 * @exception IndexOutOfBoundsException if the index is out of 486 * range (index < 0 || index >= size()). 487 */ 488 489 public short remove(final int index) 490 { 491 if (index >= _limit) 492 { 493 throw new IndexOutOfBoundsException(); 494 } 495 short rval = _array[ index ]; 496 497 System.arraycopy(_array, index + 1, _array, index, _limit - index); 498 _limit--; 499 return rval; 500 } 501 502 /** 503 * Removes the first occurrence in this list of the specified 504 * element (optional operation). If this list does not contain 505 * the element, it is unchanged. More formally, removes the 506 * element with the lowest index i such that (o.equals(get(i))) 507 * (if such an element exists). 508 * 509 * @param o element to be removed from this list, if present. 510 * 511 * @return true if this list contained the specified element. 512 */ 513 514 public boolean removeValue(final short o) 515 { 516 boolean rval = false; 517 518 for (int j = 0; !rval && (j < _limit); j++) 519 { 520 if (o == _array[ j ]) 521 { 522 System.arraycopy(_array, j + 1, _array, j, _limit - j); 523 _limit--; 524 rval = true; 525 } 526 } 527 return rval; 528 } 529 530 /** 531 * Removes from this list all the elements that are contained in 532 * the specified collection 533 * 534 * @param c collection that defines which elements will be removed 535 * from this list. 536 * 537 * @return true if this list changed as a result of the call. 538 */ 539 540 public boolean removeAll(final ShortList c) 541 { 542 boolean rval = false; 543 544 for (int j = 0; j < c._limit; j++) 545 { 546 if (removeValue(c._array[ j ])) 547 { 548 rval = true; 549 } 550 } 551 return rval; 552 } 553 554 /** 555 * Retains only the elements in this list that are contained in 556 * the specified collection. In other words, removes from this 557 * list all the elements that are not contained in the specified 558 * collection. 559 * 560 * @param c collection that defines which elements this set will 561 * retain. 562 * 563 * @return true if this list changed as a result of the call. 564 */ 565 566 public boolean retainAll(final ShortList c) 567 { 568 boolean rval = false; 569 570 for (int j = 0; j < _limit; ) 571 { 572 if (!c.contains(_array[ j ])) 573 { 574 remove(j); 575 rval = true; 576 } 577 else 578 { 579 j++; 580 } 581 } 582 return rval; 583 } 584 585 /** 586 * Replaces the element at the specified position in this list 587 * with the specified element 588 * 589 * @param index index of element to replace. 590 * @param element element to be stored at the specified position. 591 * 592 * @return the element previously at the specified position. 593 * 594 * @exception IndexOutOfBoundsException if the index is out of 595 * range (index < 0 || index >= size()). 596 */ 597 598 public short set(final int index, final short element) 599 { 600 if (index >= _limit) 601 { 602 throw new IndexOutOfBoundsException(); 603 } 604 short rval = _array[ index ]; 605 606 _array[ index ] = element; 607 return rval; 608 } 609 610 /** 611 * Returns the number of elements in this list. If this list 612 * contains more than Integer.MAX_VALUE elements, returns 613 * Integer.MAX_VALUE. 614 * 615 * @return the number of elements in this ShortList 616 */ 617 618 public int size() 619 { 620 return _limit; 621 } 622 623 /** 624 * Returns an array containing all of the elements in this list in 625 * proper sequence. Obeys the general contract of the 626 * Collection.toArray method. 627 * 628 * @return an array containing all of the elements in this list in 629 * proper sequence. 630 */ 631 632 public short [] toArray() 633 { 634 short[] rval = new short[ _limit ]; 635 636 System.arraycopy(_array, 0, rval, 0, _limit); 637 return rval; 638 } 639 640 /** 641 * Returns an array containing all of the elements in this list in 642 * proper sequence. Obeys the general contract of the 643 * Collection.toArray(Object[]) method. 644 * 645 * @param a the array into which the elements of this list are to 646 * be stored, if it is big enough; otherwise, a new array 647 * is allocated for this purpose. 648 * 649 * @return an array containing the elements of this list. 650 */ 651 652 public short [] toArray(final short [] a) 653 { 654 short[] rval; 655 656 if (a.length == _limit) 657 { 658 System.arraycopy(_array, 0, a, 0, _limit); 659 rval = a; 660 } 661 else 662 { 663 rval = toArray(); 664 } 665 return rval; 666 } 667 668 private void growArray(final int new_size) 669 { 670 int size = (new_size == _array.length) ? new_size + 1 671 : new_size; 672 short[] new_array = new short[ size ]; 673 674 System.arraycopy(_array, 0, new_array, 0, _limit); 675 _array = new_array; 676 } 677 } // end public class ShortList 678 679