Abstract Collection

Data_Structure

Collection: Interface;
AbstractCollection: Abstract Class, reduced workload of Collection interface;

// 所谓 collection骨干实现！

1. Methods Content

• Fields;
• boolean contains(Object o): judge if an Object is insided in collection
• Object[] toArray(): return collection as Array
• T[] toArray(T[] a):
• T[] finishToArray(T[] r, Iterator it):
• int hugeCapacity(int minCapacity):
• boolean remove(Object o): remove by iterator
• Batch Ooperation:
  addAll, removeAll, retainAll, containsAll
• void clear(): clear elements by iterator
• String toString(): print collection by iterator

2. Fields:

        private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
           // still confused... why minus 8??
        public abstract Iterator<E> iterator();//return iterator  
        public abstract int size();//size of container(collection)  

3. Contain Check through Iterator

        public boolean contains(Object o) { 
            Iterator<E> it = iterator();// Get Current Iterator
            if (o==null) {  // Be aware of checking null value  
                while (it.hasNext()) //  
                    if (it.next()==null)  
                        return true;  
            } else {       //Check non-null
                while (it.hasNext())  
                    if (o.equals(it.next()))//judge equiavalent  
                        return true;  
            }  
            return false;  
        }

4. Change to Array

Return collection as an array.

        public Object[] toArray() {
            Object[] r = new Object[size()];//allocate array by size  
            Iterator<E> it = iterator();  
            for (int i = 0; i < r.length; i++) {  
                if (! it.hasNext()) // end iteration if no more element  
                    return Arrays.copyOf(r, i);// to make sure the size is fit without space waste  
                r[i] = it.next();  
            }  
            return it.hasNext() ? finishToArray(r, it) : r;//for thread safety  
        }  

    public <T> T[] toArray(T[] a) {  
        int size = size();  
        // make sure the collection size is bigger than a's length, otherwise generate a new array 
        // notice the reflection to gurantee the element type
        T[] r = a.length >= size ? a :(T[])java.lang.reflect.Array.newInstance(a.getClass().getComponentType(), size);  
        Iterator<E> it = iterator(); 
        for (int i = 0; i < r.length; i++) {  
            if (! it.hasNext()) { //no more element  
                if (a == r) {  
                    r[i] = null; 
                } else if (a.length < i) {  
                    return Arrays.copyOf(r, i);
                    //when the a has no enough space copy array for expand
                } else {  
                    System.arraycopy(r, 0, a, 0, i); 
                    if (a.length > i) {  
                        a[i] = null;  
                    }  
                }  
                return a;  
            }  
            r[i] = (T)it.next();//迭代器赋值元素  
        }  
        return it.hasNext() ? finishToArray(r, it) : r;
    } 
     private static <T> T[] finishToArray(T[] r, Iterator<?> it) {//notice the static, but why?????  
        int i = r.length;  
        while (it.hasNext()) {  
            int cap = r.length;  
            if (i == cap) {//进行扩容  
                int newCap = cap + (cap >> 1) + 1;//1.5 times  
                if (newCap - MAX_ARRAY_SIZE > 0) // same step as arraylist resize?
                    newCap = hugeCapacity(cap + 1);
                r = Arrays.copyOf(r, newCap);
            }  
            r[i++] = (T)it.next();
        }  
        return (i == r.length) ? r : Arrays.copyOf(r, i);
    }

5. Clear and toString

    public void clear() {  
        Iterator<E> it = iterator();
        while (it.hasNext()) {  
            it.next();  
            it.remove();
        }  
    }  
    // print collection with "[" "]"? 
    public String toString() {  
        Iterator<E> it = iterator();  
        if (! it.hasNext())  
            return "[]";  
        StringBuilder sb = new StringBuilder();  
        sb.append('[');  
        for (;;) {  
            E e = it.next();  
            sb.append(e == this ? "(this Collection)" : e);  
            if (! it.hasNext())  
                return sb.append(']').toString();  
            sb.append(',').append(' ');  
        }  
    }