[Issue 4271] New: drop/pop methods for std.algorithm.BinaryHeap

[d-bugmail at puremagic.com]

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 at puremagic.com
        ReportedBy: bearophile_hugs at eml.cc


--- Comment #0 from bearophile_hugs at eml.cc 2010-06-04 15:28:50 PDT ---
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: -------