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
Position-based structures and Position API #1285
Comments
Original comment posted by jysjys1486 on 2013-02-10 at 06:31 AM I'll add that I was implementing depth-first retrieval of superclasses and interfaces sans recursion; I would reach position i, add all of the successors in front of it, and then advance to i+1. ListIterator doesn't have an addAll analogy; adding the successors in a preserved order involves advancing each step, and then having to retrace when done. ArrayLists aren't efficient with the insertions. PositionLists seemed to handle the case adequately. |
Original comment posted by cpovirk@google.com on 2013-02-12 at 02:23 AM The closest we've come to this is an internal NodeList class. I don't think it did subList, but it supported various other operations: Method Summary It hasn't gotten much traction. It's the kind of thing that can be very helpful in some cases, but those cases are pretty rare: Lists => mutable lists => non-random-access mutable lists => non-random-access mutable lists on which chains of position-relative operations are performed => non-random-access mutable lists on which chains of position-relative operations are performed and ListIterator isn't enough => non-random-access mutable lists on which chains of position-relative operations are performed and ListIterator isn't enough but NodeList is. Status: |
Original comment posted by jysjys1486 on 2013-02-13 at 09:30 AM A few other operations: returnType addAll[After|Before](Iterable<? extends E> elements) I would assume that this would also attempt to implement [Iterable at least|List at most] or could be viewed as such? |
Original comment posted by cpovirk@google.com on 2013-02-13 at 05:49 PM Yes, ours implements List. The operations I listed above are those on the Node class. The interface of NodeList itself is (in addition to the usual List operations): Method Summary |
Original issue created by jysjys1486 on 2013-02-10 at 01:44 AM
I was curious whether there was ever a request to implement such collections that involved returning positions (essentially polymorphic nodes) instead of having to use integer indices?
I feel as if positions and position-based structures would aid sequential access and iteration.
Cases of finding indices and using them in:
LinkedList<?> list; // initialized
int i = list.indexOf(o); // not -1; O(n)
list.subList(i, list.size() - 1); // O(n) to reach index
This is opposed to the following:
PositionList list; // initialized Position position = list.find(o); // successful; O(n)
list.subList(position, list.size() - 1); // O(1) to reach index
Even when considering ListIterator, its API is involved with integer indices that, otherwise, would be inefficient to use in the associated list.
I was just curious if position-based structures were ever considered.
The text was updated successfully, but these errors were encountered: