[review] Heaps: mutability
Tim, I'm trying to figure out how I can use a mutable queue to write something like Dijkstra's SP. Here's a skeleton with the relevant parts. Queue<Vertex*, Comp> q; Map<Vertex*, Queue::handle_type> h; h[start] = q.push(start); v->distance += x; q.update(h[v]); Comp is an indirect comparison of vertex distances (u->distance < v->distance). Does the mutable heap support this application (i.e., where I'm not directly updating the value type)? It's not clear from the examples supplied with the program. I suspect that it is, but it's not clear. Andrew
I'm trying to figure out how I can use a mutable queue to write something like Dijkstra's SP. Here's a skeleton with the relevant parts.
Queue<Vertex*, Comp> q; Map<Vertex*, Queue::handle_type> h; h[start] = q.push(start);
v->distance += x; q.update(h[v]);
Comp is an indirect comparison of vertex distances (u->distance < v->distance).
Does the mutable heap support this application (i.e., where I'm not directly updating the value type)? It's not clear from the examples supplied with the program. I suspect that it is, but it's not clear.
b.h supports two ways of updating nodes: 1: update(handle_type, value_type); 2: update(handle_type); the second version assumes that you change the priority manually, while the `update' call just fixes the heap. this is described in the `mutability' section, but i should probably improve the documentation. please note, that you *have* to call update before modifying any other node ... cheers, tim
AMDG On 06/03/2011 09:33 AM, Tim Blechmann wrote:
b.h supports two ways of updating nodes:
1: update(handle_type, value_type); 2: update(handle_type);
the second version assumes that you change the priority manually, while the `update' call just fixes the heap.
this is described in the `mutability' section, but i should probably improve the documentation. please note, that you *have* to call update before modifying any other node ...
Have you considered taking a page from MultiIndex? bool replace(iterator position, const value_type& x); bool modify(iterator position, Modifier mod); Requires: Modifier is a model of Unary Function... In Christ, Steven Watanabe
b.h supports two ways of updating nodes:
1: update(handle_type, value_type); 2: update(handle_type);
the second version assumes that you change the priority manually, while the `update' call just fixes the heap.
this is described in the `mutability' section, but i should probably improve the documentation. please note, that you *have* to call update before modifying any other node ...
Have you considered taking a page from MultiIndex?
bool modify(iterator position, Modifier mod);
i have been thinking about provinding an interface with a modifier function, but to me it seems to increase the complexety of the interface ... but with c++0x lambdas it may become more useful ... other thoughts about this idea? tim -- tim@klingt.org http://tim.klingt.org /"\ ASCII Ribbon Campaign \ / no HTML in email & vCards X no proprietary attachments / \ use open standards
i have been thinking about provinding an interface with a modifier function, but to me it seems to increase the complexety of the interface ... but with c++0x lambdas it may become more useful ... other thoughts about this idea?
I think you mean "usable" instead of "useful" :) It should be sufficient to document the protocol (modify then update). Andrew
participants (3)
-
Andrew Sutton -
Steven Watanabe -
Tim Blechmann