On 12/16/2010 10:53 AM, Andrei Alexandrescu wrote: > On 12/16/10 7:55 AM, Matthias Walter wrote: >> On 12/16/2010 04:17 AM, Andrei Alexandrescu wrote: >>> On 12/15/10 10:21 PM, Matthias Walter wrote: >>>> Hi all, >>>> >>>> I uploaded [1] a patch for std.container to use BinaryHeap as a >>>> priority >>>> queue. For the latter one it is often necessary to change a value >>>> (often >>>> called decreaseKey in a MinHeap). For example, Dijkstra's shortest >>>> path >>>> algorithm would need such a method. My implementation expects that the >>>> user calls the "update" method after changing the entry in the >>>> underlying store. >>>> >>>> My method works for value-decrease and -increase, but one might >>>> want to >>>> split this functionality into two methods for efficiency reasons. >>>> But I >>>> thought it'll be better, because one can change the MaxHeap to be a >>>> MaxHeap by changing the template alias parameter, but this wouldn't >>>> change the method names :-) >>>> >>>> The patch is against current svn trunk. >>>> >>>> [1] >>>> http://xammy.xammy.homelinux.net/files/BinaryHeap-PriorityQueue.patch >>> >>> A better primitive is to define update to take an index and a new >>> value, such that user code does not need to deal simultaneously with >>> the underlying array and the heap. No? >> Well, I thought of the case where you have an array of structs and use a >> custom less function for ordering. There you might not have a new value, >> i.e. a replaced struct, but just a minor change internally. But I see >> your idea, in most cases you would just call update after replacing your >> array entry... Could we provide both, maybe? > > Good point. Here's what I suggest: > > /** > Applies unary function fun to the element at position index, after > which moves that element to preserve the heap property. (It is assumed > that fun changes the element.) Returns the new position of the element > in the heap. > > Example: > > ---- > int[] a = [ 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 ]; > auto h = heapify(a); > assert(equal(a, [ 16, 14, 10, 9, 8, 7, 4, 3, 2, 1 ])); > h.update!"a -= 5"(1); > assert(equal(a, [ 16, 10, 9, 9, 8, 7, 4, 3, 2, 1 ])); > ---- > */ > size_t update(alias fun)(size_t index); > > Let me know of what you think, and thanks for contributing. When using > unaryFun inside update, don't forget to pass true as the second > argument to unaryFun to make sure you enact pass by reference. Good idea. I like the interface!
Btw, can I then call a routine in the string, too? Like h.update!"a.updatePriority()"(1); Although this does look ugly, so separating the call would probably make more sense. Matthias
