www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Ranges

reply pascal111 <judas.the.messiah.111 gmail.com> writes:
In next code from 
"https://www.tutorialspoint.com/d_programming/d_programming_ranges.htm", we
have two issues:

1) Why the programmer needs to program "empty()", "front()", and 
"popFront()" functions for ranges while they exist in the 
language library? it seems there's no need to exert efforts for 
that. "https://dlang.org/phobos/std_range_primitives.html"

2) "front()", and "popFront()" are using fixed constants to move 
forward the range, while they should use variables.


     '''D
     import std.stdio;
     import std.string;

     struct Student {
        string name;
        int number;

        string toString() const {
           return format("%s(%s)", name, number);
        }
     }

     struct School {
        Student[] students;
     }
     struct StudentRange {
        Student[] students;

        this(School school) {
           this.students = school.students;
        }
         property bool empty() const {
           return students.length == 0;
        }
         property ref Student front() {
           return students[0];
        }
        void popFront() {
           students = students[1 .. $];
        }
     }

     void main() {
        auto school = School([ Student("Raj", 1), Student("John", 
2), Student("Ram", 3)]);
        auto range = StudentRange(school);
        writeln(range);

        writeln(school.students.length);

        writeln(range.front);

        range.popFront;

        writeln(range.empty);
        writeln(range);
     }
     '''
Aug 04 2022
next sibling parent Salih Dincer <salihdb hotmail.com> writes:
On Thursday, 4 August 2022 at 13:08:21 UTC, pascal111 wrote:

 ```D
     import std.stdio;
     import std.string;

     struct Student {
        string name;
        int number;

        string toString() const {
           return format("%s(%s)", name, number);
        }
     }

     struct School {
        Student[] students;
     }
     struct StudentRange {
        Student[] students;

        this(School school) {
           this.students = school.students;
        }
         property bool empty() const {
           return students.length == 0;
        }
         property ref Student front() {
           return students[0];
        }
        void popFront() {
           students = students[1 .. $];
        }
     }

     void main() {
        auto school = School([ Student("Raj", 1), 
 Student("John", 2), Student("Ram", 3)]);
        auto range = StudentRange(school);
        writeln(range);

        writeln(school.students.length);

        writeln(range.front);

        range.popFront;

        writeln(range.empty);
        writeln(range);
     }
 ```


😀
Aug 04 2022
prev sibling next sibling parent reply frame <frame86 live.com> writes:
On Thursday, 4 August 2022 at 13:08:21 UTC, pascal111 wrote:


 1) Why the programmer needs to program "empty()", "front()", 
 and "popFront()" functions for ranges while they exist in the 
 language library? it seems there's no need to exert efforts for 
 that. "https://dlang.org/phobos/std_range_primitives.html"


- These functions are wrappers to use something as range
- Ranges need to implement the functions to keep their data 
private, also there are complex types the need to handle data 
differently
- Ranges must implement the functions so other function can 
recognize it as such (eg. `isInputRange`) - there is no common 
interface, it's determined by compile time


 2) "front()", and "popFront()" are using fixed constants to 
 move forward the range, while they should use variables.


`front()` is always using the first element BUT `popFront()` 
copies all elements except the first one into the variable (and 
overwrites it), so it moves the data forward.
Aug 04 2022
parent reply =?UTF-8?Q?Ali_=c3=87ehreli?= <acehreli yahoo.com> writes:
On 8/4/22 11:05, frame wrote:


 `popFront()`


The function was this:

        void popFront() {
           students = students[1 .. $];
        }


 copies all
 elements except the first one into the variable (and overwrites it), so
 it moves the data forward.


That would be very slow. :) What actually happens is, just the two 
variables that define a slice is adjusted.

Slices consist of two members:

struct __an_int_D_array_behind_the_scenes {
   size_t length;
   int * ptr;
}

So,

   students = students[1..$];

is the same as doing the following:

   students.length = (students.length - 1);
   students.ptr = students.ptr + 1;

(ptr's value would change by 4 bytes because 'int'.)

No element is copied or moved. :)

Ali
Aug 04 2022
next sibling parent reply pascal111 <judas.the.messiah.111 gmail.com> writes:
On Thursday, 4 August 2022 at 22:14:26 UTC, Ali Çehreli wrote:

 On 8/4/22 11:05, frame wrote:


 `popFront()`


 The function was this:

        void popFront() {
           students = students[1 .. $];
        }


 copies all
 elements except the first one into the variable (and


 overwrites it), so

 it moves the data forward.


 That would be very slow. :) What actually happens is, just the 
 two variables that define a slice is adjusted.

 Slices consist of two members:

 struct __an_int_D_array_behind_the_scenes {
   size_t length;
   int * ptr;
 }

 So,

   students = students[1..$];

 is the same as doing the following:

   students.length = (students.length - 1);
   students.ptr = students.ptr + 1;

 (ptr's value would change by 4 bytes because 'int'.)

 No element is copied or moved. :)

 Ali


I didn't notice that all what we needs to pop a range forward is 
just a slice, yes, we don't need variable here.
Aug 04 2022
parent reply Salih Dincer <salihdb hotmail.com> writes:
On Thursday, 4 August 2022 at 22:54:42 UTC, pascal111 wrote:

 I didn't notice that all what we needs to pop a range forward 
 is just a slice, yes, we don't need variable here.


Ranges and Slices are not the same thing. Slicing an array is 
easy. This is a language possibility. For example, you need an 
incrementing variable for the Fibonacci Series.

SDB 79
Aug 04 2022
parent reply pascal111 <judas.the.messiah.111 gmail.com> writes:
On Friday, 5 August 2022 at 04:05:08 UTC, Salih Dincer wrote:

 On Thursday, 4 August 2022 at 22:54:42 UTC, pascal111 wrote:

 I didn't notice that all what we needs to pop a range forward 
 is just a slice, yes, we don't need variable here.


 Ranges and Slices are not the same thing. Slicing an array is 
 easy. This is a language possibility. For example, you need an 
 incrementing variable for the Fibonacci Series.

 SDB 79


What!!! so where's ranges?! I thought slices of any array are 
ranges, and understood it like that, and also there's no data 
type called ranges, it's like if you are talking about Ghostly 
data type!
Aug 06 2022
next sibling parent reply "H. S. Teoh" <hsteoh qfbox.info> writes:
On Sat, Aug 06, 2022 at 03:37:32PM +0000, pascal111 via Digitalmars-d-learn
wrote:

 On Friday, 5 August 2022 at 04:05:08 UTC, Salih Dincer wrote:

 On Thursday, 4 August 2022 at 22:54:42 UTC, pascal111 wrote:

 
 I didn't notice that all what we needs to pop a range forward is
 just a slice, yes, we don't need variable here.


 
 Ranges and Slices are not the same thing. Slicing an array is easy.
 This is a language possibility. For example, you need an
 incrementing variable for the Fibonacci Series.
 
 SDB 79


 
 What!!! so where's ranges?! I thought slices of any array are ranges,
 and understood it like that, and also there's no data type called
 ranges, it's like if you are talking about Ghostly data type!


A range is any type that supports the Range API defined in std.range
(i.e., .empty, .front, .popFront). For more explanations, read:

	http://www.informit.com/articles/printerfriendly.aspx?p=1407357&rll=1
	http://ddili.org/ders/d.en/ranges.html
	http://dconf.org/2015/talks/davis.html
	http://tour.dlang.org/tour/en/basics/ranges
	http://wiki.dlang.org/Component_programming_with_ranges


T

-- 
No! I'm not in denial!
Aug 06 2022
parent reply pascal111 <judas.the.messiah.111 gmail.com> writes:
On Saturday, 6 August 2022 at 15:54:57 UTC, H. S. Teoh wrote:

 On Sat, Aug 06, 2022 at 03:37:32PM +0000, pascal111 via 
 Digitalmars-d-learn wrote:

 On Friday, 5 August 2022 at 04:05:08 UTC, Salih Dincer wrote:

 On Thursday, 4 August 2022 at 22:54:42 UTC, pascal111 wrote:

 [...]


 
 Ranges and Slices are not the same thing. Slicing an array 
 is easy. This is a language possibility. For example, you 
 need an incrementing variable for the Fibonacci Series.
 
 SDB 79


 
 What!!! so where's ranges?! I thought slices of any array are 
 ranges, and understood it like that, and also there's no data 
 type called ranges, it's like if you are talking about Ghostly 
 data type!


 A range is any type that supports the Range API defined in 
 std.range (i.e., .empty, .front, .popFront). For more 
 explanations, read:

 	http://www.informit.com/articles/printerfriendly.aspx?p=1407357&rll=1
 	http://ddili.org/ders/d.en/ranges.html
 	http://dconf.org/2015/talks/davis.html
 	http://tour.dlang.org/tour/en/basics/ranges
 	http://wiki.dlang.org/Component_programming_with_ranges


 T


You know, the problem is that ranges in D lack the usage of 
pointers as an essential tool to make all of ranges functions 
they need. If ranges exist in C, they would use pointers, and 
this is a powerful point in the account of C.
Aug 06 2022
parent reply =?UTF-8?Q?Ali_=c3=87ehreli?= <acehreli yahoo.com> writes:
On 8/6/22 14:10, pascal111 wrote:


 the problem is that ranges in D lack the usage of pointers as
 an essential tool to make all of ranges functions they need. If ranges
 exist in C, they would use pointers, and this is


There are a few cases where pointers provide functionality that ranges 
cannot:

1) Some algorithms don't make much sense with ranges. For example, most 
of the time find() can return just the element that we seek. In D, 
find() returns a range so that we can chain it with other algorithms.

2) Some algorithms like partition() better use three pointers.

Other than that, ranges are superior to pointers in every aspect. (I 
resent the fact that some C++ "experts" used those two points to decide 
ranges are inferior and helped deprive the C++ community of ranges for a 
very long time. The same "experts" did the same with 'static if'.)


 a powerful point in the account of C.


I missed how you made that connection.

Ali
Aug 06 2022
parent reply pascal111 <judas.the.messiah.111 gmail.com> writes:
On Sunday, 7 August 2022 at 05:12:38 UTC, Ali Çehreli wrote:

 On 8/6/22 14:10, pascal111 wrote:



 a powerful point in the account of C.


 I missed how you made that connection.


Everyone knows that slices are not pointers that pointers are 
real work, but slices are like a simple un-deep technique that is 
appropriate for beginners, but after that in advanced level in 
programming, we should use pointers to do same tasks we were 
doing with slices (the easy way of beginners).
Aug 07 2022
next sibling parent Salih Dincer <salihdb hotmail.com> writes:
On Sunday, 7 August 2022 at 15:34:19 UTC, pascal111 wrote:

 Everyone knows that slices are not pointers that pointers are 
 real work, but slices are like a simple un-deep technique that 
 is appropriate for beginners, but after that in advanced level 
 in programming, we should use pointers to do same tasks we were 
 doing with slices (the easy way of beginners).


The following information about slices may be helpful:


 Slices are objects from type T[] for any given type T. Slices 
 provide a view on a subset of an array of T values - or just 
 point to the whole array. Slices and dynamic arrays are the 
 same.

 A slice consists of two members - a pointer to the starting 
 element and the length of the slice:
 ```d
 T* ptr;
 size_t length; // unsigned 32 bit on 32bit, unsigned 64 bit on 
 64bit
 ```
 [...]


**Source:** https://tour.dlang.org/tour/en/basics/slices

SDB 79
Aug 07 2022
prev sibling next sibling parent reply ag0aep6g <anonymous example.com> writes:
On Sunday, 7 August 2022 at 15:34:19 UTC, pascal111 wrote:

 Everyone knows that slices are not pointers that pointers are 
 real work, but slices are like a simple un-deep technique that 
 is appropriate for beginners, but after that in advanced level 
 in programming, we should use pointers to do same tasks we were 
 doing with slices (the easy way of beginners).


I can't tell if this is a joke or not.
Aug 07 2022
parent pascal111 <judas.the.messiah.111 gmail.com> writes:
On Sunday, 7 August 2022 at 19:53:06 UTC, ag0aep6g wrote:

 On Sunday, 7 August 2022 at 15:34:19 UTC, pascal111 wrote:

 Everyone knows that slices are not pointers that pointers are 
 real work, but slices are like a simple un-deep technique that 
 is appropriate for beginners, but after that in advanced level 
 in programming, we should use pointers to do same tasks we 
 were doing with slices (the easy way of beginners).


 I can't tell if this is a joke or not.


It's just an opinion.
Aug 07 2022
prev sibling parent reply =?UTF-8?Q?Ali_=c3=87ehreli?= <acehreli yahoo.com> writes:
On 8/7/22 08:34, pascal111 wrote:


 Everyone knows that slices are not pointers


D's slices are "fat pointers": In D's case, that translates to a pointer 
plus length.


 that pointers are real work,


Agreed. Pointers are fundamental features of CPUs.


 but slices are like a simple un-deep technique that is appropriate for
 beginners,


That is not correct. Slices are designed by a C expert to prevent 
horrible bugs caused by C experts. Most C experts use slices very happily.


 but after that in advanced level in programming, we should
 use pointers to do same tasks we were doing with slices (the easy way of
 beginners).


That is an old thought. Today, we see that no matter how experienced, 
every person needs and appreciates help to prevent bugs. There are many 
cases of bugs killing people, jeopardizing expensive projects, loss of 
personal information, etc.

Ali
Aug 07 2022
parent pascal111 <judas.the.messiah.111 gmail.com> writes:
On Sunday, 7 August 2022 at 21:57:50 UTC, Ali Çehreli wrote:

 On 8/7/22 08:34, pascal111 wrote:


 but after that in advanced level in programming, we should
 use pointers to do same tasks we were doing with slices (the


 easy way of

 beginners).


 That is an old thought. Today, we see that no matter how 
 experienced, every person needs and appreciates help to prevent 
 bugs. There are many cases of bugs killing people, jeopardizing 
 expensive projects, loss of personal information, etc.

 Ali


I think you are right that this is an old thought, I didn't 
noticed that, maybe it's because I didn't study C++ and know only 
about C, so I applied C features on D.
Aug 07 2022
prev sibling next sibling parent reply Salih Dincer <salihdb hotmail.com> writes:
On Saturday, 6 August 2022 at 15:37:32 UTC, pascal111 wrote:

 On Friday, 5 August 2022 at 04:05:08 UTC, Salih Dincer wrote:

 On Thursday, 4 August 2022 at 22:54:42 UTC, pascal111 wrote:

 I didn't notice that all what we needs to pop a range forward 
 is just a slice, yes, we don't need variable here.


 Ranges and Slices are not the same thing. Slicing an array is 
 easy. This is a language possibility. For example, you need an 
 incrementing variable for the Fibonacci Series.

 SDB 79


 What!!! so where's ranges?! I thought slices of any array are 
 ranges, and understood it like that, and also there's no data 
 type called ranges, it's like if you are talking about Ghostly 
 data type!


Well, that's very normal. Because as you work with ranges, you 
will understand better. Indeed, the slices (we can call it a 
dynamic array) feel like slice, don't they?

SDB 79
Aug 06 2022
parent reply Salih Dincer <salihdb hotmail.com> writes:
On Saturday, 6 August 2022 at 16:30:55 UTC, Salih Dincer wrote:

 Indeed, the slices (we can call it a dynamic array) feel like 
 slice, don't they?


Edit: Indeed, the slices feel like ranges, don't they?

Sorry...

SDB 79
Aug 06 2022
parent reply =?UTF-8?Q?Ali_=c3=87ehreli?= <acehreli yahoo.com> writes:
On 8/6/22 09:33, Salih Dincer wrote:


 the slices feel like ranges, don't they?


Yes because they are ranges. :) (Maybe you meant they don't have range 
member functions, which is true.)

D's slices happen to be the most capable range kind: RandonAccessRange. 
All of the following operations are supported on them as long as one 
imports std.array (or std.range, which publicly does so):

- empty
- front
- popFront
- save
- back
- popBack
- indexed element access

Slices have the optional length property as well (i.e. hasLength).

Those operations are not supported by member functions but by 
free-standing functions.

Ali
Aug 06 2022
parent reply Salih Dincer <salihdb hotmail.com> writes:
On Saturday, 6 August 2022 at 17:29:30 UTC, Ali Çehreli wrote:

 On 8/6/22 09:33, Salih Dincer wrote:


 the slices feel like ranges, don't they?


 Yes because they are ranges. :) (Maybe you meant they don't 
 have range member functions, which is true.)


Slices use pointers.  Do I need to tell you what the pointers do! 
  Each of them points to a data.  Ranges are not like that, all 
they do is generate.  Ok, you use a slice just as if it were a 
range.  But they are not ranges.

SDB 79
Aug 06 2022
parent =?UTF-8?Q?Ali_=c3=87ehreli?= <acehreli yahoo.com> writes:
On 8/6/22 22:58, Salih Dincer wrote:


 Ranges are not like that, all they do is
 generate.


You may be right. I've never seen it that way.

I've been under the following impression:

- C++'s iterators are based on an existing concept: pointers. Pointers 
are iterators.

- D's ranges are based on an existing concept: slices. Slices are ranges.

However, I can't find where I read that.

Ali
Aug 07 2022
prev sibling parent Emanuele Torre <torreemanuele6 gmail.com> writes:
On Saturday, 6 August 2022 at 15:37:32 UTC, pascal111 wrote:

 On Friday, 5 August 2022 at 04:05:08 UTC, Salih Dincer wrote:

 On Thursday, 4 August 2022 at 22:54:42 UTC, pascal111 wrote:

 I didn't notice that all what we needs to pop a range forward 
 is just a slice, yes, we don't need variable here.


 Ranges and Slices are not the same thing. Slicing an array is 
 easy. This is a language possibility. For example, you need an 
 incrementing variable for the Fibonacci Series.

 SDB 79


 What!!! so where's ranges?! I thought slices of any array are 
 ranges, and understood it like that, and also there's no data 
 type called ranges, it's like if you are talking about Ghostly 
 data type!


A range is like an iterator in any other language (Java, C++, 
python3, javascript, etc), it is how D implements (lazy) 
generators https://en.wikipedia.org/wiki/Lazy_evaluation .

Ranges/Iterators don't necessarily have to be backed by memory, 
they just have to implement the interface. In D, a `empty` bool 
function that tells you whether you are at the end of the range 
or not; a `front` function to get the current value if the range 
is not `empty`; and a void function named `popFront` to advance 
to the next value if the range is not `empty`.

Once you have implemented this interface, you can use your 
"range" object with any function that accept a range; with 
`foreach`; etc.

Example of a range that is not backed by memory is a range with 
all the integer numbers.

```D
struct Integers {
   private int z = 0;

   /* or make it a bool attribute that starts as false, and you 
set to
    * true when popFront is called while z is equal to int.min */
   public bool empty() { return false; }

   public int front() { return this.z; }

   public void popFront()
   {
     /* if (this.z == int.min) { this.empty = false; return; } */
     this.z *= -1;
     if (this.z <= 0)
       --this.z;
   }
}

void main()
{
   import std.stdio : writeln;

   /* foreach is syntax sugar for
    *   for (auto r = Integers(); !r.empty(); r.popFront()) {
    *     auto z = r.front(); /+ or  const z = r.front();  or ... 
+/
    *     ...
    *   }
    * that is why it only works with ranges.
    */
   foreach (const z; Integers()) {
     writeln(z);
     if (z == 5)
       break;
   }
}
```

output:
```
0
-1
1
-2
2
-3
3
-4
4
-5
5
```

This will iterate all the integers, and the integers are of 
course, not
all in memory, and don't remain in memory after they are used, 
since
that would require infinite memory. (in the case of a range of 
integers,
not infinite, because they are constrained by being int.sizeof 
bytes,
but you could use a bignum implemenation that is not constrained 
by
that and they would actually be infinite.)

---

The equivalent in Java is the Iterable/Iterator interface.

```java
import java.util.Iterator;

public class Integers
   implements Iterable<Integer>
{
   public class IntegersIterator
     implements Iterator<Integer>
   {
     private int z = 0;
     private boolean first = true;

     public IntegersIterator(Integer z)
     {
       this.z = z;
     }

      Override
     public boolean hasNext() { return true; }

      Override
     public Integer next()
     {
       if (this.first) {
         this.first = false;
         return this.z;
       }

       this.z *= -1;
       if (this.z <= 0)
         --this.z;
       return this.z;
     }
   }

    Override
   public IntegersIterator iterator() { return new 
IntegersIterator(0); }

   public static void main(String[] args)
   {
     /* syntax sugar for
      *   {
      *     final var it = newIntegers.iterator();
      *     while (it.hasNext()) {
      *       final int z = it.next();
      *       ...
      *     }
      *   }
      */
     for (final int z : new Integers()) {
       System.out.println(z);
       if (z == 5)
         break;
     }
   }
}
```

The equivalent in python is a generator function:
```python
def integers():
   z = 0
   yield z
   while True:
     z *= -1
     if z <= 0:
       z -= 1
     yield z

for z in integers():
   print(z)
   if z == 5:
     break
```

etc
Aug 07 2022
prev sibling parent reply frame <frame86 live.com> writes:
On Thursday, 4 August 2022 at 22:14:26 UTC, Ali Çehreli wrote:


 No element is copied or moved. :)

 Ali


I know that :) I just found that this user has problems to 
understand basics in D, so I tried not to go in detail and keep 
at its kind of logical layer. It seems the better way to help 
until the user asks specific questions.
Aug 05 2022
parent reply =?UTF-8?Q?Ali_=c3=87ehreli?= <acehreli yahoo.com> writes:
On 8/5/22 01:59, frame wrote:

 On Thursday, 4 August 2022 at 22:14:26 UTC, Ali Çehreli wrote:


 No element is copied or moved. :)

 Ali


 I know that :)


And I know that. :) We don't know who else is reading these threads, so 
I didn't want to give wrong impression.

Copying would happen if we added slicing on the left-hand side. However, 
I realized that the following fails with a RangeError:

void main() {
   auto arr = [1, 2, 3];
   arr[0..$-1] = arr[1..$];    // <-- Runtime error
}

I suspect the length of the array is stamped too soon. (?)

Should that operation be supported?

Ali
Aug 05 2022
parent "H. S. Teoh" <hsteoh qfbox.info> writes:
On Fri, Aug 05, 2022 at 08:06:00AM -0700, Ali Çehreli via Digitalmars-d-learn
wrote:

 [...] I realized that the following fails with a RangeError:
 
 void main() {
   auto arr = [1, 2, 3];
   arr[0..$-1] = arr[1..$];    // <-- Runtime error
 }
 
 I suspect the length of the array is stamped too soon. (?)
 
 Should that operation be supported?


[...]

This is why in C there's a difference between memcpy and memmove.  I
don't know how to express the equivalent in D, though. In general, you
can't tell until runtime whether two slices overlap (`arr` could be
aliased by another slice, for example, so you can't just tell by whether
you're copying an overlapping range from the same variable).

But if you know beforehand the ranges being copied are overlapping, you
could use std.algorithm.bringToFront which would do the Right Thing(tm)
in this case.


T

-- 
Why are you blatanly misspelling "blatant"? -- Branden Robinson
Aug 05 2022
prev sibling parent =?UTF-8?Q?Ali_=c3=87ehreli?= <acehreli yahoo.com> writes:
On 8/4/22 06:08, pascal111 wrote:

 In next code from
 "https://www.tutorialspoint.com/d_programming/d_programming_ranges.htm",


That page seems to be adapted from this original:

   http://ddili.org/ders/d.en/ranges.html


 we have two issues:

 1) Why the programmer needs to program "empty()", "front()", and
 "popFront()" functions for ranges


The programmer almost never needs to implement those functions. Existing 
data structures and algorithms are almost always sufficient. (I did need 
to implement them but really rarely.)

I tried to explain what those functions do. I don't like my Students 
example much because wrapping a D slice does not make much sense. Again, 
I just try to explain them.


 while they exist in the language
 library?


The existing front, popFronh, etc. are only for arrays (slices).


 it seems there's no need to exert efforts for that.


Exactly.


 "https://dlang.org/phobos/std_range_primitives.html"

 2) "front()", and "popFront()" are using fixed constants to move forward
 the range, while they should use variables.


Well, 0 is always the first element and 1..$ are always the rest. 
Variables would not add any value there.

However, the example could use the existing library function that you 
mention:


          property bool empty() const {
            return students.length == 0;


Better:

              import std.array : empty;
              return students.empty;


         }
          property ref Student front() {
            return students[0];


Better:

              import std.array : front;
              return students.front;


         }
         void popFront() {
            students = students[1 .. $];


Better:

              import std.array : popFront;
              students.popFront();

But I think those implementations might confuse the reader.

Ali
Aug 04 2022