How to shift data in array?

Question

 ///Example
 some_array[0]:=0;
 some_array[1]:=1;
 some_array[2]:=2;
 some_array[3]:=3;
 some_array[4]:=4;

And now I need to shift values in array like this (by one cell up)

 some_array[0]:=1;
 some_array[1]:=2;
 some_array[2]:=3;
 some_array[3]:=4;
 some_array[4]:=0;

Is there any build in procedure or I have to do this manually by copying to some temporary array?

Answer 1

This array rotation function is fast if your not too worried about transient memory overhead.

Just change the array type to anything of your choice.

Positive values of x rotate right, negative rotate left.

function RotateArray(list:Tintarray; x:integer):Tintarray;
var n:integer;
begin
  n:=length(list);
  x:=x mod n;
  if (n<2) or (x=0) then
    result:=Copy(list)
  else
  if x>0 then
    result:=Copy(list,n-x,x) + Copy(list,0,n-x)
  else
    result:=Copy(list,-x,n-x) + Copy(list,0,-x)
end;

Answer 2

Stumbling across this one while facing a similar issue.

I have not implemented it yet, but have thought about this different approach: KEEP the array as it is, but make a new procedure to read values where you change the "zero" position.

Example:

read_array(index: integer; shift: integer)..

So if your original array is read with this function, using shift "1" it would read "1,2,3,4,0" (obviously looping). It would require you to keep track of a few things, but would not require modifying anything. So performance should be greater for very large arrays.

Similar would work for other types as well.

EDIT: an example function with free start index and variable step size plus sample size is here:

function get_shifted_array(inArray: TStringList; startindex,
  lineCount: integer;
  stepsize: integer): TStringList;

var
   i : integer;           // temp counter
   nextindex : integer;   // calculate where to get next value from...
   arraypos  : integer;   // position in inarray to take
   temp      : tstringlist;


        // function to mimic excel Remainder( A,B) function
        // in this   remainder(-2,10) = 8
        //
           function modPositive( dividend, divisor: integer): integer;
           var
              temp : integer;

            begin

               if dividend < 0 then
                   begin
                       temp := abs(dividend) mod divisor;   // 1 mod 10 =9    for -1
                                                            // 122 mod 10 = 2  for -122
                       result :=  (divisor - temp);
                   end
               else
                  result := dividend mod divisor;
            end;


begin

   nextindex := startindex;             // where in input array to get info from
   temp := tstringlist.create;          // output placeholder

   for i := 1 to lineCount do
      begin

          // convert to actual index inside loop
          arraypos := modPositive(nextindex, inarray.count);     // handle it like Excel: remainder(-1,10) = 9

          // if mod is zero, we get array.count back. Need zero index then.
          if arraypos = inArray.Count then arraypos := 0;        // for negative loops.

          // get the value at array position
          temp.Add( 'IDX=' + inttostr(arraypos) + ' V=' +   inarray[  arraypos ] );

          // where to go next
          // should we loop ?
          if ((nextindex+ stepsize +1)> inArray.Count ) then
                 begin
                     nextindex :=  (nextindex + stepsize ) mod inArray.Count;
                 end
          else
              nextindex := nextindex + stepsize;
      end;

   result := temp;

end;

Thereby:

get_shifted_array(
    inputarray, 
    -1,    // shiftindex
    length(inputarray), 
   1 )  // stepsize

would return the array shifted backwards one place.

All without any modification to array.

Answer 3

There is no such procedure in the RTL.

A generic procedure (as proposed by @DavidHeffernan) might look something like this:

Type
  TMyArray = record
    class procedure RotateLeft<T>(var a: TArray<T>); static;
  end;

class procedure TMyArray.RotateLeft<T>(var a: TArray<T>);
var
  tmp : T;
  i : Integer;
begin
  if Length(a) > 1 then begin
    tmp := a[0];
    for i := 1 to High(a) do
      a[i-1] := a[i];
    a[High(a)] := tmp;
  end;
end;

var
  a: TArray<Integer>;
  i:Integer;    
begin
  SetLength(a,5);
  for i := 0 to High(a) do a[i] := i;
  TMyArray.RotateLeft<Integer>(a);
  for i := 0 to High(a) do WriteLn(a[i]);

  ReadLn;
end.

---

A low level routine using Move() could be used if performance is critical:

class procedure TMyArray.RotateLeft<T>(var a: TArray<T>);
var
  tmp : T;
begin
  if Length(a) > 1 then begin
    Move(a[0],tmp,SizeOf(T));          // Temporary store the first element
    Move(a[1],a[0],High(a)*SizeOf(T));
    Move(tmp,a[High(a)],SizeOf(T));    // Put first element last
    // Clear tmp to avoid ref count drop when tmp goes out of scope
    FillChar(tmp,SizeOf(T),#0);
  end;
end;

Note the FillChar() call to clear the temporary variable at the end. If T is a managed type, it would otherwise drop the reference count of the last array element when going out of scope.

Answer 4

There is no built in function for this. You will need to write your own. It might look like this:

procedure ShiftArrayLeft(var arr: array of Integer);
var
  i: Integer;      
  tmp: Integer;
begin
  if Length(arr) < 2 then
    exit;

  tmp := arr[0];
  for i := 0 to high(arr) - 1 do
    arr[i] := arr[i + 1];
  arr[high(arr)] := tmp;
end;

Note that there is no need to copy to a temporary array. You only need to make a temporary copy of one element.

If your arrays are huge then the copying overhead could be significant. In which case you would be better off using a circular array. With a circular array you remember the index of the first element. Then the shift operation is just a simple increment or decrement operation on that index, modulo the length of the array.

If you use a modern Delphi then this could readily be converted to a generic method. And I think it should be easy enough for you to write the shift in the opposite direction.