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 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
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 next 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 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 next sibling parent 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
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