www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Phobos 'collections' question

reply Robert McGinley <mcginley.robert gmail.com> writes:
Hey all,
Mostly as an exercise I'm considering writing an ArrayList, AVL tree, =
and possible other standard data structures in D.  I have two questions.
1.) If completed should I send these around for review and inclusion or =
do they not belong in phobos?
2.) If I'm working on including these in phobos should I put them in =
container.d (that has RedBlack Trees and a Singlelinked List) or is =
there a better location?
Rob=
Sep 14 2011
next sibling parent Timon Gehr <timon.gehr gmx.ch> writes:
On 09/14/2011 04:08 PM, Robert McGinley wrote:
 Hey all,
 Mostly as an exercise I'm considering writing an ArrayList, AVL tree, and
possible other standard data structures in D.  I have two questions.
 1.) If completed should I send these around for review and inclusion or do
they not belong in phobos?
 2.) If I'm working on including these in phobos should I put them in
container.d (that has RedBlack Trees and a Singlelinked List) or is there a
better location?
 Rob

As far as I know, the reason why std.container is not under active development, is that phobos does not have an allocator abstraction yet. As soon as there is one, the module will probably undergo some breaking changes. But I think the more well implemented standard data structures there are in Phobos, the better. I think as soon as the standard allocator interface is settled on, your efforts will be welcome. Steve can probably answer your question better though.
Sep 14 2011
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Wed, 14 Sep 2011 12:50:25 -0400, Timon Gehr <timon.gehr gmx.ch> wrote:

 On 09/14/2011 04:08 PM, Robert McGinley wrote:
 Hey all,
 Mostly as an exercise I'm considering writing an ArrayList, AVL tree,  
 and possible other standard data structures in D.  I have two questions.
 1.) If completed should I send these around for review and inclusion or  
 do they not belong in phobos?
 2.) If I'm working on including these in phobos should I put them in  
 container.d (that has RedBlack Trees and a Singlelinked List) or is  
 there a better location?
 Rob

As far as I know, the reason why std.container is not under active development, is that phobos does not have an allocator abstraction yet. As soon as there is one, the module will probably undergo some breaking changes. But I think the more well implemented standard data structures there are in Phobos, the better. I think as soon as the standard allocator interface is settled on, your efforts will be welcome. Steve can probably answer your question better though.

Certainly more containers are welcome. The review for getting things into phobos is done via github. You do not need write permission to generate a pull request. Yes, they should all be put into std.container for now. I'd recommend doing one pull request per container, that way one container type does not detract from the inclusion of another. I don't think that lack of allocators should prevent implementing containers. My collection package (www.dsource.org/projects/dcollections) uses allocators, and they're pretty orthogonal to the operation of the container. BTW, feel free to use any ideas/code from dcollections, it's also boost licensed. Note that the red black tree implementation in phobos is copied verbatim from dcollections. If you implement a good AVL tree, I might even steal it for dcollections ;) (with attribution, of course!) -Steve
Sep 14 2011
prev sibling next sibling parent "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Wednesday, September 14, 2011 09:57 Steven Schveighoffer wrote:
 On Wed, 14 Sep 2011 12:50:25 -0400, Timon Gehr <timon.gehr gmx.ch> wrote:
 On 09/14/2011 04:08 PM, Robert McGinley wrote:
 Hey all,
 Mostly as an exercise I'm considering writing an ArrayList, AVL tree,
 and possible other standard data structures in D. I have two questions.
 1.) If completed should I send these around for review and inclusion or
 do they not belong in phobos?
 2.) If I'm working on including these in phobos should I put them in
 container.d (that has RedBlack Trees and a Singlelinked List) or is
 there a better location?
 Rob

As far as I know, the reason why std.container is not under active development, is that phobos does not have an allocator abstraction yet. As soon as there is one, the module will probably undergo some breaking changes. But I think the more well implemented standard data structures there are in Phobos, the better. I think as soon as the standard allocator interface is settled on, your efforts will be welcome. Steve can probably answer your question better though.

Certainly more containers are welcome. The review for getting things into phobos is done via github. You do not need write permission to generate a pull request. Yes, they should all be put into std.container for now.

That depends on the scope of the changes. If they're big enough or complicated enough, then they'd need to go in the review queue. With new containers, I don't know whether that's necessary or not. They're potentially large pieces of functionality, but much of their API is already stipulated by std.container, so not as thorough a review is necessary as might otherwise be the case. Simpler containers may not really need a formal review in the newsgroup, but if a particularly complicated container were being added to Phobos, then it would probably merit a more thorough review than you'd get via pull requests. It is a bit of a fuzzy area though. - Jonathan M Davis
Sep 14 2011
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Wed, 14 Sep 2011 13:12:30 -0400, Jonathan M Davis <jmdavisProg gmx.com>  
wrote:

 On Wednesday, September 14, 2011 09:57 Steven Schveighoffer wrote:
 On Wed, 14 Sep 2011 12:50:25 -0400, Timon Gehr <timon.gehr gmx.ch>  
 wrote:
 On 09/14/2011 04:08 PM, Robert McGinley wrote:
 Hey all,
 Mostly as an exercise I'm considering writing an ArrayList, AVL tree,
 and possible other standard data structures in D. I have two  


 1.) If completed should I send these around for review and inclusion  


 do they not belong in phobos?
 2.) If I'm working on including these in phobos should I put them in
 container.d (that has RedBlack Trees and a Singlelinked List) or is
 there a better location?
 Rob

As far as I know, the reason why std.container is not under active development, is that phobos does not have an allocator abstraction

 As soon as there is one, the module will probably undergo some  

 changes. But I think the more well implemented standard data  

 there are in Phobos, the better. I think as soon as the standard
 allocator interface is settled on, your efforts will be welcome. Steve
 can probably answer your question better though.

Certainly more containers are welcome. The review for getting things into phobos is done via github. You do not need write permission to generate a pull request. Yes, they should all be put into std.container for now.

That depends on the scope of the changes. If they're big enough or complicated enough, then they'd need to go in the review queue. With new containers, I don't know whether that's necessary or not. They're potentially large pieces of functionality, but much of their API is already stipulated by std.container, so not as thorough a review is necessary as might otherwise be the case. Simpler containers may not really need a formal review in the newsgroup, but if a particularly complicated container were being added to Phobos, then it would probably merit a more thorough review than you'd get via pull requests. It is a bit of a fuzzy area though.

Regardless, the best way to get your code reviewed is by creating a github fork. At least then it's easy to try out. IMO, I think a pull request is fine, we already have established that we want a std.container and what the interface should be. I'd recommend to Robert to identify exactly what containers you intend to implement, and have an informal discussion on the NG before creating the code. This will at least give you an idea of what's likely to be accepted. -Steve
Sep 14 2011
prev sibling next sibling parent "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Wednesday, September 14, 2011 10:23 Steven Schveighoffer wrote:
 Regardless, the best way to get your code reviewed is by creating a github
 fork. At least then it's easy to try out.

Indeed. Such a fork is pretty much necessary to get the code into Phobos anyway.
 IMO, I think a pull request is fine, we already have established that we
 want a std.container and what the interface should be.

My primary concern would be that if a container were particularly complicated, then it would merit a more thorough review than is likely to occur on github (github frequently does not have enough people looking at pull requests and giving feedback on them). It is true that the primary thing that formal reviews deal with is the API, which has mostly been sorted out for std.container already, but particularly large/complex chunks of new functionality or larg/complex changes could merit more thorough reviews. Simpler containers won't have that issue. However, an informal review in the newsgroup might be enough for any particularly complex container. As I said, it's fuzzy. We just need to make sure that any containers which get added get a thorough enough review, whether that's simply reviewing it in github or a more thorough review in the newsgroup.
 I'd recommend to Robert to identify exactly what containers you intend to
 implement, and have an informal discussion on the NG before creating the
 code. This will at least give you an idea of what's likely to be accepted.

Good advice. A related note would be that the basic design of std.container is that the containers be based around data structures, not what they're used for (hence why we have RedBlackTree and not Set or Map), and new containers should stick to that. We may or may not create simple wrapper functions, types, or aliases which are based on usage (e.g. Set and Map), but the actual container types should be specific data structures. - Jonathan M Davis
Sep 14 2011
prev sibling next sibling parent Robert McGinley <mcginley.robert gmail.com> writes:
Thanks everybody.  I'll have to plan things out more (my time wise more =
then anything) and I'll check with the NG before I move on anything.
Rob
On Sep 14, 2011, at 1:55 PM, Jonathan M Davis wrote:

 On Wednesday, September 14, 2011 10:23 Steven Schveighoffer wrote:
 Regardless, the best way to get your code reviewed is by creating a =


 fork. At least then it's easy to try out.

Indeed. Such a fork is pretty much necessary to get the code into =

 anyway.
=20
 IMO, I think a pull request is fine, we already have established that =


 want a std.container and what the interface should be.

My primary concern would be that if a container were particularly =

 then it would merit a more thorough review than is likely to occur on =

 (github frequently does not have enough people looking at pull =

 giving feedback on them). It is true that the primary thing that =

 reviews deal with is the API, which has mostly been sorted out for=20
 std.container already, but particularly large/complex chunks of new=20
 functionality or larg/complex changes could merit more thorough =

 Simpler containers won't have that issue. However, an informal review =

 newsgroup might be enough for any particularly complex container. As I =

 it's fuzzy. We just need to make sure that any containers which get =

 a thorough enough review, whether that's simply reviewing it in github =

 more thorough review in the newsgroup.
=20
 I'd recommend to Robert to identify exactly what containers you =


 implement, and have an informal discussion on the NG before creating =


 code. This will at least give you an idea of what's likely to be =


=20
 Good advice. A related note would be that the basic design of =

 that the containers be based around data structures, not what they're =

 (hence why we have RedBlackTree and not Set or Map), and new =

 stick to that. We may or may not create simple wrapper functions, =

 aliases which are based on usage (e.g. Set and Map), but the actual =

 types should be specific data structures.
=20
 - Jonathan M Davis

Sep 14 2011
prev sibling next sibling parent "Marco Leise" <Marco.Leise gmx.de> writes:
Am 14.09.2011, 18:57 Uhr, schrieb Steven Schveighoffer  
<schveiguy yahoo.com>:

 On Wed, 14 Sep 2011 12:50:25 -0400, Timon Gehr <timon.gehr gmx.ch> wrote:

 On 09/14/2011 04:08 PM, Robert McGinley wrote:
 Hey all,
 Mostly as an exercise I'm considering writing an ArrayList, AVL tree,  
 and possible other standard data structures in D.  I have two  
 questions.
 1.) If completed should I send these around for review and inclusion  
 or do they not belong in phobos?
 2.) If I'm working on including these in phobos should I put them in  
 container.d (that has RedBlack Trees and a Singlelinked List) or is  
 there a better location?
 Rob

As far as I know, the reason why std.container is not under active development, is that phobos does not have an allocator abstraction yet. As soon as there is one, the module will probably undergo some breaking changes. But I think the more well implemented standard data structures there are in Phobos, the better. I think as soon as the standard allocator interface is settled on, your efforts will be welcome. Steve can probably answer your question better though.

Certainly more containers are welcome. The review for getting things into phobos is done via github. You do not need write permission to generate a pull request. Yes, they should all be put into std.container for now. I'd recommend doing one pull request per container, that way one container type does not detract from the inclusion of another. I don't think that lack of allocators should prevent implementing containers. My collection package (www.dsource.org/projects/dcollections) uses allocators, and they're pretty orthogonal to the operation of the container. BTW, feel free to use any ideas/code from dcollections, it's also boost licensed. Note that the red black tree implementation in phobos is copied verbatim from dcollections. If you implement a good AVL tree, I might even steal it for dcollections ;) (with attribution, of course!) -Steve

I recently had the need for a priority queue and your library was the obvious choice. But it did the same that my code did when I ported it from 32-bit to 64-bit: array.length is no longer a uint, but a ulong, so the code breaks. So my advice is to use size_t when you deal with a natural number that can be up to the amount of addressable memory.
Oct 24 2011
prev sibling next sibling parent Andrew Wiley <wiley.andrew.j gmail.com> writes:
--20cf303bff6099192004b0186dfd
Content-Type: text/plain; charset=ISO-8859-1

On Mon, Oct 24, 2011 at 9:50 PM, Marco Leise <Marco.Leise gmx.de> wrote:

 Am 14.09.2011, 18:57 Uhr, schrieb Steven Schveighoffer <
 schveiguy yahoo.com>:


  On Wed, 14 Sep 2011 12:50:25 -0400, Timon Gehr <timon.gehr gmx.ch> wrote:
  On 09/14/2011 04:08 PM, Robert McGinley wrote:
 Hey all,
 Mostly as an exercise I'm considering writing an ArrayList, AVL tree,
 and possible other standard data structures in D.  I have two questions.
 1.) If completed should I send these around for review and inclusion or
 do they not belong in phobos?
 2.) If I'm working on including these in phobos should I put them in
 container.d (that has RedBlack Trees and a Singlelinked List) or is there a
 better location?
 Rob

As far as I know, the reason why std.container is not under active development, is that phobos does not have an allocator abstraction yet. As soon as there is one, the module will probably undergo some breaking changes. But I think the more well implemented standard data structures there are in Phobos, the better. I think as soon as the standard allocator interface is settled on, your efforts will be welcome. Steve can probably answer your question better though.

Certainly more containers are welcome. The review for getting things into phobos is done via github. You do not need write permission to generate a pull request. Yes, they should all be put into std.container for now. I'd recommend doing one pull request per container, that way one container type does not detract from the inclusion of another. I don't think that lack of allocators should prevent implementing containers. My collection package (www.dsource.org/projects/** dcollections <http://www.dsource.org/projects/dcollections>) uses allocators, and they're pretty orthogonal to the operation of the container. BTW, feel free to use any ideas/code from dcollections, it's also boost licensed. Note that the red black tree implementation in phobos is copied verbatim from dcollections. If you implement a good AVL tree, I might even steal it for dcollections ;) (with attribution, of course!) -Steve

I recently had the need for a priority queue and your library was the obvious choice. But it did the same that my code did when I ported it from 32-bit to 64-bit: array.length is no longer a uint, but a ulong, so the code breaks. So my advice is to use size_t when you deal with a natural number that can be up to the amount of addressable memory.

Wait, dcollections has a PriorityQueue? You could use a tree for that, but my understanding is that a heap is much more efficient? --20cf303bff6099192004b0186dfd Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable <br><br><div class=3D"gmail_quote">On Mon, Oct 24, 2011 at 9:50 PM, Marco L= eise <span dir=3D"ltr">&lt;<a href=3D"mailto:Marco.Leise gmx.de">Marco.Leis= e gmx.de</a>&gt;</span> wrote:<br><blockquote class=3D"gmail_quote" style= =3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;"> Am 14.09.2011, 18:57 Uhr, schrieb Steven Schveighoffer &lt;<a href=3D"mailt= o:schveiguy yahoo.com" target=3D"_blank">schveiguy yahoo.com</a>&gt;:<div><= div></div><div class=3D"h5"><br> <br> <blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1p= x #ccc solid;padding-left:1ex"> On Wed, 14 Sep 2011 12:50:25 -0400, Timon Gehr &lt;<a href=3D"mailto:timon.= gehr gmx.ch" target=3D"_blank">timon.gehr gmx.ch</a>&gt; wrote:<br> <br> <blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1p= x #ccc solid;padding-left:1ex"> On 09/14/2011 04:08 PM, Robert McGinley wrote:<br> <blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1p= x #ccc solid;padding-left:1ex"> Hey all,<br> Mostly as an exercise I&#39;m considering writing an ArrayList, AVL tree, a= nd possible other standard data structures in D. =A0I have two questions.<b= r> 1.) If completed should I send these around for review and inclusion or do = they not belong in phobos?<br> 2.) If I&#39;m working on including these in phobos should I put them in co= ntainer.d (that has RedBlack Trees and a Singlelinked List) or is there a b= etter location?<br> Rob<br> </blockquote> <br> As far as I know, the reason why std.container is not under active developm= ent, is that phobos does not have an allocator abstraction yet. As soon as = there is one, the module will probably undergo some breaking changes. But I= think the more well implemented standard data structures there are in Phob= os, the better. I think as soon as the standard allocator interface is sett= led on, your efforts will be welcome. Steve can probably answer your questi= on better though.<br> </blockquote> <br> Certainly more containers are welcome.<br> <br> The review for getting things into phobos is done via github. =A0You do not= need write permission to generate a pull request. =A0Yes, they should all = be put into std.container for now.<br> <br> I&#39;d recommend doing one pull request per container, that way one contai= ner type does not detract from the inclusion of another.<br> <br> I don&#39;t think that lack of allocators should prevent implementing conta= iners. =A0My collection package (<a href=3D"http://www.dsource.org/projects= /dcollections" target=3D"_blank">www.dsource.org/projects/<u></u>dcollectio= ns</a>) uses allocators, and they&#39;re pretty orthogonal to the operation= of the container.<br> <br> BTW, feel free to use any ideas/code from dcollections, it&#39;s also boost= licensed. =A0Note that the red black tree implementation in phobos is copi= ed verbatim from dcollections. =A0If you implement a good AVL tree, I might= even steal it for dcollections ;) =A0(with attribution, of course!)<br> <br> -Steve<br> </blockquote> <br></div></div> I recently had the need for a priority queue and your library was the obvio= us choice. But it did the same that my code did when I ported it from 32-bi= t to 64-bit: array.length is no longer a uint, but a ulong, so the code bre= aks. So my advice is to use size_t when you deal with a natural number that= can be up to the amount of addressable memory.<br> </blockquote></div><br><div>Wait, dcollections has a PriorityQueue?</div><d= iv>You could use a tree for that, but my understanding is that a heap is mu= ch more efficient?</div> --20cf303bff6099192004b0186dfd--
Oct 24 2011
prev sibling next sibling parent Gor Gyolchanyan <gor.f.gyolchanyan gmail.com> writes:
I really REALLY miss a doubly-linked list. That's all i can think of
right now, which is missing from D's containers :-)

On Tue, Oct 25, 2011 at 9:00 AM, Andrew Wiley <wiley.andrew.j gmail.com> wr=
ote:
 On Mon, Oct 24, 2011 at 9:50 PM, Marco Leise <Marco.Leise gmx.de> wrote:
 Am 14.09.2011, 18:57 Uhr, schrieb Steven Schveighoffer
 <schveiguy yahoo.com>:

 On Wed, 14 Sep 2011 12:50:25 -0400, Timon Gehr <timon.gehr gmx.ch> wrot=



 On 09/14/2011 04:08 PM, Robert McGinley wrote:
 Hey all,
 Mostly as an exercise I'm considering writing an ArrayList, AVL tree,
 and possible other standard data structures in D. =A0I have two quest=





 1.) If completed should I send these around for review and inclusion =





 do they not belong in phobos?
 2.) If I'm working on including these in phobos should I put them in
 container.d (that has RedBlack Trees and a Singlelinked List) or is t=





 better location?
 Rob

As far as I know, the reason why std.container is not under active development, is that phobos does not have an allocator abstraction yet=




 soon as there is one, the module will probably undergo some breaking
 changes. But I think the more well implemented standard data structure=




 there are in Phobos, the better. I think as soon as the standard alloc=




 interface is settled on, your efforts will be welcome. Steve can proba=




 answer your question better though.

Certainly more containers are welcome. The review for getting things into phobos is done via github. =A0You do=



 need write permission to generate a pull request. =A0Yes, they should a=



 put into std.container for now.

 I'd recommend doing one pull request per container, that way one
 container type does not detract from the inclusion of another.

 I don't think that lack of allocators should prevent implementing
 containers. =A0My collection package (www.dsource.org/projects/dcollect=



 uses allocators, and they're pretty orthogonal to the operation of the
 container.

 BTW, feel free to use any ideas/code from dcollections, it's also boost
 licensed. =A0Note that the red black tree implementation in phobos is c=



 verbatim from dcollections. =A0If you implement a good AVL tree, I migh=



 steal it for dcollections ;) =A0(with attribution, of course!)

 -Steve

I recently had the need for a priority queue and your library was the obvious choice. But it did the same that my code did when I ported it fr=


 32-bit to 64-bit: array.length is no longer a uint, but a ulong, so the =


 breaks. So my advice is to use size_t when you deal with a natural numbe=


 that can be up to the amount of addressable memory.

Wait, dcollections has a PriorityQueue? You could use a tree for that, but my understanding is that a heap is muc=

 more efficient?

Oct 25 2011
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Mon, 24 Oct 2011 22:50:33 -0400, Marco Leise <Marco.Leise gmx.de> wrote:

 Am 14.09.2011, 18:57 Uhr, schrieb Steven Schveighoffer  
 <schveiguy yahoo.com>:

 On Wed, 14 Sep 2011 12:50:25 -0400, Timon Gehr <timon.gehr gmx.ch>  
 wrote:

 On 09/14/2011 04:08 PM, Robert McGinley wrote:
 Hey all,
 Mostly as an exercise I'm considering writing an ArrayList, AVL tree,  
 and possible other standard data structures in D.  I have two  
 questions.
 1.) If completed should I send these around for review and inclusion  
 or do they not belong in phobos?
 2.) If I'm working on including these in phobos should I put them in  
 container.d (that has RedBlack Trees and a Singlelinked List) or is  
 there a better location?
 Rob

As far as I know, the reason why std.container is not under active development, is that phobos does not have an allocator abstraction yet. As soon as there is one, the module will probably undergo some breaking changes. But I think the more well implemented standard data structures there are in Phobos, the better. I think as soon as the standard allocator interface is settled on, your efforts will be welcome. Steve can probably answer your question better though.

Certainly more containers are welcome. The review for getting things into phobos is done via github. You do not need write permission to generate a pull request. Yes, they should all be put into std.container for now. I'd recommend doing one pull request per container, that way one container type does not detract from the inclusion of another. I don't think that lack of allocators should prevent implementing containers. My collection package (www.dsource.org/projects/dcollections) uses allocators, and they're pretty orthogonal to the operation of the container. BTW, feel free to use any ideas/code from dcollections, it's also boost licensed. Note that the red black tree implementation in phobos is copied verbatim from dcollections. If you implement a good AVL tree, I might even steal it for dcollections ;) (with attribution, of course!) -Steve

I recently had the need for a priority queue and your library was the obvious choice. But it did the same that my code did when I ported it from 32-bit to 64-bit: array.length is no longer a uint, but a ulong, so the code breaks. So my advice is to use size_t when you deal with a natural number that can be up to the amount of addressable memory.

The latest (unreleased) version of dcollections uses size_t and ptrdiff_t everywhere instead of uint and int. See here: http://www.dsource.org/projects/dcollections/ticket/14 I have to release a new beta soon, especially when inout works in the latest impending compiler release. -Steve
Oct 26 2011
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Tue, 25 Oct 2011 01:00:51 -0400, Andrew Wiley  
<wiley.andrew.j gmail.com> wrote:

 On Mon, Oct 24, 2011 at 9:50 PM, Marco Leise <Marco.Leise gmx.de> wrote:

 Am 14.09.2011, 18:57 Uhr, schrieb Steven Schveighoffer <
 schveiguy yahoo.com>:


  On Wed, 14 Sep 2011 12:50:25 -0400, Timon Gehr <timon.gehr gmx.ch>  
 wrote:
  On 09/14/2011 04:08 PM, Robert McGinley wrote:
 Hey all,
 Mostly as an exercise I'm considering writing an ArrayList, AVL tree,
 and possible other standard data structures in D.  I have two  
 questions.
 1.) If completed should I send these around for review and inclusion  
 or
 do they not belong in phobos?
 2.) If I'm working on including these in phobos should I put them in
 container.d (that has RedBlack Trees and a Singlelinked List) or is  
 there a
 better location?
 Rob

As far as I know, the reason why std.container is not under active development, is that phobos does not have an allocator abstraction yet. As soon as there is one, the module will probably undergo some breaking changes. But I think the more well implemented standard data structures there are in Phobos, the better. I think as soon as the standard allocator interface is settled on, your efforts will be welcome. Steve can probably answer your question better though.

Certainly more containers are welcome. The review for getting things into phobos is done via github. You do not need write permission to generate a pull request. Yes, they should all be put into std.container for now. I'd recommend doing one pull request per container, that way one container type does not detract from the inclusion of another. I don't think that lack of allocators should prevent implementing containers. My collection package (www.dsource.org/projects/** dcollections <http://www.dsource.org/projects/dcollections>) uses allocators, and they're pretty orthogonal to the operation of the container. BTW, feel free to use any ideas/code from dcollections, it's also boost licensed. Note that the red black tree implementation in phobos is copied verbatim from dcollections. If you implement a good AVL tree, I might even steal it for dcollections ;) (with attribution, of course!) -Steve

I recently had the need for a priority queue and your library was the obvious choice. But it did the same that my code did when I ported it from 32-bit to 64-bit: array.length is no longer a uint, but a ulong, so the code breaks. So my advice is to use size_t when you deal with a natural number that can be up to the amount of addressable memory.

Wait, dcollections has a PriorityQueue?

No. Not yet.
 You could use a tree for that, but my understanding is that a heap is  
 much
 more efficient?

Yes. I have a feeling dcollections will use heap from phobos (to avoid duplication) for a full priority queue. -Steve
Oct 26 2011
prev sibling next sibling parent "Marco Leise" <Marco.Leise gmx.de> writes:
 You could use a tree for that, but my understanding is that a heap is  
 much
 more efficient?

Yes. I have a feeling dcollections will use heap from phobos (to avoid duplication) for a full priority queue. -Steve

I tried a Fibonacci tree. It didn't beat the good old array based priority queue. And the more I read about garbage collection and CPU L1/L2 caches, my understanding is that packed arrays and indexes are the best choice if the amount of data is not too much. I did a test with a circular linked list. As long as it is correctly ordered in memory, the CPU is able to prefetch everything into L1 by the time the next pointer is read, independent of the byte count. It could be a few KB up to a GB. But when I randomly reordered the locations of the list nodes in memory it was up to 80x slower for the cases from several MB on. It only stayed fast as long as the complete data fit into the L1 cache. So what I learned from that is to avoid pointers to memory outside the current allocation block and to use a ushort now and then where appropriate ^^. I hope these didn't get slower on amd64.
Nov 01 2011
prev sibling parent "Marco Leise" <Marco.Leise gmx.de> writes:
Am 26.10.2011, 16:00 Uhr, schrieb Steven Schveighoffer  
<schveiguy yahoo.com>:

 On Mon, 24 Oct 2011 22:50:33 -0400, Marco Leise <Marco.Leise gmx.de>  
 wrote:

 Am 14.09.2011, 18:57 Uhr, schrieb Steven Schveighoffer  
 <schveiguy yahoo.com>:

 On Wed, 14 Sep 2011 12:50:25 -0400, Timon Gehr <timon.gehr gmx.ch>  
 wrote:

 On 09/14/2011 04:08 PM, Robert McGinley wrote:
 Hey all,
 Mostly as an exercise I'm considering writing an ArrayList, AVL  
 tree, and possible other standard data structures in D.  I have two  
 questions.
 1.) If completed should I send these around for review and inclusion  
 or do they not belong in phobos?
 2.) If I'm working on including these in phobos should I put them in  
 container.d (that has RedBlack Trees and a Singlelinked List) or is  
 there a better location?
 Rob

As far as I know, the reason why std.container is not under active development, is that phobos does not have an allocator abstraction yet. As soon as there is one, the module will probably undergo some breaking changes. But I think the more well implemented standard data structures there are in Phobos, the better. I think as soon as the standard allocator interface is settled on, your efforts will be welcome. Steve can probably answer your question better though.

Certainly more containers are welcome. The review for getting things into phobos is done via github. You do not need write permission to generate a pull request. Yes, they should all be put into std.container for now. I'd recommend doing one pull request per container, that way one container type does not detract from the inclusion of another. I don't think that lack of allocators should prevent implementing containers. My collection package (www.dsource.org/projects/dcollections) uses allocators, and they're pretty orthogonal to the operation of the container. BTW, feel free to use any ideas/code from dcollections, it's also boost licensed. Note that the red black tree implementation in phobos is copied verbatim from dcollections. If you implement a good AVL tree, I might even steal it for dcollections ;) (with attribution, of course!) -Steve

I recently had the need for a priority queue and your library was the obvious choice. But it did the same that my code did when I ported it from 32-bit to 64-bit: array.length is no longer a uint, but a ulong, so the code breaks. So my advice is to use size_t when you deal with a natural number that can be up to the amount of addressable memory.

The latest (unreleased) version of dcollections uses size_t and ptrdiff_t everywhere instead of uint and int. See here: http://www.dsource.org/projects/dcollections/ticket/14 I have to release a new beta soon, especially when inout works in the latest impending compiler release. -Steve

Ah that's good to know. I've gotten into writing my own containers now though. :) It is a good playground to learn some aspects of D as well.
Nov 01 2011