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.