www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Using std.container.BinaryHeap like C++

reply Paulo Pinto <pjmlp progtools.org> writes:
Hi,

I was wondering if it is possible to use the BinaryHeap store like
the C++'s make_heap/pop_heap/push_heap functions.

I would like to port to D some A* C++ code I have which rearranges the 
priorities on the underlying store, followed by another
make_heap() call on the vector used as store.

Doing the same in D by calling again heapify() does not seem to provide 
similar behavior.

Just curious about it, as I don't plan to invest too much time on it.

Thanks,
Paulo
Aug 17 2014
parent reply "monarch_dodra" <monarchdodra gmail.com> writes:
On Sunday, 17 August 2014 at 18:54:27 UTC, Paulo Pinto wrote:

 Hi,

 I was wondering if it is possible to use the BinaryHeap store 
 like
 the C++'s make_heap/pop_heap/push_heap functions.

 I would like to port to D some A* C++ code I have which 
 rearranges the priorities on the underlying store, followed by 
 another
 make_heap() call on the vector used as store.

 Doing the same in D by calling again heapify() does not seem to 
 provide similar behavior.

 Just curious about it, as I don't plan to invest too much time 
 on it.

 Thanks,
 Paulo


AFAIK, D's BinaryHeap works just like C++'s 
make_heap/pop_heap/push_heap, except that it provides an actual 
object you can interface with, which has font, removeFront, 
removeAny and insert.

What exactly is the difference in behavior you are seeing? Just 
different results that can be attributed to implementation 
details, or fundamental differences?
Aug 17 2014
parent reply "Paulo Pinto" <pjmlp progtools.org> writes:
On Sunday, 17 August 2014 at 21:09:04 UTC, monarch_dodra wrote:

 On Sunday, 17 August 2014 at 18:54:27 UTC, Paulo Pinto wrote:

 Hi,

 I was wondering if it is possible to use the BinaryHeap store 
 like
 the C++'s make_heap/pop_heap/push_heap functions.

 I would like to port to D some A* C++ code I have which 
 rearranges the priorities on the underlying store, followed by 
 another
 make_heap() call on the vector used as store.

 Doing the same in D by calling again heapify() does not seem 
 to provide similar behavior.

 Just curious about it, as I don't plan to invest too much time 
 on it.

 Thanks,
 Paulo


 AFAIK, D's BinaryHeap works just like C++'s 
 make_heap/pop_heap/push_heap, except that it provides an actual 
 object you can interface with, which has font, removeFront, 
 removeAny and insert.

 What exactly is the difference in behavior you are seeing? Just 
 different results that can be attributed to implementation 
 details, or fundamental differences?


It doesn't seem to like I change the store contents directly 
under its feet
and recalling heapify again on the same store, like I am doing in 
C++'s heap.

Sometimes I get a different sequence of data or just a crash.

I still need to make the D code reflect my latest C++ changes, as 
the C++ code is what really matters in this hobby project, there 
is where my focus has been lately.

The D version is more of a "playing around" thing.

As I said, I curious what the behavior is supposed to be.

Thanks,
Paulo
Aug 17 2014
parent reply "monarch_dodra" <monarchdodra gmail.com> writes:
On Monday, 18 August 2014 at 06:50:08 UTC, Paulo Pinto wrote:

 On Sunday, 17 August 2014 at 21:09:04 UTC, monarch_dodra wrote:

 On Sunday, 17 August 2014 at 18:54:27 UTC, Paulo Pinto wrote:

 Hi,

 I was wondering if it is possible to use the BinaryHeap store 
 like
 the C++'s make_heap/pop_heap/push_heap functions.

 I would like to port to D some A* C++ code I have which 
 rearranges the priorities on the underlying store, followed 
 by another
 make_heap() call on the vector used as store.

 Doing the same in D by calling again heapify() does not seem 
 to provide similar behavior.

 Just curious about it, as I don't plan to invest too much 
 time on it.

 Thanks,
 Paulo


 AFAIK, D's BinaryHeap works just like C++'s 
 make_heap/pop_heap/push_heap, except that it provides an 
 actual object you can interface with, which has font, 
 removeFront, removeAny and insert.

 What exactly is the difference in behavior you are seeing? 
 Just different results that can be attributed to 
 implementation details, or fundamental differences?


 It doesn't seem to like I change the store contents directly 
 under its feet
 and recalling heapify again on the same store, like I am doing 
 in C++'s heap.

 Sometimes I get a different sequence of data or just a crash.

 I still need to make the D code reflect my latest C++ changes, 
 as the C++ code is what really matters in this hobby project, 
 there is where my focus has been lately.

 The D version is more of a "playing around" thing.

 As I said, I curious what the behavior is supposed to be.

 Thanks,
 Paulo


Weird. The behavior should be the same as C++'s. As I said, the 
difference is that D gives you a "handle" object. This object 
assumes you *don't* modify it's store under the hood, but as long 
as you don't use the heap after a store modification, you should 
be fine. Do you have a minimal test case?
Aug 18 2014
parent Paulo Pinto <pjmlp progtools.org> writes:
Am 18.08.2014 14:49, schrieb monarch_dodra:

 On Monday, 18 August 2014 at 06:50:08 UTC, Paulo Pinto wrote:

 On Sunday, 17 August 2014 at 21:09:04 UTC, monarch_dodra wrote:

 On Sunday, 17 August 2014 at 18:54:27 UTC, Paulo Pinto wrote:

 Hi,

 I was wondering if it is possible to use the BinaryHeap store like
 the C++'s make_heap/pop_heap/push_heap functions.

 I would like to port to D some A* C++ code I have which rearranges
 the priorities on the underlying store, followed by another
 make_heap() call on the vector used as store.

 Doing the same in D by calling again heapify() does not seem to
 provide similar behavior.

 Just curious about it, as I don't plan to invest too much time on it.

 Thanks,
 Paulo


 AFAIK, D's BinaryHeap works just like C++'s
 make_heap/pop_heap/push_heap, except that it provides an actual
 object you can interface with, which has font, removeFront, removeAny
 and insert.

 What exactly is the difference in behavior you are seeing? Just
 different results that can be attributed to implementation details,
 or fundamental differences?


 It doesn't seem to like I change the store contents directly under its
 feet
 and recalling heapify again on the same store, like I am doing in
 C++'s heap.

 Sometimes I get a different sequence of data or just a crash.

 I still need to make the D code reflect my latest C++ changes, as the
 C++ code is what really matters in this hobby project, there is where
 my focus has been lately.

 The D version is more of a "playing around" thing.

 As I said, I curious what the behavior is supposed to be.

 Thanks,
 Paulo


 Weird. The behavior should be the same as C++'s. As I said, the
 difference is that D gives you a "handle" object. This object assumes
 you *don't* modify it's store under the hood, but as long as you don't
 use the heap after a store modification, you should be fine. Do you have
 a minimal test case?


Actually, that is exactly what I am doing. :)

The store contains the open list of nodes to visit, and when new paths 
are found, I re-parent the nodes which leads to a different cost, thus
I re-generate the heap.

The D code is still not up to date with what I am doing on C++ and the 
code I had before lost it somehow while jumping around computers. But 
both projects are on Github.

C++
https://github.com/pjmlp/AStarDemoCpp/blob/master/AStarDemo/AStarSolver.cpp

D
https://github.com/pjmlp/AStarDemoD/blob/master/src/solver.d


--
Paulo
Aug 18 2014