Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

scala.collection.generic.Sorted needs a nextKey() method #6642

Closed
scabug opened this issue Nov 9, 2012 · 8 comments
Closed

scala.collection.generic.Sorted needs a nextKey() method #6642

scabug opened this issue Nov 9, 2012 · 8 comments
Labels
enhancement has PR
Milestone
2.11.0-M2

Comments

@scabug
Copy link

scabug commented Nov 9, 2012

We should be able to query the nextKey: Option[T] from a TreeMap[T, U] that is using the Sorted[T] interface. We also think the firstKey and lastKey implementations should not throw a NoSuchElementException but return Option[T] as well. We do not want to create a new iterator (such as keySet would do) or a new collection (as dropWhile would do).

Seems to me like this would be implemented with some kind of pointer to "currentKey" in the collection. Which worries me because now we'd have to pay attention to concurrency issues.
@scabug
Copy link
Author

scabug commented Nov 9, 2012

Imported From: https://issues.scala-lang.org/browse/SI-6642?orig=1
Reporter: Jamie Allen (shinolajla)
Assignee: @JamesIry
Affected Versions: 2.10.0-RC2

@scabug
Copy link
Author

scabug commented Nov 9, 2012

Jamie Allen (shinolajla) said:
BTW, I don't consider this a "Blocker", but I couldn't change the priority field when creating the issue. Nor can I edit the field now.

@scabug
Copy link
Author

scabug commented Nov 9, 2012

@retronym said:
Welome to JIRA, a land of coarse grained permissions.

Demoted to Major on your behalf.

@scabug
Copy link
Author

scabug commented Feb 4, 2013

@JamesIry said:
We can certainly look at an efficient mutable bidirectional iterator over TreeMaps, but we can't break immutability guarantees of the core collections.

@scabug
Copy link
Author

scabug commented Feb 4, 2013

@JamesIry said:
Just to clarify. A TreeMap is at heart just an immutable, unidirectional, rooted tree. There are no backwards pointers. Having backwards pointers would destroy the structure sharing properties which are key to the efficiency of immutable, persistent data structures.

There are well known ways to create navigable views over such structures but they all involve allocations. So when I say efficient I don't mean free from allocations.

Is it possible you'd be better off with an entirely different data structure?

@scabug
Copy link
Author

scabug commented Feb 6, 2013

@JamesIry said:
After much offline back and forth it's become clear that what's being asked for is a cheap way to navigate keys in order given a starting key. Seems like a good fit for something zipper-ish.

@scabug
Copy link
Author

scabug commented Feb 11, 2013

@JamesIry said:
I still like the zipper-ish idea, but I'd rather give that more time to bake a clean API. The existing iterator on red-black tree is nice and clean, it just lacks the ability to start anywhere but the first key.

@scabug
Copy link
Author

scabug commented Feb 12, 2013

@JamesIry said:
scala/scala#2119

@scabug scabug closed this as completed Feb 20, 2013
@scabug scabug added this to the 2.11.0-M2 milestone Apr 7, 2017
@scabug scabug mentioned this issue Apr 7, 2017
Open
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
enhancement has PR
Projects
None yet
Milestone
2.11.0-M2
Development

No branches or pull requests
1 participant
@scabug