October 15, 2008
Christopher Wright:

>Any particular reason?<

'is' is for object equivalence. But you have values there.


>And then it takes slightly more work to change it into a multiline comment.<

Right.


>I actually need this behavior.<

I'll probably add that key mapping function to your code in the following days. If you want I may show you the code later...


>The version I submitted had a virtual comparison method, so that would have been reasonably simple to implement:<

Interesting.


>I use a large monitor. Whitespace makes things more readable for me.<

I think older people tend to write more compact code, because in the past monitors were smaller (and probably because of other factors, like the amount of code you can put on the screen at once) while the new style (that can be usually seen in C# code, or like your code of the Heap) is to have very few sparse lines on the screen. I think my style is midway.


>the Tango heap will not suffice for my needs.<

Well, if you are the author you can change the situation, can't you? :-)

Bye,
bearophile
October 15, 2008
On Tue, Oct 14, 2008 at 5:53 PM, bearophile <bearophileHUGS@lycos.com> wrote:
> Christopher Wright:
>> http://dsource.org/projects/tango/browser/trunk/tango/util/container/more/Heap.d?rev=3959
>
> Very nice, thank you. Few quick comments (no deep comments, I haven't used it nor read it carefully):
>
> In this lines:
> assert (other.pop is 4);
>
> I think it's better to use
> assert(other.pop == 4);
>
>
> This lines show that a bulk addition method may be useful, that accepts any lazy/eagar iterable:
> MaxHeap!(uint) h;
> h ~= 1;
> h ~= 3;
> h ~= 2;
> h ~= 4;
>
>
> The following aliases can be moved just below their respective methods, with a /// ditto before them:
> alias pop       remove;
> alias push      opCatAssign;
>
>
> This style of comments:
> /** Inserts all elements in the given array into the heap. */
>
> Can sometimes be replaced by:
> /// Inserts all elements in the given array into the heap.
>
>
> The class ddoc misses the explanation for the Min template argument:
> struct Heap(T, bool Min) {
>
>
> Some lines of comments are too much long, they may be broken at 80-95 chars long.
>
>
> An optional 'key' callable can be added; it can be used as sorting key mapper (Swartz-style). If not specified it can be "null" that means the current behaviour.
>
>
> Few other handy methods may be added:
>
> A merge() (~ and ~=) method can be added, maybe.
>
> heapreplace(heap, item) (pop and return the smallest item from the heap, and also push the new item. The heap size doesn't change)
>
> heapify(iterable)
> nlargest(n, iterable)
> nsmallest(n, iterable)
>
>
> The following is not a critic, just a note, I think programs with such low code density are harder to read to me, they seem like fresh snow:
>
> /** Inserts all elements in the given array into the heap. */
> void push (T[] array)
> {
>        while (heap.length < next + array.length)
>        {
>                heap.length = 2 * heap.length + 32;
>        }
>        foreach (t; array) push (t);
> }
>
>
> I'd write that as this, allowing me to have more code on the screen:
>
> /// Inserts all elements in the given array into the heap.
> void push(T[] array) {
>    while (heap.length < next + array.length)
>        heap.length = 2 * heap.length + 32;
>    foreach (t; array)
>        push(t);
> }
>

Bearophile, you're doing it again.  Why are you so hung up on how other people format their code?  Please, please get over it.
October 15, 2008
Jarrett Billingsley:
> Why are you so hung up on how
> other people format their code?

Not all coding styles are created equal. Some are better.

Bye,
bearophile
October 15, 2008
"bearophile" wrote
> Jarrett Billingsley:
>> Why are you so hung up on how
>> other people format their code?
>
> Not all coding styles are created equal. Some are better.

Yes, but clearly not yours.  Mine is much better.

-Steve


October 15, 2008
Benji Smith wrote:
> Andrei Alexandrescu wrote:
>> Benji Smith wrote:
>>> Andrei Alexandrescu wrote:
>>>> Christopher Wright wrote:
>>>>> Containers as value types is such an idiotic idea for precisely this reason.
>>>>
>>>> I'd say this statement reflects a lack of understanding of value types, rather than value containers are an idiotic idea.
>>>
>>> I'll bite.
>>>
>>> Why is it a good idea that containers are implements as structs?
>>
>> As the Mexican would say: why not?
> 
> Well... here are a few reasons why not:
> 
> Structs can't implement interfaces, and a collection API is the poster-child of good interface usage.

I don't want to seem like picking on you, but I would like to answer
this message too.

In my humble opinion, collections APIs are the poster-child of the
misguided joy of the beginnings of object-orientation, right next to the
mammal isa animal example. Organizing collections in hierarchies is of
occasional benefit, but the real benefit comes from decoupling
containers from algorithms via iterators, the way the STL did. The
savings there were that an O(m * n) problem has been solved with writing
O(m + n) code. Container hierarchies do not achieve such a reduction
unless efforts are being made that have little to do with hierarchical
organization. At most they factor out some code in the upper classes,
but hierarchies help when types have many commonalities and few
difference, and that is very rarely the case with containers.

> Structs can't inherit from abstract classes. A good deal of functionality in a collection class can be implemented once in an abstract base class, making it simpler for subclass authors to implement the API without duplicating a bunch of boilerplate.

This also reveals a beginner's view of inheritance. You don't inherit to
reuse. You inherit to be reused. If all you want is to reuse, use
composition.

> Conceptually -- and there's no hard and fast rule about this -- structs usually either represent small logically-atomic values (DateTime), or some fixed-size collection of logically-atomic values (Vector3). Using a struct as an arbitrarily-sized container seems, on the face of it, to break those conventions.

I see how it breaks those conventions, but I've never heard of them. The
convention I heard of is that if you want dynamic polymorphism you use
classes, otherwise you don't.


Andrei
October 15, 2008
Wed, 15 Oct 2008 09:17:57 -0500,
Andrei Alexandrescu wrote:
> I see how it breaks those conventions, but I've never heard of them. The convention I heard of is that if you want dynamic polymorphism you use classes, otherwise you don't.

How about if you want pass-by-value you use structs, otherwise you don't? My argument against structs-collections is that I want to toss collections around and build other collections out of them without messing with pointers.
October 15, 2008
Sergey Gromov wrote:
> Wed, 15 Oct 2008 09:17:57 -0500,
> Andrei Alexandrescu wrote:
>> I see how it breaks those conventions, but I've never heard of them. The
>> convention I heard of is that if you want dynamic polymorphism you use
>> classes, otherwise you don't.
> 
> How about if you want pass-by-value you use structs, otherwise you don't?  My argument against structs-collections is that I want to toss collections around and build other collections out of them without messing with pointers.

A struct can choose to implement value or reference semantics as it pleases. The only thing it can't readily implement is dynamic polymorphism.

Andrei
October 15, 2008
Wed, 15 Oct 2008 09:49:08 -0500,
Andrei Alexandrescu wrote:
> Sergey Gromov wrote:
> > Wed, 15 Oct 2008 09:17:57 -0500,
> > Andrei Alexandrescu wrote:
> >> I see how it breaks those conventions, but I've never heard of them. The convention I heard of is that if you want dynamic polymorphism you use classes, otherwise you don't.
> > 
> > How about if you want pass-by-value you use structs, otherwise you don't? My argument against structs-collections is that I want to toss collections around and build other collections out of them without messing with pointers.
> 
> A struct can choose to implement value or reference semantics as it pleases. The only thing it can't readily implement is dynamic polymorphism.

I can imagine the documentation: "Ignore the fact it's a struct, it's actually a reference internally."  So how do I return it?  Should I return it by value, hoping that the implied reference semantics will stay that way in future releases?  How does your Array!() behave?
October 15, 2008
"Sergey Gromov" wrote
> Wed, 15 Oct 2008 09:49:08 -0500,
> Andrei Alexandrescu wrote:
>> Sergey Gromov wrote:
>> > Wed, 15 Oct 2008 09:17:57 -0500,
>> > Andrei Alexandrescu wrote:
>> >> I see how it breaks those conventions, but I've never heard of them.
>> >> The
>> >> convention I heard of is that if you want dynamic polymorphism you use
>> >> classes, otherwise you don't.
>> >
>> > How about if you want pass-by-value you use structs, otherwise you
>> > don't?
>> > My argument against structs-collections is that I want to toss
>> > collections around and build other collections out of them without
>> > messing with pointers.
>>
>> A struct can choose to implement value or reference semantics as it pleases. The only thing it can't readily implement is dynamic polymorphism.
>
> I can imagine the documentation: "Ignore the fact it's a struct, it's actually a reference internally."  So how do I return it?  Should I return it by value, hoping that the implied reference semantics will stay that way in future releases?  How does your Array!() behave?

There's nothing requiring that a struct must implement value semantics.  The fact that you are expecting such just because it is a struct is a mistake.

The reality is that only structs can implement value semantics because of the inability to override A = A in a class.

That being said, I think containers work best as a mixture of interface and compile-time typing. See http://www.dsource.org/projects/dcollections.

-Steve


October 15, 2008
Sergey Gromov wrote:
> Wed, 15 Oct 2008 09:49:08 -0500,
> Andrei Alexandrescu wrote:
>> Sergey Gromov wrote:
>>> Wed, 15 Oct 2008 09:17:57 -0500,
>>> Andrei Alexandrescu wrote:
>>>> I see how it breaks those conventions, but I've never heard of them. The
>>>> convention I heard of is that if you want dynamic polymorphism you use
>>>> classes, otherwise you don't.
>>> How about if you want pass-by-value you use structs, otherwise you don't?  My argument against structs-collections is that I want to toss collections around and build other collections out of them without messing with pointers.
>> A struct can choose to implement value or reference semantics as it pleases. The only thing it can't readily implement is dynamic polymorphism.
> 
> I can imagine the documentation: "Ignore the fact it's a struct, it's actually a reference internally."

No. "Don't submit to the dogma that struct == value semantics, because that was never true".

> So how do I return it?  Should I return it by value, hoping that the implied reference semantics will stay that way in future releases?  How does your Array!() behave?

That's not finished, but e.g. Appender can be copied around and always refers to the same underlying array.


Andrei