a while ago I wrote a doubly linked list (in C), which has a compare callback to allow custom sorting for example

int cmpNodes(cnode_t* n1, cnode_t* n2)
{
  mapNode_t* rn1 = (mapNode_t*)(n1->data);
  mapNode_t* rn2 = (mapNode_t*)(n2->data);
  if (rn1->G + rn1->H > rn2->G + rn2->H) return 1;
  return 0;
}

would be called by

clistSort(openList, cmpNodes);

The list would then be ordered by G + H fields (or any other algorithm you code)


I notice there is a doubly linked list in the standard library, however it doesn't seem to allow for a custom compare, I'd rather not port my old C list code, can someone please give me some clues as to how I can reorder a list with a custom comparison...?

On 10/12/18 3:40 PM, Codifies wrote:
> a while ago I wrote a doubly linked list (in C), which has a compare callback to allow custom sorting for example
> 
> int cmpNodes(cnode_t* n1, cnode_t* n2)
> {
>    mapNode_t* rn1 = (mapNode_t*)(n1->data);
>    mapNode_t* rn2 = (mapNode_t*)(n2->data);
>    if (rn1->G + rn1->H > rn2->G + rn2->H) return 1;
>    return 0;
> }
> 
> would be called by
> 
> clistSort(openList, cmpNodes);
> 
> The list would then be ordered by G + H fields (or any other algorithm you code)
> 
> 
> I notice there is a doubly linked list in the standard library, however it doesn't seem to allow for a custom compare, I'd rather not port my old C list code, can someone please give me some clues as to how I can reorder a list with a custom comparison...?

Unfortunately, I can't find a way to sort a doubly linked list in phobos, so comparisons are somewhat moot.

However, if there *were* a sorting routine, generally the comparison function is done via whatever type you give it, or is given a custom comparison routine.

In my ancient dcollections library linked-list sorting is supported via a `less` parameter: https://github.com/schveiguy/dcollections/blob/82118cfd4faf3f1ad77df078d279f1b964f274e7/dcollections/LinkList.d#L997

-Steve

On Friday, 12 October 2018 at 20:29:27 UTC, Steven Schveighoffer wrote:
> On 10/12/18 3:40 PM, Codifies wrote:
>> [...]
>
> Unfortunately, I can't find a way to sort a doubly linked list in phobos, so comparisons are somewhat moot.
>
> However, if there *were* a sorting routine, generally the comparison function is done via whatever type you give it, or is given a custom comparison routine.
>
> In my ancient dcollections library linked-list sorting is supported via a `less` parameter: https://github.com/schveiguy/dcollections/blob/82118cfd4faf3f1ad77df078d279f1b964f274e7/dcollections/LinkList.d#L997
>
> -Steve

I think I'll look later and see if the links (in the dlist) are accessible, I could at least implement a bubble sort if I can swap two nodes....

On 10/12/18 4:59 PM, Codifies wrote:
> On Friday, 12 October 2018 at 20:29:27 UTC, Steven Schveighoffer wrote:
>> On 10/12/18 3:40 PM, Codifies wrote:
>>> [...]
>>
>> Unfortunately, I can't find a way to sort a doubly linked list in phobos, so comparisons are somewhat moot.
>>
>> However, if there *were* a sorting routine, generally the comparison function is done via whatever type you give it, or is given a custom comparison routine.
>>
>> In my ancient dcollections library linked-list sorting is supported via a `less` parameter: https://github.com/schveiguy/dcollections/blob/82118cfd4faf3f1ad77df078d279f1b964f274e7/dcollections/LinkList.d#L997 
>>
>>
> 
> I think I'll look later and see if the links (in the dlist) are accessible, I could at least implement a bubble sort if I can swap two nodes....

I really should copy my mergesort implementation to Phobos. It's really simple, and there's no reason not to have sortable lists (both singly and doubly linked).

-Steve

On 2018-10-12 21:40, Codifies wrote:
> a while ago I wrote a doubly linked list (in C), which has a compare callback to allow custom sorting for example
> 
> int cmpNodes(cnode_t* n1, cnode_t* n2)
> {
>    mapNode_t* rn1 = (mapNode_t*)(n1->data);
>    mapNode_t* rn2 = (mapNode_t*)(n2->data);
>    if (rn1->G + rn1->H > rn2->G + rn2->H) return 1;
>    return 0;
> }
> 
> would be called by
> 
> clistSort(openList, cmpNodes);
> 
> The list would then be ordered by G + H fields (or any other algorithm you code)
> 
> 
> I notice there is a doubly linked list in the standard library, however it doesn't seem to allow for a custom compare, I'd rather not port my old C list code, can someone please give me some clues as to how I can reorder a list with a custom comparison...?

I don't think you can sort a list because sorting requires random access, which a list doesn't provide. Is there a reason you cannot use an array?

-- 
/Jacob Carlborg

On Saturday, 13 October 2018 at 07:48:04 UTC, Jacob Carlborg wrote:
> On 2018-10-12 21:40, Codifies wrote:
>> a while ago I wrote a doubly linked list (in C), which has a compare callback to allow custom sorting for example
>> 
>> int cmpNodes(cnode_t* n1, cnode_t* n2)
>> {
>>    mapNode_t* rn1 = (mapNode_t*)(n1->data);
>>    mapNode_t* rn2 = (mapNode_t*)(n2->data);
>>    if (rn1->G + rn1->H > rn2->G + rn2->H) return 1;
>>    return 0;
>> }
>> 
>> would be called by
>> 
>> clistSort(openList, cmpNodes);
>> 
>> The list would then be ordered by G + H fields (or any other algorithm you code)
>> 
>> 
>> I notice there is a doubly linked list in the standard library, however it doesn't seem to allow for a custom compare, I'd rather not port my old C list code, can someone please give me some clues as to how I can reorder a list with a custom comparison...?
>
> I don't think you can sort a list because sorting requires random access, which a list doesn't provide. Is there a reason you cannot use an array?

it to port my old C pathfinding code, at the start of the path you don't know how long it will be and it need to grow and shrink depending on the obstacles and different potential paths it finds, using a list is just easier, I've ended up porting my C doubly linked list that has its own simple bubble sort...

On 10/13/18 3:48 AM, Jacob Carlborg wrote:
> On 2018-10-12 21:40, Codifies wrote:
>> a while ago I wrote a doubly linked list (in C), which has a compare callback to allow custom sorting for example
>>
>> int cmpNodes(cnode_t* n1, cnode_t* n2)
>> {
>>    mapNode_t* rn1 = (mapNode_t*)(n1->data);
>>    mapNode_t* rn2 = (mapNode_t*)(n2->data);
>>    if (rn1->G + rn1->H > rn2->G + rn2->H) return 1;
>>    return 0;
>> }
>>
>> would be called by
>>
>> clistSort(openList, cmpNodes);
>>
>> The list would then be ordered by G + H fields (or any other algorithm you code)
>>
>>
>> I notice there is a doubly linked list in the standard library, however it doesn't seem to allow for a custom compare, I'd rather not port my old C list code, can someone please give me some clues as to how I can reorder a list with a custom comparison...?
> 
> I don't think you can sort a list because sorting requires random access, which a list doesn't provide. Is there a reason you cannot use an array?
> 

You can't quick-sort a list. You can merge sort it, and it's O(nlgn).

I'll work on getting a sort routine into Phobos for it, but I don't know what the appropriate location for it is, as a member or along-side std.algorithm.sort.

-Steve

On Saturday, October 13, 2018 6:52:05 PM MDT Steven Schveighoffer via Digitalmars-d-learn wrote:
> You can't quick-sort a list. You can merge sort it, and it's O(nlgn).
>
> I'll work on getting a sort routine into Phobos for it, but I don't know what the appropriate location for it is, as a member or along-side std.algorithm.sort.

Unless there's something about the implementation that's tied to the list itself, I would think that it would make more sense to make it a generic algorithm, then it will work with any non-random-access range, and it avoids needing to reimplement it for similar circumstances. IMHO, it really only makes sense to tie it to the container if the implementation itself needs to be for some reason.

- Jonathan M Davis

On Sunday, 14 October 2018 at 01:31:26 UTC, Jonathan M Davis wrote:
>
> Unless there's something about the implementation that's tied to the list itself, I would think that it would make more sense to make it a generic algorithm, then it will work with any non-random-access range, and it avoids needing to reimplement it for similar circumstances. IMHO, it really only makes sense to tie it to the container if the implementation itself needs to be for some reason.
>
> - Jonathan M Davis

I'm currently using this...

https://dpaste.dzfl.pl/09ea7fa8c58c

you can delete/insert from anywhere in the list, sort it, and even produce an array from it...

On Sunday, 14 October 2018 at 01:31:26 UTC, Jonathan M Davis wrote:
> Unless there's something about the implementation that's tied to the list itself, I would think that it would make more sense to make it a generic algorithm, then it will work with any non-random-access range, and it avoids needing to reimplement it for similar circumstances. IMHO, it really only makes sense to tie it to the container if the implementation itself needs to be for some reason.
>
> - Jonathan M Davis

All operations on collections are tied to implementation. Phobos just intorduced range abstraction that hides iteration code (and is still implemented by collection itself). Iteration is only a small part of functionality that one expects from the data structure. I'm against operation generalization, collections have little in common besides basic semantics of insertion, they should provide their own methods.

It is the lack of such methods that is more disheartening. And the lack of cursor\iterator concept, wich maps well to mutation semantics of lists\trees.