Hello there,
If I had a DLL, how would I sort it judging by the node contents, the D way?

In C if I were to sort a piece of malloc'd memory pointing to node pointers, I would write my compare function and let qsort sort it out. In D, I tried to use std.algorithm's sort functionality to no avail, because my guess would be it only operates on arrays. This opens up another can of worms as I am not fond of VLAs and D desperately wants to know what the size is at compile time.

Let's say we this trivial implementation:

Node* get_node(DLL* list, uint index);

struct Node {
  int x;
  Node* prev, next;
};

struct DLL {
  Node* head;
  uint size;
};

Node** nodes = cast(Node**) malloc(DLL.size * (Node*).sizeof);

and I would like to sort based on Node.t, how should I tackle it, preferably without resorting to C libraries?

On Tuesday, 13 August 2019 at 09:48:52 UTC, Mirjam Akkersdijk wrote:
> Hello there,
> If I had a DLL, how would I sort it judging by the node contents, the D way?
>
> [...]

>Node.t

Node.x, my bad

You can make an array from it

On Tue, Aug 13, 2019 at 12:05 PM Mirjam Akkersdijk via Digitalmars-d-learn <digitalmars-d-learn@puremagic.com> wrote:
>
> On Tuesday, 13 August 2019 at 09:48:52 UTC, Mirjam Akkersdijk wrote:
> > Hello there,
> > If I had a DLL, how would I sort it judging by the node
> > contents, the D way?
> >
> > [...]
>
> >Node.t
>
> Node.x, my bad

On Tuesday, August 13, 2019 3:48:52 AM MDT Mirjam Akkersdijk via Digitalmars-d-learn wrote:
> Hello there,
> If I had a DLL, how would I sort it judging by the node contents,
> the D way?
>
> In C if I were to sort a piece of malloc'd memory pointing to node pointers, I would write my compare function and let qsort sort it out. In D, I tried to use std.algorithm's sort functionality to no avail, because my guess would be it only operates on arrays. This opens up another can of worms as I am not fond of VLAs and D desperately wants to know what the size is at compile time.
>
> Let's say we this trivial implementation:
>
> Node* get_node(DLL* list, uint index);
>
> struct Node {
>    int x;
>    Node* prev, next;
> };
>
> struct DLL {
>    Node* head;
>    uint size;
> };
>
> Node** nodes = cast(Node**) malloc(DLL.size * (Node*).sizeof);
>
> and I would like to sort based on Node.t, how should I tackle it, preferably without resorting to C libraries?

std.algorithm.sort operates on random-access ranges, not just dynamic arrays, and there's no need to know the size at compile time. I don't know why you would think that arrays would need to know their size at compile time unless you've only been using static arrays. However, a doubly-linked list definitely isn't random access, so it wouldn't work with std.algorithm.sort, and I don't think that Phobos has anything which would be able to sort it. There might be a solution somewhere on code.dlang.org, but I don't know of any that I could point you to. Either way, if there's a solution floating around that you can use to sort a doubly-linked list in place, it's not an official one.

- Jonathan M Davis

On Tuesday, 13 August 2019 at 09:48:52 UTC, Mirjam Akkersdijk wrote:
> Hello there,
> If I had a DLL, how would I sort it judging by the node contents, the D way?
>
> In C if I were to sort a piece of malloc'd memory pointing to node pointers, I would write my compare function and let qsort sort it out. In D, I tried to use std.algorithm's sort functionality to no avail, because my guess would be it only operates on arrays. This opens up another can of worms as I am not fond of VLAs and D desperately wants to know what the size is at compile time.

You can check std.container.rbtree which will build sorted "list" for you on every Node insert. Again, not sure how this can be done at compile time.

On Tuesday, 13 August 2019 at 09:48:52 UTC, Mirjam Akkersdijk wrote:

> I would write my compare function and let qsort sort it out.

I'm confused by this statement. Are you referring to the qsort in C's stdlib? I had never heard of using that to sort a linked list, so I searched, and it is not possible.

https://cboard.cprogramming.com/c-programming/64520-sorting-linked-list-qsort.html
https://stackoverflow.com/questions/7091685/doesnt-qsort-c-library-function-work-on-linked-lists: "qsort works on plain arrays of equally sized data, not linked lists"

On Tuesday, 13 August 2019 at 09:48:52 UTC, Mirjam Akkersdijk wrote:
> and I would like to sort based on Node.t, how should I tackle it, preferably without resorting to C libraries?

Convert the nodes into an D array, sort the array with nodes.sort!"a.x < b.x" and then iterate the array and repair the next/prev pointers.

On Tuesday, 13 August 2019 at 12:34:46 UTC, bachmeier wrote:
> I'm confused by this statement. Are you referring to the qsort in C's stdlib? I had never heard of using that to sort a linked list, so I searched, and it is not possible.

Ah yes, maybe I should have elaborated. In C, you can just create an array

(1) struct Node* nodes[buf_size];

and then loop over it, filling it with

(2) nodes[i] = (DLLbuf + i * sizeof(struct Node));

subsequently calling our dear friend from stdlib

(3) qsort(nodes, buf_size, sizeof(struct Node*), buf_compare_function);

You can then rechain all nodes together but that's a bit out of scope for this thread unless you do really want me to work it out :)

But I was looking for a more D-specific approach to solve this, as it feels archaic to do it the C way. If there is anyone with a better one please let me know.

On Tuesday, 13 August 2019 at 14:04:45 UTC, Sebastiaan Koppe wrote:
> On Tuesday, 13 August 2019 at 09:48:52 UTC, Mirjam Akkersdijk wrote:
>> and I would like to sort based on Node.t, how should I tackle it, preferably without resorting to C libraries?
>
> Convert the nodes into an D array, sort the array with nodes.sort!"a.x < b.x" and then iterate the array and repair the next/prev pointers.

Thank you, this is what I eventually chose to do. It's also fairly fast, though doesn't the nature of the dynamic array slow it down a bit? Since I already know the size of the array (but just not at compile time), can't I define an array of fixed size, which is dependent on the input of the function?

On Tuesday, August 13, 2019 11:33:10 AM MDT Mirjam Akkersdijk via Digitalmars-d-learn wrote:
> On Tuesday, 13 August 2019 at 14:04:45 UTC, Sebastiaan Koppe
>
> wrote:
> > On Tuesday, 13 August 2019 at 09:48:52 UTC, Mirjam Akkersdijk
> >
> > wrote:
> >> and I would like to sort based on Node.t, how should I tackle it, preferably without resorting to C libraries?
> >
> > Convert the nodes into an D array, sort the array with nodes.sort!"a.x < b.x" and then iterate the array and repair the next/prev pointers.
>
> Thank you, this is what I eventually chose to do. It's also fairly fast, though doesn't the nature of the dynamic array slow it down a bit? Since I already know the size of the array (but just not at compile time), can't I define an array of fixed size, which is dependent on the input of the function?

In D, static arrays must know their length at compile time. Dynamic arrays can have their length determined at runtime. I don't know why a dynamic array would slow anything down here though - especially if you just allocate it with the correct length. Appending each element individually instead of allocating the full dynamic array and then setting each element would certainly be slower, but once the dynamic array is fully allocated, as far as accessing elements go, accessing a dynamic array and static array should be basically the same. The only real difference is that one would have its elements on the stack, whereas the other would have them on the heap. Even if you used a static array, you'd have to slice it to pass to sort, which would mean that you'd be passing it a dynamic array. A dynamic array is basically just a struct with a pointer and a length. e.g.

struct DynamicArray(T)
{
    size_t length;
    T* ptr;
}

and accessing its elements is the same as you'd get with a pointer in C except for the fact that in @safe code, the bounds are checked when indexing elements. The only thing about dynamic arrays that can get slow is if you're doing a lot of appending to them, because then it has to keep checking to see whether it can expand in place or has to allocate a new block of memory and copy the elements. In that respect, it's similar to C++'s std::vector.

- Jonathan M Davis