Hello Everyone!, I am a Junior Undergraduate at BIT Mesra, one of the premier institutes in the field of Engineering and Sciences in India, pursuing Computer Science & Engineering. I am looking forward for a challenging project as a part of GSOC '11 under Boost Organisation during summers. I would like to put forward my own idea for a Library which is: - Templatized General Purpose Tree based data structures and algorithms for them The idea is to provide template based containers which will provide general purpose tree containers as there are for Stack, Queue and few others in the Standard Template Library. As of now, I would like to propose the library to consist of 5 containers which includes: 1. Binary Search Trees 2. Red-Black Trees 3. B-Trees 4. Binomial Heaps 5. Fibonacci Heaps Now, these containers will provide the used a generic container set as they are used along with their common operations like Insertion, Deletion, Search etc. Also, they will provide the user with specific operations for each type of container like, Decreasing key of a node in Fibonacci Heaps, Rotation in Red-Black Trees etc. [PS: Any Additions as well as Modifications are welcome to be put forward] I am looking forward towards Boost Community so that I can find a mentor for this project. I would like to discuss more about the details of the above project so that I can contribute to the Boost as well as OSS Community. I would like to mention that I have strong foundations in algorithm intensive programming and have advanced foundations in C/C++ too. I am fully aware of the responsibilities and requirements for this position. To consolidate my knowledge in the fields of interest, I have acquired conceptual knowledge in the fields of algorithms and data structures & have done basic projects in these fields too. If any further information is required, I would be glad to furnish the same. -- Regards, Sitesh Shrivastava Junior Undergraduate, BIT Mesra Phone: +91-9470521313 E-Mail: siteshshrivastava@gmail.com Home-Page: https://sites.google.com/site/siteshshrivastava
The idea is to provide template based containers which will provide general purpose tree containers as there are for Stack, Queue and few others in the Standard Template Library. As of now, I would like to propose the library to consist of 5 containers which includes: 1. Binary Search Trees 2. Red-Black Trees 3. B-Trees 4. Binomial Heaps 5. Fibonacci Heaps
during last year's gsoc, i was implementing different heap data structures [1,2], including binomial and fibonaci heaps. maybe a good point to start? cheers, tim [1] http://tim.klingt.org/boost_heap/ [2] http://tim.klingt.org/git?p=boost_heap.git;a=summary
Hi Sitesh
The idea is to provide template based containers which will provide general purpose tree containers as there are for Stack, Queue and few others in the Standard Template Library. As of now, I would like to propose the library to consist of 5 containers which includes: 1. Binary Search Trees 2. Red-Black Trees 3. B-Trees 4. Binomial Heaps 5. Fibonacci Heaps
I don't believe that this would be a suitable GSoC project for Boost. The C++ Standard Library already uses red-black trees to implement set and map, there has been recent work on B-trees (B+ trees?) for Boot and, (as Tim says), he worked on binomial and fibonacci heaps last summer. If you are serious about submitting a proposal for Boost, then your best bet is to identify a single data structure or small set of closely related data structures that are either not in the Standard Library or Boost, or are not well-supported in either library. Best regards, Andrew
At Sat, 26 Mar 2011 08:44:21 -0500, Andrew Sutton wrote:
Hi Sitesh
The idea is to provide template based containers which will provide general purpose tree containers as there are for Stack, Queue and few others in the Standard Template Library. As of now, I would like to propose the library to consist of 5 containers which includes: 1. Binary Search Trees 2. Red-Black Trees 3. B-Trees 4. Binomial Heaps 5. Fibonacci Heaps
I don't believe that this would be a suitable GSoC project for Boost. The C++ Standard Library already uses red-black trees to implement set and map, there has been recent work on B-trees (B+ trees?) for Boot and, (as Tim says), he worked on binomial and fibonacci heaps last summer.
If you are serious about submitting a proposal for Boost, then your best bet is to identify a single data structure or small set of closely related data structures that are either not in the Standard Library or Boost, or are not well-supported in either library.
Andrew, What do you think of the job of gathering, completing (i.e. with docs and tests) polishing, and submitting all that work as a GSOC project? Note: most (probably all) STL implementations use RB trees in their implementations, but they don't expose an RB-tree interface, which, had it been available, could have been used to implement e.g. interval sets). So I don't see that as redundant -- Dave Abrahams BoostPro Computing http://www.boostpro.com
Exactly, that is my point! Although Map from std::library uses RB-Trees as a base for implementing these data structures, those are not the exhaustive operations, which you can perform using RB-Trees. So, I think it will much better and useful to provide them as raw containers rather just making a limited set of them to users. Next, You didn't said anything about BSTs, I think you will be interested in getting it done. Also, I would like to see how much of the fibonacci and binomial heaps have already been done. In case, they they have been at all, I would be more than happy in improving them and making it more generic. And, B-Trees and B+ Trees are obviously not sme(Check out: http://en.wikipedia.org/wiki/B%2B_tree, http://en.wikipedia.org/wiki/B-tree), though similar in many features. One more thing, what is the position of BigInteger class for C++. Is it completed ? Thanks! On Sat, Mar 26, 2011 at 7:50 PM, Dave Abrahams <dave@boostpro.com> wrote:
At Sat, 26 Mar 2011 08:44:21 -0500, Andrew Sutton wrote:
Hi Sitesh
The idea is to provide template based containers which will provide
purpose tree containers as there are for Stack, Queue and few others in
Standard Template Library. As of now, I would like to propose the
general the library to
consist of 5 containers which includes: 1. Binary Search Trees 2. Red-Black Trees 3. B-Trees 4. Binomial Heaps 5. Fibonacci Heaps
I don't believe that this would be a suitable GSoC project for Boost. The C++ Standard Library already uses red-black trees to implement set and map, there has been recent work on B-trees (B+ trees?) for Boot and, (as Tim says), he worked on binomial and fibonacci heaps last summer.
If you are serious about submitting a proposal for Boost, then your best bet is to identify a single data structure or small set of closely related data structures that are either not in the Standard Library or Boost, or are not well-supported in either library.
Andrew,
What do you think of the job of gathering, completing (i.e. with docs and tests) polishing, and submitting all that work as a GSOC project?
Note: most (probably all) STL implementations use RB trees in their implementations, but they don't expose an RB-tree interface, which, had it been available, could have been used to implement e.g. interval sets). So I don't see that as redundant
-- Dave Abrahams BoostPro Computing http://www.boostpro.com
-- Regards, *Sitesh Shrivastava* Junior Undergraduate, BIT Mesra
Next, You didn't said anything about BSTs, I think you will be interested in getting it done.
There is a Tree library floating around in the Boost Sandbox. I don't know what the status of this project is... it's been about a year since I looked at. I do know that the work was written up as TR2 proposal at one point (hierarchical containers or something like that). If the library is unfinished and abandoned, then it might be worth trying to get it dusted off and see if there's interest in it. The project was worked on as part of 2006 or 2007 GSoC, so it will be in the SOC directory in the sandbox, unless there's a more recent branch. Andrew
That is why, I wanted to discuss the idea so as to realise the feasibility and time period required to carry out the desired operations. Well, I already have been working on the idea of my Algorithm Library, in which I have worked about these data structures and hence, the only time required will be to make them template based and more generic. I was wondering, how can 8 hours a day of work for almost 10 weeks during summers won't suffice for at least completion of Core Features. I can always carry it on further so as to raise it above standards, in case that's required. Also, please help me out to narrow down the features, which one thinks are good for GSoC and where I can a mentor for it ? In case, My ideas are not that fascinating, please tell me where to include or modify ? On Sat, Mar 26, 2011 at 9:41 PM, Andrew Sutton <asutton.list@gmail.com>wrote:
Next, You didn't said anything about BSTs, I think you will be interested in getting it done.
There is a Tree library floating around in the Boost Sandbox. I don't know what the status of this project is... it's been about a year since I looked at. I do know that the work was written up as TR2 proposal at one point (hierarchical containers or something like that).
If the library is unfinished and abandoned, then it might be worth trying to get it dusted off and see if there's interest in it.
The project was worked on as part of 2006 or 2007 GSoC, so it will be in the SOC directory in the sandbox, unless there's a more recent branch.
Andrew
-- Regards, *Sitesh Shrivastava* Junior Undergraduate, BIT Mesra
Hi Sitesh, I believe that in addition to the prior GSOC project there was at least one other tree library proposed (search the list). Trees require a more complex interface than a regular container and I'm not sure if there is consensus what that should look like. Boost.Intrusive has quite a few trees but I believe it only exposes the associative container interface.
I was wondering, how can 8 hours a day of work for almost 10 weeks during summers won't suffice for at least completion of Core Features. I can always carry it on further so as to raise it above standards, in case that's required.
You would definitely need to commit to working on it further, because just completing the core features doesn't really make it useful to anyone or boost quality. Documentation, tests, examples, hashing out the feature set with users.....
Also, please help me out to narrow down the features, which one thinks are good for GSoC and where I can a mentor for it ?
Unfortunately, I am not qualified as a mentor - I don't have my own library in yet, really, and will be putting my whole summer into it. :-)
In case, My ideas are not that fascinating, please tell me where to include or modify ?
I think there is plenty of interest in a Tree library, but you've got scope and interface issues here. Wish I could help more! Cheers, Gordon
What do you think of the job of gathering, completing (i.e. with docs and tests) polishing, and submitting all that work as a GSOC project?
Ambitious? Seriously, though... The amount of work required to implement a Boost-quality library is way more than a 3 month project. Even if the library consists of a few relatively simple abstractions, I think it's unlikely that a Boost-ready library can be completed by the end of the summer. This sentiment has been echoed a number of times on the list, already. Successful projects, those that actually make it into the Boost release seem to take about year, in some cases 2 or 3. I don't think that's the for maintenance or extension projects, but for new development, certainly.
Note: most (probably all) STL implementations use RB trees in their implementations, but they don't expose an RB-tree interface, which, had it been available, could have been used to implement e.g. interval sets). So I don't see that as redundant
That's a good point. Doesn't the intrusive library have an RB-tree with an binary tree interface, though? Andrew
The idea is to provide template based containers which will provide general purpose tree containers as there are for Stack, Queue and few others in the Standard Template Library. As of now, I would like to propose the library to consist of 5 containers which includes: 1. Binary Search Trees 2. Red-Black Trees 3. B-Trees 4. Binomial Heaps 5. Fibonacci Heaps
I don't believe that this would be a suitable GSoC project for Boost. The C++ Standard Library already uses red-black trees to implement set and map, there has been recent work on B-trees (B+ trees?) for Boot and, (as Tim says), he worked on binomial and fibonacci heaps last summer.
what might be interesting is to introduce these data structures as part of boost.intrusive. boost.intrusive already contains red-black, avl and splay trees, but no pure heap data structures. cheers, tim -- tim@klingt.org http://tim.klingt.org You can play a shoestring if you're sincere John Coltrane
Sitesh Shrivastava <siteshshrivastava <at> gmail.com> writes:
- Templatized General Purpose Tree based data structures and algorithms for them
I think this is a great idea! I would like to see an abstraction of walks of the trees. So it was very easy to specify left-hand and right-hand walks with left-side, bottom, and right-side visitations. I'd also like to be able to easily do stuff like perform a right-hand walk on the left child in a binary tree and a left-hand walk on the right child. What would be even sweeter, is if these same walks could be done on some of the abstract expression trees that are in boost. Joel
On 3/26/2011 3:41 PM, Joel Young wrote:
Sitesh Shrivastava<siteshshrivastava<at> gmail.com> writes:
- Templatized General Purpose Tree based data structures and algorithms for them
I think this is a great idea!
I would like to see an abstraction of walks of the trees. So it was very easy to specify left-hand and right-hand walks with left-side, bottom, and right-side visitations.
I'd also like to be able to easily do stuff like perform a right-hand walk on the left child in a binary tree and a left-hand walk on the right child.
What would be even sweeter, is if these same walks could be done on some of the abstract expression trees that are in boost.
<http://svn.boost.org/svn/boost/sandbox/SOC/2006/tree/trunk/> <http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2101.html> -- -- Grafik - Don't Assume Anything -- Redshift Software, Inc. - http://redshift-software.com -- rrivera/acm.org (msn) - grafik/redshift-software.com -- 102708583/icq - grafikrobot/aim,yahoo,skype,efnet,gmail
On Mar 26, 2011, at 4:41 PM, Joel Young <jdy@cryregarder.com> wrote:
What would be even sweeter, is if these same walks could be done on some of the abstract expression trees that are in boost.
Note that this is a case for heterogeneous trees with N node *types* in the same structure. I made some progress with an adapter for Proto last year (see Proto mailing list archives), and intend to develop this more this year. I'll look at Rene's proposal for inspiration (thanks for the link Rene!) Gordon
participants (8)
-
Andrew Sutton -
Dave Abrahams -
Gordon Woodhull -
Ion Gaztañaga -
Joel Young -
Rene Rivera -
Sitesh Shrivastava -
Tim Blechmann