Position-based structures and Position API

[gissuebot]

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.

[gissuebot]

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. LinkedLists have to traverse part of the list sequentially with each index.

PositionLists seemed to handle the case adequately.

[gissuebot]

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  NodeList.Node<E> addAfter(E e)           Adds the provided element at the list position after this node.  NodeList.Node<E> addBefore(E e)           Adds the provided element at the list position before this node.  E get()           Retrieves the element that the node contains.  int index()           Returns the position of the node within the list.  NodeList<E> list()           Returns the list containing this node, or null if this node is no longer in a list.  ListIterator<E> listIterator()           Returns a ListIterator whose cursor position is just before this node.  boolean moveToEnd()           Moves this node to the end of the list.  boolean moveToStart()           Moves this node to the start of the list.  NodeList.Node<E> next()           Returns the node that comes after this node in the list, or null if this is the last node in the list.  NodeList.Node<E> previous()           Returns the node that comes before this node in the list, or null if this is the first node in the list.  void remove()           Removes the node from the underlying list.  E set(E e)           Replaces the node's current element.  NodeList<E> splitAfter()           Splits the list containing this node into two lists, separating the lists just after this node.  NodeList<E> splitBefore()           Splits the list containing this node into two lists, separating the lists just before this node.  boolean swap(NodeList.Node<E> node)           Switches the list position of this node and the provided node.  String toString()           Returns the string representation of the node's element, or null if the element is null.

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: Research

[gissuebot]

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)         Adds the specified elements in place (after|before) this node.         Not sure what to return, if anything. boolean at[End|Start]()         Returns true if this node is at the (end|start) of the list. (NodeList|Node)<E> atIndex(int index)         Returns the node at the specified index.         Not sure if specified index should be relative or absolute to the current position.         @throws IndexOutOfBoundsException? (NodeList|Node)<E> [end|start]()         Returns the (last|first) position in this list. (NodeList|Node)<E> find[After|Before](Object o)         Searches for the first element (after|before) this position that equals the specified value.         Or null? int index()         Returns the index of this position relative to the underlying list.

I would assume that this would also attempt to implement [Iterable at least|List at most] or could be viewed as such?

[gissuebot]

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  NodeList.Node<E> addAndGetNode(E e)           Inserts the provided object at the end of the list.  NodeList.Node<E> addAndGetNode(int index, E e)           Inserts the provided object at the specified position of the list.  boolean concat(NodeList<E> nodeList)           Concatenates the supplied list to the end of this list.  NodeList.Node<E> getNode(int index)           Returns the node at the specified position within the list.  NodeList.Node<E> lastNodeWith(Object o)           Returns the last node in the list whose element equals the provided object, or null if the list does not contain the element.  NodeList.Node<E> nodeWith(Object o)           Returns the first node in the list whose element equals the provided object, or null if the list does not contain the element.