Java中Set&List的迭代器实现步骤解析

private class Itr implements Iterator<E> {    int cursor;    // index of next element to return    int lastRet = -1; // index of last element returned; -1 if no such    int expectedModCount = modCount;    // prevent creating a synthetic constructor    Itr() {}    public boolean hasNext() {      return cursor != size;    }    @SuppressWarnings("unchecked")    public E next() {      checkForComodification();      int i = cursor;      if (i >= size)        throw new NoSuchElementException();      Object[] elementData = ArrayList.this.elementData;      if (i >= elementData.length)        throw new ConcurrentModificationException();      cursor = i + 1;      return (E) elementData[lastRet = i];    }    public void remove() {      if (lastRet < 0)        throw new IllegalStateException();      checkForComodification();      try {        ArrayList.this.remove(lastRet);        cursor = lastRet;        lastRet = -1;        expectedModCount = modCount;      } catch (IndexOutOfBoundsException ex) {        throw new ConcurrentModificationException();      }    }  }

private class ListItr implements ListIterator<E> {    private Node<E> lastReturned;    private Node<E> next;    private int nextIndex;    private int expectedModCount = modCount;    ListItr(int index) {      // assert isPositionIndex(index);      next = (index == size) ? null : node(index);      nextIndex = index;    }    public boolean hasNext() {      return nextIndex < size;    }    public E next() {      checkForComodification();      if (!hasNext())        throw new NoSuchElementException();      lastReturned = next;      next = next.next;      nextIndex++;      return lastReturned.item;    }    public boolean hasPrevious() {      return nextIndex > 0;    }    public E previous() {      checkForComodification();      if (!hasPrevious())        throw new NoSuchElementException();      lastReturned = next = (next == null) ? last : next.prev;      nextIndex--;      return lastReturned.item;    }    public int nextIndex() {      return nextIndex;    }    public int previousIndex() {      return nextIndex - 1;    }    public void remove() {      checkForComodification();      if (lastReturned == null)        throw new IllegalStateException();      Node<E> lastNext = lastReturned.next;      unlink(lastReturned);      if (next == lastReturned)        next = lastNext;      else        nextIndex--;      lastReturned = null;      expectedModCount++;    }    public void set(E e) {      if (lastReturned == null)        throw new IllegalStateException();      checkForComodification();      lastReturned.item = e;    }    public void add(E e) {      checkForComodification();      lastReturned = null;      if (next == null)        linkLast(e);      else        linkBefore(e, next);      nextIndex++;      expectedModCount++;    }    public void forEachRemaining(Consumer<? super E> action) {      Objects.requireNonNull(action);      while (modCount == expectedModCount && nextIndex < size) {        action.accept(next.item);        lastReturned = next;        next = next.next;        nextIndex++;      }      checkForComodification();    }    final void checkForComodification() {      if (modCount != expectedModCount)        throw new ConcurrentModificationException();    }  }

/**   * Constructs a new, empty set; the backing {@code HashMap} instance has   * default initial capacity (16) and load factor (0.75).   */  public HashSet() {    map = new HashMap<>();  }  /**   * Constructs a new set containing the elements in the specified   * collection. The {@code HashMap} is created with default load factor   * (0.75) and an initial capacity sufficient to contain the elements in   * the specified collection.   *   * @param c the collection whose elements are to be placed into this set   * @throws NullPointerException if the specified collection is null   */  public HashSet(Collection<? extends E> c) {    map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));    addAll(c);  }  /**   * Constructs a new, empty set; the backing {@code HashMap} instance has   * the specified initial capacity and the specified load factor.   *   * @param   initialCapacity  the initial capacity of the hash map   * @param   loadFactor    the load factor of the hash map   * @throws   IllegalArgumentException if the initial capacity is less   *       than zero, or if the load factor is nonpositive   */  public HashSet(int initialCapacity, float loadFactor) {    map = new HashMap<>(initialCapacity, loadFactor);  }  /**   * Constructs a new, empty set; the backing {@code HashMap} instance has   * the specified initial capacity and default load factor (0.75).   *   * @param   initialCapacity  the initial capacity of the hash table   * @throws   IllegalArgumentException if the initial capacity is less   *       than zero   */  public HashSet(int initialCapacity) {    map = new HashMap<>(initialCapacity);  }  /**   * Constructs a new, empty linked hash set. (This package private   * constructor is only used by LinkedHashSet.) The backing   * HashMap instance is a LinkedHashMap with the specified initial   * capacity and the specified load factor.   *   * @param   initialCapacity  the initial capacity of the hash map   * @param   loadFactor    the load factor of the hash map   * @param   dummy       ignored (distinguishes this   *       constructor from other int, float constructor.)   * @throws   IllegalArgumentException if the initial capacity is less   *       than zero, or if the load factor is nonpositive   */  HashSet(int initialCapacity, float loadFactor, boolean dummy) {    map = new LinkedHashMap<>(initialCapacity, loadFactor);  }

public Iterator<E> iterator() {    return map.keySet().iterator();  }

final class KeySet extends AbstractSet<K> {    public final int size()         { return size; }    public final void clear()        { HashMap.this.clear(); }    public final Iterator<K> iterator()   { return new KeyIterator(); }    public final boolean contains(Object o) { return containsKey(o); }    public final boolean remove(Object key) {      return removeNode(hash(key), key, null, false, true) != null;    }    public final Spliterator<K> spliterator() {      return new KeySpliterator<>(HashMap.this, 0, -1, 0, 0);    }    public final void forEach(Consumer<? super K> action) {      Node<K,V>[] tab;      if (action == null)        throw new NullPointerException();      if (size > 0 && (tab = table) != null) {        int mc = modCount;        for (Node<K,V> e : tab) {          for (; e != null; e = e.next)            action.accept(e.key);        }        if (modCount != mc)          throw new ConcurrentModificationException();      }    }  }

abstract class HashIterator {    Node<K,V> next;    // next entry to return    Node<K,V> current;   // current entry    int expectedModCount; // for fast-fail    int index;       // current slot    HashIterator() {      expectedModCount = modCount;      Node<K,V>[] t = table;      current = next = null;      index = 0;      if (t != null && size > 0) { // advance to first entry        do {} while (index < t.length && (next = t[index++]) == null);      }    }    public final boolean hasNext() {      return next != null;    }    final Node<K,V> nextNode() {      Node<K,V>[] t;      Node<K,V> e = next;      if (modCount != expectedModCount)        throw new ConcurrentModificationException();      if (e == null)        throw new NoSuchElementException();      if ((next = (current = e).next) == null && (t = table) != null) {        do {} while (index < t.length && (next = t[index++]) == null);      }      return e;    }    public final void remove() {      Node<K,V> p = current;      if (p == null)        throw new IllegalStateException();      if (modCount != expectedModCount)        throw new ConcurrentModificationException();      current = null;      removeNode(p.hash, p.key, null, false, false);      expectedModCount = modCount;    }  }  final class KeyIterator extends HashIterator    implements Iterator<K> {    public final K next() { return nextNode().key; }  }