digitalmars.D.learn - custom sorting of lists ?
- Codifies (17/17) Oct 12 2018 a while ago I wrote a doubly linked list (in C), which has a
- Steven Schveighoffer (10/33) Oct 12 2018 Unfortunately, I can't find a way to sort a doubly linked list in
- Codifies (5/16) Oct 12 2018 I think I'll look later and see if the links (in the dlist) are
- Steven Schveighoffer (5/25) Oct 12 2018 I really should copy my mergesort implementation to Phobos. It's really
- Jacob Carlborg (6/29) Oct 13 2018 I don't think you can sort a list because sorting requires random
- Codifies (7/35) Oct 13 2018 it to port my old C pathfinding code, at the start of the path
- Steven Schveighoffer (6/35) Oct 13 2018 You can't quick-sort a list. You can merge sort it, and it's O(nlgn).
- Jonathan M Davis (9/13) Oct 13 2018 Unless there's something about the implementation that's tied to the lis...
- Codifies (6/14) Oct 14 2018 I'm currently using this...
- Boris-Barboris (12/20) Oct 14 2018 All operations on collections are tied to implementation. Phobos
- Steven Schveighoffer (15/29) Oct 15 2018 But that's just the thing -- merge sort *does* depend on the container
- Carl Sturtivant (4/13) Oct 17 2018 Doesn't this just mean a new special kind of range is needed to
- Steven Schveighoffer (7/22) Oct 17 2018 I don't think it fits into range primitives. Basically, I need to
- Carl Sturtivant (14/39) Oct 19 2018 If we imagine an Ordered Range being a finite Range of some kind
- Stanislav Blinov (3/6) Oct 19 2018 There's already a SortedRange:
- Carl Sturtivant (4/11) Oct 19 2018 That's nice. So perhaps all this can be done in using the
- Steven Schveighoffer (7/20) Oct 22 2018 Again, the benefit of linked lists here is we don't have to actually
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...?
Oct 12 2018
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
Oct 12 2018
On Friday, 12 October 2018 at 20:29:27 UTC, Steven Schveighoffer wrote:On 10/12/18 3:40 PM, Codifies wrote: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....[...]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
Oct 12 2018
Steven Schveighoffer <schveiguy gmail.com> On 10/12/18 4:59 PM, Codifies wrote:On Friday, 12 October 2018 at 20:29:27 UTC, Steven Schveighoffer wrote: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). -SteveOn 10/12/18 3:40 PM, Codifies wrote: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....[...]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/dcollect ons/LinkList.d#L997
Oct 12 2018
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
Oct 13 2018
On Saturday, 13 October 2018 at 07:48:04 UTC, Jacob Carlborg wrote:On 2018-10-12 21:40, Codifies wrote: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...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?
Oct 13 2018
On 10/13/18 3:48 AM, Jacob Carlborg wrote:On 2018-10-12 21:40, Codifies 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. -Stevea 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?
Oct 13 2018
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
Oct 13 2018
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 DavisI'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...
Oct 14 2018
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 DavisAll 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.
Oct 14 2018
On 10/13/18 9:31 PM, Jonathan M Davis wrote:On Saturday, October 13, 2018 6:52:05 PM MDT Steven Schveighoffer via Digitalmars-d-learn wrote:But that's just the thing -- merge sort *does* depend on the container type. It requires the ability to rearrange the elements structurally, since you merge the sets of items together. This requires making another list from the original list, and ranges don't lend themselves to that. One thing you *can* do is allocate an array beside the original container, and move things back and forth. But this is not required if you have a linked-list type which can simply be restructured without moving. What I would do if I put it in std.algorithm is simply have an overload for that specific type. Even that is kind of odd. What I probably will do is make it a member of dlist and slist. At least there it is limited to those items. I don't think dlist and slist have the appropriate structural primitives to rearrange the list without copying values around. -SteveYou 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.
Oct 15 2018
On Monday, 15 October 2018 at 13:39:59 UTC, Steven Schveighoffer wrote:But that's just the thing -- merge sort *does* depend on the container type. It requires the ability to rearrange the elements structurally, since you merge the sets of items together. This requires making another list from the original list, and ranges don't lend themselves to that. One thing you *can* do is allocate an array beside the original container, and move things back and forth. But this is not required if you have a linked-list type which can simply be restructured without moving.Doesn't this just mean a new special kind of range is needed to be defined?
Oct 17 2018
On 10/17/18 2:03 PM, Carl Sturtivant wrote:On Monday, 15 October 2018 at 13:39:59 UTC, Steven Schveighoffer wrote:I don't think it fits into range primitives. Basically, I need to rearrange one element from one place to another in O(1) time (and without actually moving/copying the data). This really just is a linked-list special feature. One thing to note is that in a range of T, this move has nothing to do with the T. -SteveBut that's just the thing -- merge sort *does* depend on the container type. It requires the ability to rearrange the elements structurally, since you merge the sets of items together. This requires making another list from the original list, and ranges don't lend themselves to that. One thing you *can* do is allocate an array beside the original container, and move things back and forth. But this is not required if you have a linked-list type which can simply be restructured without moving.Doesn't this just mean a new special kind of range is needed to be defined?
Oct 17 2018
On Wednesday, 17 October 2018 at 19:02:00 UTC, Steven Schveighoffer wrote:On 10/17/18 2:03 PM, Carl Sturtivant wrote:If we imagine an Ordered Range being a finite Range of some kind with the additional property that its values are ordered (--- exact definition needed ---). And work with Ranges of Ordered Ranges, can't we then sort by starting with a Range of single element Ranges (which are automatically ordered), and then pairwise merge repeatedly, i.e. get the next two elements (which are ordered ranges) and merge them & repeat, producing a Range of Ordered Ranges with half as many elements --- this is what I meant by pairwise merging --- and apply that pairwise merge repeatedly to the original range. I'm speculating intuitively, but it does look like there exists a possible extension of the notion of Range that would do the job.On Monday, 15 October 2018 at 13:39:59 UTC, Steven Schveighoffer wrote:I don't think it fits into range primitives. Basically, I need to rearrange one element from one place to another in O(1) time (and without actually moving/copying the data). This really just is a linked-list special feature. One thing to note is that in a range of T, this move has nothing to do with the T. -SteveBut that's just the thing -- merge sort *does* depend on the container type. It requires the ability to rearrange the elements structurally, since you merge the sets of items together. This requires making another list from the original list, and ranges don't lend themselves to that. One thing you *can* do is allocate an array beside the original container, and move things back and forth. But this is not required if you have a linked-list type which can simply be restructured without moving.Doesn't this just mean a new special kind of range is needed to be defined?
Oct 19 2018
On Friday, 19 October 2018 at 17:40:59 UTC, Carl Sturtivant wrote:If we imagine an Ordered Range being a finite Range of some kind with the additional property that its values are ordered (--- exact definition needed ---)...There's already a SortedRange: https://dlang.org/phobos/std_range.html#.SortedRange
Oct 19 2018
On Friday, 19 October 2018 at 17:53:58 UTC, Stanislav Blinov wrote:On Friday, 19 October 2018 at 17:40:59 UTC, Carl Sturtivant wrote:That's nice. So perhaps all this can be done in using the existing machinery in Phobos.If we imagine an Ordered Range being a finite Range of some kind with the additional property that its values are ordered (--- exact definition needed ---)...There's already a SortedRange: https://dlang.org/phobos/std_range.html#.SortedRange
Oct 19 2018
On 10/19/18 3:58 PM, Carl Sturtivant wrote:On Friday, 19 October 2018 at 17:53:58 UTC, Stanislav Blinov wrote:Again, the benefit of linked lists here is we don't have to actually move any data, we are just rearranging pointers. We can certainly create a mergesort routine that works with any data types, as long as it has scratch space to move the data around. But that isn't as effective or efficient as a dedicated linked-list routine. -SteveOn Friday, 19 October 2018 at 17:40:59 UTC, Carl Sturtivant wrote:That's nice. So perhaps all this can be done in using the existing machinery in Phobos.If we imagine an Ordered Range being a finite Range of some kind with the additional property that its values are ordered (--- exact definition needed ---)...There's already a SortedRange: https://dlang.org/phobos/std_range.html#.SortedRange
Oct 22 2018