Java AbstractList

介绍

AbstractList文件的内部结构是这样的

• AbstractList.java
  • class AbstractList
    • class Itr
    • class ListItr
  • class SubList
  • class RandomAccess

AbstractCollection

AbstractList 继承 AbastractCollection

AbstractCollection 内部具体实现了

• isEmpty
• contains
• toArray
• T[] toArray
• remove
• containsAll
• addAll
• removeAll
• retainAll
• clear
• toString

这些方法,只有 iterator和size 作为抽象方法交由子类实现

AbstractList

AbstractList extends AbstractCollection implements List

这个类只是实现了

• indexOf
• lastIndexOf
• clear
• addAll

同时,AbstractList内部还有两个子类

• Itr
• ListItr

Itr & ListItr

其中 Itr 有下面这两个方法

• next
• remove

而 ListItr extends Itr implements ListIterator
实现了

• previous
• previousIndex
• nextIndex
• set
• add
• equals
• ..
  等方法.

总结

到这一步为止,nextIndex,previousIndex这些方法通过 迭代器中的cursor变量得以实现.equals方法也是通过迭代器的hasNext()+next()完成.但是get,set,add等方法还未曾有具体的实现.

目前为止AbstractList是一个抽象类,SubList继承了AbstractList,
在SubList中,set,get方法会调用SubList内部的private AbstractList 变量实现. 但是AbstractList内部,并没有对set,get方法进行实现.

set 方法会抛出异常,而get方法还是一个抽象方法.

源码

public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> {
  protected AbstractList(){

  }

  public boolean add(E e){
    add(size(), e);
    return true;
  }

  abstract public E get(int index);

  public E set(int index , E elemnt ){
    throw new UnsupportedOperationException();
  }

  public void add(int index, E element){
    throw new UnsupportedOperationException();
  }

  public E remove(int index ){
    throw new UnsupportedOperationException();
  }

  public int indexOf(Object o){
    ListIterator<E> it = listIterator();
    if(o == null){
      while(it.hasNext()){
        if(it.next() == null)
          return it.previousIndex();
      }
    } else {
      while(it.hasNext()){
        if(o.equals(it.next()))
          return it.previousIndex();
      }
    }

    return -1;
  }

  public int lastIndexOf(Object o ){
    ListIterator<E> it = listIterator();
    if( o == null){
      while(it.hasPrevious()){
        if(it.previous() == null)
          return it.nextIndex();
      }
    } else {
      while(it.hasPrevious()){
        if(o.equals(it.previous()))
          return it.nextIndex();
      }
    }
    return -1;
  }

  public void clear(){
    removeRange(0,size());
  }

  public boolean addAll(int index, Collection<? extends E> c){
    rangeCheckForAdd(index);
    boolean modified = false;
    for(E e : c){
      add(index++,e);
      mmodified = true;
    }

    return modified;
  }

  public ListIterator<E> listIterator(){
    return listIterator(0);
  }

  public ListIterator<E> listIterator(final int index){
    rangeCheckForAdd(index);
    return new ListItr(index);
  }

  private class Itr implements Iterator<E> {
    int cursor = 0;

    int lastRet = -1 ;

    int expectedModCount = modCount;

    public E next(){
      checkForComodification();
      try{
        int i = cursor;
        E next = get(i);
        lastRet = i;
        cursor = i +1 ;
        return next;
      } catch(IndexOutofBoundsException e){
        checkForComodification();
        throw new NoSuchElementException();
      }
    }

    public void remove(){
      if(lastRet <0)
        throw new IllegalStateException();
      checkForComodification();

      try{
        AbstractList.this.remove(lastRet);
        if(lastRet < cursor)
          cursor--;
        lastRet = -1;
        expectedModCount = modCount;
      } catch(IndexOutofBoundsException e) {
        throw new ConcurrentModificationException();
      }
    }

    final void checkForComodification(){
      if(modCount != expectedModCount)
        throw new ConcurrentModificationException();
    }
  }

  private class ListItr extends   Itr implements ListIterator<E>{
    ListItr(int index ) { cursor = index;}

    public boolean hasPrevious{ return cursor != 0;}

    public E previous(){
      checkForComodification();
      try{
        int i = cursor -1;
        E previous = get(i);
        lastRet = cursor = i;
        return previous;
      } catch(IndexOutofBoundsException e){
        checkForComodification();
        throw new NoSuchElementException();
      }
    }

    public int nextIndex(){
      return cursor;
    }

    public int previousIndex(){
      return cursor -1;
    }

    public set(E e){
      if(lastRet < 0)
        throw new IllegalStateException();
      checkForComodification();

      try{
        AbastractList.this.set(lastRet,e);
        expectedModCount = modCount;
      } catch( IndexOutofBoundsException ex){
        throw new ConcurrentModificationException();
      }
    }

    public void add(E e){
      checkForComodification();

      try{
        int i = cursor;

        AbstractList.this.add(i,e);
        lastRet = -1;
        cursor  =i+1;
        expectedModCount = modCount;
      } catch(IndexOutofBoundsException ex){
        throw new ConcurrentModificationException();
      }
    }

    public List<E> subList(int fromIndex, int toIndex){
      return (this instanceof RandomAccess ? new RandomAccessSubList<>(this,fromIndex,toIndex) : new SubList<>(this,fromIndex,toIndex));
    }

    public boolean equals(Object c){
      if( o == this){
        return true;
      }

      if (!(o instanceof List))
        return false;

      ListIterator<E> e1 = listIterator();
      ListIterator<?> e2 = ((List<?>) o).listIterator();

      while(e1.hasNext() && e2.hasNext()){
        E o1 =  e1.next();
        Object o2 = e2.next();
        if(!(o1 == null ? o2 == null : o1.equals(o2)))
          return false;
      }

      return !(e1.hasNext() || e2.hasNext());
    }

    public int hashCode(){
      int hashCode = 1;
      for (E e : this){
        hashCode = 31* hashCode + (e == null ?  0 : e.hashCode());
      }
      return hashCode;
    }

    protected void removeRange(int fromIndex, int toIndex){
      ListIterator<E> it = listIterator(fromIndex)
      for(int i =0, n  = toIndex- fromIndex; i<n;i++){
        it.next();
        it.remove();
      }
    }

    protected transient int modCount = 0;

    private void rangeCheckForAdd(int index){
      if(index<0 || index > size)
        throw new IndexOutofBoundsException(outOfBoundsMsg(index));
    }

    private String outOfBoundsMsg(int index){
      return "index " + index+ ", size :"+ size();
    }
  }

}

class SubList<E> extends AbstractList<E>{
  private final AbstractList<E> l;
  private final int offset;

  private int size;


      SubList(AbstractList<E> list, int fromIndex, int toIndex) {
          if (fromIndex < 0)
              throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
          if (toIndex > list.size())
              throw new IndexOutOfBoundsException("toIndex = " + toIndex);
          if (fromIndex > toIndex)
              throw new IllegalArgumentException("fromIndex(" + fromIndex +
                                                 ") > toIndex(" + toIndex + ")");
          l = list;
          offset = fromIndex;
          size = toIndex - fromIndex;
          this.modCount = l.modCount;
      }

      public E set(int index, E element) {
          rangeCheck(index);
          checkForComodification();
          return l.set(index+offset, element);
      }

      public E get(int index) {
          rangeCheck(index);
          checkForComodification();
          return l.get(index+offset);
      }

      public int size() {
          checkForComodification();
          return size;
      }

      public void add(int index, E element) {
          rangeCheckForAdd(index);
          checkForComodification();
          l.add(index+offset, element);
          this.modCount = l.modCount;
          size++;
      }

      public E remove(int index) {
          rangeCheck(index);
          checkForComodification();
          E result = l.remove(index+offset);
          this.modCount = l.modCount;
          size--;
          return result;
      }

      protected void removeRange(int fromIndex, int toIndex) {
          checkForComodification();
          l.removeRange(fromIndex+offset, toIndex+offset);
          this.modCount = l.modCount;
          size -= (toIndex-fromIndex);
      }

      public boolean addAll(Collection<? extends E> c) {
          return addAll(size, c);
      }

      public boolean addAll(int index, Collection<? extends E> c) {
          rangeCheckForAdd(index);
          int cSize = c.size();
          if (cSize==0)
              return false;

          checkForComodification();
          l.addAll(offset+index, c);
          this.modCount = l.modCount;
          size += cSize;
          return true;
      }

      public Iterator<E> iterator() {
          return listIterator();
      }

      public ListIterator<E> listIterator(final int index) {
          checkForComodification();
          rangeCheckForAdd(index);

          return new ListIterator<E>() {
              private final ListIterator<E> i = l.listIterator(index+offset);

              public boolean hasNext() {
                  return nextIndex() < size;
              }

              public E next() {
                  if (hasNext())
                      return i.next();
                  else
                      throw new NoSuchElementException();
              }

              public boolean hasPrevious() {
                  return previousIndex() >= 0;
              }

              public E previous() {
                  if (hasPrevious())
                      return i.previous();
                  else
                      throw new NoSuchElementException();
              }

              public int nextIndex() {
                  return i.nextIndex() - offset;
              }

              public int previousIndex() {
                  return i.previousIndex() - offset;
              }

              public void remove() {
                  i.remove();
                  SubList.this.modCount = l.modCount;
                  size--;
              }

              public void set(E e) {
                  i.set(e);
              }

              public void add(E e) {
                  i.add(e);
                  SubList.this.modCount = l.modCount;
                  size++;
              }
          };
      }

      public List<E> subList(int fromIndex, int toIndex) {
          return new SubList<>(this, fromIndex, toIndex);
      }

      private void rangeCheck(int index) {
          if (index < 0 || index >= size)
              throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
      }

      private void rangeCheckForAdd(int index) {
          if (index < 0 || index > size)
              throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
      }

      private String outOfBoundsMsg(int index) {
          return "Index: "+index+", Size: "+size;
      }

      private void checkForComodification() {
          if (this.modCount != l.modCount)
              throw new ConcurrentModificationException();
      }
}

class RandomAccessSubList<E> extends SubList<E> implements RandomAccess {
    RandomAccessSubList(AbstractList<E> list, int fromIndex, int toIndex) {
        super(list, fromIndex, toIndex);
    }

    public List<E> subList(int fromIndex, int toIndex) {
        return new RandomAccessSubList<>(this, fromIndex, toIndex);
    }
}