[boost] [gsoc] heaps

Subject: [boost] [gsoc] heaps
From: Tim Blechmann (tim_at_[hidden])
Date: 2010-06-11 08:48:24

hi all,

since the heaps/queues project is likely to be used by multiple people, i 
think it may be a good idea to share some ideas on the list ...

for now, i have been implementing a (non-intrusive) d-ary heap, which was 
very useful to do some prototyping of the actual interface.

all data structures support the following template arguments:
typename T  // value type
bool stable // stability 
class Cmp   // compare object
class Alloc // allocator for internal data structures

the interface matches the forward container requirement, except that it does 
not support iterators (only const_iterators) and container comparison. at 
the moment, i distinguish between immutable and mutable heaps. the interface 
for immutable heaps would look like this:

class immutable_heap
{
public:
    // priority queue support
    value_type const & top(void) const;
    void push(value_type const & v);
    void pop(void);

    // merge support
    void merge (immutable_heap const & rhs);
    void merge_and_clear (immutable_heap & rhs); // moves all elements from
                                                    rhs to *this
};

for mutable heaps, i have been using a `handle' to refer to specific 
elements:

class mutable_heap
{
public:
    typedef handle_type;

    // priority queue support
    value_type const & top(void) const;
    handle_type push(value_type const & v);
    void pop(void);

    // update via function
    void update(handle_type const & node, value_type const & v);
    void increase(handle_type const & node, value_type const & v);
    void decrease(handle_type const & node, value_type const & v);

    // force update after element has been changed via the handle
    void update(handle_type const & node);
    void increase(handle_type const & node);
    void decrease(handle_type const & node);

    // merge support
    void merge (mutable_heap const & rhs);
    void merge_and_clear (mutable_heap & rhs);
};

the forced update api is rather dangerous, since the heap would enter an 
undefined state, of the node is changed, but the heap is not updated. otoh, 
it would help to update values using a different api than the assignment 
operator.

also, i am unsure, whether by default the heaps should be min-heaps (like in 
most textbooks on data structures) or max-heaps (like std::priority_queue). 
so i'd be curious, what people think about it ...

the code is available from my public git repository. i would be curious to 
hear some thoughts!
http://tim.klingt.org/git?p=boost_heap.git

cheers, tim

-- 
tim_at_[hidden]
http://tim.klingt.org
A year ago, six months ago, I thought that I was an artist. I no 
longer think about it, I am.
  Henry Miller