Relocating arrays using System.arraycopy

Thread view:

- - 01 Jun 2005 02:33 GMT

I have an array, eg. int[] x = {1, 2, 3, 4};

I want to relocate the index such that relocate(fromIndex, toIndex)
using values relocate(3, 1) will change the array to {1, 4, 2, 3}.

The following is a working code:

int movedX = x[fromIndex];
System.arraycopy(x, 0, x, 0, fromIndex);
int index = fromIndex + 1;
System.arraycopy(x, index, x, fromIndex, x.length - index);
System.arraycopy(x, 0, x, 0, toIndex);
System.arraycopy(x, toIndex, x, toIndex + 1, x.length - toIndex - 1);
x[toIndex] = movedX;

Is there a shorter way to do it?
(Using the classes in the java.util.* package is not an option.)

Reply to this Message

Skip - 01 Jun 2005 08:22 GMT

> I have an array, eg. int[] x = {1, 2, 3, 4};
>
[quoted text clipped - 10 lines]
> System.arraycopy(x, toIndex, x, toIndex + 1, x.length - toIndex - 1);
> x[toIndex] = movedX;

Just look at your problem very good. You only want to move the range between
"to" and "from" 1 position, either to the left or the right. So you need
only 1 call to System.arraycopy(..) for each case:

public static final void relocate(int[] a, int from, int to)
{
int move = a[from];

if (from < to)
System.arraycopy(a, from + 1, a, from, to - from);
else
System.arraycopy(a, to, a, to + 1, from - to);

a[to] = move;
}

Reply to this Message

Wibble - 01 Jun 2005 11:40 GMT

>>I have an array, eg. int[] x = {1, 2, 3, 4};
>>
[quoted text clipped - 26 lines]
> a[to] = move;
> }

Dont shift around the array. Keep an additional offset and use a getter
to access an element.

int getNthFromOffset(int n) { return(a[(n+offset)%a.length]); }

If the array is large, shifting becomes a mess.

Reply to this Message

Wibble - 01 Jun 2005 12:20 GMT

>>> I have an array, eg. int[] x = {1, 2, 3, 4};
>>>
[quoted text clipped - 34 lines]
>
> If the array is large, shifting becomes a mess.

Oh, ignore that... your not rotating. This can't be part of an
efficient algorithm though, can it?

Reply to this Message

Skip - 02 Jun 2005 11:11 GMT

[snip]

> > Dont shift around the array. Keep an additional offset and use a getter
> > to access an element.
> >
> > int getNthFromOffset(int n) { return(a[(n+offset)%a.length]); }
> >
> > If the array is large, shifting becomes a mess.

> Oh, ignore that... your not rotating. This can't be part of an
> efficient algorithm though, can it?

The 'algorithm' is crap, really, but the fastest possible. It's just a
problem that can't be solved efficiently.

Reply to this Message

googmeister@gmail.com - 02 Jun 2005 15:15 GMT

> The 'algorithm' is crap, really, but the fastest possible.
> It's just a problem that can't be solved efficiently.

In what sense do you claim this the fastest possible?

Using a (balanced) BST, it's possible to support
relocate() in logarithmic time per op, using total
space proportional to the number of elements.

Unfortunately this algorithm is not shorter, which
was the original poster's goal. It is, however, much
more efficient if the number of elements is
sufficiently large.

Reply to this Message

P.Hill - 01 Jun 2005 17:18 GMT

> I have an array, eg. int[] x = {1, 2, 3, 4};
>
[quoted text clipped - 12 lines]
>
> Is there a shorter way to do it?

So why aren't you just manipluting.
movedX, x[fromIndex] and x[toIndex]?

Maybe I don't understand the intended result.
Is it two objects move and the rest stay in place,
but then I'd call that swap( index1, index2 )

> System.arraycopy(x, 0, x, 0, fromIndex);

arrayCopy to itself with no movement; what are you trying to
accomplish with that?

Someone is missing something, but it might be me.

-Paul

Reply to this Message

Relocating arrays using System.arraycopy

Free Magazines