[boost] [GSoC] Heaps & Queues (draft proposal)

Subject: [boost] [GSoC] Heaps & Queues (draft proposal)
From: iaml (lintao30_at_[hidden])
Date: 2010-04-02 15:16:53

Hi everyone.
        I am Lintao from Sun Yat-sen University, China. This is my first
time to send mail on mailing list. I'm a little nervous:-).
        I am interested in Heaps & Queues provided by Boost in 2010 GSoC.
And I have finished my draft proposal after viewing the mailing list these
days. Thank you for your comments and suggestions.

        ====== project proposal ======
In my opinion, most of work is to reuse and rearrange the existing data
structure in boost/pending and other data structures which have already
existed.[1] The most important thing I should consider is the APIs design of
the new library. So for each data structure, it should not only agree to the
formulation provided by the BGL, but also should be easy to remember and
user-friendly. Besides, I would like to add d-ary heap and splay heap into
the new library. Because d-ary heap is a variation of binary heap and has
faster running time. As for splay heap, it has the attractive property that
recently accessed elements are quick to access again. I think it will be
very useful in application software programming. If time permits, I want to
add others implementations of heap [2] into the new library.
 Below is my design to the library APIs.

         template <class T, class Compare = std::less<T>>
         class heap{
                  public:
*                            void insert(T& key);*
*                            void delete(T* key);*
*                            void update(T* t, T& new_key);*
                            T* getRoot();
                            T* find(T& key);
                            bool empty() const;
                            size_type size() const;
                            void print() const;
                  private:
                            void print_recur() const;
                  protected:
                            T* _root;
          };

        NOTICE:
                     * operations in bold mean it should be implement by the
subclass.
                     * operations print and print_recur is optional. But I
prefer to include them because it'll be helpful when debugging the programs
using this library.

The class mentioned above is the base class for all the heap structures in
the new library. The classes such as Fibonacci heap, relaxed heap, binomial
heap and splay heap should inherit from this abstract class and add
additional operations if needed.
 And I would prefer to use lists rather than vectors (as shown in
boost/pending/fibonacci_heap.hpp) to implement it for three reasons.
        1. It will save memory since the later needs extra space to store
the key to value mapping.
        2. Vector requires continuous memory while list doesn’t. It does not
matter when the amount of data is small. But when the amount of data becomes
large, it will be a tough problem;
        3. It takes time to resize and reallocate the memory for vectors.

        Of course, list implementation has its own drawback such as easy to
leak memory and cost more time when searching the heap. From my point of
view, it is acceptable comparing with the problems mentioned before.
 As the adaptor of heaps, the priority queue API may like:

        template<class T,
                       class Compare = std::less<T>,
                       class Container = fibonacci_heap<T, Compare>>
       class priority_queue{
                public:
                          void push(T& key);
                          T pop();
                          const T& front() const;
                          T& front();
                          T* find(T& key);
                          void update(T* t, T& new_key);
                          bool empty() const;
                          size_type size() const;
                          void print() const;
                private:
                          void print_recur() const;
      };

[1][2] It means the data structure in this URL:
https://svn.boost.org/svn/boost/sandbox/libs/pri_queue/

Thank you for reading.