java开发中abstractCollection、List和AbstractList解析

AbstractCollection继承collection，只抽象了两个方法，因为其他方法基本都是可以使用迭代器实现的。
而List接口是增加了八个接口，两个ListIterator方法(ListIterator是可以双向遍历的一种迭代器，只适用于list)，两个搜索操作(indexOf，lastIndexof)，四个Positional Access Operations。

AbstractList感觉是精华啊，这个类里面实现了Iterator和ListIterator，ListIterator是只用于list的迭代器，提供向前遍历的功能。然后是一层一层抽象下来，到abstractList为止，只剩下最基本的增删改查(add(int index, E element), remove(int index),set(int index, E element),public E get)没有实现，其他的方法都已经实现好了。也就是说其他所有的逻辑都可以通过这四个方法组合。好特么厉害啊，逻辑清晰而且代码复用率高。
还有一点很出乎意料的就是sublist，本来还以为sublist会新建一个list然后将元素添加进去，结果原来是直接持有原来的对象，仅仅是限制了下标。其实仔细想想也应该的，如果再添加一次不是白白浪费计算时间了= =。

还有一点就是RandomAccess接口的用处。
RandomAccess是用来标记collection的，如果某个容器实现了这个接口，那么这个容器更适合使用for循环来遍历，

AbstractCollection两个地方比较注意，一个是对于数组越界的处理，一个是数组容量的处理。emmm只能说写的真的很严谨= =。

public abstract class MyAbstractCollection implements MyCollection {
    protected MyAbstractCollection(){}

    public abstract Iterator iterator();

    public abstract int size();

    @Override
    public boolean isEmpty() {
        return size()==0;
    }

    @Override
    public boolean contains(Object o) {
        Iterator iterator = iterator();
        if (o==null){
            //当collection为null，输入为null时返回true
            while (iterator.hasNext()){
                if (iterator.next()==null){
                    return true;
                }
            }
        }else {
            while (iterator.hasNext()){
                if (o.equals(iterator.next())){
                    return true;
                }
            }
        }
        return false;
    }

    /*将list以数组的形式返回*/
    @Override
    public Object[] toArray() {
        Object[] r = new Object[size()];//定义一个等大小的数组
        Iterator iterator = iterator();
        for (int i=0;i T[] toArray(T[] a) {
        int size = size();
        //使用反射来创建数组
        T[] r = a.length >= size ? a :
                (T[])java.lang.reflect.Array
                        .newInstance(a.getClass().getComponentType(), size);
        Iterator it = iterator();

        for (int i = 0; i < r.length; i++) {
            if (! it.hasNext()) { // collection中的数量小于期望值
                if (a == r) {
                    r[i] = null; // null-terminate
                } else if (a.length < i) {
                    return Arrays.copyOf(r, i);
                } else {
                    System.arraycopy(r, 0, a, 0, i);
                    if (a.length > i) {
                        a[i] = null;
                    }
                }
                return a;
            }
            r[i] = (T)it.next();
        }
        // more elements than expected
        return it.hasNext() ? finishToArray(r, it) : r;
    }

    //为什么要-8呢，因为这是个对象数组，而不是一个基础类型的数组，需要留有空间来描述这个对象
    //The object header consists of a mark word and a klass pointer.
    //The mark word has word size (4 byte on 32 bit architectures, 8 byte on 64 bit architectures) and
    //the klass pointer has word size on 32 bit architectures. On 64 bit architectures the klass pointer either has word size,
    // but can also have 4 byte if the heap addresses can be encoded in these 4 bytes.
    /**
     * @see 
     *     为什么数组最大值减8
     * */
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE-8;


    @SuppressWarnings("unchecked")
    private static  T[] finishToArray(T[] r,Iterator iterator){
        int i = r.length;
        while (iterator.hasNext()){
            int cap = r.length;
            if (i == cap){
                //数组扩容
                int newCap = cap + (cap >> 1)+1;
                //扩容后的数组容量过大，
                if (newCap-MAX_ARRAY_SIZE>0){
                    newCap = hugeCapacity(cap+1);
                }
                //扩容后数组转移
                r = Arrays.copyOf(r,newCap);
            }
            r[i++] = (T)iterator.next();
        }
        // trim if overallocated
        return (i==r.length)? r: Arrays.copyOf(r,i);
    }

    private static int hugeCapacity(int minCapacity){
        if(minCapacity < 0 ){//意味着大于MaxInteger了
            throw new OutOfMemoryError("Required array size too large");
        }
        return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
    }

    /*为什么一直抛出异常= =*/
    @Override
    public boolean add(E e) {
        throw new UnsupportedOperationException();
    }

    /**
     * 能用迭代器解决的问题都用迭代器些了
     * */
    @Override
    public boolean remove(Object o) {
        Iterator iterator = iterator();
        if (o == null){
            while (iterator.hasNext()){
                if (iterator.next() == null){
                    iterator.remove();
                    return true;
                }
            }
        }else {
            while (iterator.hasNext()){
                if (o.equals(iterator.next())){
                    iterator.remove();
                    return true;
                }
            }
        }
        return false;
    }

    @Override
    public boolean containsAll(MyCollection collection) {
        for (Object o:collection){
            if (!contains(o))
                return false;
        }
        return true;
    }

    //所以这里其实是只要有改变就返回true，而不需要全部确认插入
    @Override
    public boolean addAll(MyCollection collection) {
        boolean modified = false;
        for (E e:collection){
            if (add(e))
                modified = true;
        }
        return modified;
    }

    //写到这里下意识remove的时候想调用class中的remove方法= =，但是这样会多遍历一遍
    @Override
    public boolean removeAll(MyCollection collection) {
        if (collection == null)
            throw new NullPointerException();
        boolean modified = false;
        Iterator iterator = iterator();
        while (iterator.hasNext()){
            if (collection.contains(iterator.next())){
                iterator.remove();
                modified = true;
            }
        }
        return modified;
    }

    @Override
    public void clear() {
        Iterator iterator = iterator();
        while (iterator.hasNext()){
            iterator.next();
            iterator.remove();
        }
    }

    @Override
    public String toString() {
        Iterator iterator = iterator();
        if (! iterator.hasNext())
            return "[]";
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append('[');
        for (;;){
            E e = iterator.next();
            stringBuilder.append(e == this?"(this collection)":e);
            if (!iterator.hasNext())
                return stringBuilder.append(']').toString();
            stringBuilder.append(',').append(' ');
        }
    }
}

public interface List extends MyCollection{
    @Override
    int size();

    @Override
    boolean isEmpty();

    @Override
    boolean contains(Object o);

    @Override
    Iterator iterator();

    @Override
    Object[] toArray();

    @Override
    Object[] toArray(Object[] a);

    @Override
    boolean add(Object o);

    @Override
    boolean remove(Object o);

    @Override
    boolean containsAll(MyCollection collection);

    @Override
    boolean addAll(MyCollection collection);

    boolean addAll(int index, MyCollection collection);

    @Override
    boolean removeAll(MyCollection collection);

    @Override
    void clear();

    @Override
    int hashCode();

    @Override
    boolean equals(Object o);


    E get(int index);

    E set(int index,E element);

    void add(int index,E element);

    E remove(int index);

    int indexOf(Object o);

    int lastIndexOf(Object o);

    ListIterator listIterator();

    ListIterator listIterator(int index);

//具体的迭代器在这个abstract中实现。
public abstract class MyAbstractList extends MyAbstractCollection
        implements MyList {



    protected MyAbstractList(){}


    //Iterators


    //修饰该变量不需要参与序列化过程，
    //用于记录该容器的修改次数
    protected transient int modCount = 0;


    private class Itr implements Iterator{

        //这里的cursor = next；lastRet=current；
        int cursor = 0;

        int lastRet = -1;

        int expectedModeCount = modCount;

        @Override
        public boolean hasNext() {
            return cursor!=size();
        }

        @Override
        public E next() {
            checkDorComodification();
            try {
                int i= cursor;
                E next = get(i);
                lastRet = i;
                cursor = i+1;
                return next;
            }catch (IndexOutOfBoundsException e){
                checkDorComodification();
                throw new NoSuchElementException();
            }

        }

        final  void checkDorComodification(){
            if (modCount != expectedModeCount)
                throw new ConcurrentModificationException();
        }
    }

    private class ListItr extends Itr implements ListIterator{

        //cursor = next;
        ListItr(int index){
            cursor = index;
        }

        @Override
        public boolean hasPrevious() {
            return cursor!=0;
        }

        @Override
        public E previous() {
            checkDorComodification();
            try {
                int i = cursor-1;
                E privious = get(i);
                lastRet = cursor = i;
                return privious;
            }catch (IndexOutOfBoundsException e){
                checkDorComodification();
                throw new NoSuchElementException();
            }

        }

        @Override
        public int nextIndex() {
            return cursor;
        }

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

        @Override
        public void remove() {
            if (lastRet<0)
                throw new IllegalStateException();
            checkDorComodification();

        }

        @Override
        public void set(E e) {
            if (lastRet<0){
                throw new IllegalStateException();
            }
            checkDorComodification();
            try {
                MyAbstractList.this.set(lastRet,e);
                expectedModeCount = modCount;
            }catch (IndexOutOfBoundsException e1){
                throw new ConcurrentModificationException();
            }
        }


        @Override
        public void add(E e) {
            checkDorComodification();
            try{
                int i = cursor;
                MyAbstractList.this.add(i,e);
                lastRet = -1;
                cursor = i+1;
                expectedModeCount = modCount;
            }catch (IndexOutOfBoundsException ex){
                throw new ConcurrentModificationException();
            }
        }
    }

    @Override
    public Iterator iterator() {
        return new Itr();
    }

    @Override
    public ListIterator listIterator() {
        return listIterator(0);
    }

    @Override
    public ListIterator listIterator(final int index) {
        rangeCheckForAdd(index);
        return new ListItr(index);
    }

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







    //能用方法互相调用的，就不要用到持有的属性，
    //比如说这里要是我自己写，，，一定是又写一遍逻辑
    //这么想其实逻辑相近的接口互相调用着实现，能省很多的代码= =。
    public boolean add(E e) {
         add(size(),e);
        return true;
    }

    abstract public E get(int index);

    @Override
    public E set(int index, E element) {
        throw new UnsupportedOperationException();
    }

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

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

    @Override
    public int indexOf(Object o) {
        ListIterator iterator = listIterator();
        if(o == null){
            while (iterator.hasNext()){
                if (iterator.next()==null){
                    return iterator.previousIndex();
                }
            }
        }else {
            while (iterator.hasNext()){
                if (o.equals(iterator.next()))
                    return iterator.previousIndex();
            }
        }
        return -1;
    }

    @Override
    public int lastIndexOf(Object o) {
        ListIterator iterator = listIterator(size());
        if (o==null){
            while (iterator.hasPrevious()){
                if (iterator.previous()==null)return iterator.nextIndex();
            }
        }
        else {
            while (iterator.hasPrevious()){
                if (o.equals(iterator.previous())){
                    return iterator.nextIndex();
                }
            }
        }
        return -1;
    }

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

    @Override
    public boolean addAll(int index, MyCollection collection) {
        rangeCheckForAdd(index);
        boolean modified =false;
        for (E e:collection){
            add(index++,e);
            modified = true;
        }
        return modified;
    }

    protected void removeRange(int fromIndex, int toIndex){
        ListIterator listIterator = listIterator(fromIndex);
        for (int i=0,n=toIndex-fromIndex;i e1 = listIterator();
        ListIterator e2 = ((MyList)obj).listIterator();
        while (e1.hasNext() && e2.hasPrevious()){
            E o1 = e1.next();
            Object o2 = e2.next();
            //不知道嘛时候写逻辑的时候我能马上想到这样写= =
            if (!(o1==null ? o2 == null : o1.equals(o2)))
                return false;
        }
        //长度不一样
        return !(e1.hasNext()||e2.hasNext());
    }

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

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


}

//本来还以为sublist会新建一个list然后将元素添加进去，
// 结果原来是直接持有原来的对象，仅仅是限制了下标。
class MySubList extends MyAbstractList{
    private final MyAbstractList l;
    private final int offset ;
    private int size ;

    MySubList(MyAbstractList 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;
    }

    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();
    }

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

    //真是每次都需要检查一遍越界异常哦，，，
    @Override
    public E get(int index) {
        rangeCheck(index);
        checkForComodification();
        return l.get(index+offset);
    }

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

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

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

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

    @Override
    public boolean addAll(MyCollection collection) {
        return addAll(size,collection);
    }

    @Override
    public boolean addAll(int index, MyCollection collection) {
        rangeCheck(index);
        int cSize = collection.size();
        if (cSize==0)return false;
        checkForComodification();
        l.addAll(offset+index,collection);
        this.modCount = l.modCount;
        size+=cSize;
        return true;
    }

    @Override
    public Iterator iterator() {
        return listIterator();
    }

    @Override
    public ListIterator listIterator(final int index) {
        checkForComodification();
        rangeCheckForAdd(index);

        return new ListIterator() {
            private final ListIterator iterator = l.listIterator(index+offset);


            @Override
            public boolean hasNext() {
                return nextIndex()=0;
            }

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

            @Override
            public int nextIndex() {
                return iterator.nextIndex()-offset;
            }

            @Override
            public int previousIndex() {
                return iterator.previousIndex()-offset;
            }

            @Override
            public void remove() {
                iterator.remove();
                MySubList.this.modCount = l.modCount;
                size--;
            }

            @Override
            public void set(E e) {
                iterator.set(e);
            }

            @Override
            public void add(E e) {
                iterator.add(e);
                MySubList.this.modCount = l.modCount;
                size++;
            }
        };
    }

    @Override
    public MyList subList(int fromIndex, int toIndex) {
        return new MySubList(this, fromIndex, toIndex);
    }

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

class RandomAccessSublist extends MySubList implements RandomAccess{

    RandomAccessSublist(MyAbstractList list, int fromIndex, int toIndex) {
        super(list, fromIndex, toIndex);
    }
    public MyList subList(int fromIndex, int toIndex) {
        return new RandomAccessSublist(this, fromIndex, toIndex);
    }
}