Re: Sort bug / strangeness

[H. S. Teoh via Digitalmars-d-learn]

On Fri, Oct 01, 2021 at 06:30:48PM +, Danny Arends via Digitalmars-d-learn 
wrote:
[...]
> Is there a sort() algorithm that avoids swapping the items themselves
> and e.g. just returns the indexes so I can reorder the original array
> myself ?

https://dlang.org/phobos/std_algorithm_sorting.html#.makeIndex


T

-- 
Caffeine underflow. Brain dumped.

Re: Sort bug / strangeness

[Danny Arends via Digitalmars-d-learn]

On Friday, 1 October 2021 at 17:53:24 UTC, Steven Schveighoffer 
wrote:
I think your struct is different than this, because this only 
happens if aliasing is inside the struct being sorted (i.e. it 
has pointers). Your presented struct doesn't have pointers, and 
the code you linked to is completely parameterized on the 
struct type.


If it does have pointers, you are not allowed to swap the 
values if either points to each other (or themselves).


Thanks Steve for saving Friday,

The struct has indeed a parent pointer, It's a pretty big struct 
so just posted the excerpt (sorry). So that's the cause then.


So how to sort this N[] object by f() then ?

The pointer is only used to be traversed back after the search 
has finished. Is there a sort() algorithm that avoids swapping 
the items themselves and e.g. just returns the indexes so I can 
reorder the original array myself ?


Danny

Re: Sort bug / strangeness

[Steven Schveighoffer via Digitalmars-d-learn]

On 10/1/21 12:44 PM, Danny Arends wrote:

Hey all,

Using a modified 3D A* tile searching algorithm, full code see:

https://github.com/DannyArends/CalderaD/blob/master/src/math/search.d

I get the following AssertError, 'sometimes' but not always on running 
the code:


mutation.d(2816): Swap: rhs points to lhs.

the first time I hit Phobos is because I call the 
std.algorithm.sorting.sort function to sort my open list (just an array 
of search node objects);


```
search.openlist.sort!("a.f < b.f")();
```

sneakily f here is a @property function of the object, which just 
computes and returns a float:


```
// sum of cumulative cost of this node + predecessors + heuristic
struct Node {
   float g; // cost of this node + it's predecessors
   float h; // heuristic estimate of distance to goal
   @nogc @property float f() nothrow const { return(this.g + this.h); }
}
```


I think your struct is different than this, because this only happens if 
aliasing is inside the struct being sorted (i.e. it has pointers). Your 
presented struct doesn't have pointers, and the code you linked to is 
completely parameterized on the struct type.


If it does have pointers, you are not allowed to swap the values if 
either points to each other (or themselves).


-Steve

Sort bug / strangeness

[Danny Arends via Digitalmars-d-learn]

Hey all,

Using a modified 3D A* tile searching algorithm, full code see:

https://github.com/DannyArends/CalderaD/blob/master/src/math/search.d

I get the following AssertError, 'sometimes' but not always on 
running the code:


mutation.d(2816): Swap: rhs points to lhs.

the first time I hit Phobos is because I call the 
std.algorithm.sorting.sort function to sort my open list (just an 
array of search node objects);


```
search.openlist.sort!("a.f < b.f")();
```

sneakily f here is a @property function of the object, which just 
computes and returns a float:


```
// sum of cumulative cost of this node + predecessors + heuristic
struct Node {
  float g; // cost of this node + it's predecessors
  float h; // heuristic estimate of distance to goal
  @nogc @property float f() nothrow const { return(this.g + 
this.h); }

}
```

For the life of me I cannot fathom, how 2 function calls would 
end up pointing to the same memory location ?


To mention (might be relevant or not, I'm lost badly), the search 
struct around the map is parameterized. because I want to give 
objects the ability to have their own map walker definition (eg. 
ground, ground+air, ground+shallow water ). I am using the 
following wrapper struct:


```
struct Search(M, N) {
  N[] openlist; // Astar open list
  N[] closedlist; // Astar closed list
}
```

Anyone got some idea what I'm doing wrong, or explain me why I am 
messing up my Dijkstra here ?


Thanks,

Danny

Full stack trace/ dump below:

```
core.exception.AssertError@C:\D\dmd2\windows\bin\..\..\src\phobos\std\algorithm\mutation.d(2816):
 Swap: rhs points to lhs.

0x00014008A2E3 in d_assert_msg
0x000140056F35 in 
std.algorithm.mutation.swap!(searchnode.Node).swap at 
C:\D\dmd2\windows\bin\..\..\src\phobos\std\algorithm\mutation.d(2816)
0x000140057A07 in 
std.algorithm.mutation.swapAt!(searchnode.Node[]).swapAt at 
C:\D\dmd2\windows\bin\..\..\src\phobos\std\algorithm\mutation.d(3090)
0x0001400582BE in std.algorithm.sorting.medianOf!(binaryFun, 
Flag.no, searchnode.Node[], ulong, ulong, ulong).medianOf at 
C:\D\dmd2\windows\bin\..\..\src\phobos\std\algorithm\sorting.d(4237)
0x000140057DF4 in std.algorithm.sorting.getPivot!(binaryFun, 
searchnode.Node[]).getPivot at 
C:\D\dmd2\windows\bin\..\..\src\phobos\std\algorithm\sorting.d(1620)
0x000140057112 in 
std.algorithm.sorting.quickSortImpl!(binaryFun, 
searchnode.Node[]).quickSortImpl at 
C:\D\dmd2\windows\bin\..\..\src\phobos\std\algorithm\sorting.d(2124)
0x000140056FB5 in std.algorithm.sorting.sort!("a.f < b.f", 
SwapStrategy.unstable, searchnode.Node[]).sort at 
C:\D\dmd2\windows\bin\..\..\src\phobos\std\algorithm\sorting.d(1905)
0x000140050C1F in search.step!(search.Search!(Map, Node), 
searchnode.Node).step at C:\Github\CalderaD\src\math\search.d(119)
0x00014005012E in search.performSearch!(map.Map, 
searchnode.Node).performSearch at 
C:\Github\CalderaD\src\math\searchnode.d(11)
0x00014004723B in map.testGenMap at 
C:\Github\CalderaD\src\game\map.d(125)
0x00014004CD9E in main.run at 
C:\Github\CalderaD\src\main.d(32)

0x00014004CD3E in D main at C:\Github\CalderaD\src\main.d(25)
```