-
Notifications
You must be signed in to change notification settings - Fork 194
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
Spliterators for Tree data structures #135
Comments
What I am thinking currently is to make the spliterator go over the elements like the iterator, but keep a reference to the "right most seen but not traversed" node. When constructed, the current nodes is set to Then when trySplit() is called, the newly returned spliterator (the prefix) has the current spliterators current node, the right most pointer set (some undermined algorithm), and a fence telling it not to traverse past the split point. Then the current iterator, the suffix, "jumps" to the Assuming a mostly balanced tree, this should result in a mostly even split. Does this rough algorithm sound correct to you? Aside from the big glaring unknown about how to handle the prefix's |
But, the trees are threaded. The iterator uses threads. I think you are referring to a recursive visiting iterator. Am I wrong? |
The idea is that a spliterator needs to be able to split efficiently but still maintain sorted order. This means I need some way to find a node somewhere further along efficiently (more towards the middle of the current and the end is better, but not required) as well as some way to designate a maximum element to return (which iterator does not have to do since it always goes over everything). I couldn't figure out the iteration algorithm to understand how to accomplish all this. Thus for now it is just inheriting the iterator based spliterator from SortedSet interface. I didn't want to just rip off what OpenJDK does for TreeMap because, well, ripping off code that directly is a bad idea. ;) |
Mmmmhhhh... it seems a pretty trivial recurive subdivision. Am I missing something? |
It probably is, I just couldn't figure it out. :embarrassed: |
I'll have a look. But this is something to be done in the long run. |
The current pull request to add spliterator methods to collection types omits optimized Spliterator implementations for the tree data structures, due to complexity of "splitting" a tree data structure (not a true split operation, since it still is one tree. This is just splitting a view of the tree)
This bug tracks adding Spliterator implementations for these data structures.
The text was updated successfully, but these errors were encountered: