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

Subject: Re: [boost] [GSoC] Heaps & Queues (draft proposal)
From: iaml (lintao30_at_[hidden])
Date: 2010-04-06 22:45:11

      First of all, thank you, Andrew and Luke, for pointing out my mistakes
and misunderstanding in my draft project which I sent several days ago.
After that, I have read some source code in the STL and do some more
research on this topic. Now, I work out my draft proposal again. Please feel
free to point out my stupidity. I will be very grateful for this.

      Besides, I still have some doubt on this project:
      What we need to do in this project is to build a new library as the
result of decoupling boost/pending from the BGL. So the compatibility with
the new library and the BGL need to be concerned. However, I have read the
document in the BGL. It’s said that we can convert existing graphs to the
BGL by implementing some functions. Dose it mean the APIs of the new library
does not effect the compatibility of the new library and the BGL since we
can change it properly. Is that right?

==== draft proposal v0.2 ====

Project Proposal

* Please provide a description of your proposed work.
** Background
There are a number of data structures in boost/pending that implement
different kinds of heaps and queues that are used in a number of different
Boost Graph (BGL) algorithms. These can be cleaned up, decoupled from the
BGL and redeveloped into a useful library for advanced data structures.
Why don’t we use them directly?
We can’t use boost/pending or libs/pri_queue as the new library directly for
several reasons:
1. Heaps don’t parameterize for container type. They use vector as default.
In the STL, there is very clear abstraction between containers and
algorithms (they use iterator to achieve this abstraction). Since
abstraction is a goal of the project, it’s necessary to modify the data
structure in boost/pending rather than use it directly.
2. The APIs designed in the boost/pending is not user-friendly. In my
opinion, the heaps in boost/pending act as the container of the priority
queue rather than as a data structure. So some operations are omitted since
they are useless in priority queue, but useful in heap and maybe necessary
for other adaptors. They lack some operations such as delete one key (not
just pop the minimum or maximum key), update the key in heap. This leads to
the necessity of redeveloping a new library.

** Benefit for Boost
Heap is widely used in development such as heap sort, priority queue and
other graph algorithm. It also can be the container for advanced data
structures. But the heaps in boost/pending and libs/pri_queue is not
extendable or highly abstract. This leads to the limited usage of this
library. To redevelop a new library about heaps and priority queue more
abstract and more user-friendly not only can broaden the user group of
Boost, but also can fix the design deficiency in boost/pending and make it
more conforms to the philosophy of Boost.

** Solution
In my opinion, most of work is to rewrite and reuse the existing data
structures in boost/pending and libs/pri_queue. The most important thing I
should consider is the APIs design of the new library. It should be highly
abstract and user-friendly. The compatibility with the new library and the
BGL needs to be concerned.

*In order to be extendible, I would like to add iterator to the base class,
which is more frequently used in programming, especially generic
programming, than pointer. In some libraries, such as the STL, iterator is a
bridge for container and algorithm. Since one of the goals of this project
is to redevelop a new library for advance data structures and adaptors, I
consider iterator to be necessary component to the library. Maybe it’ll take
a little bit more memory, but in modern PCs, I think it acceptable.(am I
wrong about the usage of the iterator?)*
*
*
Besides the heaps required, I would like to add d-ary heap into the new
library. Because d-ary heap is a variation of binary heap (so I can use
binary heap as a special case for d-ary) and has faster running time.
 If time permits, I want to add splay heap (because 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) and other heaps
mentioned in libs/pri_queue into the new library.
 Below is my design to the library APIs.

    template <class RandomAccessIterator, // iterator of the container
                   class TreeNode,                      // key type
                   class Comp = std::less<TreeNode>>
         class heap{
 public:
class iterator{
                                        // implement iterator so that this
class can be use as container
                                        // for other adaptors and algorithms
   public:
   TreeNode const& operator* () const;
     TreeNode const* operator->() const;
     iterator& operator++();
     iterator  operator++(int);
     bool operator== (iterator const& it);
     bool operator!= (iterator const& it);
   };
                  public:
   /* param: new_inserted points to the bottom of the container
                            *       where the new value has been inserted
but not heapify.
                            */
                            void insert(RandomAccessIterator new_inserted);
                            void delete(RandomAccessIterator delete_node);
                            void update(RandomAccessIterator update_node,
                                              TreeNode& new_node);    //
make the heap mutable
     RandomAccessIterator merge(RandomAccessIterator other_root);
                            RandomAccessIterator getRoot();
                            RandomAccessIterator find(TreeNode& node);
                            bool empty() const;
                            size_type size() const;
                            iterator begin() const;
      iterator end() const;
                            void print() const;
                  private:
                            void print_recur() const;
                  protected:
                            RandomAccessIterator _root;
          };

        NOTICE: 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 d-ary heap should inherit from this abstract class and add
additional operations if needed.
 As the adaptor of heaps, the priority queue API may like:

  template< class RandomAccessIterator,
 class TreeNode,
 class Comp = std::less<TreeNode>
                         class Container  =
fibonacci_heap<RandomAccessIterator,

 TreeNode, Comp>>
       class priority_queue{
                public:
                          /* param: new_inserted points to the place
                           *       where the new value has been inserted
                           */
                          void push(RandomAccessIterator new_inserted);
                          void pop();

   // get the first value without popping it
                          const TreeNode& front() const;
                          TreeNode& front() ;
          RandomAccessIterator front() const;
                          RandomAccessIterator find(TreeNode& node);
                          void update(RandomAccessIterator update_node,
                                            TreeNode& new_node); // make the
priority queue mutable
                          RandomAccessIterator merge(RandomAccessIterator
other_head);
                          bool empty() const;
                          size_type size() const;
                          void print() const;
                private:
                          void print_recur() const;
   protected:
  RandomAccessIterator _head;
      };

Thank you for reading