On Tue, 25 Oct 2011 01:00:51 -0400, Andrew Wiley
<[email protected]> wrote:
On Mon, Oct 24, 2011 at 9:50 PM, Marco Leise <[email protected]> wrote:
Am 14.09.2011, 18:57 Uhr, schrieb Steven Schveighoffer <
[email protected]>:
On Wed, 14 Sep 2011 12:50:25 -0400, Timon Gehr <[email protected]>
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
