Scala Programming Language
  1. Scala Programming Language
  2. SI-6642

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

    Details

      Description

      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.

        Activity

        Hide
        Jamie Allen added a comment -

        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.

        Show
        Jamie Allen added a comment - 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.
        Hide
        Jason Zaugg added a comment -

        Welome to JIRA, a land of coarse grained permissions.

        Demoted to Major on your behalf.

        Show
        Jason Zaugg added a comment - Welome to JIRA, a land of coarse grained permissions. Demoted to Major on your behalf.
        Hide
        James Iry added a comment -

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

        Show
        James Iry added a comment - We can certainly look at an efficient mutable bidirectional iterator over TreeMaps, but we can't break immutability guarantees of the core collections.
        Hide
        James Iry added a comment -

        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?

        Show
        James Iry added a comment - 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?
        Hide
        James Iry added a comment -

        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.

        Show
        James Iry added a comment - 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.
        Hide
        James Iry added a comment -

        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.

        Show
        James Iry added a comment - 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.
        Show
        James Iry added a comment - https://github.com/scala/scala/pull/2119

          People

          • Assignee:
            James Iry
            Reporter:
            Jamie Allen
          • Votes:
            0 Vote for this issue
            Watchers:
            5 Start watching this issue

            Dates

            • Created:
              Updated:
              Resolved:

              Development