Jump to page: 1 2
Thread overview
Arrays - Inserting and moving data
Feb 09, 2012
MattCodr
Feb 09, 2012
Pedro Lacerda
Feb 09, 2012
MattCodr
Feb 09, 2012
Ali Çehreli
Feb 09, 2012
H. S. Teoh
Feb 09, 2012
Ali Çehreli
Feb 09, 2012
MattCodr
Feb 09, 2012
Timon Gehr
Feb 09, 2012
MattCodr
Feb 10, 2012
Marco Leise
Feb 10, 2012
Jonathan M Davis
Feb 13, 2012
James Miller
Feb 13, 2012
Timon Gehr
Feb 13, 2012
James Miller
Feb 13, 2012
Ali Çehreli
Feb 14, 2012
James Miller
Feb 14, 2012
Jonathan M Davis
Feb 14, 2012
Timon Gehr
Feb 15, 2012
Manfred Nowak
February 09, 2012
I have a doubt about the best way to insert and move (not replace) some data on an array.

For example,

In some cases if I want to do action above, I do a loop moving the data until the point that I want and finally I insert the new data there.


In D I did this:

begin code
.
.
.
   int[] arr = [0,1,2,3,4,5,6,7,8,9];

   arr.insertInPlace(position, newValue);
   arr.popBack();
.
.
.
end code


After the insertInPlace my array changed it's length to 11, so I use arr.popBack(); to keep the array length = 10;

The code above is working well, I just want know if is there a better way?

Thanks,

Matheus.
February 09, 2012
I __believe__ that insertInPlace doesn't shift the elements, but use an
appender allocating another array instead.
Maybe this function do what you want.


    int[] arr = [0,1,2,3,4,5,6,7,8,9];

    void maybe(T)(T[] arr, size_t pos, T value) {
        size_t i;
        for (i = arr.length - 1; i > pos; i--) {
            arr[i] = arr[i-1];
        }
        arr[i] = value;
    }

    maybe(arr, 3, 0);
    maybe(arr, 0, 1);
    assert(arr == [1, 0, 1, 2, 0, 3, 4, 5, 6, 7]);



2012/2/9 MattCodr <matheus_nab@hotmail.com>

> I have a doubt about the best way to insert and move (not replace) some
> data on an array.
>
> For example,
>
> In some cases if I want to do action above, I do a loop moving the data until the point that I want and finally I insert the new data there.
>
>
> In D I did this:
>
> begin code
> .
> .
> .
>   int[] arr = [0,1,2,3,4,5,6,7,8,9];
>
>   arr.insertInPlace(position, newValue);
>   arr.popBack();
> .
> .
> .
> end code
>
>
> After the insertInPlace my array changed it's length to 11, so I use arr.popBack(); to keep the array length = 10;
>
> The code above is working well, I just want know if is there a better way?
>
> Thanks,
>
> Matheus.
>


February 09, 2012
On Thursday, 9 February 2012 at 12:51:09 UTC, Pedro Lacerda wrote:
> I __believe__ that insertInPlace doesn't shift the elements,

Yes, It appears that it really doesn't shift the array, insertInPlace just returns a new array with a new element in n position.


> Maybe this function do what you want.
>
>
>   int[] arr = [0,1,2,3,4,5,6,7,8,9];
>
>   void maybe(T)(T[] arr, size_t pos, T value) {
>       size_t i;
>       for (i = arr.length - 1; i > pos; i--) {
>           arr[i] = arr[i-1];
>       }
>       arr[i] = value;
>   }
>


In fact, I usually wrote functions as you did. I just looking for a new way to do that with D and Phobos lib.

Thanks,

Matheus.
February 09, 2012
On 02/09/2012 03:47 AM, MattCodr wrote:
> I have a doubt about the best way to insert and move (not replace) some
> data on an array.
>
> For example,
>
> In some cases if I want to do action above, I do a loop moving the data
> until the point that I want and finally I insert the new data there.
>
>
> In D I did this:
>
> begin code
> .
> .
> .
> int[] arr = [0,1,2,3,4,5,6,7,8,9];
>
> arr.insertInPlace(position, newValue);
> arr.popBack();
> .
> .
> .
> end code
>
>
> After the insertInPlace my array changed it's length to 11, so I use
> arr.popBack(); to keep the array length = 10;
>
> The code above is working well, I just want know if is there a better way?
>
> Thanks,
>
> Matheus.

Most straightforward that I know of is the following:

    arr = arr[0 .. position] ~ [ newValue ] ~ arr[position + 1 .. $];

But if you don't actually want to modify the data, you can merely access the elements in-place by std.range.chain:

import std.stdio;
import std.range;

void main()
{
    int[] arr = [0,1,2,3,4,5,6,7,8,9];
    immutable position = arr.length / 2;
    immutable newValue = 42;

    auto r = chain(arr[0 .. position], [ newValue ], arr[position + 1 .. $]);
    writeln(r);
}

'r' above is a lazy range that just provides access to the three ranges given to it. 'arr' does not change in any way.

Ali
February 09, 2012
On Thu, Feb 09, 2012 at 10:30:22AM -0800, Ali Çehreli wrote: [...]
> But if you don't actually want to modify the data, you can merely access the elements in-place by std.range.chain:
> 
> import std.stdio;
> import std.range;
> 
> void main()
> {
>     int[] arr = [0,1,2,3,4,5,6,7,8,9];
>     immutable position = arr.length / 2;
>     immutable newValue = 42;
> 
>     auto r = chain(arr[0 .. position], [ newValue ], arr[position +
> 1 .. $]);
>     writeln(r);
> }
> 
> 'r' above is a lazy range that just provides access to the three ranges given to it. 'arr' does not change in any way.
[...]

Wow! This is really cool. So you *can* have O(1) insertions in the
middle of an array after all. :)

Of course, you probably want to flatten it once in a while to keep random access cost from skyrocketing. (I'm assuming delegates or something equivalent are involved in generating the lazy range?)


T

-- 
Give a man a fish, and he eats once. Teach a man to fish, and he will sit forever.
February 09, 2012
On Thursday, 9 February 2012 at 18:30:22 UTC, Ali Çehreli wrote:
> On 02/09/2012 03:47 AM, MattCodr wrote:
>> I have a doubt about the best way to insert and move (not replace) some
>> data on an array.
>>
>> For example,
>>
>> In some cases if I want to do action above, I do a loop moving the data
>> until the point that I want and finally I insert the new data there.
>>
>>
>> In D I did this:
>>
>> begin code
>> .
>> .
>> .
>> int[] arr = [0,1,2,3,4,5,6,7,8,9];
>>
>> arr.insertInPlace(position, newValue);
>> arr.popBack();
>> .
>> .
>> .
>> end code
>>
>>
>> After the insertInPlace my array changed it's length to 11, so I use
>> arr.popBack(); to keep the array length = 10;
>>
>> The code above is working well, I just want know if is there a better way?
>>
>> Thanks,
>>
>> Matheus.
>
> Most straightforward that I know of is the following:
>
>    arr = arr[0 .. position] ~ [ newValue ] ~ arr[position + 1 .. $];
>
> But if you don't actually want to modify the data, you can merely access the elements in-place by std.range.chain:
>
> import std.stdio;
> import std.range;
>
> void main()
> {
>    int[] arr = [0,1,2,3,4,5,6,7,8,9];
>    immutable position = arr.length / 2;
>    immutable newValue = 42;
>
>    auto r = chain(arr[0 .. position], [ newValue ], arr[position + 1 .. $]);
>    writeln(r);
> }
>
> 'r' above is a lazy range that just provides access to the three ranges given to it. 'arr' does not change in any way.
>
> Ali

Hi Ali,

You gave me a tip with this "chain" feature.

I changed a few lines of your code, and it worked as I wanted:


import std.stdio;
import std.range;
import std.array;

void main()
{
    int[] arr = [0,1,2,3,4,5,6,7,8,9];
    immutable position = arr.length / 2;
    immutable newValue = 42;

    auto r = chain(arr[0 .. position], [ newValue ], arr[position .. $-1]);
    arr = array(r);

    foreach(int i; arr)
        writefln("%d", i);
}


Thanks,

Matheus.



February 09, 2012
On 02/09/2012 11:03 AM, H. S. Teoh wrote:
> On Thu, Feb 09, 2012 at 10:30:22AM -0800, Ali Çehreli wrote:
> [...]
>> But if you don't actually want to modify the data, you can merely
>> access the elements in-place by std.range.chain:
>>
>> import std.stdio;
>> import std.range;
>>
>> void main()
>> {
>>      int[] arr = [0,1,2,3,4,5,6,7,8,9];
>>      immutable position = arr.length / 2;
>>      immutable newValue = 42;
>>
>>      auto r = chain(arr[0 .. position], [ newValue ], arr[position +
>> 1 .. $]);
>>      writeln(r);
>> }
>>
>> 'r' above is a lazy range that just provides access to the three
>> ranges given to it. 'arr' does not change in any way.
> [...]
>
> Wow! This is really cool. So you *can* have O(1) insertions in the
> middle of an array after all. :)
>
> Of course, you probably want to flatten it once in a while to keep
> random access cost from skyrocketing.

O(1) would be violated only if there are too many actual ranges.

> (I'm assuming delegates or
> something equivalent are involved in generating the lazy range?)

Simpler than that. :) The trick is that chain() returns a range object that operates lazily. I have used chain() as an example for finite RandomAccessRange types (I used the name 'Together' instead of Chain). Search for "Finite RandomAccessRange" here:

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

And yes, I note there that the implementation is not O(1). Also look under the title "Laziness" in that chapter.

Ali

February 09, 2012
On 02/09/2012 08:20 PM, MattCodr wrote:
> On Thursday, 9 February 2012 at 18:30:22 UTC, Ali Çehreli wrote:
>> On 02/09/2012 03:47 AM, MattCodr wrote:
>>> I have a doubt about the best way to insert and move (not replace) some
>>> data on an array.
>>>
>>> For example,
>>>
>>> In some cases if I want to do action above, I do a loop moving the data
>>> until the point that I want and finally I insert the new data there.
>>>
>>>
>>> In D I did this:
>>>
>>> begin code
>>> .
>>> .
>>> .
>>> int[] arr = [0,1,2,3,4,5,6,7,8,9];
>>>
>>> arr.insertInPlace(position, newValue);
>>> arr.popBack();
>>> .
>>> .
>>> .
>>> end code
>>>
>>>
>>> After the insertInPlace my array changed it's length to 11, so I use
>>> arr.popBack(); to keep the array length = 10;
>>>
>>> The code above is working well, I just want know if is there a better
>>> way?
>>>
>>> Thanks,
>>>
>>> Matheus.
>>
>> Most straightforward that I know of is the following:
>>
>> arr = arr[0 .. position] ~ [ newValue ] ~ arr[position + 1 .. $];
>>
>> But if you don't actually want to modify the data, you can merely
>> access the elements in-place by std.range.chain:
>>
>> import std.stdio;
>> import std.range;
>>
>> void main()
>> {
>> int[] arr = [0,1,2,3,4,5,6,7,8,9];
>> immutable position = arr.length / 2;
>> immutable newValue = 42;
>>
>> auto r = chain(arr[0 .. position], [ newValue ], arr[position + 1 .. $]);
>> writeln(r);
>> }
>>
>> 'r' above is a lazy range that just provides access to the three
>> ranges given to it. 'arr' does not change in any way.
>>
>> Ali
>
> Hi Ali,
>
> You gave me a tip with this "chain" feature.
>
> I changed a few lines of your code, and it worked as I wanted:
>
>
> import std.stdio;
> import std.range;
> import std.array;
>
> void main()
> {
> int[] arr = [0,1,2,3,4,5,6,7,8,9];
> immutable position = arr.length / 2;
> immutable newValue = 42;
>
> auto r = chain(arr[0 .. position], [ newValue ], arr[position .. $-1]);
> arr = array(r);
>
> foreach(int i; arr)
> writefln("%d", i);
> }
>
>
> Thanks,
>
> Matheus.
>

Note that this code does the same, but is more efficient if you don't actually need the array:


import std.stdio;
import std.range;
import std.array;

void main()
{
    int[] arr = [0,1,2,3,4,5,6,7,8,9];
    immutable position = arr.length / 2;
    immutable newValue = 42;

    auto r = chain(arr[0 .. position], [ newValue ], arr[position .. $-1]);

    foreach(i; r)
        writefln("%d", i);
}




February 09, 2012
On Thursday, 9 February 2012 at 19:49:43 UTC, Timon Gehr wrote:
> Note that this code does the same, but is more efficient if you don't actually need the array:

Yes I know, In fact I need re-think the way I code with this new features of D, like ranges for example.

Thanks,

Matheus.
February 10, 2012
Am 09.02.2012, 22:03 Uhr, schrieb MattCodr <matheus_nab@hotmail.com>:

> On Thursday, 9 February 2012 at 19:49:43 UTC, Timon Gehr wrote:
>> Note that this code does the same, but is more efficient if you don't actually need the array:
>
> Yes I know, In fact I need re-think the way I code with this new features of D, like ranges for example.
>
> Thanks,
>
> Matheus.

I know that feeling. I had no exposure to functional programming and options like chain never come to my head. Although "map" is a concept that I made friends with early.
« First   ‹ Prev
1 2