On 2008-09-08 23:57:49 -0400, "Manfred_Nowak" <svv1999@hotmail.com> said:

> Andrei Alexandrescu wrote:
> 
>> maybe "nextTo" or something could be more suggestive.
> 
> r.tillBeg(s), r.tillEnd(s),
> r.fromBeg(s), r.fromEnd(s) ?
> 
> -manfred

I'm not sure I like this because you have to be careful when reversing the iterating direction. With my previous proposal, you only had to change "next" for "pull" everywhere. With yours, it's "till" to "from" *and* "Beg" to "End", as the relationship is somewhat interleaved:

r.nextUntil(s) => r.tillBeg(s)
r.nextAfter(s) => r.tillEnd(s)

r.pullUntil(s) => r.fromEnd(s)
r.pullAfter(s) => r.fromBeg(s)

-- 
Michel Fortin
michel.fortin@michelf.com
http://michelf.com/

On 2008-09-08 23:43:11 -0400, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> said:

> I like the alternate names quite some. One thing, however, is that head and rear are not near-antonyms (which ideally they should be). Maybe front and rear would be an improvement. (STL uses front and back). Also, I may be dirty-minded, but somehow headNext just sounds... bad :o).

Yeah, pehaps. I mostly wanted a verb, not "frontNext" which seems wrong, and "head" is both a noun and a verb so I kept it.

> I like the intersection functions as members because they clarify the relationship between the two ranges, which is asymmetric. I will definitely heed this suggestion. "Until" suggests iteration, however, which it shouldn't be (should be constant time) so maybe "nextTo" or something could be more suggestive.

Well, initially I thought about nextTo, but then it stuck me as also meaning "the thing just after", which is not really it. I also though about nextUpTo, but that's many capitals to type and many small words and I prefered nextUntil even with the downside of sounding like we're iterating.

But perhaps we could get rid of next and replace it with a verb.

What about this terminology?

r.frontShift      // conceptually r.front; r.shift
r.putShift(e)     // conceptually r.front = e; r.shift

r.front
r.shift
r.shiftTo(s)
r.shiftAfter(s)

r.back
r.pull
r.pullTo(s)
r.pullAfter(s)

-- 
Michel Fortin
michel.fortin@michelf.com
http://michelf.com/

On Tue, Sep 9, 2008 at 12:57 PM, Manfred_Nowak <svv1999@hotmail.com> wrote:
> Andrei Alexandrescu wrote:
>
>> maybe "nextTo" or something could be more suggestive.
>
> r.tillBeg(s), r.tillEnd(s),
> r.fromBeg(s), r.fromEnd(s) ?

Another idea might be go back to Intro to Algebra with the "FOIL" method for first,inner,outer,last.

Really you're trying to form the different elements of the cartesian
product of (rb,re) and (sb,se), so the "FOIL method" (a mnemonic for
multiplying binomials) tells you the resulting monomials are:

First:  (rb, sb)
Outer: (rb, se)
Inner: (re, sb)
Last: (re, se)

So you could have functions like:

fromFirsts(r,s)    aka  leftDiff(r,s)
fromLasts(s,r)    aka  rightDiff(r,s)  --- note the order reversal!
fromInner(r,s)     -- nonsense for ranges but would be "end of r to
beginning of s"
fromOuter(r,s)    aka leftUnion(r,s) aka rightUnion(s,r)

To me I think this way of decomposing the names makes it easier to visualize what the things are doing.  I get no picture whatsoever from "pullNext" and I think it's going to be really hard for me to remember exactly what that does.  And leftUnion is also tough because it's actually not a union of the two ranges, it's more like a union followed by intersection with complement.

Thinking in terms of which components you're plucking out to make your new iterator makes it easy for me to visualize.  But maybe not everyone had the FOIL method drilled into their heads so thoroughly at a young age like me.

Anyway I think it does suggest that maybe left and right union can just be a single union op that goes from beginning of first arg to end of second.  Maybe something like "span" would be a better name then. And the precondition is that either r contains s, or vice versa.

--bb

> r.rear

I think 'tail' would be better as the opposite of 'head'.

L.

On Mon, 08 Sep 2008 23:53:17 -0400, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:

> Robert Jacques wrote:
>> On Mon, 08 Sep 2008 20:37:41 -0400, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:
>>> Denis Koroskin wrote:
>>>> 3) Walter mentioned that built-in array could be re-implemented using a pair of pointers instead of ptr+length. Will it ever get a green light? It fits range concept much better.
>>>
>>> Walter told me to first implement my design, and if it works, he'll do the change. Yes, it does fit ranges much better because the often-used next and, um, pop will only touch one word instead of two.
>>  I'd warn that changing away from ptr+length would create logical incosistencies between 1D arrays and 2D/3D/ND arrays.
>
> How so?

An ND array is typically defined as a fat pointer like so:
struct array(T,size_t N) {
    T* ptr;
    size_t[N]    lengths;      // of each dimension
    ptrdiff_t[N] byte_strides; // of each dimension
}
So a 1D array is
{
    T* ptr;
    size_t lengths;
    ptrdiff_t byte_strides = T.sizeof; //Currently a compile time constant in the built-in array
    size_t length() { return lengths; }
}
which is logically consistent with a general dense matrix and aside from some name change and the stride being a compile time constant, is identical to the current D arrays.
However, { T* first; T* last } may not be logically extended to ND arrays, particularly sliced ND arrays, as T* last no longer has any meaning.

>>>> 4) We need some way of supporting dollar notation in user containers. The hack of using __dollar is bad (although it works).
>>>
>>> It doesn't work for multiple dimensions. There should be an opDollar(uint dim) that gives the library information on which argument count it occured in. Consider:
>>>
>>> auto x = matrix[$-1, $-1];
>>>
>>> Here the dollar's occurrences have different meanings. A good start would be to expand the above into:
>>>
>>> auto x = matrix[matrix.opDollar(0)-1, matrix.opDollar(1)-1];
>>  I'd also add that multiple dimension slicing should be supported. i.e.
>> auto x = matrix[2..5,0..$,3]
>> would become
>> auto x = matrix.opSlice(Slice!(size_t)(2,5),Slice!(size_t)(0,matrix.opDollar(0)),3)
>> with
>> struct Slice (T) { T start; T end; }
>> Strided slices would also be nice. i.e. matrix[0..$:10] // decimate the array
>
> Multidimensional slicing can be implemented with staggered indexing:
>
> matrix[2..5][0..$][3]

Yes, but doing so utilizes expression templates and is relatively slow:
matrix_row_slice temp1 = matrix.opSlice(2,5);
matrix_col_slice temp2 = temp1.opSlice(0,$);
matrix                 = temp2.opIndex(3);

And causes code bloat. Worst matrix[2..5] by itself would be an unstable type. Either foo(matrix[2..5]) would not compile or it would generate code bloat and hard to find logic bugs. (Due to the fact that you've embedded the dimension of the slice operation into the type).

> means: first, take a slice 2..5 that returns a matrix range one dimension smaller. Then, for that type take a slice from 0 to $. And so on.
>
> This works great for row-wise storage. I'm not sure how efficient it would be for other storage schemes.

No it doesn't. It works great for standard C arrays of arrays, but these are not matrices and have a large number of well documented performance issues when used as such. In general, multi-dimentional data structures relatively common and should be cleanly supported.

> Note how nice the distinction between the container and its views works: there is only one matrix. But there are many ranges and subranges within it, bearing various relationships with one another.

Yes, Data+View (i.e MVC for data structures) is a good thing(TM). But generally, matrices have been views into data and not the data themselves. (unless needed for memory management, etc)

On Tue, Sep 9, 2008 at 6:50 AM, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:
> I put together a short document for the range design. I definitely missed about a million things and have been imprecise about another million, so feedback would be highly appreciated. See:
>
> http://ssli.ee.washington.edu/~aalexand/d/tmp/std_range.html

Small typo:

"which opens forward ranges to much more many algorithms"

--bb

On Mon, 08 Sep 2008 22:22:04 -0400, Robert Jacques wrote:
> Essentially a slice of a matrix is another matrix

I see it a little differently. To me, a slice of a matrix is a set of data that can be used to construct a new matrix, among other uses of course. Because a matrix can be sliced and diced in very many ways, some of which are clearly not matrices, the best we can generalize about a matrix slice is just that it is a set of data values. How one uses those values is dependant, to a degree, on what sort of slice created the set.

-- 
Derek
(skype: derek.j.parnell)
Melbourne, Australia
9/09/2008 6:30:46 PM

Andrei Alexandrescu wrote:

[...]

4) Operations on Ranges

In the discussion on the naming of `leftDiff' etc. the arguments of all participants implicitely declared "splitting" and "concatenating" operations on ranges. But there are none defined. Why?


Googling for "range algebra" gave a hit on

http://www.idealliance.org/papers/extreme/proceedings/xslfo- pdf/2002/Nicol01/EML2002Nicol01.pdf

which seems to express pretty much of the concept presented.

-manfred
-- 
If life is going to exist in this Universe, then the one thing it cannot afford to have is a sense of proportion. (Douglas Adams)

Denis Koroskin <2korden@gmail.com> wrote:
> 5) I don't quite like names left and right! :) I think they should represent limits (pointers to begin and end, in case of array) rather that values. In this case, built-in arrays could be implemented as follows:
> 
> struct Array(T)
> {
>      T* left;
>      T* right;
>      size_t length() { return right-left; }
>      ref T opIndex(size_t index) { return left[index]; }
>      // etc
> }
> 
> The rationale behind having access to range limits is to allow operations
> on them. For example,
> R.left-=n;
> 
> could be used instead of
> foreach(i; 0..n) {
>      R.pop();
> }

Now you stepped onto your own landmine.  :)  "R.left-=n" extends the range beyond its beginning with unpredictable consequences.  That's why such operations shouldn't be easily accessible.

Andrei Alexandrescu wrote:
>(why the heck don't they call it structural typing...) 
> 
> Andrei

If it were the norm to call it "structural typing" and someone asked why it was called
so, the one being asked would likely have to resort to diagrams and gesticulation in
order to adequately convey the reasoning.

With "duck typing" a simple and widespread saying* is all that is required.

A...

* "If it walks like a duck and it quacks like a duck, then it's a duck!"