CODEWITHSUNDEEP
iteratortreeset
Zhong Yang
Zhong Yang

Reputation: 203

How Iterator implement in TreeSet

I read java source about TreeSet , but I can not find the implement of Iterator in TreeSet. Could anybody tell me how Iterator implements in TreeSet, and where is the source code in TreeSet? thanks!

Upvotes: 4

Views: 735

Answers (2)

TomerBu
TomerBu

Reputation: 1503

Thanks to @kriegaex i was able to dig up and find the base class for TreeMap Iterators in TreeMap.java Line# 1466

As we can see from the source - Iterator is implemented via the predecessor and successor methods that accept a child node parameter.

Start from the min value, than for each next() find its in-order successor.

 abstract class PrivateEntryIterator<T> implements Iterator<T> {
    Entry<K,V> next;
    Entry<K,V> lastReturned;
    int expectedModCount;

    PrivateEntryIterator(Entry<K,V> first) {
        expectedModCount = modCount;
        lastReturned = null;
        next = first;
    }

    public final boolean hasNext() {
        return next != null;
    }

    final Entry<K,V> nextEntry() {
        Entry<K,V> e = next;
        if (e == null)
            throw new NoSuchElementException();
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        next = successor(e);
        lastReturned = e;
        return e;
    }

    final Entry<K,V> prevEntry() {
        Entry<K,V> e = next;
        if (e == null)
            throw new NoSuchElementException();
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        next = predecessor(e);
        lastReturned = e;
        return e;
    }

    public void remove() {
        if (lastReturned == null)
            throw new IllegalStateException();
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        // deleted entries are replaced by their successors
        if (lastReturned.left != null && lastReturned.right != null)
            next = lastReturned;
        deleteEntry(lastReturned);
        expectedModCount = modCount;
        lastReturned = null;
    }
}

The successor method traverses the tree:

static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
        if (t == null)
            return null;
        else if (t.right != null) {
            Entry<K,V> p = t.right;
            while (p.left != null)
                p = p.left;
            return p;
        } else {
            Entry<K,V> p = t.parent;
            Entry<K,V> ch = t;
            while (p != null && ch == p.right) {
                ch = p;
                p = p.parent;
            }
            return p;
        }
}

Thanks @kriegaex for the guidance.

Upvotes: 0

kriegaex
kriegaex

Reputation: 67387

Well, if you look at the source code of TreeSet<E>.iterator() you see:

public Iterator<E> iterator() {
    return m.navigableKeySet().iterator();
}

Next search for the definition of m:

private transient NavigableMap<E,Object> m;

So obviously TreeSet points to a NavigableMap which is not really a surprise because TreeSet's JavaDoc says:

A NavigableSet implementation based on a TreeMap.

Okay, so let us check the source code of TreeMap. There you will find the method navigableKeySet() which was referenced above, pointing to a member named navigableKeySet which is of type TreeMap.KeySet<K>, a static inner class. There in turn you will find an iterator() method and so forth. The TreeMap class contains quite a lot of inner classes, the whole structure is pretty complex, but if you are interested you can sort it out by yourself. I think I gave you a good headstart. ;-)

Upvotes: 2

Related Questions