digitalmars.D.bugs - [Issue 4271] New: drop/pop methods for std.algorithm.BinaryHeap
- d-bugmail puremagic.com (53/53) Jun 04 2010 http://d.puremagic.com/issues/show_bug.cgi?id=4271
- d-bugmail puremagic.com (10/10) Jun 04 2010 http://d.puremagic.com/issues/show_bug.cgi?id=4271
- d-bugmail puremagic.com (18/18) Jun 04 2010 http://d.puremagic.com/issues/show_bug.cgi?id=4271
- d-bugmail puremagic.com (10/10) Jun 04 2010 http://d.puremagic.com/issues/show_bug.cgi?id=4271
- d-bugmail puremagic.com (9/9) Jan 09 2011 http://d.puremagic.com/issues/show_bug.cgi?id=4271
http://d.puremagic.com/issues/show_bug.cgi?id=4271 Summary: drop/pop methods for std.algorithm.BinaryHeap Product: D Version: future Platform: x86 OS/Version: Windows Status: NEW Severity: enhancement Priority: P2 Component: Phobos AssignedTo: nobody puremagic.com ReportedBy: bearophile_hugs eml.cc During the usage of a Heap one of the most commonly used operations is to pop an item from a heap and then to use it. But in std.algorithm.BinaryHeap the pop() doesn't return the item, probably for performance reasons (it requires the copy of the item). (So to pop an use one item you can use pop(1)[0] or take the top and then pop, but the second possibility is not an expression.) There are some ways to solve this problem, but the simpler is probably to just use two different names for two functions. So the pop() can return the popped item. And then the heap can define another method that just pops the top item and doesn't return it, this method can be called for example "drop". The following untested code gives is an idea of how it can be implemented: /** Pops the largest element (according to the predicate $(D less)) and returns it. */ ElementType!Range pop() { enforce(_length); auto tmp = _store.front; enforce(_length); if (_length > 1) swap(_store.front, _store[_length - 1]); --_length; percolateDown(_store[0 .. _length]); return tmp; } /** Drops the largest element (according to the predicate $(D less)). */ void drop() { enforce(_length); if (_length > 1) swap(_store.front, _store[_length - 1]); --_length; percolateDown(_store[0 .. _length]); } -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email ------- You are receiving this mail because: -------
Jun 04 2010
http://d.puremagic.com/issues/show_bug.cgi?id=4271 Andrei Alexandrescu <andrei metalanguage.com> changed: What |Removed |Added ---------------------------------------------------------------------------- CC| |andrei metalanguage.com 15:30:36 PDT --- What's wrong with top()? -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email ------- You are receiving this mail because: -------
Jun 04 2010
http://d.puremagic.com/issues/show_bug.cgi?id=4271 In most of my usages of a heap I don't have just to use the top item or just to pop the top item, I have to pop the top item and then use the popped out item. To perform this operation I can currently use something like: item = heap.top(); heap.pop(); But this is not handy because that is not a single expression, so I can't put it inside other expressions. So I have to use: somefunction(heap.top(1)[0]); But being this operation so common, I'd like to write simpler code: somefunction(heap.top()); I have suggested to add the drop() method too to not decrease the performance of the (uncommon) code that just needs to remove the top item with no need to use it (or uses it using top() in other points of the code). -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email ------- You are receiving this mail because: -------
Jun 04 2010
http://d.puremagic.com/issues/show_bug.cgi?id=4271 Sorry, that was a partially wrong comment, I meant: So I have to use: somefunction(heap.pop(1)[0]); But being this operation so common, I'd like to write simpler code: somefunction(heap.pop()); -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email ------- You are receiving this mail because: -------
Jun 04 2010
http://d.puremagic.com/issues/show_bug.cgi?id=4271 Andrei Alexandrescu <andrei metalanguage.com> changed: What |Removed |Added ---------------------------------------------------------------------------- Status|NEW |ASSIGNED AssignedTo|nobody puremagic.com |andrei metalanguage.com -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email ------- You are receiving this mail because: -------
Jan 09 2011