How should I sort a doubly linked list the D way?

[Johannes Loher]

Am 13.08.19 um 11:48 schrieb Mirjam Akkersdijk:
> 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?

I'd do something along the lines of this:

```
import std;

struct Node(T)
{
private:
    typeof(this)* prev, next;
public:
    T data;
}

struct DoublyLinkedList(T)
{
private:
    Node!T* head = null;
    Node!T* tail = null;

public:
    void pushFront(T t)
    {
        auto n = new Node!T;
        if (head != null)
        {
            head.prev = n;
        }
        else
        {
            tail = n;
        }
        n.data = t;
        n.next = head;
        head = n;
    }

    T front() const @property
    {
        return head.data;
    }

    void popFront()
    {
        head = head.next;
        if (head != null)
        {
            head.prev = null;
        }
        else
        {
            tail = null;
        }
    }

    void pushBack(T t)
    {
        auto n = new Node!T;
        if (tail != null)
        {
            tail.next = n;
        }
        else
        {
            head = n;
        }
        n.data = t;
        n.prev = tail;
        tail = n;
    }

    T back() const @property
    {
        return tail.data;
    }

    void popBack()
    {
        tail = tail.prev;
        if (tail != null)
        {
            tail.next = null;
        }
        else
        {
            head = null;
        }
    }

    size_t empty() const @property
    {
        return head == null;
    }

    auto nodes() @property
    {
        static struct NodePointerRange
        {
        private:
            Node!T* head;

        public:
            Node!T* front() @property
            {
                return head;
            }

            void popFront()
            {
                head = head.next;
            }

            bool empty() const @property
            {
                return head == null;
            }
        }

        return NodePointerRange(head);
    }
}

auto doublyLinkedList(R)(R r) if (isInputRange!R)
{
    DoublyLinkedList!(ElementType!R) list;

    foreach (e; r)
    {
        list.pushBack(e);
    }
    return list;
}

auto doublyLinkedListFromNodePointerRange(R)(R r)
        if (isInputRange!R && isPointer!(ElementType!R)
            && isInstanceOf!(Node, PointerTarget!(ElementType!R)))
{
    DoublyLinkedList!(TemplateArgsOf!(PointerTarget!(ElementType!R))) list;
    foreach (n; r)
    {
        n.prev = list.tail;
        if (list.tail != null)
        {
            list.tail.next = n;
        }
        else
        {
            list.head = n;
        }
        list.tail = n;
    }
    list.tail.next = null;
    return list;
}

void main()
{
    auto list = doublyLinkedList([5, 3, 7, 24, 1]);
    // looks natural but allocates new nodes
    auto sortedList = list.array.sort.doublyLinkedList;
    sortedList.each!writeln;

    writeln;

    auto anotherList = doublyLinkedList([54, 23, 8]);
    // looks a bit uglier but reuses the already allocated nodes
    auto anotherSortedList = anotherList.nodes
        .array
        .sort!((n1, n2) => n1.data < n2.data)
        .doublyLinkedListFromNodePointerRange;
    anotherSortedList.each!writeln;
}
```

Modulo bugs of course ;)

This uses the GC. If you want to avoid it in favor of malloc (or
std.experimental.allocator), you need to add `free`s (and possibly
referece counting) accordingly.