Re: Collections question

[deadalnix via Digitalmars-d]

On Wednesday, 2 December 2015 at 15:58:19 UTC, Andrei 
Alexandrescu wrote:

On 12/02/2015 01:45 AM, deadalnix wrote:
On Tuesday, 1 December 2015 at 17:27:20 UTC, Andrei 
Alexandrescu wrote:
Ah, the good old assignment to reference. We need to prevent 
that from

happening in safe code. Got any fresh ideas? -- Andrei


Disable owner when borrowing 'mutably', and not when borrowing 
'constly'.


What does "disable owner" mean? Thx! -- Andrei


I mean you can't use it for the lifetime of the borrowing.

Re: Collections question

[Marc Schütz via Digitalmars-d]

On Wednesday, 2 December 2015 at 15:58:19 UTC, Andrei 
Alexandrescu wrote:

On 12/02/2015 01:45 AM, deadalnix wrote:
On Tuesday, 1 December 2015 at 17:27:20 UTC, Andrei 
Alexandrescu wrote:
Ah, the good old assignment to reference. We need to prevent 
that from

happening in safe code. Got any fresh ideas? -- Andrei


Disable owner when borrowing 'mutably', and not when borrowing 
'constly'.


What does "disable owner" mean? Thx! -- Andrei


(He probably means: The owner is the object to which the 
reference points. Disabling means disallowing any access to it, 
at compile time.)


But your question gave me another idea: Instead of making the 
owner const, the compiler can insert calls to `owner.opFreeze()` 
and `owner.opThaw()` at the beginning/end of each borrowing, and 
leave the owner mutable. It's then up to the implementer to 
handle things in a way they like. For example, opFreeze() could 
just set a flag and assert that the underlying memory isn't freed 
during borrowing, or it could increment/decrement a reference 
count, or it could queue up any releases of the underlying 
storage to happen after the last borrow has expired (the idea you 
proposed as a solution for RCArray).


It's helpful in this case if the operators have the following 
signatures:


T opFreeze();
void opThaw(T cookie);

For the refcounting solution, opFreeze() can increment the 
refcount and return a pointer to it, and opThaw() can decrement 
it again. The methods need to be called each time a borrow 
starts/ends.

Re: Collections question

[Andrei Alexandrescu via Digitalmars-d]

On 12/02/2015 01:45 AM, deadalnix wrote:

On Tuesday, 1 December 2015 at 17:27:20 UTC, Andrei Alexandrescu wrote:

Ah, the good old assignment to reference. We need to prevent that from
happening in safe code. Got any fresh ideas? -- Andrei


Disable owner when borrowing 'mutably', and not when borrowing 'constly'.


What does "disable owner" mean? Thx! -- Andrei

Re: Collections question

[Marc Schütz via Digitalmars-d]

On Wednesday, 2 December 2015 at 06:45:33 UTC, deadalnix wrote:
On Tuesday, 1 December 2015 at 17:27:20 UTC, Andrei 
Alexandrescu wrote:
Ah, the good old assignment to reference. We need to prevent 
that from happening in safe code. Got any fresh ideas? -- 
Andrei


Disable owner when borrowing 'mutably', and not when borrowing 
'constly'.


Making it const is enough, it doesn't need to be disabled 
completely. (Except if you want to go full Rust with uniqueness 
etc.)


Maybe there's a way to relax it further. Not all modifications of 
the owner are necessarily bad... If we limit the restriction to 
types with indirections (or types with destructors?), and only 
apply it in @safe functions, this might not even break much code. 
I suspect that almost all @trusted code, and probably most @safe 
code, will already be written in a way that conforms to the new 
rules.

Re: Collections question

[ZombineDev via Digitalmars-d]

On Wednesday, 2 December 2015 at 06:45:33 UTC, deadalnix wrote:
On Tuesday, 1 December 2015 at 17:27:20 UTC, Andrei 
Alexandrescu wrote:
Ah, the good old assignment to reference. We need to prevent 
that from happening in safe code. Got any fresh ideas? -- 
Andrei


Disable owner when borrowing 'mutably', and not when borrowing 
'constly'.


+1

Re: Collections question

[deadalnix via Digitalmars-d]

On Tuesday, 1 December 2015 at 17:27:20 UTC, Andrei Alexandrescu 
wrote:
Ah, the good old assignment to reference. We need to prevent 
that from happening in safe code. Got any fresh ideas? -- Andrei


Disable owner when borrowing 'mutably', and not when borrowing 
'constly'.

Re: Collections question

[Andrei Alexandrescu via Digitalmars-d]

On 12/01/2015 09:35 AM, Marc Schütz wrote:

On Tuesday, 1 December 2015 at 14:15:47 UTC, Andrei Alexandrescu wrote:

On 12/1/15 4:55 AM, Marc Schütz wrote:

On Monday, 30 November 2015 at 18:18:38 UTC, Andrei Alexandrescu wrote:

* The one matter with the value/RefCounted approach is that RefCounted
cannot be made @safe.


That's just as true for internal refcounting.


I don't think that's the case. The way I wrote code, safety can be
achieved with a few controlled insertions of @trusted. -- Andrei


As long as you can pass the container and one of it's elements by
mutable ref, it's unsafe (see the RCArray discussion [1]). If you can
only access the elements by value (i.e. opIndex returns a copy), this
precondition isn't fulfilled, but otherwise, I see no way to prevent it
with the current language.

[1] http://forum.dlang.org/post/huspgmeupgobjubts...@forum.dlang.org


Ah, the good old assignment to reference. We need to prevent that from 
happening in safe code. Got any fresh ideas? -- Andrei

Re: Collections question

[Marc Schütz via Digitalmars-d]

On Tuesday, 1 December 2015 at 14:15:47 UTC, Andrei Alexandrescu 
wrote:

On 12/1/15 4:55 AM, Marc Schütz wrote:
On Monday, 30 November 2015 at 18:18:38 UTC, Andrei 
Alexandrescu wrote:
* The one matter with the value/RefCounted approach is that 
RefCounted

cannot be made @safe.


That's just as true for internal refcounting.


I don't think that's the case. The way I wrote code, safety can 
be achieved with a few controlled insertions of @trusted. -- 
Andrei


As long as you can pass the container and one of it's elements by 
mutable ref, it's unsafe (see the RCArray discussion [1]). If you 
can only access the elements by value (i.e. opIndex returns a 
copy), this precondition isn't fulfilled, but otherwise, I see no 
way to prevent it with the current language.


[1] 
http://forum.dlang.org/post/huspgmeupgobjubts...@forum.dlang.org

Re: Collections question

[Andrei Alexandrescu via Digitalmars-d]

On 12/1/15 4:55 AM, Marc Schütz wrote:

On Monday, 30 November 2015 at 18:18:38 UTC, Andrei Alexandrescu wrote:

* The one matter with the value/RefCounted approach is that RefCounted
cannot be made @safe.


That's just as true for internal refcounting.


I don't think that's the case. The way I wrote code, safety can be 
achieved with a few controlled insertions of @trusted. -- Andrei

Re: Collections question

[Marc Schütz via Digitalmars-d]

On Monday, 30 November 2015 at 18:18:38 UTC, Andrei Alexandrescu 
wrote:
* The one matter with the value/RefCounted approach is that 
RefCounted cannot be made @safe.


That's just as true for internal refcounting.

Re: Collections question

[Andrei Alexandrescu via Digitalmars-d]

On 11/30/2015 12:56 PM, bitwise wrote:

On Saturday, 28 November 2015 at 13:39:35 UTC, Andrei Alexandrescu wrote:

On 11/28/15 1:59 AM, bitwise wrote:


Classes/real-ref-types dont act as you're describing, so why should
these fake struct wrapper ref things act this way? This will likely
achieve the exact opposite of what you're aiming for, by making
something that's supposed to act like a reference type have different
behaviour from D's built in ref types.


So what would work for you? -- Andrei


Sorry if that response seemed a tad flippant, but I have to be
honest...I am completely against this design...to put it mildly.

I have my own containers to use, but on top of the fact that I would
prefer something which is collaboratively maintained, I don't want to be
forced to deal with, or support these "reference" containers, which will
most likely happen if they get added to Phobos.

I'm really not sure where to begin tearing this idea apart. The
principal I have a problem with is much more fundamental than this one
decision. In general, there is a lot in D that is very hackish.

I understand that you don't want eager copying of containers, but when I
way predictability, simplicity, clarity, and flexibility against that
concern, there is no way I'm agreeing with you, when you can simply wrap
a proper container in a RefCounted(T) or something. A class is a
reference type, and a struct is a value type. If a user sees a struct,
they should expect a value type which will copy on assign, and if they
see a class, they should expect a reference. In D, the differentiation
between value and reference types is clearly specified, and D users
_should_ be, and should be expected to be, aware of it.

If you really want reference containers, they should be implemented
either as value-type structs, or classes that can work with
RefCounted(T). Baking the reference count directly into the container is
limiting, and buys nothing. I really don't see a problem with GC'ed
classes if you really want reference types. It's going to be forever, if
ever before you can actually turn off the GC when using Phobos. At
least, if it's a class, you can use Scoped(T), or RefCounted(T) on
it...assuming RefCounted(T) is fixed up to work with classes at some
point, which seems like a better path then baking ref counting into a
container implementation.

I'm feeling a bit repetitive at this point, and wondering if I should
have responded to this at all, and I'm sure you know exactly what I'm
talking about, and that it's a matter of choice at this point, but there
you have it.


Thanks, your response is appreciated! Let me make sure I understand. So, 
in your opinion:


* Value containers plus a way to wrap them with RefCounted is a better 
solution than containers with built-in reference semantics.


* The design supported by D most naturally is: classes have reference 
semantics and structs have value semantics.


* Reference semantics for containers seem to work best with GC. Pursuing 
reference containers with baked-in RC seems nonproductive.


This is all sensible. Here are a couple of follow-up questions and 
considerations:


* I couldn't integrate this with the rest of your post: "The principal I 
have a problem with is much more fundamental than this one decision. In 
general, there is a lot in D that is very hackish." Could you please 
elaborate?


* The one matter with the value/RefCounted approach is that RefCounted 
cannot be made @safe. One core design decision I made was to aim for 
safe containers. I do agree that if safety is off the table, your design 
would be a very good choice (probably the best I can think of, and I'd 
start an implementation using it).



Thanks,

Andrei

Re: Collections question

[bitwise via Digitalmars-d]

On Saturday, 28 November 2015 at 13:39:35 UTC, Andrei 
Alexandrescu wrote:

On 11/28/15 1:59 AM, bitwise wrote:


Classes/real-ref-types dont act as you're describing, so why 
should
these fake struct wrapper ref things act this way? This will 
likely

achieve the exact opposite of what you're aiming for, by making
something that's supposed to act like a reference type have 
different

behaviour from D's built in ref types.


So what would work for you? -- Andrei


Sorry if that response seemed a tad flippant, but I have to be 
honest...I am completely against this design...to put it mildly.


I have my own containers to use, but on top of the fact that I 
would prefer something which is collaboratively maintained, I 
don't want to be forced to deal with, or support these 
"reference" containers, which will most likely happen if they get 
added to Phobos.


I'm really not sure where to begin tearing this idea apart. The 
principal I have a problem with is much more fundamental than 
this one decision. In general, there is a lot in D that is very 
hackish.


I understand that you don't want eager copying of containers, but 
when I way predictability, simplicity, clarity, and flexibility 
against that concern, there is no way I'm agreeing with you, when 
you can simply wrap a proper container in a RefCounted(T) or 
something. A class is a reference type, and a struct is a value 
type. If a user sees a struct, they should expect a value type 
which will copy on assign, and if they see a class, they should 
expect a reference. In D, the differentiation between value and 
reference types is clearly specified, and D users _should_ be, 
and should be expected to be, aware of it.


If you really want reference containers, they should be 
implemented either as value-type structs, or classes that can 
work with RefCounted(T). Baking the reference count directly into 
the container is limiting, and buys nothing. I really don't see a 
problem with GC'ed classes if you really want reference types. 
It's going to be forever, if ever before you can actually turn 
off the GC when using Phobos. At least, if it's a class, you can 
use Scoped(T), or RefCounted(T) on it...assuming RefCounted(T) is 
fixed up to work with classes at some point, which seems like a 
better path then baking ref counting into a container 
implementation.


I'm feeling a bit repetitive at this point, and wondering if I 
should have responded to this at all, and I'm sure you know 
exactly what I'm talking about, and that it's a matter of choice 
at this point, but there you have it.


Bit

Re: Collections question

[Steven Schveighoffer via Digitalmars-d]

On 11/30/15 11:21 AM, Tobias Pankrath wrote:

On Monday, 30 November 2015 at 16:06:43 UTC, Steven Schveighoffer wrote:

MyCollection!(int) c1;
auto c2 = c1;
c1 ~= 1;

assert(c2.contains(1)); // pass? fail?

BTW, I third Jonathan's and Timon's suggestion -- go with an external
factory function. Use IFTI to its fullest!


That should throw, because you're using an uninitialised reference (c1).
It's the equivalent to:

Class C { .. }

C c1;
C c2 = c1;
c1.foo(); // call via nullptr

Or it needs to pass, but that's probably not worth it.


It means such a collection won't operate in the same way that 
associative arrays do.


If that's the case, I'm OK with that.

Technically, a wrapper could be constructed that performed the "lazy 
creation".


But my point to Andrei was that the functions he suggests don't actually 
address the "oddity" of copying AAs. Addressing it, if it's done in the 
way you say, is as simple as not worrying about null pointers.


-Steve

Re: Collections question

[Tobias Pankrath via Digitalmars-d]

On Monday, 30 November 2015 at 16:06:43 UTC, Steven Schveighoffer 
wrote:

MyCollection!(int) c1;
auto c2 = c1;
c1 ~= 1;

assert(c2.contains(1)); // pass? fail?

BTW, I third Jonathan's and Timon's suggestion -- go with an 
external factory function. Use IFTI to its fullest!


-Steve


That should throw, because you're using an uninitialised 
reference (c1). It's the equivalent to:


Class C { .. }

C c1;
C c2 = c1;
c1.foo(); // call via nullptr

Or it needs to pass, but that's probably not worth it.

Re: Collections question

[Steven Schveighoffer via Digitalmars-d]

On 11/27/15 3:14 PM, Andrei Alexandrescu wrote:

There's this oddity of built-in hash tables: a reference to a non-empty
hash table can be copied and then both references refer to the same hash
table object. However, if the hash table is null, copying the reference
won't track the same object later on.

Fast-forward to general collections. If we want to support things like
reference containers, clearly that oddity must be addressed. There are
two typical approaches:

1. Factory function:

struct MyCollection(T)
{
 static MyCollection make(U...)(auto ref U args);
 ...
}

So then client code is:

auto c1 = MyCollection!(int).make(1, 2, 3);
auto c2 = MyCollection!(int).make();
auto c3 = c2; // refers to the same collection as c2

2. The opCall trick:

struct MyCollection(T)
{
 static MyCollection opCall(U...)(auto ref U args);
 ...
}

with the client code:

auto c1 = MyCollection!(int)(1, 2, 3);
auto c2 = MyCollection!(int)();
auto c3 = c2; // refers to the same collection as c2

There's some experience in various libraries with both approaches. Which
would you prefer?


How do you prevent the AA behavior? In other words, what happens here:

MyCollection!(int) c1;
auto c2 = c1;
c1 ~= 1;

assert(c2.contains(1)); // pass? fail?

BTW, I third Jonathan's and Timon's suggestion -- go with an external 
factory function. Use IFTI to its fullest!


-Steve

Re: Collections question

[Jonathan M Davis via Digitalmars-d]

On Sunday, 29 November 2015 at 15:06:49 UTC, Andrei Alexandrescu 
wrote:

Thanks all. I'll go with the factory function. -- Andrei


As Timon suggested, I'd encourage you to go for a free factory 
function named after the container like RedBlackTree does with 
redBlackTree rather than having a static factory function, since 
it's less verbose and allows for type inference, though there's 
no reason why we couldn't have both:


auto c1 = MyCollection!int.make(1, 2, 3);
auto c2 = myCollection!int(1, 2, 3);
auto c3 = myCollection(1, 2, 3);

Regardless, it's better to avoid static opCall.

- Jonathan M Davis

Re: Collections question

[Andrei Alexandrescu via Digitalmars-d]

On 11/29/15 5:06 AM, Atila Neves wrote:

On Friday, 27 November 2015 at 20:14:21 UTC, Andrei Alexandrescu wrote:

There's this oddity of built-in hash tables: a reference to a
non-empty hash table can be copied and then both references refer to
the same hash table object. However, if the hash table is null,
copying the reference won't track the same object later on.

[...]


static opCAll is just confusing IMHO. Factory function please.


Thanks all. I'll go with the factory function. -- Andrei

Re: Collections question

[Atila Neves via Digitalmars-d]

On Friday, 27 November 2015 at 20:14:21 UTC, Andrei Alexandrescu 
wrote:
There's this oddity of built-in hash tables: a reference to a 
non-empty hash table can be copied and then both references 
refer to the same hash table object. However, if the hash table 
is null, copying the reference won't track the same object 
later on.


[...]


static opCAll is just confusing IMHO. Factory function please.

Atila

Re: Collections question

[Jakob Ovrum via Digitalmars-d]

On Saturday, 28 November 2015 at 13:41:10 UTC, Andrei 
Alexandrescu wrote:

On 11/28/15 2:26 AM, Jakob Ovrum wrote:
Another thing: wouldn't providing a custom allocator require a 
separate

primitive?


All collections will work with IAllocator. -- Andrei


Yes, I assumed as much. So how would this be handled? Is this not 
a relevant question to the construction issue?

Re: Collections question

[Jonathan M Davis via Digitalmars-d]

On Saturday, 28 November 2015 at 12:20:36 UTC, Timon Gehr wrote:

3. (Non-internal) factory function:

auto c1 = myCollection(1,2,3);
auto c2 = myCollection!int();
auto c3 = c2; // refers to the same collection as c2


Yeah. In general, I prefer that approach. It's what we currently 
do with RedBlackTree. It's more flexible (e.g. it can infer the 
element type like we do with dynamic arrays) and less verbose. 
The only downside that I can think of is that it doesn't work as 
well in generic code that's creating a container (as in where the 
container type is a template argument), but that's not something 
that's done normally. And if the factory function is just making 
using templated constructors cleaner, then generic code that's 
constructing such a container can still use the constructors. It 
just wouldn't be as nice as using the factory function.


But for almost all cases, a non-internal factory function named 
after the container is less verbose and more flexible.


- Jonathan M Davis

Re: Collections question

[Kagamin via Digitalmars-d]

On Saturday, 28 November 2015 at 18:43:33 UTC, Adam D. Ruppe 
wrote:

On Saturday, 28 November 2015 at 18:38:37 UTC, Kagamin wrote:

Well... doesn't work: http://dpaste.dzfl.pl/2c69cc3584b8


I don't understand... of course you can't call what is returned 
by makeEmpty.


Recently someone complained that it was a mistake to use round 
braces for template syntax. I noticed it too, that sometimes it's 
hard to tell where's template instantiation and where is function 
invocation.

Re: Collections question

[Adam D. Ruppe via Digitalmars-d]

On Saturday, 28 November 2015 at 18:38:37 UTC, Kagamin wrote:

Well... doesn't work: http://dpaste.dzfl.pl/2c69cc3584b8


I don't understand... of course you can't call what is returned 
by makeEmpty.

Re: Collections question

[Kagamin via Digitalmars-d]

On Saturday, 28 November 2015 at 06:26:03 UTC, Jakob Ovrum wrote:
On Friday, 27 November 2015 at 20:25:12 UTC, Adam D. Ruppe 
wrote:
That syntax is the same as constructors... if that's what you 
want it to look like, we ought to actually use a constructor 
for all but the zero-argument ones which I'd use a static 
named function for (perhaps .make or perhaps .makeEmpty too)


While I think this would be nice and explicit, it's bad for 
generic code, which would have to specialize to correctly call 
the nullary version.


Well... doesn't work: http://dpaste.dzfl.pl/2c69cc3584b8

Re: Collections question

[Andrei Alexandrescu via Digitalmars-d]

On 11/28/15 2:26 AM, Jakob Ovrum wrote:

Another thing: wouldn't providing a custom allocator require a separate
primitive?


All collections will work with IAllocator. -- Andrei

Re: Collections question

[Andrei Alexandrescu via Digitalmars-d]

On 11/28/15 1:59 AM, bitwise wrote:


Classes/real-ref-types dont act as you're describing, so why should
these fake struct wrapper ref things act this way? This will likely
achieve the exact opposite of what you're aiming for, by making
something that's supposed to act like a reference type have different
behaviour from D's built in ref types.


So what would work for you? -- Andrei

Re: Collections question

[Sebastiaan Koppe via Digitalmars-d]

On Friday, 27 November 2015 at 20:14:21 UTC, Andrei Alexandrescu 
wrote:

1. Factory function:
2. The opCall trick:


1. Factory

Shouldn't opCall be used when you want something to (only) behave 
as a function? E.g. functors.

Re: Collections question

[Timon Gehr via Digitalmars-d]

On 11/27/2015 09:14 PM, Andrei Alexandrescu wrote:

There's this oddity of built-in hash tables: a reference to a non-empty
hash table can be copied and then both references refer to the same hash
table object. However, if the hash table is null, copying the reference
won't track the same object later on.

Fast-forward to general collections. If we want to support things like
reference containers, clearly that oddity must be addressed. There are
two typical approaches:

1. Factory function:
...

2. The opCall trick:
...



3. (Non-internal) factory function:

auto c1 = myCollection(1,2,3);
auto c2 = myCollection!int();
auto c3 = c2; // refers to the same collection as c2

Re: Collections question

[Tobias Pankrath via Digitalmars-d]

On Friday, 27 November 2015 at 20:14:21 UTC, Andrei Alexandrescu 
wrote:
There's this oddity of built-in hash tables: a reference to a 
non-empty hash table can be copied and then both references 
refer to the same hash table object. However, if the hash table 
is null, copying the reference won't track the same object 
later on.


Fast-forward to general collections. [...]

Andrei


I'd prefer the factory method and we shouldn't allow lazy 
initialization. That's only confusing, if it sometimes works and 
sometimes won't work. Null container should throw.

Re: Collections question

[default0 via Digitalmars-d]

On Friday, 27 November 2015 at 20:14:21 UTC, Andrei Alexandrescu 
wrote:
There's this oddity of built-in hash tables: a reference to a 
non-empty hash table can be copied and then both references 
refer to the same hash table object. However, if the hash table 
is null, copying the reference won't track the same object 
later on.


Fast-forward to general collections. If we want to support 
things like reference containers, clearly that oddity must be 
addressed. There are two typical approaches:


1. Factory function:

struct MyCollection(T)
{
static MyCollection make(U...)(auto ref U args);
...
}

So then client code is:

auto c1 = MyCollection!(int).make(1, 2, 3);
auto c2 = MyCollection!(int).make();
auto c3 = c2; // refers to the same collection as c2

2. The opCall trick:

struct MyCollection(T)
{
static MyCollection opCall(U...)(auto ref U args);
...
}

with the client code:

auto c1 = MyCollection!(int)(1, 2, 3);
auto c2 = MyCollection!(int)();
auto c3 = c2; // refers to the same collection as c2

There's some experience in various libraries with both 
approaches. Which would you prefer?



Andrei


This is probably naive and silly, but: can't you just put a dummy 
element in the hash table on creation of the struct, set a flag 
"containsDummyElement" and then have all methods you implement 
from that struct (count, range implementation, etc) check that 
flag and ignore the one element it contains when the flag is set? 
Then when the first real element gets added, just remove the 
element and reset the flag. When the last element gets removed, 
put the dummy element back.


I feel like I'm either misunderstanding the problem or 
misunderstanding built-in associative arrays, so sorry if what I 
said above is really stupid and cannot (or should not) be done 
for reasons everyone else here knows about.

Re: Collections question

[Dicebot via Digitalmars-d]

Factory please. Static opCall has always been nothing but trouble 
in my experience.

Re: Collections question

[Jakob Ovrum via Digitalmars-d]

On Friday, 27 November 2015 at 20:14:21 UTC, Andrei Alexandrescu 
wrote:
There's some experience in various libraries with both 
approaches. Which would you prefer?


Another thing: wouldn't providing a custom allocator require a 
separate primitive? I am assuming that the allocator type won't 
be a template parameter, or at least that it will support 
IAllocator.


alias Allocator = ...; // some std.allocator type

Allocator alloc;

// empty collection of int with user-specified allocator
auto c = Collection!int.makeCustomAllocation(alloc);

// collection of one allocator using theAllocator
auto c = Collection!Allocator.make(alloc);

// empty collection of Allocator with user-specified allocator
auto c = Collection!Allocator.makeCustomAllocation(alloc);

The last two don't look like they could use the same name. A way 
around this would be to forego variadic construction in favour of 
range construction, but it would necessitate copying of those 
elements, whether with `only` or putting in an array etc.


If we need two names, then opCall becomes less attractive.

Re: Collections question

[Jakob Ovrum via Digitalmars-d]

On Saturday, 28 November 2015 at 06:59:35 UTC, bitwise wrote:

Classes/real-ref-types dont act as you're describing


They do, actually.

class Collection(E) { ... }

Collection!E a; // null reference
auto b = new Collection!E(); // reference to empty collection

The only outlier is the associative array, which lazily 
initializes when operations are performed on null references.

Re: Collections question

[Jakob Ovrum via Digitalmars-d]

On Friday, 27 November 2015 at 20:14:21 UTC, Andrei Alexandrescu 
wrote:
There's some experience in various libraries with both 
approaches. Which would you prefer?


Well, I think we should recognize that they're the same thing but 
with different names. I don't have a strong preference for 
either, but I think the opCall approach might invite questions 
like "why is T t; different from auto t = T(); with this 
collection type?".


The current container library's `make` function has a neat 
feature (well, I'm biased here) where the element type doesn't 
have to be specified when construction arguments are provided:


auto arr = make!Array(1, 2, 3); // element type inferred to be 
`int`

auto arr = make!Array([42]); // Also for range construction

Naturally this doesn't work with nullary construction, but I 
think it's worth mentioning because this is not nearly as 
practical with static member functions. Of course the current 
model is not usable as-is because `make` uses an ugly hack when 
"making" empty struct containers.

Re: Collections question

[bitwise via Digitalmars-d]

On Friday, 27 November 2015 at 20:14:21 UTC, Andrei Alexandrescu 
wrote:
There's this oddity of built-in hash tables: a reference to a 
non-empty hash table can be copied and then both references 
refer to the same hash table object. However, if the hash table 
is null, copying the reference won't track the same object 
later on.


Fast-forward to general collections. If we want to support 
things like reference containers, clearly that oddity must be 
addressed. There are two typical approaches:


1. Factory function:

struct MyCollection(T)
{
static MyCollection make(U...)(auto ref U args);
...
}

So then client code is:

auto c1 = MyCollection!(int).make(1, 2, 3);
auto c2 = MyCollection!(int).make();
auto c3 = c2; // refers to the same collection as c2

2. The opCall trick:

struct MyCollection(T)
{
static MyCollection opCall(U...)(auto ref U args);
...
}

with the client code:

auto c1 = MyCollection!(int)(1, 2, 3);
auto c2 = MyCollection!(int)();
auto c3 = c2; // refers to the same collection as c2

There's some experience in various libraries with both 
approaches. Which would you prefer?



Andrei


Classes/real-ref-types dont act as you're describing, so why 
should these fake struct wrapper ref things act this way? This 
will likely achieve the exact opposite of what you're aiming for, 
by making something that's supposed to act like a reference type 
have different behaviour from D's built in ref types.


Bit

Re: Collections question

[Jakob Ovrum via Digitalmars-d]

On Friday, 27 November 2015 at 20:25:12 UTC, Adam D. Ruppe wrote:
That syntax is the same as constructors... if that's what you 
want it to look like, we ought to actually use a constructor 
for all but the zero-argument ones which I'd use a static named 
function for (perhaps .make or perhaps .makeEmpty too)


While I think this would be nice and explicit, it's bad for 
generic code, which would have to specialize to correctly call 
the nullary version.

Re: Collections question

[Luís Marques via Digitalmars-d]

On Friday, 27 November 2015 at 20:14:21 UTC, Andrei Alexandrescu 
wrote:
There's this oddity of built-in hash tables: a reference to a 
non-empty hash table can be copied and then both references 
refer to the same hash table object. However, if the hash table 
is null, copying the reference won't track the same object 
later on.


I keep hoping that that design decision would be changed...


1. Factory function:


Something I find deeply unsatisfying about D structs is their 
inability to reliably set non-trivial invariants, due to the lack 
of custom default ctors. If you are careful, you @disable this(), 
and provide a factory function that sets the invariant. But then, 
you aren't doing much more than renaming this() to make() or 
whatever. The issues with .init could be addressed without 
prohibiting a default ctor...

Re: Collections question

[Adam D. Ruppe via Digitalmars-d]

On Friday, 27 November 2015 at 20:14:21 UTC, Andrei Alexandrescu 
wrote:

1. Factory function:


This is my preference for zero arg at least because the opCall 
thing is commonly misunderstood and confused with C++ default 
construction and we don't need to encourage that.



static MyCollection opCall(U...)(auto ref U args);
auto c1 = MyCollection!(int)(1, 2, 3);


That syntax is the same as constructors... if that's what you 
want it to look like, we ought to actually use a constructor for 
all but the zero-argument ones which I'd use a static named 
function for (perhaps .make or perhaps .makeEmpty too)


But the opCall in cases where it conflicts with constructors 
ought to be discouraged.

Re: Collections question

[Minas Mina via Digitalmars-d]

On Friday, 27 November 2015 at 20:14:21 UTC, Andrei Alexandrescu 
wrote:
There's this oddity of built-in hash tables: a reference to a 
non-empty hash table can be copied and then both references 
refer to the same hash table object. However, if the hash table 
is null, copying the reference won't track the same object 
later on.


[...]


2, The opCall() one.

Collections question

[Andrei Alexandrescu via Digitalmars-d]

There's this oddity of built-in hash tables: a reference to a non-empty 
hash table can be copied and then both references refer to the same hash 
table object. However, if the hash table is null, copying the reference 
won't track the same object later on.


Fast-forward to general collections. If we want to support things like 
reference containers, clearly that oddity must be addressed. There are 
two typical approaches:


1. Factory function:

struct MyCollection(T)
{
static MyCollection make(U...)(auto ref U args);
...
}

So then client code is:

auto c1 = MyCollection!(int).make(1, 2, 3);
auto c2 = MyCollection!(int).make();
auto c3 = c2; // refers to the same collection as c2

2. The opCall trick:

struct MyCollection(T)
{
static MyCollection opCall(U...)(auto ref U args);
...
}

with the client code:

auto c1 = MyCollection!(int)(1, 2, 3);
auto c2 = MyCollection!(int)();
auto c3 = c2; // refers to the same collection as c2

There's some experience in various libraries with both approaches. Which 
would you prefer?



Andrei

Re: Phobos 'collections' question

[Marco Leise]

Am 26.10.2011, 16:00 Uhr, schrieb Steven Schveighoffer  
:


On Mon, 24 Oct 2011 22:50:33 -0400, Marco Leise   
wrote:


Am 14.09.2011, 18:57 Uhr, schrieb Steven Schveighoffer  
:


On Wed, 14 Sep 2011 12:50:25 -0400, Timon Gehr   
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.

Re: Phobos 'collections' question

[Marco Leise]

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.

Re: Phobos 'collections' question

[Steven Schveighoffer]

On Tue, 25 Oct 2011 01:00:51 -0400, Andrew Wiley  
 wrote:



On Mon, Oct 24, 2011 at 9:50 PM, Marco Leise  wrote:


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


 On Wed, 14 Sep 2011 12:50:25 -0400, Timon Gehr   
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.



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

Re: Phobos 'collections' question

[Steven Schveighoffer]

On Mon, 24 Oct 2011 22:50:33 -0400, Marco Leise  wrote:

Am 14.09.2011, 18:57 Uhr, schrieb Steven Schveighoffer  
:


On Wed, 14 Sep 2011 12:50:25 -0400, Timon Gehr   
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

Re: Phobos 'collections' question

[Gor Gyolchanyan]

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  wrote:
>
>
> On Mon, Oct 24, 2011 at 9:50 PM, Marco Leise  wrote:
>>
>> Am 14.09.2011, 18:57 Uhr, schrieb Steven Schveighoffer
>> :
>>
>>> On Wed, 14 Sep 2011 12:50:25 -0400, Timon Gehr  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.
>
> Wait, dcollections has a PriorityQueue?
> You could use a tree for that, but my understanding is that a heap is much
> more efficient?

Re: Phobos 'collections' question

[Andrew Wiley]

On Mon, Oct 24, 2011 at 9:50 PM, Marco Leise  wrote:

> Am 14.09.2011, 18:57 Uhr, schrieb Steven Schveighoffer <
> schvei...@yahoo.com>:
>
>
>  On Wed, 14 Sep 2011 12:50:25 -0400, Timon Gehr  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.
>

Wait, dcollections has a PriorityQueue?
You could use a tree for that, but my understanding is that a heap is much
more efficient?

Re: Phobos 'collections' question

[Marco Leise]

Am 14.09.2011, 18:57 Uhr, schrieb Steven Schveighoffer  
:



On Wed, 14 Sep 2011 12:50:25 -0400, Timon Gehr  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.

Re: Phobos 'collections' question

[Robert McGinley]

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 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

Re: Phobos 'collections' question

[Jonathan M Davis]

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

Re: Phobos 'collections' question

[Steven Schveighoffer]

On Wed, 14 Sep 2011 13:12:30 -0400, Jonathan M Davis   
wrote:



On Wednesday, September 14, 2011 09:57 Steven Schveighoffer wrote:
On Wed, 14 Sep 2011 12:50:25 -0400, Timon Gehr   
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.


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

Re: Phobos 'collections' question

[Jonathan M Davis]

On Wednesday, September 14, 2011 09:57 Steven Schveighoffer wrote:
> On Wed, 14 Sep 2011 12:50:25 -0400, Timon Gehr  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

Re: Phobos 'collections' question

[Steven Schveighoffer]

On Wed, 14 Sep 2011 12:50:25 -0400, Timon Gehr  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

Re: Phobos 'collections' question

[Timon Gehr]

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.

Re: Phobos 'collections' question

[Jonathan M Davis]

On Wednesday, September 14, 2011 10:08:28 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

1. We have std.container.Array, so there's no need for ArrayList.
2. Containers go in std.container, so any container proposals should put the 
containers in there.
3. One of the primary reasons that there are not more containers in 
std.container right now is the fact that the custom allocator scheme still 
needs to be sorted out (the current review for the region allocator relates to 
that). So, until that's been done, I don't think that we're intended to add 
any more containers, since they'd have to be redone on some level anyway.

We do want more containers in Phobos, but I'm not sure that we're really ready 
to look at including any more right now because of #3. So, feel free to work 
on container implementations, but I'm not sure that we'd review them for 
inclusion until #3 has been sorted out. However, if you do implement any 
containers with the idea of trying to get them into Phobos, you need to have 
them follow the function scheme as listed in std.container - both in terms of 
names and performance requirements.

- Jonathan M Davis

Phobos 'collections' question

[Robert McGinley]

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