Re: [boost] GSoC 2010: Heaps and Queues

Subject: Re: [boost] GSoC 2010: Heaps and Queues
From: Dan Larkin (danielhlarkin_at_[hidden])
Date: 2010-04-08 23:26:46

Okay, pending any incredibly prompt responses, this may be the final 
revision for the project detail section of my proposal, seeing as it's 
due in about 13 hours now, and I'll be spending several of those 
sleeping and another couple in class.
=====================================

I would like to implement a library which allows a simple, unified 
concept for a heap/priority queue with a common interface.  Through this 
common interface, I would allow the user to select the specific model to 
use based on their needs.

The standard interface would allow the following functions to be used 
regardless of the model:
  - insert
  - delete
  - merge
  - findMin
  - deleteMin
  - decreaseKey

Furthermore, I would implement the following heap models:
  - D-ary
  - Binomial
  - Fibonacci
  - Brodal (may be replaced with a different model with similar 
performance, pending further research)

As it stands, the current heap implementations in Boost C++ 
(specifically in sandbox/libs/pri_queue), take what I think to be 
slightly the wrong approach.  Heaps are conceptually very simple 
structures, as are their interfaces.  By nature, they have a single 
important element (the minimum), and the rest is treated as a mystery to 
the outside world.  Thus, the issue of iterator access is rather tricky. 
  Many operations can change the structure of the heap so as to 
invalidate a traversal.  These trouble spots would need to be 
documented.  Along the same lines, I feel like a lot of the internal 
structure can be simplified and memory usage minimized by keeping only 
pointers to elements.  This may seem excessive in the case of simple 
data types like integers, but I believe it will lead to much simpler 
memory management, despite the fact that the user will need to handle 
some of it by themselves.  This leads nicely into the use of iterators 
to simply encapsulate the original data pointers and give them some 
(arbitrary) order within the structure.  This offers a mutability scheme 
which should perform much better than the reference-based one currently 
implemented in Boost.  A reference-based scheme assumes efficient 
copy-constructors and does not allow partial updates, both issues which 
can be circumvented quite gracefully by a pointer-based scheme.

All that said, I do believe that the existing d-heap and f-heap 
implementations can be used as a guide to help me in my development 
process, in both examining the design decisions along the way and 
verifying performance.

Below are draft interfaces for the base Heap class and the PriorityQueue 
wrapper class.  I've left out some of the tedious bits, such as 
constructors, in favor of keeping the focus on the functional interface.

template <class T, class Compare = std::less<T>>
class Heap {

    public:

       virtual iterator& insert( T* elem ) = 0;
       virtual void remove( iterator& elem ) = 0;
       virtual void update( iterator& elem ) = 0;
       virtual iterator& findMin() = 0;
       virtual void removeMin() = 0;
       virtual void merge( Heap<T,Compare> other ) = 0;

       virtual bool empty() = 0;
       virtual int size() = 0;
       class iterator {
          public:
             T& operator* ();
             T* operator-> ();
             iterator& operator++();
             iterator& operator--();
             bool operator== (iterator const& other);
             bool operator!= (iterator const& other);
       };
       virtual iterator& begin() = 0;
       virtual iterator& end() = 0;

};

template <class T, class Compare = std::less<T>>
class PriorityQueue {

    public:

       iterator& push( T* elem );
       iterator& pop();
       void remove( iterator& elem );
       void update( iterator& elem );
       void merge( PriorityQueue<T,Compare> other );

       bool empty();
       int size();
       class iterator {
          public:
             T& operator* ();
             T* operator-> ();
             iterator& operator++();
             iterator& operator--();
             bool operator== (iterator const& other);
             bool operator!= (iterator const& other);
       };
       virtual iterator& begin() = 0;
       virtual iterator& end() = 0;

    private:

       Heap<T,Compare> data;

};

Dan Larkin