www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Sort bug / strangeness

reply Danny Arends <Danny.Arends gmail.com> writes:
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\algorit
m\mutation.d(2816): Swap: rhs points to lhs.
----------------
0x000000014008A2E3 in d_assert_msg
0x0000000140056F35 in 
std.algorithm.mutation.swap!(searchnode.Node).swap at 
C:\D\dmd2\windows\bin\..\..\src\phobos\std\algorithm\mutation.d(2816)
0x0000000140057A07 in 
std.algorithm.mutation.swapAt!(searchnode.Node[]).swapAt at 
C:\D\dmd2\windows\bin\..\..\src\phobos\std\algorithm\mutation.d(3090)
0x00000001400582BE 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)
0x0000000140057DF4 in std.algorithm.sorting.getPivot!(binaryFun, 
searchnode.Node[]).getPivot at 
C:\D\dmd2\windows\bin\..\..\src\phobos\std\algorithm\sorting.d(1620)
0x0000000140057112 in 
std.algorithm.sorting.quickSortImpl!(binaryFun, 
searchnode.Node[]).quickSortImpl at 
C:\D\dmd2\windows\bin\..\..\src\phobos\std\algorithm\sorting.d(2124)
0x0000000140056FB5 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)
0x0000000140050C1F in search.step!(search.Search!(Map, Node), 
searchnode.Node).step at C:\Github\CalderaD\src\math\search.d(119)
0x000000014005012E in search.performSearch!(map.Map, 
searchnode.Node).performSearch at 
C:\Github\CalderaD\src\math\searchnode.d(11)
0x000000014004723B in map.testGenMap at 
C:\Github\CalderaD\src\game\map.d(125)
0x000000014004CD9E in main.run at 
C:\Github\CalderaD\src\main.d(32)
0x000000014004CD3E in D main at C:\Github\CalderaD\src\main.d(25)
```
Oct 01 2021
parent reply Steven Schveighoffer <schveiguy gmail.com> writes:
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
Oct 01 2021
parent reply Danny Arends <Danny.Arends gmail.com> writes:
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
Oct 01 2021
parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Fri, Oct 01, 2021 at 06:30:48PM +0000, 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.
Oct 01 2021