search

dart-lang / sdk

The Dart SDK, including the VM, JS and Wasm compilers, analysis, core libraries, and more.
https://dart.dev
BSD 3-Clause "New" or "Revised" License
10.09k stars 1.56k forks source link

Add iteratorFrom SplayTreeMap #10158

Open jtmcdole opened 11 years ago

jtmcdole commented 11 years ago

It would be nice to have an iterator (forward and reverse varieties) starting from a given key. Currently if you want to walk the tree from a given point, its a series of map lookups.

lrhn commented 11 years ago

Removed Type-Defect label. Added Type-Enhancement, Area-Library, Triaged labels.

lrhn commented 11 years ago

Splay trees are not really built for iteration. If you even read from the tree while iterating, it changes its structure. However, it isn't suitable to throw a ConcurrentModificationError due to a reading operation, so we'll have to handle it behind the scenes (somewhat inefficiently).

Iteration would be easier if we added a parent link, but that would be an overhead when it's not used.

It would probably be better to have a stable tree structure (AVL or Red/Black trees) as well. They have a slightly higher overhead, but better guarantees/worst case behavior. For those, an "iterateFrom/bidi-iterator" would make more sense.

jtmcdole commented 11 years ago

Ah, I didn't notice the missing parent link. I can just pull over an AVL implementation from java.