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

Subject: Re: [boost] [GSoC] Heaps & Queues (draft proposal)
From: iaml (lintao30_at_[hidden])
Date: 2010-04-07 13:19:24

      First of all, thank you, Andrew for your appreciation and Jeremiah for
your information.
      I do not notice there exists d-ary in the BGL since I just focus on
boost/pending and libs/pri_queue these days. But after a quick glance on the
code in boost/graph/detail/d_ary_heap.hpp, I think that the container is
supposed to have push_back() and pop()_back() because they are used directly
in push() and pop(), This is something like the alias for vector type, not
the parameter. Is that right or I just misunderstand the code
in boost/graph/detail/d_ary_heap.hpp?

      As someone says: APIs design is main contributor to the Boost (I have
read it today in somewhere in boost.org, but I can find it now :-( ). And I
am lack of experience in APIs design for library. So I want to focus on my
APIs design again. I know I am a bit annoying, but I want to do my best
since it is my first time to join in GSoC. Feedback are welcome. It will be
nice of you to  do that.

==== description here ====
      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?*)

    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 your time.

Yours sincerely,
Tao Lin