www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - SortedRange and new docs for std.container

reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Hello,


I just added SortedRange as discussed a while ago in this newsgroup. I 
think it turned out pretty neat. Generally the range abstraction is 
turning out to be very solid.

To get a SortedRange object for a given range r either call sort(r) if 
you want to sort one, or assumeSorted(r) if you know that the range is 
sorted already.

I've also fixed Zip (finally!) to get rid of a couple of dirty tricks. 
It turns out that front()/front(v)/moveFront() are a correct way to 
abstract proxy ranges like Zip is.

Search this documentation preview for "SortedRange" and "Zip":

http://erdani.com/d/phobos/std_range.html
http://erdani.com/d/phobos/std_algorithm.html

I've also improved the look of container requirements, check:

http://erdani.com/d/phobos/std_container.html


Comments and ideas are welcome.

Andrei
Sep 08 2010
next sibling parent reply dsimcha <dsimcha yahoo.com> writes:
== Quote from Andrei Alexandrescu (SeeWebsiteForEmail erdani.org)'s article

 Hello,
 I just added SortedRange as discussed a while ago in this newsgroup. I
 think it turned out pretty neat. Generally the range abstraction is
 turning out to be very solid.
 To get a SortedRange object for a given range r either call sort(r) if
 you want to sort one, or assumeSorted(r) if you know that the range is
 sorted already.
 I've also fixed Zip (finally!) to get rid of a couple of dirty tricks.
 It turns out that front()/front(v)/moveFront() are a correct way to
 abstract proxy ranges like Zip is.
 Search this documentation preview for "SortedRange" and "Zip":
 http://erdani.com/d/phobos/std_range.html
 http://erdani.com/d/phobos/std_algorithm.html
 I've also improved the look of container requirements, check:
 http://erdani.com/d/phobos/std_container.html
 Comments and ideas are welcome.
 Andrei


One question:  Now that hasAt is gone, how does one use StoppingPolicy.longest
properly?  IMHO StoppingPolicy.longest was never all that useful and should just
be removed.
Sep 08 2010
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 9/8/10 9:21 CDT, dsimcha wrote:

 == Quote from Andrei Alexandrescu (SeeWebsiteForEmail erdani.org)'s article

 Hello,
 I just added SortedRange as discussed a while ago in this newsgroup. I
 think it turned out pretty neat. Generally the range abstraction is
 turning out to be very solid.
 To get a SortedRange object for a given range r either call sort(r) if
 you want to sort one, or assumeSorted(r) if you know that the range is
 sorted already.
 I've also fixed Zip (finally!) to get rid of a couple of dirty tricks.
 It turns out that front()/front(v)/moveFront() are a correct way to
 abstract proxy ranges like Zip is.
 Search this documentation preview for "SortedRange" and "Zip":
 http://erdani.com/d/phobos/std_range.html
 http://erdani.com/d/phobos/std_algorithm.html
 I've also improved the look of container requirements, check:
 http://erdani.com/d/phobos/std_container.html
 Comments and ideas are welcome.
 Andrei


 One question:  Now that hasAt is gone, how does one use StoppingPolicy.longest
 properly?  IMHO StoppingPolicy.longest was never all that useful and should
just
 be removed.


Hmmm, I was wrong to remove hasAt. Will add it back.

Andrei
Sep 08 2010
prev sibling next sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
Andrei:

 I've also fixed Zip (finally!) to get rid of a couple of dirty tricks. 
 It turns out that front()/front(v)/moveFront() are a correct way to 
 abstract proxy ranges like Zip is.


In this changeset:
http://www.dsource.org/projects/phobos/changeset/1968

I see code as:

auto arr2 = t.field[1]; 
auto zShortest = zip(arr1, arr2); 
assert(equal(map!"a.at!0"(zShortest), [1, 2])); 

Changed in:

auto arr2 = t.field[1]; 
auto zShortest = zip(arr1, arr2); 
assert(equal(map!"a.field[0]"(zShortest), [1, 2])); 

So is this related to this enhancement request?
http://d.puremagic.com/issues/show_bug.cgi?id=4382

Bye,
bearophile
Sep 08 2010
next sibling parent reply Andrej Mitrovic <andrej.mitrovich gmail.com> writes:
I don't want to hijack the topic, but can I ask a question?

In the Phobos docs I often see this kind of code:

assert(equal(radial(a), [ 3, 4, 2, 5, 1 ][]));

What is the purpose of the extra square brackets after the array
literal? Because the code works both with and without them.

On Wed, Sep 8, 2010 at 6:52 PM, bearophile <bearophileHUGS lycos.com> wrote:

 Andrei:

 I've also fixed Zip (finally!) to get rid of a couple of dirty tricks.
 It turns out that front()/front(v)/moveFront() are a correct way to
 abstract proxy ranges like Zip is.


 In this changeset:
 http://www.dsource.org/projects/phobos/changeset/1968

 I see code as:

 auto arr2 = t.field[1];
 auto zShortest = zip(arr1, arr2);
 assert(equal(map!"a.at!0"(zShortest), [1, 2]));

 Changed in:

 auto arr2 = t.field[1];
 auto zShortest = zip(arr1, arr2);
 assert(equal(map!"a.field[0]"(zShortest), [1, 2]));

 So is this related to this enhancement request?
 http://d.puremagic.com/issues/show_bug.cgi?id=4382

 Bye,
 bearophile
Sep 08 2010
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 9/8/10 12:06 CDT, Andrej Mitrovic wrote:

 I don't want to hijack the topic, but can I ask a question?

 In the Phobos docs I often see this kind of code:

 assert(equal(radial(a), [ 3, 4, 2, 5, 1 ][]));

 What is the purpose of the extra square brackets after the array
 literal? Because the code works both with and without them.


Just historical vestige. There was a time when it didn't work without 
the [].

Andrei
Sep 08 2010
parent reply Jesse Phillips <jessekphillips+D gmail.com> writes:
Andrei Alexandrescu Wrote:


 On 9/8/10 12:06 CDT, Andrej Mitrovic wrote:

 I don't want to hijack the topic, but can I ask a question?

 In the Phobos docs I often see this kind of code:

 assert(equal(radial(a), [ 3, 4, 2, 5, 1 ][]));

 What is the purpose of the extra square brackets after the array
 literal? Because the code works both with and without them.


 
 Just historical vestige. There was a time when it didn't work without 
 the [].
 
 Andrei


To be more exact, [3,4,2,5,1] use to create a static array, int[5u], but what
was required was a dynamic array, int[], by adding the ending [] you are taking
a 'slice' of the entire array, which is of type int[]. adding the [] to the end
still does the same thing, but now array literals are dynamic arrays. You can
use literals to create static arrays by giving the type you want.

http://ideone.com/qInPu

The default was changed because Phobos was littered with [...][] in all the
tests... Andrei must have gotten annoyed. :)
Sep 08 2010
next sibling parent bearophile <bearophileHUGS lycos.com> writes:
Jesse Phillips:

 The default was changed because Phobos was littered with [...][] in all the
tests... Andrei must have gotten annoyed. :)


The default was changed because most times you want a dynamic array. (On the
other hand I don't love the amount of memory allocations caused by the current
array literals. I think still that there's a need for some optimization on this
situation).

Bye,
bearophile
Sep 08 2010
prev sibling parent Andrej Mitrovic <andrej.mitrovich gmail.com> writes:
Wow, you can actually interpret code on that site. Nice. I wonder how
safe that is for them..

On Wed, Sep 8, 2010 at 9:47 PM, Jesse Phillips
<jessekphillips+D gmail.com> wrote:
You can use literals to create static arrays by giving the type you want.

 http://ideone.com/qInPu

 The default was changed because Phobos was littered with [...][] in all the
tests... Andrei must have gotten annoyed. :)
Sep 08 2010
prev sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 9/8/10 11:52 CDT, bearophile wrote:

 Andrei:

 I've also fixed Zip (finally!) to get rid of a couple of dirty tricks.
 It turns out that front()/front(v)/moveFront() are a correct way to
 abstract proxy ranges like Zip is.


 In this changeset:
 http://www.dsource.org/projects/phobos/changeset/1968

 I see code as:

 auto arr2 = t.field[1];
 auto zShortest = zip(arr1, arr2);
 assert(equal(map!"a.at!0"(zShortest), [1, 2]));

 Changed in:

 auto arr2 = t.field[1];
 auto zShortest = zip(arr1, arr2);
 assert(equal(map!"a.field[0]"(zShortest), [1, 2]));

 So is this related to this enhancement request?
 http://d.puremagic.com/issues/show_bug.cgi?id=4382


Well now Proxy is gone, so the enhancement request got satisfied in an 
unexpected way :o).

Andrei
Sep 08 2010
prev sibling parent reply =?iso-8859-2?B?VG9tZWsgU293afFza2k=?= <just ask.me> writes:
Dnia 08-09-2010 o 15:55:30 Andrei Alexandrescu  =

<SeeWebsiteForEmail erdani.org> napisa=B3(a):


 I just added SortedRange as discussed a while ago in this newsgroup. I=


  =


 think it turned out pretty neat. Generally the range abstraction is  =



 turning out to be very solid.

 To get a SortedRange object for a given range r either call sort(r) if=


  =


 you want to sort one, or assumeSorted(r) if you know that the range is=


  =


 sorted already.


1. I'm missing quantile, though it's trivial to compute.
2. Could makeIndex() also return SortedRange? The predicate should be  =

morphed of course to account for dereferencing.
3. Overall impression is good.


 I've also fixed Zip (finally!) to get rid of a couple of dirty tricks.=


  =


 It turns out that front()/front(v)/moveFront() are a correct way to  =



 abstract proxy ranges like Zip is.


Good to hear. Speaking of Zip, I often find myself assembling combos lik=
e  =

map!fun(zip(r1, r2, ...). Nothing wrong with it, but there's usually a  =

problem with the transformation function -- I always have to make my own=
.  =

If I have a function that takes multiple parameters (can happen), I can'=
t  =

plug it directly, I have to make a wrapper that takes a tuple and forwar=
ds  =

fields to the arguments. So how about zip!funnel(r1, r2, ...)? funnel mu=
st  =

take the sequence of ElementTypes of the zipped ranges as parameters. Th=
e  =

ElementType of the resulting range is funnel's return type. Plus, the  =

compiler is not bothered with optimizing out the intermediary tuple of  =

arguments.

Would the ROI of this feature be positive?


Tomek
Sep 08 2010
parent Tomek =?UTF-8?B?U293acWEc2tp?= <just ask.me> writes:
Tomek Sowiński napisał:


 2. Could makeIndex() also return SortedRange? The predicate should be
 morphed of course to account for dereferencing.


Or better: SortedRange's underlying range should account for dereferencing and
leave the predicate intact.

Tomek
Sep 09 2010