libjava/java/util/AbstractList.java

   1 /* AbstractList.java -- Abstract implementation of most of List
   2    Copyright (C) 1998, 1999, 2000 Free Software Foundation, Inc.
   3
   4 This file is part of GNU Classpath.
   5
   6 GNU Classpath is free software; you can redistribute it and/or modify
   7 it under the terms of the GNU General Public License as published by
   8 the Free Software Foundation; either version 2, or (at your option)
   9 any later version.
  10
  11 GNU Classpath is distributed in the hope that it will be useful, but
  12 WITHOUT ANY WARRANTY; without even the implied warranty of
  13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14 General Public License for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GNU Classpath; see the file COPYING.  If not, write to the
  18 Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
  19 02111-1307 USA.
  20
  21 As a special exception, if you link this library with other files to
  22 produce an executable, this library does not by itself cause the
  23 resulting executable to be covered by the GNU General Public License.
  24 This exception does not however invalidate any other reasons why the
  25 executable file might be covered by the GNU General Public License. */
  26
  27
  28 // TO DO:
  29 // ~ Doc comments for almost everything.
  30 // ~ Better general commenting
  31
  32 package java.util;
  33
  34 /**
  35  * A basic implementation of most of the methods in the List interface to make
  36  * it easier to create a List based on a random-access data structure. To
  37  * create an unmodifiable list, it is only necessary to override the size() and
  38  * get(int) methods (this contrasts with all other abstract collection classes
  39  * which require an iterator to be provided). To make the list modifiable, the
  40  * set(int, Object)  method should also be overridden, and to make the list
  41  * resizable, the add(int, Object) and remove(int) methods should be overridden
  42  * too. Other methods should be overridden if the backing data structure allows
  43  * for a more efficient implementation. The precise implementation used by
  44  * AbstractList is documented, so that subclasses can tell which methods could
  45  * be implemented more efficiently.
  46  */
  47 public abstract class AbstractList extends AbstractCollection implements List {
  48
  49   /**
  50    * A count of the number of structural modifications that have been made to
  51    * the list (that is, insertions and removals).
  52    */
  53   protected transient int modCount = 0;
  54
  55   public abstract Object get(int index);
  56
  57   public void add(int index, Object o) {
  58     throw new UnsupportedOperationException();
  59   }
  60
  61   public boolean add(Object o) {
  62     add(size(), o);
  63     return true;
  64   }
  65
  66   public boolean addAll(int index, Collection c) {
  67     Iterator i = c.iterator();
  68     if (i.hasNext()) {
  69       do {
  70         add(index++, i.next());
  71       } while (i.hasNext());
  72       return true;
  73     } else {
  74       return false;
  75     }
  76   }
  77
  78   public void clear() {
  79     removeRange(0, size());
  80   }
  81
  82   public boolean equals(Object o) {
  83     if (o == this) {
  84       return true;
  85     } else if (!(o instanceof List)) {
  86       return false;
  87     } else {
  88       Iterator i1 = iterator();
  89       Iterator i2 = ((List)o).iterator();
  90       while (i1.hasNext()) {
  91         if (!i2.hasNext()) {
  92           return false;
  93         } else {
  94           Object e = i1.next();
  95           if (e == null ? i2.next() != null : !e.equals(i2.next())) {
  96             return false;
  97           }
  98         }
  99       }
 100       if (i2.hasNext()) {
 101         return false;
 102       } else {
 103         return true;
 104       }
 105     }
 106   }
 107
 108   public int hashCode() {
 109     int hashCode = 1;
 110     Iterator i = iterator();
 111     while (i.hasNext()) {
 112       Object obj = i.next();
 113       hashCode = 31 * hashCode + (obj == null ? 0 : obj.hashCode());
 114     }
 115     return hashCode;
 116   }
 117
 118   public int indexOf(Object o) {
 119     int index = 0;
 120     ListIterator i = listIterator();
 121     if (o == null) {
 122       while (i.hasNext()) {
 123         if (i.next() == null) {
 124           return index;
 125         }
 126         index++;
 127       }
 128     } else {
 129       while (i.hasNext()) {
 130         if (o.equals(i.next())) {
 131           return index;
 132         }
 133         index++;
 134       }
 135     }
 136     return -1;
 137   }
 138
 139   public Iterator iterator() {
 140     return new Iterator() {
 141       private int knownMod = modCount;
 142       private int position = 0;
 143       boolean removed = true;
 144
 145       private void checkMod() {
 146         if (knownMod != modCount) {
 147           throw new ConcurrentModificationException();
 148         }
 149       }
 150
 151       public boolean hasNext() {
 152         checkMod();
 153         return position < size();
 154       }
 155
 156       public Object next() {
 157         checkMod();
 158         removed = false;
 159         try {
 160           return get(position++);
 161         } catch (IndexOutOfBoundsException e) {
 162           throw new NoSuchElementException();
 163         }
 164       }
 165
 166       public void remove() {
 167         checkMod();
 168         if (removed) {
 169           throw new IllegalStateException();
 170         }
 171         AbstractList.this.remove(--position);
 172         knownMod = modCount;
 173         removed = true;
 174       }
 175     };
 176   }
 177
 178   public int lastIndexOf(Object o) {
 179     int index = size();
 180     ListIterator i = listIterator(index);
 181     if (o == null) {
 182       while (i.hasPrevious()) {
 183         index--;
 184         if (i.previous() == null) {
 185           return index;
 186         }
 187       }
 188     } else {
 189       while (i.hasPrevious()) {
 190         index--;
 191         if (o.equals(i.previous())) {
 192           return index;
 193         }
 194       }
 195     }
 196     return -1;
 197   }
 198
 199   public ListIterator listIterator() {
 200     return listIterator(0);
 201   }
 202
 203   public ListIterator listIterator(final int index) {
 204
 205     if (index < 0 || index > size()) {
 206       throw new IndexOutOfBoundsException();
 207     }
 208
 209     return new ListIterator() {
 210       private int knownMod = modCount;
 211       private int position = index;
 212       private int lastReturned = -1;
 213
 214       private void checkMod() {
 215         if (knownMod != modCount) {
 216           throw new ConcurrentModificationException();
 217         }
 218       }
 219
 220       public boolean hasNext() {
 221         checkMod();
 222         return position < size();
 223       }
 224
 225       public boolean hasPrevious() {
 226         checkMod();
 227         return position > 0;
 228       }
 229
 230       public Object next() {
 231         checkMod();
 232         if (hasNext()) {
 233           lastReturned = position++;
 234           return get(lastReturned);
 235         } else {
 236           throw new NoSuchElementException();
 237         }
 238       }
 239
 240       public Object previous() {
 241         checkMod();
 242         if (hasPrevious()) {
 243           lastReturned = --position;
 244           return get(lastReturned);
 245         } else {
 246           throw new NoSuchElementException();
 247         }
 248       }
 249
 250       public int nextIndex() {
 251         checkMod();
 252         return position;
 253       }
 254
 255       public int previousIndex() {
 256         checkMod();
 257         return position - 1;
 258       }
 259
 260       public void remove() {
 261         checkMod();
 262         if (lastReturned < 0) {
 263           throw new IllegalStateException();
 264         }
 265         AbstractList.this.remove(lastReturned);
 266         knownMod = modCount;
 267         position = lastReturned;
 268         lastReturned = -1;
 269       }
 270
 271       public void set(Object o) {
 272         checkMod();
 273         if (lastReturned < 0) {
 274           throw new IllegalStateException();
 275         }
 276         AbstractList.this.set(lastReturned, o);
 277       }
 278
 279       public void add(Object o) {
 280         checkMod();
 281         AbstractList.this.add(position++, o);
 282         lastReturned = -1;
 283         knownMod = modCount;
 284       }
 285     };
 286   }
 287
 288   public Object remove(int index) {
 289     throw new UnsupportedOperationException();
 290   }
 291
 292   /**
 293    * Remove a subsection of the list. This is called by the clear and
 294    * removeRange methods of the class which implements subList, which are
 295    * difficult for subclasses to override directly. Therefore, this method
 296    * should be overridden instead by the more efficient implementation, if one
 297    * exists.
 298    * <p>
 299    * This implementation first checks for illegal or out of range arguments. It
 300    * then obtains a ListIterator over the list using listIterator(fromIndex).
 301    * It then calls next() and remove() on this iterator repeatedly, toIndex -
 302    * fromIndex times.
 303    *
 304    * @param fromIndex the index, inclusive, to remove from.
 305    * @param toIndex the index, exclusive, to remove to.
 306    * @exception UnsupportedOperationException if this list does not support
 307    *   the removeRange operation.
 308    * @exception IndexOutOfBoundsException if fromIndex > toIndex || fromIndex <
 309    *   0 || toIndex > size().
 310    */
 311   protected void removeRange(int fromIndex, int toIndex) {
 312     if (fromIndex > toIndex) {
 313       throw new IllegalArgumentException();
 314     } else if (fromIndex < 0 || toIndex > size()) {
 315       throw new IndexOutOfBoundsException();
 316     } else {
 317       ListIterator i = listIterator(fromIndex);
 318       for (int index = fromIndex; index < toIndex; index++) {
 319         i.next();
 320         i.remove();
 321       }
 322     }
 323   }
 324
 325   public Object set(int index, Object o) {
 326     throw new UnsupportedOperationException();
 327   }
 328
 329   public List subList(final int fromIndex, final int toIndex) {
 330     if (fromIndex > toIndex)
 331       throw new IllegalArgumentException();
 332     if (fromIndex < 0 || toIndex > size())
 333       throw new IndexOutOfBoundsException();
 334     return new SubList(this, fromIndex, toIndex);
 335   }
 336
 337   static class SubList extends AbstractList {
 338
 339     private AbstractList backingList;
 340     private int offset;
 341     private int size;
 342
 343     public SubList(AbstractList backing, int fromIndex, int toIndex) {
 344       backingList = backing;
 345       upMod();
 346       offset = fromIndex;
 347       size = toIndex - fromIndex;
 348     }
 349
 350     // Note that within this class two fields called modCount are inherited -
 351     // one from the superclass, and one from the outer class.
 352     // The code uses both these two fields and *no other* to provide fail-fast
 353     // behaviour. For correct operation, the two fields should contain equal
 354     // values. Therefore, if this.modCount != backingList.modCount, there
 355     // has been a concurrent modification. This is all achieved purely by using
 356     // the modCount field, precisely according to the docs of AbstractList.
 357     // See the methods upMod and checkMod.
 358
 359     /**
 360      * This method checks the two modCount fields to ensure that there has
 361      * not been a concurrent modification. It throws an exception if there
 362      * has been, and otherwise returns normally.
 363      * Note that since this method is private, it will be inlined.
 364      *
 365      * @exception ConcurrentModificationException if there has been a
 366      *   concurrent modification.
 367      */
 368     private void checkMod() {
 369       if (this.modCount != backingList.modCount) {
 370         throw new ConcurrentModificationException();
 371       }
 372     }
 373
 374     /**
 375      * This method is called after every method that causes a structural
 376      * modification to the backing list. It updates the local modCount field
 377      * to match that of the backing list.
 378      * Note that since this method is private, it will be inlined.
 379      */
 380     private void upMod() {
 381       this.modCount = backingList.modCount;
 382     }
 383
 384     /**
 385      * This method checks that a value is between 0 and size (inclusive). If
 386      * it is not, an exception is thrown.
 387      * Note that since this method is private, it will be inlined.
 388      *
 389      * @exception IndexOutOfBoundsException if the value is out of range.
 390      */
 391     private void checkBoundsInclusive(int index) {
 392       if (index < 0 || index > size) {
 393         throw new IndexOutOfBoundsException();
 394       }
 395     }
 396
 397     /**
 398      * This method checks that a value is between 0 (inclusive) and size
 399      * (exclusive). If it is not, an exception is thrown.
 400      * Note that since this method is private, it will be inlined.
 401      *
 402      * @exception IndexOutOfBoundsException if the value is out of range.
 403      */
 404     private void checkBoundsExclusive(int index) {
 405       if (index < 0 || index >= size) {
 406         throw new IndexOutOfBoundsException();
 407       }
 408     }
 409
 410     public int size() {
 411       checkMod();
 412       return size;
 413     }
 414
 415     public Iterator iterator() {
 416       return listIterator();
 417     }
 418
 419     public ListIterator listIterator(final int index) {
 420
 421       checkMod();
 422       checkBoundsInclusive(index);
 423
 424       return new ListIterator() {
 425         ListIterator i = backingList.listIterator(index + offset);
 426         int position = index;
 427
 428         public boolean hasNext() {
 429           checkMod();
 430           return position < size;
 431         }
 432
 433         public boolean hasPrevious() {
 434           checkMod();
 435           return position > 0;
 436         }
 437
 438         public Object next() {
 439           if (position < size) {
 440             Object o = i.next();
 441             position++;
 442             return o;
 443           } else {
 444             throw new NoSuchElementException();
 445           }
 446         }
 447
 448         public Object previous() {
 449           if (position > 0) {
 450             Object o = i.previous();
 451             position--;
 452             return o;
 453           } else {
 454             throw new NoSuchElementException();
 455           }
 456         }
 457
 458         public int nextIndex() {
 459           return offset + i.nextIndex();
 460         }
 461
 462         public int previousIndex() {
 463           return offset + i.previousIndex();
 464         }
 465
 466         public void remove() {
 467           i.remove();
 468           upMod();
 469           size--;
 470           position = nextIndex();
 471         }
 472
 473         public void set(Object o) {
 474           i.set(o);
 475         }
 476
 477         public void add(Object o) {
 478           i.add(o);
 479           upMod();
 480           size++;
 481           position++;
 482         }
 483
 484         // Here is the reason why the various modCount fields are mostly
 485         // ignored in this wrapper listIterator.
 486         // IF the backing listIterator is failfast, then the following holds:
 487         //   Using any other method on this list will call a corresponding
 488         //   method on the backing list *after* the backing listIterator
 489         //   is created, which will in turn cause a ConcurrentModException
 490         //   when this listIterator comes to use the backing one. So it is
 491         //   implicitly failfast.
 492         // If the backing listIterator is NOT failfast, then the whole of
 493         //   this list isn't failfast, because the modCount field of the
 494         //   backing list is not valid. It would still be *possible* to
 495         //   make the iterator failfast wrt modifications of the sublist
 496         //   only, but somewhat pointless when the list can be changed under
 497         //   us.
 498         // Either way, no explicit handling of modCount is needed.
 499         // However upMod() must be called in add and remove, and size
 500         // must also be updated in these two methods, since they do not go
 501         // through the corresponding methods of the subList.
 502
 503       };
 504     }
 505
 506     public Object set(int index, Object o) {
 507       checkMod();
 508       checkBoundsExclusive(index);
 509       o = backingList.set(index + offset, o);
 510       upMod();
 511       return o;
 512     }
 513
 514     public Object get(int index) {
 515       checkMod();
 516       checkBoundsExclusive(index);
 517       return backingList.get(index + offset);
 518     }
 519
 520     public void add(int index, Object o) {
 521       checkMod();
 522       checkBoundsInclusive(index);
 523       backingList.add(index + offset, o);
 524       upMod();
 525       size++;
 526     }
 527
 528     public Object remove(int index) {
 529       checkMod();
 530       checkBoundsExclusive(index);
 531       Object o = backingList.remove(index + offset);
 532       upMod();
 533       size--;
 534       return o;
 535     }
 536
 537     public void removeRange(int fromIndex, int toIndex) {
 538       checkMod();
 539       checkBoundsExclusive(fromIndex);
 540       checkBoundsInclusive(toIndex);
 541
 542       // this call will catch the toIndex < fromIndex condition
 543       backingList.removeRange(offset + fromIndex, offset + toIndex);
 544       upMod();
 545       size -= toIndex - fromIndex;
 546     }
 547
 548     public boolean addAll(int index, Collection c) {
 549       checkMod();
 550       checkBoundsInclusive(index);
 551       int s = backingList.size();
 552       boolean result = backingList.addAll(offset + index, c);
 553       upMod();
 554       size += backingList.size() - s;
 555       return result;
 556     }
 557   }
 558 }