[boost] GSoC draft proposal: Heaps & Queues library

Subject: [boost] GSoC draft proposal: Heaps & Queues library
From: Andre Ferreira (greiskul_at_[hidden])
Date: 2010-03-21 19:39:09

This is only a draft, not the final proposal.

Personal Details:
        Name: André Martins Ferreira
        Email: greiskul_at_[hidden]
        University: Universidade Federal do Rio Grande do Sul < www.ufrgs.br >
        Course: Computer Science
        Degree Program: Bachelor of Computer Science
        Availability: About 30 hours a week will be devoted to the project,
more if nescessary.
                                  Start Date: April 1st
                                  End Date: not yet decided
                                  Factors of influence: I live in the Southern Hemisphere, so the
Summer of Code will be during Winter. While I will have
                                  a winter vacation where my attettion will be 100% devoted to the
project, it will only last about a month, from July to August.
                                  During the rest of the time I will study in the morning, and
work on the project on my free time, which luckily this semester
entails
                                  all afternoons. I have worked during school time in previous
semesters, and know that it's possible.

Background Information:
        I am a brazilian computer science student, my course has 9 semesters,
I am currently in the 7th. I have been programming for the last 5
years, mostly in C++
but also in Scheme, Lua, and many other languages. I've had an
intership in developing parallel programs using MPI, and more recently
in supporting an
ERP written in C++.
        My main interest is in algorithms and data structures, but I'm also
interested in functional programming languages.
        My experience with heaps comes from my university classes, Cormen's
Introduction to algorithms book, various online sources and personal
experimentation.
        While I have implemented heap data structures before (binary,
binomial, skew), I have never integrated them in a single package
generic package before
and I'm looking foward to learn from it.
        I would rate my experience in the following technologies this way:
                4   C++
                4   C++ Standard Library
                2   Boost C++ Libraries
                3   Subversion
        I use mainly Eclipse and Geany for development, but I have also done
projects with Visual Studio.
        For documentation I prefer to use Doxygen.

Purpose and goal:
        Heaps are very useful data structures and are used as building blocks
in many algorithms.
        There are some heap data structures implemented in boost, for use in
Boost.Graph for example,
but at the moment they are coupled with the library they support.
        This project's goal is to decouple them into a boost/heaps library,
cleaning them up where needed,
and completely rewritting them if nescessary. All heaps will provide a
common interface where possible,
allowing algorithms writters to quickly change the data structure they
are using without further changes to their code.
        The complexity of every operation on every heap will be documented,
and tested to ensure correctness.
        A priority queue wrapper like std::priority_queue will also be provided.
        Heaps structures that will be provided: binary, binomial, fibonnaci,
mutable heaps, suggestions are welcomed.

Proposed Milestones and Schedule (work in progress):
        Binary heap implemented and submitted, possibly on top of STL heap
algorithms, to have some foundation for the rest of the work,
allowing tests on the other data structures to be compared to a simple
but correct heap implementation.
        Moving heap structures from /boost/pending to the heap library,
adapting them to a common interface and cleaning up where nescessary.
No rewrites.
        Binomial Heap implementation.
        If any of the heap structures from pending were deemed unfit, rewritting them.
        
This proposal is still under work, but I would like feedback from the
community, not only on the project but also in the proposal itself.