STL-like Java Red-black tree / TreeSet/Map and linked lists with non fail-fast/safe iterators

I am looking for a library with a Red-black tree and Linked list implementation offering iterators which are not fail-fast. I would like to have the same functionality as I do in C++ using STL and that is:

• insertion in the tree/list does not invalidate any iterators
• removal invalidates only the iterator that points at the element being removed
• it is possible to somehow store the "position" of the iterator and refer to the value it is pointing at

This implementation would be nice as it would offer the ability to modify the list/tree while using the a part of it. Here are some examples:

• obtaining adjacent element in linked list / red-black tree to some stored value in O(1)
• batch insertions / removals (no constraints such as one removal per position increment)
• splitting linked list in O(1) via position of the iterator
• more efficient removals when having stored position of the iterator (e.g. by keeping iterators to a position in linked list, removal is O(1), not O(N))

I would also like that library/source code/implementation to have some Apache/GPL-friendly licence and is fairly extensible (so I can make my own modifications to implement some ope开发者_开发问答rations such as the ones from the examples above).

If there exists no such library, is there some other library which could help me in implementing those two data structures on my own?

---

These are both pretty easy to implement yourself. The iterator has to do three things:

1. Only store two references, one to the "current" element and one to the outer container object (the blob storing the root reference (tree) or the head/tail references (list)).

2. Be able to determine whether the referred-to element is valid (easy, if parent pointer is null (tree) or prev/next pointers are null (list) then this better be the tree root or the head/tail of the list). Throw something when any operations at all are attempted on an invalid iterator.

3. Be able to find the prev/next element.

There are a couple gotchas: for the list, it would be a pain to support the java.util.ListIterator's nextIndex() and prevIndex() efficiently, and, of course, now you have the problem of dealing with concurrent modifications! Here's an example of how things could go bad:

while (it.hasNext()) {
    potentially_delete_the_last_element()
    it.next() // oops, may throw NoSuchElementException.
}

The way to avoid this would be never to modify the list between checking if it has next/prev and actually retrieving next/prev.