Back to index

plt-scheme  4.2.1
AbstractList.java
Go to the documentation of this file.
00001 /* AbstractList.java -- Abstract implementation of most of List
00002    Copyright (C) 1998, 1999, 2000, 2001, 2002 Free Software Foundation, Inc.
00003 
00004 This file is part of GNU Classpath.
00005 
00006 GNU Classpath is free software; you can redistribute it and/or modify
00007 it under the terms of the GNU General Public License as published by
00008 the Free Software Foundation; either version 2, or (at your option)
00009 any later version.
00010 
00011 GNU Classpath is distributed in the hope that it will be useful, but
00012 WITHOUT ANY WARRANTY; without even the implied warranty of
00013 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00014 General Public License for more details.
00015 
00016 You should have received a copy of the GNU General Public License
00017 along with GNU Classpath; see the file COPYING.  If not, write to the
00018 Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
00019 02111-1307 USA.
00020 
00021 Linking this library statically or dynamically with other modules is
00022 making a combined work based on this library.  Thus, the terms and
00023 conditions of the GNU General Public License cover the whole
00024 combination.
00025 
00026 As a special exception, the copyright holders of this library give you
00027 permission to link this library with independent modules to produce an
00028 executable, regardless of the license terms of these independent
00029 modules, and to copy and distribute the resulting executable under
00030 terms of your choice, provided that you also meet, for each linked
00031 independent module, the terms and conditions of the license of that
00032 module.  An independent module is a module which is not derived from
00033 or based on this library.  If you modify this library, you may extend
00034 this exception to your version of the library, but you are not
00035 obligated to do so.  If you do not wish to do so, delete this
00036 exception statement from your version. */
00037 
00038 
00039 package java.util;
00040 
00071 public abstract class AbstractList extends AbstractCollection implements List
00072 {
00088   protected int modCount;
00089 
00090   public boolean contains(Object o) { return super.contains(o); }
00091   public boolean containsAll( Collection c) { return super.containsAll(c); }
00092   public boolean isEmpty() { return super.isEmpty(); }
00093   public boolean remove(Object o) { return super.remove(o); }
00094   public boolean removeAll( Collection c) { return super.removeAll(c); }
00095   public boolean retainAll( Collection c) { return super.retainAll(c); }
00096   abstract public int size();
00097   public Object[] toArray() { return super.toArray(); }
00098   public Object[] toArray(Object[] o){ return super.toArray(o); }
00099 
00100 
00104   protected AbstractList()
00105   {
00106   }
00107 
00115   public abstract Object get(int index);
00116 
00137   public void add(int index, Object o)
00138   {
00139     throw new UnsupportedOperationException();
00140   }
00141 
00158   public boolean add(Object o)
00159   {
00160     add(size(), o);
00161     return true;
00162   }
00163 
00187   public boolean addAll(int index, Collection c)
00188   {
00189     Iterator itr = c.iterator();
00190     int size = c.size();
00191     for (int pos = size; pos > 0; pos--)
00192       add(index++, itr.next());
00193     return size > 0;
00194   }
00195 
00196   public boolean addAll(Collection c) { return super.addAll(c); }
00197 
00209   public void clear()
00210   {
00211     removeRange(0, size());
00212   }
00213 
00233   public boolean equals(Object o)
00234   {
00235     if (o == this)
00236       return true;
00237     if (! (o instanceof List))
00238       return false;
00239     int size = size();
00240     if (size != ((List) o).size())
00241       return false;
00242 
00243     Iterator itr1 = iterator();
00244     Iterator itr2 = ((List) o).iterator();
00245 
00246     while (--size >= 0)
00247       if (! AbstractCollection.equals(itr1.next(), itr2.next()))
00248         return false;
00249     return true;
00250   }
00251 
00272   public int hashCode()
00273   {
00274     int hashCode = 1;
00275     Iterator itr = iterator();
00276     int pos = size();
00277     while (--pos >= 0)
00278       hashCode = 31 * hashCode + AbstractCollection.hashCode(itr.next());
00279     return hashCode;
00280   }
00281 
00291   public int indexOf(Object o)
00292   {
00293     ListIterator itr = listIterator();
00294     int size = size();
00295     for (int pos = 0; pos < size; pos++)
00296       if (AbstractCollection.equals(o, itr.next()))
00297         return pos;
00298     return -1;
00299   }
00300 
00314     class ALIterator implements Iterator
00315     {
00316       private int pos = 0;
00317       private int size = AbstractList.this.size();
00318       private int last = -1;
00319       private int knownMod = AbstractList.this.modCount;
00320 
00321       // This will get inlined, since it is private.
00322       private void checkMod()
00323       {
00324         if (knownMod != AbstractList.this.modCount)
00325           throw new ConcurrentModificationException();
00326       }
00327 
00328       public boolean hasNext()
00329       {
00330         checkMod();
00331         return pos < size;
00332       }
00333 
00334       public Object next()
00335       {
00336         checkMod();
00337         if (pos == size)
00338           throw new NoSuchElementException();
00339         last = pos;
00340         return AbstractList.this.get(pos++);
00341       }
00342 
00343       public void remove()
00344       {
00345         checkMod();
00346         if (last < 0)
00347           throw new IllegalStateException();
00348         AbstractList.this.remove(last);
00349         pos--;
00350         size--;
00351         last = -1;
00352         knownMod = AbstractList.this.modCount;
00353       }
00354     }
00355 
00356   public Iterator iterator()
00357   {
00358     // Bah, Sun's implementation forbids using listIterator(0).
00359     return new ALIterator();
00360   }
00361 
00370   public int lastIndexOf(Object o)
00371   {
00372     int pos = size();
00373     ListIterator itr = listIterator(pos);
00374     while (--pos >= 0)
00375       if (AbstractCollection.equals(o, itr.previous()))
00376         return pos;
00377     return -1;
00378   }
00379 
00387   public ListIterator listIterator()
00388   {
00389     return listIterator(0);
00390   }
00391 
00411   class lIListIterator implements ListIterator {
00412 
00413       int index;
00414 
00415       lIListIterator(int i) { index = i; }
00416 
00417       private int knownMod = AbstractList.this.modCount;
00418       private int position = index;
00419       private int lastReturned = -1;
00420       private int size = AbstractList.this.size();
00421 
00422       // This will get inlined, since it is private.
00423       private void checkModL()
00424       {
00425         if (knownMod != AbstractList.this.modCount)
00426           throw new ConcurrentModificationException();
00427       }
00428 
00429       public boolean hasNext()
00430       {
00431         checkModL();
00432         return position < size;
00433       }
00434 
00435       public boolean hasPrevious()
00436       {
00437         checkModL();
00438         return position > 0;
00439       }
00440 
00441       public Object next()
00442       {
00443         checkModL();
00444         if (position == size)
00445           throw new NoSuchElementException();
00446         lastReturned = position;
00447         return AbstractList.this.get(position++);
00448       }
00449 
00450       public Object previous()
00451       {
00452         checkModL();
00453         if (position == 0)
00454           throw new NoSuchElementException();
00455         lastReturned = --position;
00456         return AbstractList.this.get(lastReturned);
00457       }
00458 
00459       public int nextIndex()
00460       {
00461         checkModL();
00462         return position;
00463       }
00464 
00465       public int previousIndex()
00466       {
00467         checkModL();
00468         return position - 1;
00469       }
00470 
00471       public void remove()
00472       {
00473         checkModL();
00474         if (lastReturned < 0)
00475           throw new IllegalStateException();
00476         AbstractList.this.remove(lastReturned);
00477         size--;
00478         position = lastReturned;
00479         lastReturned = -1;
00480         knownMod = AbstractList.this.modCount;
00481       }
00482 
00483       public void set(Object o)
00484       {
00485         checkModL();
00486         if (lastReturned < 0)
00487           throw new IllegalStateException();
00488         AbstractList.this.set(lastReturned, o);
00489       }
00490 
00491       public void add(Object o)
00492       {
00493         checkModL();
00494         AbstractList.this.add(position++, o);
00495         size++;
00496         lastReturned = -1;
00497         knownMod = AbstractList.this.modCount;
00498       }
00499     }
00500 
00501   public ListIterator listIterator(final int index)
00502   {
00503     if (index < 0 || index > size())
00504       throw new IndexOutOfBoundsException("Index: " + index + ", Size:"
00505                                           + size());
00506 
00507     return new lIListIterator(index);
00508   }
00509 
00524   public Object remove(int index)
00525   {
00526     throw new UnsupportedOperationException();
00527   }
00528 
00546   protected void removeRange(int fromIndex, int toIndex)
00547   {
00548     ListIterator itr = listIterator(fromIndex);
00549     for (int index = fromIndex; index < toIndex; index++)
00550       {
00551         itr.next();
00552         itr.remove();
00553       }
00554   }
00555 
00571   public Object set(int index, Object o)
00572   {
00573     throw new UnsupportedOperationException();
00574   }
00575 
00620   public List subList(int fromIndex, int toIndex)
00621   {
00622     // This follows the specification of AbstractList, but is inconsistent
00623     // with the one in List. Don't you love Sun's inconsistencies?
00624     if (fromIndex > toIndex)
00625       throw new IllegalArgumentException(fromIndex + " > " + toIndex);
00626     if (fromIndex < 0 || toIndex > size())
00627       throw new IndexOutOfBoundsException();
00628 
00629     if (((Object) this) instanceof RandomAccess)
00630       return new RandomAccessSubList(this, fromIndex, toIndex);
00631     return new SubList(this, fromIndex, toIndex);
00632   }
00633 
00634 } // class AbstractList
00635 
00636 
00645 class SubList extends AbstractList
00646 {
00647   // Package visible, for use by iterator.
00649   AbstractList backingList;
00651   int offset;
00653   int size;
00654 
00655   public boolean contains(Object o) { return super.contains(o); }
00656   public boolean containsAll( Collection c) { return super.containsAll(c); }
00657   public boolean isEmpty() { return super.isEmpty(); }
00658   public boolean remove(Object o) { return super.remove(o); }
00659   public boolean removeAll( Collection c) { return super.removeAll(c); }
00660   public boolean retainAll( Collection c) { return super.retainAll(c); }
00661   public Object[] toArray() { return super.toArray(); }
00662   public Object[] toArray(Object[] o){ return super.toArray(o); }
00663 
00671   SubList(AbstractList backing, int fromIndex, int toIndex)
00672   {
00673     backingList = backing;
00674     modCount = backing.modCount;
00675     offset = fromIndex;
00676     size = toIndex - fromIndex;
00677   }
00678 
00686   // This can be inlined. Package visible, for use by iterator.
00687   void checkMod()
00688   {
00689     if (modCount != backingList.modCount)
00690       throw new ConcurrentModificationException();
00691   }
00692 
00700   // This will get inlined, since it is private.
00701   private void checkBoundsInclusive(int index)
00702   {
00703     if (index < 0 || index > size)
00704       throw new IndexOutOfBoundsException("Index: " + index + ", Size:"
00705                                           + size);
00706   }
00707 
00715   // This will get inlined, since it is private.
00716   private void checkBoundsExclusive(int index)
00717   {
00718     if (index < 0 || index >= size)
00719       throw new IndexOutOfBoundsException("Index: " + index + ", Size:"
00720                                           + size);
00721   }
00722 
00728   public int size()
00729   {
00730     checkMod();
00731     return size;
00732   }
00733 
00741   public Object set(int index, Object o)
00742   {
00743     checkMod();
00744     checkBoundsExclusive(index);
00745     return backingList.set(index + offset, o);
00746   }
00747 
00754   public Object get(int index)
00755   {
00756     checkMod();
00757     checkBoundsExclusive(index);
00758     return backingList.get(index + offset);
00759   }
00760 
00767   public void add(int index, Object o)
00768   {
00769     checkMod();
00770     checkBoundsInclusive(index);
00771     backingList.add(index + offset, o);
00772     size++;
00773     modCount = backingList.modCount;
00774   }
00775 
00782   public Object remove(int index)
00783   {
00784     checkMod();
00785     checkBoundsExclusive(index);
00786     Object o = backingList.remove(index + offset);
00787     size--;
00788     modCount = backingList.modCount;
00789     return o;
00790   }
00791 
00800   protected void removeRange(int fromIndex, int toIndex)
00801   {
00802     checkMod();
00803 
00804     backingList.removeRange(offset + fromIndex, offset + toIndex);
00805     size -= toIndex - fromIndex;
00806     modCount = backingList.modCount;
00807   }
00808 
00816   public boolean addAll(int index, Collection c)
00817   {
00818     checkMod();
00819     checkBoundsInclusive(index);
00820     int csize = c.size();
00821     boolean result = backingList.addAll(offset + index, c);
00822     size += csize;
00823     modCount = backingList.modCount;
00824     return result;
00825   }
00826 
00833   public boolean addAll(Collection c)
00834   {
00835     return addAll(size, c);
00836   }
00837 
00843   public Iterator iterator()
00844   {
00845     return ((Iterator) ((Object) listIterator()));
00846   }
00847 
00856   class SLListIterator implements ListIterator 
00857 {
00858       int index;
00859       SLListIterator(int i) { index = i; }
00860 
00861       private final ListIterator i = 
00862                     SubList.this.backingList.listIterator(index + SubList.this.offset);
00863       private int position = index;
00864 
00865       public boolean hasNext()
00866       {
00867         SubList.this.checkMod();
00868         return position < SubList.this.size;
00869       }
00870 
00871       public boolean hasPrevious()
00872       {
00873         SubList.this.checkMod();
00874         return position > 0;
00875       }
00876 
00877       public Object next()
00878       {
00879         if (position == SubList.this.size)
00880           throw new NoSuchElementException();
00881         position++;
00882         return i.next();
00883       }
00884 
00885       public Object previous()
00886       {
00887         if (position == 0)
00888           throw new NoSuchElementException();
00889         position--;
00890         return i.previous();
00891       }
00892 
00893       public int nextIndex()
00894       {
00895         return i.nextIndex() - SubList.this.offset;
00896       }
00897 
00898       public int previousIndex()
00899       {
00900         return i.previousIndex() - SubList.this.offset;
00901       }
00902 
00903       public void remove()
00904       {
00905         i.remove();
00906         SubList.this.size--;
00907         position = nextIndex();
00908         SubList.this.modCount = SubList.this.backingList.modCount;
00909       }
00910 
00911       public void set(Object o)
00912       {
00913         i.set(o);
00914       }
00915 
00916       public void add(Object o)
00917       {
00918         i.add(o);
00919         SubList.this.size++;
00920         position++;
00921         SubList.this.modCount = SubList.this.backingList.modCount;
00922       }
00923 
00924       // Here is the reason why the various modCount fields are mostly
00925       // ignored in this wrapper listIterator.
00926       // If the backing listIterator is failfast, then the following holds:
00927       //   Using any other method on this list will call a corresponding
00928       //   method on the backing list *after* the backing listIterator
00929       //   is created, which will in turn cause a ConcurrentModException
00930       //   when this listIterator comes to use the backing one. So it is
00931       //   implicitly failfast.
00932       // If the backing listIterator is NOT failfast, then the whole of
00933       //   this list isn't failfast, because the modCount field of the
00934       //   backing list is not valid. It would still be *possible* to
00935       //   make the iterator failfast wrt modifications of the sublist
00936       //   only, but somewhat pointless when the list can be changed under
00937       //   us.
00938       // Either way, no explicit handling of modCount is needed.
00939       // However modCount = backingList.modCount must be executed in add
00940       // and remove, and size must also be updated in these two methods,
00941       // since they do not go through the corresponding methods of the subList.
00942     }
00943 
00944   public ListIterator listIterator(final int index)
00945   {
00946     checkMod();
00947     checkBoundsInclusive(index);
00948 
00949     return new SLListIterator(index);
00950   }
00951 } // class SubList
00952 
00959 final class RandomAccessSubList extends SubList
00960   implements RandomAccess
00961 {
00962 
00970   RandomAccessSubList(AbstractList backing, int fromIndex, int toIndex)
00971   {
00972     super(backing, fromIndex, toIndex);
00973   }
00974 } // class RandomAccessSubList