www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Interested in a GSoC project idea

reply %u Ishan Thilina <ishanthilina gmail.com> writes:
Hi,

I'm interested in the GSoC project idea which is listed in
http://prowiki.org/wiki4d/wiki.cgi?GSOC_2011_Ideas#Containers . But the
problem is that I couldn't find the relevant mentor for the project. Can
somebody help me to find the mentor and contact him?

Thank you...!
Mar 21 2011
parent reply Jens Mueller <jens.k.mueller gmx.de> writes:
%u Ishan Thilina wrote:

 Hi,
 
 I'm interested in the GSoC project idea which is listed in
 http://prowiki.org/wiki4d/wiki.cgi?GSOC_2011_Ideas#Containers . But the
 problem is that I couldn't find the relevant mentor for the project. Can
 somebody help me to find the mentor and contact him?


I suppose there is no mentor for this project yet.
I suggest you just post your questions to this list so that we can
discuss ideas.

Jens
Mar 22 2011
parent reply %u Ishan Thilina <ishanthilina gmail.com> writes:
Well, The biggest question in my mind is that how many container types that I
should implement? Also will I be able to use a hierarchy similar to a
programming
language such as Java or C++ ?
Mar 22 2011
next sibling parent reply Jens Mueller <jens.k.mueller gmx.de> writes:
%u Ishan Thilina wrote:

 Well, The biggest question in my mind is that how many container types
 that I should implement?


Sorry to answer with a question: In which are you interested? What data
structures do you know already?


 Also will I be able to use a hierarchy similar to a programming
 language such as Java or C++ ?


What do you mean by this? What kind of hierarchy?

Jens
Mar 22 2011
parent %u Ishan Thilina <ishanthilina gmail.com> writes:
== Repost the article of Jens Mueller (jens.k.mueller gmx.de)
== Posted at 2011/03/22 05:48 to digitalmars.D

%u Ishan Thilina wrote:

 Well, The biggest question in my mind is that how many container types
 that I should implement?





Sorry to answer with a question: In which are you interested? What data
structures do you know already?


-----------------------
I know about stacks,Trees,Linked lists and graphs. I am willing to learn new
data
structures if needed :)
-----------------------


 Also will I be able to use a hierarchy similar to a programming
 language such as Java or C++ ?





What do you mean by this? What kind of hierarchy?



Jens


-----------------------------
Sorry,my mistake. I thought there is a hierarchy in D as is the case in Java

-Ishan Thilina
Mar 24 2011
prev sibling next sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
%u Ishan Thilina:


 Well, The biggest question in my mind is that how many container types that I
 should implement?


There are many data structures useful for Phobos, ordered from the most useful:
- a graph (boost graph is huge. But if you remove many algorithms, what's left
is not huge);
- a hash set like the Python built-in one;
- A deque made with a dynamic array of fixed sized arrays;
- an ordered (chained, keeps the insertion order) associative array (not hard,
no need to re-implement associative arrays);
- a Union-Find (not too much hard);
- a Bloom filter (easy with the already present bit arrays);
- a dawg;
- a simple trie;
- a BK-tree;
- a bidirectional associative array;
- a parallelizable immutable finger tree...
- A n-dimensional matrix type?



 Also will I be able to use a hierarchy similar to a programming
 language such as Java or C++ ?


For Phobos Andrei wants a design very different from the Java one. I think more
with static composition/mixins, done with templates. Other people will give you
better answers.

Bye,
bearophile
Mar 22 2011
parent reply spir <denis.spir gmail.com> writes:
On 03/22/2011 10:56 AM, bearophile wrote:

 - an ordered (chained, keeps the insertion order) associative array (not hard,
no need to re-implement associative arrays);


? How would you do that? (Without requiring lookup for each key on traversal.) 
I'm really interested, I need it. Have had a look at current AA implementation 
in hope to tweak it, but too complicated.

Denis
-- 
_________________
vita es estrany
spir.wikidot.com
Mar 22 2011
parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Tue, 22 Mar 2011 11:55:29 -0400, spir <denis.spir gmail.com> wrote:


 On 03/22/2011 10:56 AM, bearophile wrote:

 - an ordered (chained, keeps the insertion order) associative array  
 (not hard, no need to re-implement associative arrays);


 ? How would you do that? (Without requiring lookup for each key on  
 traversal.) I'm really interested, I need it. Have had a look at current  
 AA implementation in hope to tweak it, but too complicated.


Someone told me once, you just embed a secondary linked list pointer into  
the nodes.  The linked list contains the order of insertion.

I plan on making such a type for dcollections (oh, how I wish I had more  
time).

-Steve
Mar 22 2011
prev sibling parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
 Well, The biggest question in my mind is that how many container types that
 I should implement? Also will I be able to use a hierarchy similar to a
 programming language such as Java or C++ ?


There is no hierarchy to std.container like you'd get in Java. The current 
plain is for the containers to be final classes, so they're reference types, 
but you still get the benefits of inlining and whatnot. No container will 
inherit from another. The genericity of containers comes from templates, not 
inheritance.

Also, containers should be based on what their data structure is, not what 
they're used for (e.g. RedBlackTree instead of Set or Map). If you're 
interested in working on std.container, you should look at what's in there 
now. It includes a table of common functions and their required Big-O 
complexity.

I think that the main thing is to get a list of the main container types which 
have not yet been implemented - e.g. a doubly-linked list. Those are what 
needed to be implemented.

Really, the person to talk to about what needs to be done with std.container 
is Andrei. He's its initial designer and best knows what the overall plan for 
it is. Also, part of the reason that more containers haven't been implemented 
yet has to do with some language issues IIRC. It had to do with avoiding code 
duplication in the implementations of the various containers, but I don't 
remember exactly what it was off the top of my head. Regardless, Andrei is the 
best acquainted with how std.container works and what the plans for it are.

- Jonathan M Davis
Mar 22 2011
parent reply Ishan Thilina <ishanthilina gmail.com> writes:
Sorry for being this much late to reply( and thanks to all of you for replying
this much quickly), I was really busy with my semester end exams. Now that it's
over I can concentrate fully on this project.

I implemented a stack using D in the little time I had to study D. And currently
I'm looking at the implementation of the std.container.

It seems that the best way to go is to contact Mr. Andrei Alexandrescu. Shall I
wait till he reply to this mailing list? It's not a good thing to directly mail
him,isn't it?
Mar 23 2011
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 3/23/11 10:03 AM, Ishan Thilina wrote:

 Sorry for being this much late to reply( and thanks to all of you for replying
 this much quickly), I was really busy with my semester end exams. Now that it's
 over I can concentrate fully on this project.

 I implemented a stack using D in the little time I had to study D. And
currently
 I'm looking at the implementation of the std.container.

 It seems that the best way to go is to contact Mr. Andrei Alexandrescu. Shall I
 wait till he reply to this mailing list? It's not a good thing to directly mail
 him,isn't it?


Best way is to simply post to this group. You'll get more and quicker 
help than from me alone.

Thanks,

Andrei
Mar 23 2011