www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Creating a Sub-view of a non - RA (hasSlicing) range.

reply "monarch_dodra" <monarch_dodra gmail.com> writes:
I've been enjoying my time with D's ranges, but something is 
nagging at me: If the range is not random access, then how does 
one create a sub-view of that range?

Say I have a forward range (for example, an SList[]). I would 
like to create a new range containing only the first 5 elements 
of that old range. How can I do that?

I see no logical reason that prevents me from doing it, since C++ 
iterators can do it quite fine. (the C++ algorithms that work 
only on RA ranges is mostly for efficiency reasons). Not being 
able to do this would severely limit the amount of containers 
that can seamlessly merge with algorithms.

For example, I can't call splitter on an SList. Not sure if this 
is just "not currently supported", or just not possible...

Any thoughts?
Jun 30 2012
next sibling parent reply "Tobias Pankrath" <tobias pankrath.net> writes:
 Say I have a forward range (for example, an SList[]). I would 
 like to create a new range containing only the first 5 elements 
 of that old range. How can I do that?

std.algorithm.take. But I would generally avoid SList.
Jun 30 2012
next sibling parent reply Dmitry Olshansky <dmitry.olsh gmail.com> writes:
On 30-Jun-12 15:35, Tobias Pankrath wrote:
 Say I have a forward range (for example, an SList[]). I would like to
 create a new range containing only the first 5 elements of that old
 range. How can I do that?

std.algorithm.take. But I would generally avoid SList.

Indeed. I'd be hard pressed to devise realistic use case where it performs better. That makes me think that a proper type people should be using is the unrolled list, that is a list of fixed-sized array chunks. Or even chunked array like bearophile suggests. -- Dmitry Olshansky
Jun 30 2012
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 6/30/12 9:15 AM, Dmitry Olshansky wrote:
 On 30-Jun-12 15:35, Tobias Pankrath wrote:
 Say I have a forward range (for example, an SList[]). I would like to
 create a new range containing only the first 5 elements of that old
 range. How can I do that?

std.algorithm.take. But I would generally avoid SList.

Indeed. I'd be hard pressed to devise realistic use case where it performs better.

Singly-linked lists are frequently used with lock-free algorithms. Generally it's simplistic to compare slists with arrays as to "which performs better" because they have different primitives. Andrei
Jun 30 2012
parent Dmitry Olshansky <dmitry.olsh gmail.com> writes:
On 30-Jun-12 18:25, Andrei Alexandrescu wrote:
 On 6/30/12 9:15 AM, Dmitry Olshansky wrote:
 On 30-Jun-12 15:35, Tobias Pankrath wrote:
 Say I have a forward range (for example, an SList[]). I would like to
 create a new range containing only the first 5 elements of that old
 range. How can I do that?

std.algorithm.take. But I would generally avoid SList.

Indeed. I'd be hard pressed to devise realistic use case where it performs better.

Singly-linked lists are frequently used with lock-free algorithms.

As post involved terms like "generally" I pointed out that indeed List should not be used "generally" :) Their value in certain scenarios is remarkable, or rather of linked storage such as in free lists, and (like you mentioned) certain lock-free algorithms. Let's not forget however that what people seek is lock-free queues and other high-level abstractions. S-lists just happen to be a means to an end that works on current hardware. I totally expect a new wave of simpler lock-free algorithms with things like Intel's TSX and something analogous that AMD will have. (others would either copy or redesign similar things as it's an obvious need for the future multicores) There a lot of links but this gives a nice overview and is fairly new: http://arstechnica.com/business/2012/02/transactional-memory-going-mainstream-with-intel-haswell/
 Generally it's simplistic to compare slists with arrays as to "which
 performs better" because they have different primitives.

Agreed. Though it's not at all uncommon to mix things up in awful ways. *cough* Java *cough* -- Dmitry Olshansky
Jul 01 2012
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 6/30/12 8:24 AM, monarch_dodra wrote:
 On Saturday, 30 June 2012 at 11:35:07 UTC, Tobias Pankrath wrote:
 std.algorithm.take.

 But I would generally avoid SList.

Thanks, but isn't that kind of a crutch solution? I mean: 1) It creates a new type, so any attempt to use it to modify an existing range becomes impossible: void main() { SList!int slist; foreach(i; iota(5,0,-1)) slist.insertFront(i); sr1 = take(sr1, 2); //Nope, not gonna happen writeln(sr1); }

One can't expect that to happen more than suspending a law of physics. The state needed for iterating an entire slist is a pointer. The state needed for iterating at most n elements of an slist is a pointer plus and integer. They're just different notions.
 2) The new range is defined as a fixed length from the beginning of the
 range, as opposed to start and finish points. If I were to insert new
 items into my Slist, the new range would just bump the top items out of
 its range.

SList's range is not defined by start and finish points. It's defined as the start point, and the finish point is implicit by use of a sentinel (the null pointer).
 3) This doesn't work for BidirectionalRanges: The resulting range is
 forward only. For the same reason, it is not possible to have a TakeLast
 for bidirectional ranges.

Not sure I understand this, but when we get into the realm of bidir ranges, things get a fair amount better. How would TakeLast work? Andrei
Jun 30 2012
next sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 6/30/12 11:15 AM, Monarch Dodra wrote:
 On Saturday, 30 June 2012 at 14:22:06 UTC, Andrei Alexandrescu wrote:
 2) The new range is defined as a fixed length from the beginning of the
 range, as opposed to start and finish points. If I were to insert new
 items into my Slist, the new range would just bump the top items out of
 its range.

SList's range is not defined by start and finish points. It's defined as the start point, and the finish point is implicit by use of a sentinel (the null pointer).

would be defined by a start and finish point?

Yes. But now you're moving the goalposts because many of your arguments referred to SList.
 Take, on the other hand, creates a range, which is defined by a start
 point, and a fixed length. Inserting elements into the middle of the
 original list would bump elements out of the "take range", which remains
 fixed sized.

Correct. take() and takeExactly() work under the assumption there's no surreptitious change in the structure of the range underneath. I think that's a reasonable decision.
 On the other hand, had I manually shrunk my BDlistRange until it was 5
 elements long, and then inserted elements into the midle of the list, it
 would cause my BDListRange to grow, and nothing to drop out of it.

Right. Generally ranges are not responsible for accurately tracking underlying structural changes. There will always be ways to mess up things in ways that leave extant ranges unsynchronized.
 Not sure I understand this, but when we get into the realm of bidir
 ranges, things get a fair amount better. How would TakeLast work?

Well, if we forget Slist, and just focus on a standard BidirectionalRange, say comming from a DList. Things don't really get any better, because take still returns just a ForwardRange.

Which is as it should be. How would you otherwise take the first n elements of a given doubly-linked list in constant time?
 There is no way of doing, say:

 BidirectionalRange aBD = ...;

 //Create subrange...
 //aBD = take(aBD, 5); //Error, wrong type
 auto subrange = take(aBD, 5);

 if(subrange.back == 5) //Error, subrange does not have a back method.
 //...But that's strange, because aBD IS a bidiretinal range

 Since the Take Range it is defined by a begining point and a length,
 there is no way it could give Bidir access.

It's all about what it takes to reach a certain point. You are sensing something indeed, but take() is not it. The problem is there's no simple way to count 5 starting from the left side of a doubly-linked list, stop there, and then create a range from the beginning of the list and that mid point. In C++, that's trivial because range ends are separate.
 ----
 I came to D after reading your talk on ranges, and I really liked (and
 am still enjoying) the concept. However, with C++, when you iterate over
 [First, Last), you are also creating a two new ranges: [First, Current)
 & [Current, Last). D doesn't provide that, it only provides a way to
 shrink the current range and create [Current, Last).

Yes, that's a good way of putting it.
 Using range, you don't get [First, Current). At best, you only get
 a)A forward range only
 b)A fixed size range
 c)A range of another type

We could extend the range interface for specific ranges to allow for such. However, there hasn't been a strong need so far. Andrei
Jun 30 2012
prev sibling parent travert phare.normalesup.org (Christophe Travert) writes:
Have you had a look at dcollection ?

http://www.dsource.org/projects/dcollections

There is a doubly linked list implementation, with range and cursors 
(entities that have iterator functionalities).
Jul 02 2012
prev sibling next sibling parent "monarch_dodra" <monarch_dodra gmail.com> writes:
On Saturday, 30 June 2012 at 11:35:07 UTC, Tobias Pankrath wrote:
 std.algorithm.take.

 But I would generally avoid SList.

Thanks, but isn't that kind of a crutch solution? I mean: 1) It creates a new type, so any attempt to use it to modify an existing range becomes impossible: void main() { SList!int slist; foreach(i; iota(5,0,-1)) slist.insertFront(i); sr1 = take(sr1, 2); //Nope, not gonna happen writeln(sr1); } 2) The new range is defined as a fixed length from the beginning of the range, as opposed to start and finish points. If I were to insert new items into my Slist, the new range would just bump the top items out of its range. 3) This doesn't work for BidirectionalRanges: The resulting range is forward only. For the same reason, it is not possible to have a TakeLast for bidirectional ranges. ---- Doesn't D offer any approach to "grow" a range?
Jun 30 2012
prev sibling next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
Tobias Pankrath:

 But I would generally avoid SList.

It's not good. And in general linked lists are quite overrated. On modern CPUs it's not easy to find situations where a linked list is better than a dynamic array or a chunked array (that is a dynamic array of pointers to arrays. It's often used to implement deques, etc). Regarding arrays, maybe a StableVector will be good to have in Phobos: http://www.boost.org/doc/libs/1_50_0_beta1/doc/html/container/non_standard_containers.html#container.non_standard_containers.stable_vector Bye, bearophile
Jun 30 2012
prev sibling next sibling parent "monarch_dodra" <monarch_dodra gmail.com> writes:
On Saturday, 30 June 2012 at 12:27:38 UTC, bearophile wrote:
 Tobias Pankrath:

 But I would generally avoid SList.

It's not good. And in general linked lists are quite overrated. ... Bye, bearophile

I appreciate the input, which I (mostly) agree with (I still love list's splice ability, which can be very powerful), but this isn't really what the question is about. It's about getting generic algorithms to work with any generic range. Right now, they appear (to me) to heavily favor RA, even when they should theoretically support simple bidirectionality... Those that do support directionality do it using "cheat" using take. For example: void main() { SList!int slist; foreach(i; iota(5,0,-1)) slist.insertFront(i); auto rnge = slist[]; auto fs = findSplit!("a == b")(rnge, [3]); writeln(fs[0]); // [1, 2] slist.insertAfter(take(rnge, 1), 25); //insert 25 between [1, 2] writeln(fs[0]); // [1, 25] !? Should arguably be [1, 25, 2] } This, arguably, is not normal behavior. SList modeling forward ranges, ranges to the list should not be bounded by a fixed size. And again, had my input been a BDList (if it existed), findSplit would have returned 3 forwardRanges, which is also arguably wrong.
Jun 30 2012
prev sibling next sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 6/30/12 7:31 AM, monarch_dodra wrote:
 I've been enjoying my time with D's ranges, but something is nagging at
 me: If the range is not random access, then how does one create a
 sub-view of that range?

Use take or takeExactly.
 Say I have a forward range (for example, an SList[]). I would like to
 create a new range containing only the first 5 elements of that old
 range. How can I do that?

take(r, n) or takeExactly(r, n).
 I see no logical reason that prevents me from doing it, since C++
 iterators can do it quite fine.

Actually, not at all. Iterators are a lot worse off than ranges here. C++'s std::forward_list (and generally any iterator-providing singly-linked list) only offers an iterator to the first element. (The "end" iterator is a wrapped null pointer. This is by definition of the structure - singly-linked lists don't track their last element.) So if you were to to take 5 elements off a std::forward_list, you can't use lst.begin() and lst.begin() + 5 because there's no addition; you'd need to define a new iterator type that combines a forward iterator with an integer, and iterate using that. It's all painstaking revealing how much a range is better for such. This is because the range keeps together the iteration limits, whereas iterators insist on the fact that the iteration limits belong separately.
 (the C++ algorithms that work only on RA
 ranges is mostly for efficiency reasons). Not being able to do this
 would severely limit the amount of containers that can seamlessly merge
 with algorithms.

 For example, I can't call splitter on an SList. Not sure if this is just
 "not currently supported", or just not possible...

 Any thoughts?

It must be very well understood what the structural limits of singly-linked lists impose on their iteration. There's no way to take 5 elements off a SList and pretend that's pretty much the same as taking the whole list. We could build a design for using splitter with SLists only if the element type of splitter's result is different from SList's native range. Andrei
Jun 30 2012
prev sibling next sibling parent "Monarch Dodra" <monarchdodra gmail.com> writes:
On Saturday, 30 June 2012 at 14:22:06 UTC, Andrei Alexandrescu 
wrote:
 2) The new range is defined as a fixed length from the 
 beginning of the
 range, as opposed to start and finish points. If I were to 
 insert new
 items into my Slist, the new range would just bump the top 
 items out of
 its range.

SList's range is not defined by start and finish points. It's defined as the start point, and the finish point is implicit by use of a sentinel (the null pointer).

Surelly, it would be defined by a start and finish point? Take, on the other hand, creates a range, which is defined by a start point, and a fixed length. Inserting elements into the middle of the original list would bump elements out of the "take range", which remains fixed sized. On the other hand, had I manually shrunk my BDlistRange until it was 5 elements long, and then inserted elements into the midle of the list, it would cause my BDListRange to grow, and nothing to drop out of it. On Saturday, 30 June 2012 at 14:22:06 UTC, Andrei Alexandrescu wrote:
 On 6/30/12 8:24 AM, monarch_dodra wrote:
 3) This doesn't work for BidirectionalRanges: The resulting 
 range is
 forward only. For the same reason, it is not possible to have 
 a TakeLast
 for bidirectional ranges.

Not sure I understand this, but when we get into the realm of bidir ranges, things get a fair amount better. How would TakeLast work? Andrei

Well, if we forget Slist, and just focus on a standard BidirectionalRange, say comming from a DList. Things don't really get any better, because take still returns just a ForwardRange. There is no way of doing, say: BidirectionalRange aBD = ...; //Create subrange... //aBD = take(aBD, 5); //Error, wrong type auto subrange = take(aBD, 5); if(subrange.back == 5) //Error, subrange does not have a back method. //...But that's strange, because aBD IS a bidiretinal range Since the Take Range it is defined by a begining point and a length, there is no way it could give Bidir access. ---- I came to D after reading your talk on ranges, and I really liked (and am still enjoying) the concept. However, with C++, when you iterate over [First, Last), you are also creating a two new ranges: [First, Current) & [Current, Last). D doesn't provide that, it only provides a way to shrink the current range and create [Current, Last). Using range, you don't get [First, Current). At best, you only get a)A forward range only b)A fixed size range c)A range of another type
Jun 30 2012
prev sibling next sibling parent "monarch_dodra" <monarch_dodra gmail.com> writes:
On Saturday, 30 June 2012 at 23:51:42 UTC, Andrei Alexandrescu 
wrote:
 Yes. But now you're moving the goalposts because many of your 
 arguments referred to SList.

moved, rather misplaced to begin with. Using SList for making my point was not the best choice of containers. I'd hae used a "DList" like container if I had one. On Saturday, 30 June 2012 at 23:51:42 UTC, Andrei Alexandrescu wrote:
 Correct. take() and takeExactly() work under the assumption 
 there's no surreptitious change in the structure of the range 
 underneath. I think that's a reasonable decision.

those that _cut_ a range into several subranges (for example "findSplit"), such "surreptitious" change should (IMO) be expected and supported. On Saturday, 30 June 2012 at 23:51:42 UTC, Andrei Alexandrescu wrote:
 Which is as it should be. How would you otherwise take the 
 first n elements of a given doubly-linked list in constant time?

it in o(N) ;) On Saturday, 30 June 2012 at 23:51:42 UTC, Andrei Alexandrescu wrote:
 It's all about what it takes to reach a certain point. You are 
 sensing something indeed, but take() is not it. The problem is 
 there's no simple way to count 5 starting from the left side of 
 a doubly-linked list, stop there, and then create a range from 
 the beginning of the list and that mid point. In C++, that's 
 trivial because range ends are separate.

 ----
 I came to D after reading your talk on ranges, and I really 
 liked (and
 am still enjoying) the concept. However, with C++, when you 
 iterate over
 [First, Last), you are also creating a two new ranges: [First, 
 Current)
 & [Current, Last). D doesn't provide that, it only provides a 
 way to
 shrink the current range and create [Current, Last).

Yes, that's a good way of putting it.
 Using range, you don't get [First, Current). At best, you only 
 get
 a)A forward range only
 b)A fixed size range
 c)A range of another type

We could extend the range interface for specific ranges to allow for such. However, there hasn't been a strong need so far. Andrei

Thanks again for your replies. I'm really enjoying using D and ranges, and I get that nothing is "free", and this issue is one of the by products of moving from iterators-pairs to more powerful, but restrictive, ranges. I get the "no sense in making things more complicated if there is not a strong need", but at the same time, I've always felt that a language's algorithm facility should always we imaculate. Further more, it really feels as if the interface is just one concept shy of being able to make something like this work... Something like... "inverseRangeBegin(R big, R small)": Creates a range that begins where big starts, and ends where small starts. R must be at least bidirectional. small must be included inside big. From an implementation point of view, I think any container, and even arrays, can do it. I pretty sure this is compeltly feasable. Just off the top of my head. I'm sure there are brighter thinkers out there that have put more thought into it.
Jul 01 2012
prev sibling next sibling parent "monarch_dodra" <monarch_dodra gmail.com> writes:
On Sunday, 1 July 2012 at 13:22:17 UTC, monarch_dodra wrote:
 Something like...
 "inverseRangeBegin(R big, R small)": Creates a range that 
 begins where big starts, and ends where small starts. R must be 
 at least bidirectional. small must be included inside big.

 From an implementation point of view, I think any container, 
 and even arrays, can do it. I pretty sure this is compeltly 
 feasable. Just off the top of my head. I'm sure there are 
 brighter thinkers out there that have put more thought into it.

Or not. On second thought, while I'm sure there might be an implementable solution, I doubt it could be done with any real safety guarantees.
Jul 01 2012
prev sibling parent Brad Anderson <eco gnuk.net> writes:
--bcaec517a7227143f104c3ef0466
Content-Type: text/plain; charset=ISO-8859-1

On Sat, Jun 30, 2012 at 6:27 AM, bearophile <bearophileHUGS lycos.com>wrote:

 Tobias Pankrath:


  But I would generally avoid SList.

It's not good. And in general linked lists are quite overrated. On modern CPUs it's not easy to find situations where a linked list is better than a dynamic array or a chunked array (that is a dynamic array of pointers to arrays. It's often used to implement deques, etc). Regarding arrays, maybe a StableVector will be good to have in Phobos: http://www.boost.org/doc/libs/**1_50_0_beta1/doc/html/** container/non_standard_**containers.html#container.non_** standard_containers.stable_**vector<http://www.boost.org/doc/libs/1_50_0_beta1/doc/html/container/non_standard_containers.html#container.non_standard_containers.stable_vector> Bye, bearophile

I also think flat_map/_set from that same boost library would be great additions when the time comes to add new stuff to std.container. Red black trees are kind of a niche container[1]. I replaced almost all of my usage of C++'s std::set and std::map with flat_map and flat_set and saw better memory use and far fewer cache misses (assuming I was reading the profiler correctly). It was win-win since I rarely needed std::set/::map's exclusive features (iterator stability, log N insertions). I believe I've read Andrei added something just like these to Loki. [1] http://lafstern.org/matt/col1.pdf : Why you shouldn't use set (and what you should use instead) Regards, Brad Anderson --bcaec517a7227143f104c3ef0466 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable On Sat, Jun 30, 2012 at 6:27 AM, bearophile <span dir=3D"ltr">&lt;<a href= =3D"mailto:bearophileHUGS lycos.com" target=3D"_blank">bearophileHUGS lycos= .com</a>&gt;</span> wrote:<br><div class=3D"gmail_quote"><blockquote class= =3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padd= ing-left:1ex"> Tobias Pankrath:<div class=3D"im"><br> <br> <blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1p= x #ccc solid;padding-left:1ex"> But I would generally avoid SList.<br> </blockquote> <br></div> It&#39;s not good.<br> <br> And in general linked lists are quite overrated. On modern CPUs it&#39;s no= t easy to find situations where a linked list is better than a dynamic arra= y or a chunked array (that is a dynamic array of pointers to arrays. It&#39= ;s often used to implement deques, etc).<br> <br> <br> Regarding arrays, maybe a StableVector will be good to have in Phobos:<br> <a href=3D"http://www.boost.org/doc/libs/1_50_0_beta1/doc/html/container/no= n_standard_containers.html#container.non_standard_containers.stable_vector"= target=3D"_blank">http://www.boost.org/doc/libs/<u></u>1_50_0_beta1/doc/ht= ml/<u></u>container/non_standard_<u></u>containers.html#container.non_<u></= u>standard_containers.stable_<u></u>vector</a><br> <br> Bye,<br> bearophile<br> </blockquote></div><br><div>I also think flat_map/_set from that same boost= library would be great additions when the time comes to add new stuff to s= td.container. =A0Red black trees are kind of a niche container[1]. =A0I rep= laced almost all of my usage of C++&#39;s std::set and std::map with flat_m= ap and flat_set and saw better memory use and far fewer cache misses (assum= ing I was reading the profiler correctly). =A0It was win-win since I rarely= needed std::set/::map&#39;s exclusive features (iterator stability, log N = insertions). =A0I believe I&#39;ve read Andrei added something just like th= ese to Loki.</div> <div><br></div><div><br></div><div>[1]=A0<a href=3D"http://lafstern.org/mat= t/col1.pdf">http://lafstern.org/matt/col1.pdf</a>=A0: Why you shouldn&#39;t= use set (and what you should use instead)</div><div><br></div><div>Regards= ,</div> <div>Brad Anderson</div> --bcaec517a7227143f104c3ef0466--
Jul 03 2012