www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - proper range usage

reply Alex <sascha.orlov gmail.com> writes:
Hi everybody,

first of all: this question is going to be unclear, because I'm 
lack of the "buzz word" I would like to ask about, sorry for this 
in advance.

I try to describe the problem, where I stuck and hope somebody 
could think just a step further. Just a hint where to read about 
the way of solution would be enough, I think.

Starting with chapter 73 in the recent "Programming in D" book 
(the revision of 2015-10-24), about "foreach with structs and 
classes" I would like to implement either the opAssign method or 
the three range member functions in a simple struct.
Let's say, the example of NumberRange struct in the example on 
page 486 is enough. In terms of .front(), .popFront() and .empty: 
I understand what the first two things do, but I have a problem 
with the empty property:

In my case, the container class can't become empty. Even if it 
contains one single element, in this case the example should 
return true for begin == end, it is not empty. At the same time, 
my container is surely always finite, so I can't define the empty 
property to false as shown on page 568, last line.

A further problem/wish is: I don't want to store my elements 
explicitly as members. So taking the simplest example on page 486 
has a further meaning for me: It does not contain an array as 
member and it is not meant to.

So far from me. I hope, I could describe my problem good enough 
and I hope somebody could help me out. Still, the solution is 
important, but I also would like to know what a weird thing I'm 
describing in terms of... well... some structure... not to say 
pattern :)

Thanks in advance
Alex
Nov 02 2015
parent reply =?UTF-8?Q?Ali_=c3=87ehreli?= <acehreli yahoo.com> writes:
On 11/02/2015 11:59 PM, Alex wrote:


 "Programming in D" book (the revision of 2015-10-24)


Oooh! That smells very fresh. :)


 In my case, the container class can't become empty. Even if it contains
 one single element, in this case the example should return true for
 begin == end, it is not empty.


That problem is solved by the convention that 'end' is one beyond the 
last valid element. So, when there is only the element 42, then 
begin==42 and end==43. Only when the last element (42 in this case) is 
consumed, begin==end.


 A further problem/wish is: I don't want to store my elements explicitly
 as members. So taking the simplest example on page 486 has a further
 meaning for me: It does not contain an array as member and it is not
 meant to.


Such ranges are called generators. As long as .front returns the current 
element, and popFront() advances to the next one, you don't need to 
store any array. (You seem to say the same thing, so I don't understand 
the question.)

Ali
Nov 03 2015
parent reply Alex <sascha.orlov gmail.com> writes:
On Tuesday, 3 November 2015 at 08:23:20 UTC, Ali Çehreli wrote:

 "Programming in D" book (the revision of 2015-10-24)


 Oooh! That smells very fresh. :)


:)


 In my case, the container class can't become empty. Even if


 it contains

 one single element, in this case the example should return


 true for

 begin == end, it is not empty.


 That problem is solved by the convention that 'end' is one 
 beyond the last valid element. So, when there is only the 
 element 42, then begin==42 and end==43. Only when the last 
 element (42 in this case) is consumed, begin==end.


This part is dangerous, and I'm not sure how dangerous it is. 
Now, I have to dive into my structure a little bit deeper:
Say, I have three classes:


class B //current structure
{
     M[] _ms;
     P[] _ps;
     P[M] assoc;
}

struct M
{
     int id;
     alias id this;
}

struct P
{
     int id;
     alias id this;
     int begin;
     int end;
}

The idea is, that P structs are disjunct (and contigous, if this 
does matter) arrays of M's. And the question is, what happens, if 
I set the end property of a P to a number, which belongs to 
another P.
At the current time class B contains arrays of different M's 
(constant, big one, say order of 10^6 elements, elements itself 
are not very large, say about 5 members and a bunch of properties 
calculated at runtime) as well as an array of P's (at the 
beginning not so big one, but growing fast) and the array of 
associations between the M's and P's. In my program I implement 
this array as int[int], and reassign the associated values at the 
same time as the array of P's is growing.

Here I have to deliver the "buzz words", so I'm trying to 
implement a set partition algorithm with disjoint sets. With the 
standard question how to achieve the fastest cutting of the whole 
array into its single components. The application in my case are 
just some constraints which say, how the cutting is allowed.


 Such ranges are called generators.


ok, cool! Thx.
Nov 03 2015
next sibling parent Alex <sascha.orlov gmail.com> writes:
... and yes, each P's M's are meant to be the same, as the 
associated M's in the B's class to the P. If you understand, what 
I mean ;)
Nov 03 2015
prev sibling parent reply =?UTF-8?Q?Ali_=c3=87ehreli?= <acehreli yahoo.com> writes:
On 11/03/2015 01:12 AM, Alex wrote:


 That problem is solved by the convention that 'end' is one beyond the
 last valid element. So, when there is only the element 42, then
 begin==42 and end==43. Only when the last element (42 in this case) is
 consumed, begin==end.


 This part is dangerous, and I'm not sure how dangerous it is.


If I understand correctly, you are referring to 'end' being one beyond. 
It is not dangerous because nobody dereferences that index. The slice is 
simply empty when beg==end.

This is how C++'s iterators work and how D's number ranges work:

     foreach (i; 0 .. 3) {
         arr[i];    // i will not be 3
     }


 Now, I
 have to dive into my structure a little bit deeper:
 Say, I have three classes:


 class B //current structure
 {
      M[] _ms;
      P[] _ps;
      P[M] assoc;
 }

 struct M
 {
      int id;
      alias id this;
 }

 struct P
 {
      int id;
      alias id this;
      int begin;
      int end;
 }



 The idea is, that P structs are disjunct (and contigous, if this does
 matter) arrays of M's. And the question is, what happens, if I set the
 end property of a P to a number, which belongs to another P.


That's fine. D's slices do that all the time: arr[0..3] and arr[3..$] 
seem to share index 3 but it is not the case: The first slice does not 
use it but the second one does.

Aside: If 'begin' and 'end' are indexes into an actual array (of Ms? I 
forgot), perhaps you can keep slices instead:

struct P
{
      int id;
      alias id this;
      M[] ms;    // <--
}

It would be almost as efficient but larger: Altough you use two ints 
(total 8 bytes), a slice is 16 bytes on a 64-bit system: a pointer and a 
size_t.

Ali
Nov 03 2015
parent Alex <sascha.orlov gmail.com> writes:
On Tuesday, 3 November 2015 at 22:36:21 UTC, Ali Çehreli wrote:


 That's fine. D's slices do that all the time: arr[0..3] and 
 arr[3..$] seem to share index 3 but it is not the case: The 
 first slice does not use it but the second one does.


Ok... great! This is what I worried about...


 Aside: If 'begin' and 'end' are indexes into an actual array 
 (of Ms? I forgot), perhaps you can keep slices instead:

 struct P
 {
      int id;
      alias id this;
      M[] ms;    // <--
 }

 It would be almost as efficient but larger: Altough you use two 
 ints (total 8 bytes), a slice is 16 bytes on a 64-bit system: a 
 pointer and a size_t.


Thats cool! Thank you very much!
Nov 03 2015