Chapel: Support LinkedList.insertAfter()

[haris741]

implement; proc insertAfter(e: eltType, node : unmanaged listNode(eltType)? = nil): bool
this function adds the node next to the reference node in the argument and returns true if successfully added

[souris-dev]

A linked list, by design, is not supposed to provide random access to elements. As such, the overload of the [] operator might not be necessary. Similarly, the insertat() procedure may instead be designed to insert after a particular element and not an index.

Using a linked list in Chapel when the user requires the use of [] to access the items in it would be quite uncommon, I believe.

The search procedure is already being implemented in a PR: please see issue #15294 and PR #15317.

[priyank23]

@haris741 I agree with @souris-dev here. The implementation of insert and accessor functions on the basis of indices is point-less in case of a linked list.

[haris741]

@priyank23 @souris-dev, I really appreciate your comments.
@souris-dev How about adding proc insertat() that adds after a certain value?

[haris741]

moreover, the find() proc implemented returns true or false. How about overloading that funciton that returns the reference of the node if found?

[haris741]

I have opened a pull request #15509 please someone review. As I am new to Chapel kindly guide me through if I make errors somewhere.

[priyank23]

@haris741 before implementing such a function, we must think about the implementation of linked lists. Is it correct to insert elements in a data structure that manages the data on the basis of references and not the value of the data itself. I mean, creating a find() function to return the reference is good but inserting on the basis of existence of values in the linked list, is it really necessary? I would rather suggest to implement an insertAfter() function to insert an element or a node after a certain node whose ref should be passed as a parameter.

[souris-dev]

I think I was unable to convey my point properly earlier, my apologies.

@haris741 Inserting after a particular element, in my opinion, should not imply searching for the element _value_ and inserting it after that. This could lead to an ambiguity in the position of insertion if there are two or more elements who have the same value (further leading to unexpected results).
Rather, as @priyank23 suggests, we could position it after a reference to a node.

Also, for the find(e: eltType) procedure, it should be discussed what the procedure should do in case that element is not found in the list. An exception could be thrown or something else may be done, though returning nil could have difficulties. Halting the program may be another option, but could be counter-intuitive for the user.

[souris-dev]

Similarly, for the find(e: eltType) procedure, one could think of a scenario where there are two or more than two elements that have the same value. Using simple linear search would return a ref to only the first occurrence of that value. The user should be given further control, I believe in case they want a reference to the second or third occurrence.

To be clear about what I'm driving at, I would ask you to recall the list.index(item) method for lists in Python, which returns the index of the first occurrence of item. It also allows us to specify an offset for searching, which could be used to find the indices of the other occurrences of item in the list.

However, for linked lists, this offset may not be specified as an index, and we need another method that will allow similar control over the search operation.

[ben-albrecht]

search(int) needs to be implemented. Moreover operator [] overloading can help accesing the data better. Insertat() also needs implementation

@haris741 - I would suggest splitting this up into separate issues per feature request to help keep the discussion organized. Also, see the design section of the contributor info doc for guidance on proposing new features.

[haris741]

@ben-albrecht thanks alot for correction. I will take care of these from now on.

[haris741]

@priyank23 really obliged for your suggestions. What you mean for insertAfter() is having two arguments, one is the node to be inserted and the second is the reference of the node. is it?

[priyank23]

one is the node to be inserted and the second is the reference of the node. is it?

I am sorry. I am a little bit confused about the two things you mentioned here.
What I meant was, we can have a function with two parameters, one is the reference of the node in the linked list after which we want to insert and the other can be e: eltType or a reference to a linked list node. You can imagine the push_back(e: eltType) as a special case of this insertAfter() function. The definition of the function can be
proc insertAfter(e: eltType, node : unmanaged listNode(eltType)? = nil): bool
This returns a false upon failure.

[haris741]

one is the node to be inserted and the second is the reference of the node. is it?

I am sorry. I am a little bit confused about the two things you mentioned here.
What I meant was, we can have a function with two parameters, one is the reference of the node in the linked list after which we want to insert and the other can be e: eltType or a reference to a linked list node. You can imagine the push_back(e: eltType) as a special case of this insertAfter() function. The definition of the function can be
proc insertAfter(e: eltType, node : unmanaged listNode(eltType)? = nil): bool
This returns a false upon failure.

Yes I meant exactly same. Thank You for the clarification.

[priyank23]

@haris741 I think you should modify the title of this issue as this issue is now focused towards implementing an insertAfter function.

[ben-albrecht]

I think you should modify the title of this issue as this issue is now focused towards implementing an insertAfter function.

Agreed, and the description should follow that as well.

The title could be simplified to Support LinkedList.insertAfter() with the actual suggested signature in the description. Feel free to open separate issues for the other requests that were originally in this issue.

[ben-albrecht]

To motivate this feature, does LinkedList.insertAfter exist in other languages' standard libraries? If so, what naming convention and arguments are used? Do they also support insertBefore, or just insert?