www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - rotate left an array

reply Fausto <fausap outlook.it> writes:
Hello all,

I am trying to rotate left an array.
I found a very basic way, and I am not sure if there is something 
clever than this :) maybe using slices...
the external for represents how many times you are rotating (in 
this case 2).

```d
void main()
{
     import std.range;
     import std.stdio: write, writeln, writef, writefln;

     int[] arr1 = [ 1, 2, 3, 4 ];
     int t = 0;

     writeln(arr1);

     for (int j = 0;j<2;j++) {
     t = arr1[0];
     for(int i = 0;i<arr1.length-1;i++) {
         arr1[i] =  arr1[i+1];
     }
     arr1[$-1] = t;
     }

     writeln(arr1);

}
```

thanks a lot
Fausto
Oct 03 2022
next sibling parent Nick Treleaven <nick geany.org> writes:
On Monday, 3 October 2022 at 18:09:05 UTC, Fausto wrote:

 Hello all,

 I am trying to rotate left an array.
 I found a very basic way, and I am not sure if there is 
 something clever than this :) maybe using slices...


Here we can't use slice assignment instead of the inner loop 
because that doesn't work for an overlapping slice. (Instead 
there's `copy` in std.algorithm).

The algorithm you wrote doesn't scale the best for speed - yours 
is the second one mentioned here:
https://www.geeksforgeeks.org/array-rotation/

Phobos has `bringToFront(arr[0..2], arr[2..$])` which does the 
same thing as a `rotate(arr, 2)` function. It seems to use the 
third algorithm from the link (or at least has the same time and 
space complexity).

The first algorithm may also work better in some cases, when 
swapping is expensive or when the result is duplicated anyway.
Oct 03 2022
prev sibling next sibling parent reply Andrey Zherikov <andrey.zherikov gmail.com> writes:
On Monday, 3 October 2022 at 18:09:05 UTC, Fausto wrote:

 Hello all,

 I am trying to rotate left an array.
 I found a very basic way, and I am not sure if there is 
 something clever than this :) maybe using slices...
 the external for represents how many times you are rotating (in 
 this case 2).


If you don't need to add or remove the data from your array then 
I'd go with constant array and translating external index to an 
internal one for this array. So it's gonna be something like a 
"rotated view".
Oct 03 2022
parent reply =?UTF-8?Q?Ali_=c3=87ehreli?= <acehreli yahoo.com> writes:
On 10/3/22 13:48, Andrey Zherikov wrote:

 a "rotated view".


Without indexes:

import std.range : empty;

auto rotatedView(R)(R range)
in (!range.empty)
{
     import std.range : chain, front, only, popFront;
     const fr = range.front;
     range.popFront();
     return chain(range, only(fr));
}

void main()
{
     import std.algorithm : equal;
     int[] arr1 = [ 1, 2, 3, 4 ];
     assert(arr1.rotatedView.equal([ 2, 3, 4, 1 ]));

     // Now this is getting a little expensive! :)
     assert(arr1
            .rotatedView
            .rotatedView
            .equal([ 3, 4, 1, 2 ]));
}

Ali
Oct 03 2022
next sibling parent reply Paul Backus <snarwin gmail.com> writes:
On Monday, 3 October 2022 at 21:06:36 UTC, Ali Çehreli wrote:

 On 10/3/22 13:48, Andrey Zherikov wrote:

 a "rotated view".


 Without indexes:

 import std.range : empty;

 auto rotatedView(R)(R range)
 in (!range.empty)
 {
     import std.range : chain, front, only, popFront;
     const fr = range.front;
     range.popFront();
     return chain(range, only(fr));
 }


Tiny nitpick: this should use

     const fr = range.save.front;

...to ensure that `fr` is not invaliated or overwritten by the 
subsequent call to range.popFront (e.g., think of File.byLine 
here).
Oct 03 2022
parent reply =?UTF-8?Q?Ali_=c3=87ehreli?= <acehreli yahoo.com> writes:
On 10/3/22 17:00, Paul Backus wrote:

 On Monday, 3 October 2022 at 21:06:36 UTC, Ali Çehreli wrote:

 On 10/3/22 13:48, Andrey Zherikov wrote:

 a "rotated view".


 Without indexes:

 import std.range : empty;

 auto rotatedView(R)(R range)
 in (!range.empty)
 {
     import std.range : chain, front, only, popFront;
     const fr = range.front;
     range.popFront();
     return chain(range, only(fr));
 }


 Tiny nitpick: this should use

      const fr = range.save.front;

 ...to ensure that `fr` is not invaliated or overwritten by the
 subsequent call to range.popFront (e.g., think of File.byLine here).


Good catch but I think what we want is a copy of the front element, at 
least for InputRanges (.save does not work for File.byLine :/).

What is the generic way of copying an element? I wonder whether we have 
to use isSomeString to take care of all element types.

Ali
Oct 03 2022
next sibling parent Paul Backus <snarwin gmail.com> writes:
On Tuesday, 4 October 2022 at 00:38:25 UTC, Ali Çehreli wrote:

 Good catch but I think what we want is a copy of the front 
 element, at least for InputRanges (.save does not work for 
 File.byLine :/).

 What is the generic way of copying an element? I wonder whether 
 we have to use isSomeString to take care of all element types.


AFAIK there is no generic way to perform a deep copy of an 
arbitrary value in D. You could write a function to do it for all 
built-in types, but you might still run into trouble with 
user-defined types (e.g., how do you deep-copy a RefCounted!T 
without any knowledge of its specific semantics?).

I guess you could use a hybrid approach; e.g.,

     static if (isDeepCopyable!(ElementType!R))
         auto fr = range.front.deepCopy;
     else
         auto fr = range.front.save;

This would make it possible to accommodate some pure input ranges 
(including File.byLine), but would still require a forward range 
in the general case.
Oct 03 2022
prev sibling parent "H. S. Teoh" <hsteoh qfbox.info> writes:
On Mon, Oct 03, 2022 at 05:38:25PM -0700, Ali Çehreli via Digitalmars-d-learn
wrote:
[...]

 Good catch but I think what we want is a copy of the front element, at
 least for InputRanges (.save does not work for File.byLine :/).


One of the things we need to settle in Phobos v2 is what to do with
transient ranges like File.byLine (i.e., ranges whose .front value is
invalidated by .popFront).  When you don't need to access each line
after calling .popFront, .byLine's current implementation reduces
allocations and decreases GC pressure.  However, when you do need to
save it, it produces counterintuitive results, like here.



 What is the generic way of copying an element? I wonder whether we
 have to use isSomeString to take care of all element types.


[...]

This was discussed many years ago.  There is no generic way to copy an
element, because there is no language-wide .clone method that enforces
the right semantics for every type.  You cannot simply deep-copy
something, as might be a tempting solution at first glance, because you
cannot tell, for an arbitary type, whether a reference member is meant
to be an owning reference (the referent needs to be cloned) or a
non-owning reference (the referent should not be cloned).  Both are
valid use cases, and there is no way to distinguish between them without
contextual knowledge of the type.

For example, if your range is generating, say, a tree of objects each
time .popFront is called, then you probably want to deep-copy the object
tree when you're saving the element.  However, if the range is iterating
over, say, some nodes in a preexisting graph, then you probably *don't*
want to be duplicating graph nodes when you save the value of .front,
because in this case .front merely references these nodes, it doesn't
own them.  Without application-specific knowledge, you can't tell which
of these cases you're dealing with.


T

-- 
Customer support: the art of getting your clients to pay for your own
incompetence.
Oct 03 2022
prev sibling parent rassoc <rassoc posteo.de> writes:
On 10/3/22 23:06, Ali Çehreli via Digitalmars-d-learn wrote:

 auto rotatedView(R)(R range)


Or even more generic by chaining two slices in case the range permits it:

auto rotatedView(R)(R range, long n = 1)
if (...)
{
	if (n == 0) return range;
	...
	n %= range.length;
	...
	return chain(slice1, slice2);
}

Used something like that in previous advent of code challenges where they
expect you to go for doubly linked lists due to large buffer size.
Oct 03 2022
prev sibling parent =?UTF-8?Q?Christian_K=c3=b6stlin?= <christian.koestlin gmail.com> writes:
If you are ok with using things from std.range you could use something 
like this:


```d
import std.range : cycle, drop, take;
import std.stdio : writeln;

int main(string[] args)
{
     auto r = [1, 2, 3, 4, 5, 6, 7, 8];
     writeln(r.cycle.drop(3).take(r.length));
     return 0;
}
```

Kind regards,
Christian
Oct 04 2022