arrays - 如何在没有临时数组的情况下对齐 2 个数组？

Question

我有 2 个数组需要对齐线条。我准备了“控制”数组，其中包含有关如何对齐数组的信息，然后我在临时数组的帮助下执行此操作。

在图片中查看数组和对齐数组的结果:

这是我作为 MCVE 使用的代码:

    unit Unit1;

    interface

    uses
      Winapi.Windows, Winapi.Messages, System.SysUtils, System.Variants, System.Classes, Vcl.Graphics,
      Vcl.Controls, Vcl.Forms, Vcl.Dialogs, Vcl.StdCtrls,
      System.Math,
      System.Generics.Defaults,
      System.Generics.Collections;

    type
      TForm1 = class(TForm)
        Button1: TButton;
        Button2: TButton;
        procedure Button1Click(Sender: TObject);
        procedure Button2Click(Sender: TObject);
      private
        { Private declarations }
      public
        { Public declarations }
      end;

      TSide = (sLeft, sRight, sBoth);

      TData = record
        DataID: integer;
        DataName: string;
        BlankLine: boolean;
      end;

      TCtrlData = record
        Side: TSide;
        Idx_l: integer;
        Idx_r: integer;
      end;

    var
      Form1: TForm1;
      aLeft, aRight, aLeft_tmp, aRight_tmp: TArray<TData>; // main and temp arrays
      aCtrl: TArray<TCtrlData>; // control array with instructions o nhow to align lines

    implementation

    {$R *.dfm}

    procedure PrepareData;
    begin
      // prepare data
      SetLength(aLeft, 4);
      aLeft[0].DataID := 1; aLeft[0].DataName := 'One';
      aLeft[1].DataID := 2; aLeft[1].DataName := 'Three';
      aLeft[2].DataID := 3; aLeft[2].DataName := 'Six';
      aLeft[3].DataID := 4; aLeft[3].DataName := 'Eight';
      SetLength(aRight, 6);
      aRight[0].DataID := 1; aRight[0].DataName := 'One';
      aRight[1].DataID := 2; aRight[1].DataName := 'Two';
      aRight[2].DataID := 3; aRight[2].DataName := 'Four';
      aRight[3].DataID := 4; aRight[3].DataName := 'Five';
      aRight[4].DataID := 5; aRight[4].DataName := 'Seven';
      aRight[5].DataID := 6; aRight[5].DataName := 'Eight';

      // do the magic - prepare control array
      SetLength(aCtrl, 8);
      aCtrl[0].Side := sBoth; aCtrl[0].Idx_L := 0; aCtrl[0].Idx_R := 0;
      aCtrl[1].Side := sRight; aCtrl[1].Idx_R := 1;
      aCtrl[2].Side := sLeft; aCtrl[2].Idx_L := 1;
      aCtrl[3].Side := sRight; aCtrl[3].Idx_R := 2;
      aCtrl[4].Side := sRight; aCtrl[4].Idx_R := 3;
      aCtrl[5].Side := sLeft; aCtrl[5].Idx_L := 2;
      aCtrl[6].Side := sRight; aCtrl[6].Idx_R := 4;
      aCtrl[7].Side := sBoth; aCtrl[7].Idx_L := 3; aCtrl[7].Idx_R := 5;
    end;

    procedure TForm1.Button1Click(Sender: TObject);
    var
      i, vIndex: integer;
    begin
      PrepareData;


      { prepare arrays based on Control array
      Loop through Control array and fill temp arrays from Left or Right arrays }
      SetLength(aLeft_tmp, 0);
      SetLength(aRight_tmp, 0);
      SetLength(aLeft_tmp, Length(aCtrl));
      SetLength(aRight_tmp, Length(aCtrl));
      vIndex := 0;
      for i := 0 to High(aCtrl) do
      begin
        if aCtrl[i].Side = sBoth then // Data from Both
        begin
          aLeft_tmp[vIndex] := aLeft[aCtrl[i].Idx_L];
          aRight_tmp[vIndex] := aRight[aCtrl[i].Idx_R];
          Inc(vIndex);
        end;
        if aCtrl[i].Side = sLeft then // Data from Left side
        begin
          aLeft_tmp[vIndex] := aLeft[aCtrl[i].Idx_L];
          aRight_tmp[vIndex].BlankLine := true;
          Inc(vIndex);
        end;
        if aCtrl[i].Side = sRight then // Data from Right side
        begin
          aRight_tmp[vIndex] := aRight[aCtrl[i].Idx_R];
          aLeft_tmp[vIndex].BlankLine := true;
          Inc(vIndex);
        end;
      end;

      // Assign aligned data to main arrays
      aLeft := aLeft_tmp;
      aRight := aRight_tmp;
    end;

因为我对很多数组使用相同或相似的代码，所以我尝试使用 AlignArrays 函数重构和简化它:

    procedure AlignArrays(vCtrl: TArray<TCtrlData>; var vLeft, vRight: TArray<TData>);
    var
      i, vIndex: integer;
      vLeft_tmp, vRight_tmp: TArray<TData>;
    begin
      SetLength(vLeft_tmp, Length(vCtrl));
      SetLength(vRight_tmp, Length(vCtrl));
      vIndex := 0;

     { prepare arrays based on Control array
      Loop through Control array and fill temp arrays from Left or Right arrays }
      for i := 0 to High(vCtrl) do
      begin
        if vCtrl[i].Side = sBoth then // Data from Both
        begin
          vLeft_tmp[vIndex] := vLeft[vCtrl[i].Idx_L];
          vRight_tmp[vIndex] := vRight[vCtrl[i].Idx_R];
          Inc(vIndex);
        end;
        if vCtrl[i].Side = sLeft then // Data from Left side
        begin
          vLeft_tmp[vIndex] := vLeft[vCtrl[i].Idx_L];
          vRight_tmp[vIndex].BlankLine := true;
          Inc(vIndex);
        end;
        if vCtrl[i].Side = sRight then // Data from Right side
        begin
          vRight_tmp[vIndex] := vRight[vCtrl[i].Idx_R];
          vLeft_tmp[vIndex].BlankLine := true;
          Inc(vIndex);
        end;
      end;

      vLeft := vLeft_tmp;
      vRight := vRight_tmp;
    end;

    procedure TForm1.Button2Click(Sender: TObject);
    var
      i, vIndex: integer;
    begin
      PrepareData;

      AlignArrays(aCtrl, aLeft, aRight);

    end;

问题:是否可以更好地重构，是否可以在没有临时数组的情况下处理数组？

编辑:

从评论和回答来看，我似乎在准备 MCVE 上浪费了太多时间，我应该更好地解释我遇到的问题。但是，从 CleoR 的回答中，我想到了通过从最后一行开始并对齐到顶部来对齐数组的想法。它似乎有效，原因如下:因为控件数组有关于如何对齐行的说明，所以我确切地知道数组的大小是多少。由于对齐意味着“拉伸(stretch)”数组/在需要的地方插入新的空行，如果我从下往上开始，我不需要插入任何东西，只移动需要移动的行。

简单且有效 - 无需临时数组:

procedure AlignArraysBackwards(vCtrl: TArray<TCtrlData>; var vLeft, vRight: TArray<TData>);
var
  i: integer;
  vBlankRecord:TData;
begin

  // set blank record to blank out the moved line
  vBlankRecord.DataID:=0;
  vBlankRecord.DataName:='';
  vBlankRecord.BlankLine:=True;

  // set lenght for arrays
  SetLength(vLeft, Length(vCtrl));
  SetLength(vRight, Length(vCtrl));

  // align - starting from the bottom up
  for i := High(vCtrl) downto 0 do
  begin
    if vCtrl[i].Side = sBoth then // Data from Both
    begin
      // move Left line
      vLeft[i] := vLeft[vCtrl[i].Idx_L];
      // blank out the line we just moved
      if vCtrl[i].Idx_L<>i then vLeft[vCtrl[i].Idx_L]:=vBlankRecord;
      // move Rigth line
      vRight[i] := vRight[vCtrl[i].Idx_R];
      // blank out the line we copied from
      if vCtrl[i].Idx_R<>i then vRight[vCtrl[i].Idx_R]:=vBlankRecord;
    end;
    if vCtrl[i].Side = sLeft then // Data from Left side
    begin
      // move Left line
      vLeft[i] := vLeft[vCtrl[i].Idx_L];
      // blank out the line we just moved
      if vCtrl[i].Idx_L<>i then  vLeft[vCtrl[i].Idx_L]:=vBlankRecord;
      // blank Right line
      vRight[i].BlankLine := true;
    end;
    if vCtrl[i].Side = sRight then // Data from Right side
    begin
      // move Left line
      vRight[i] := vRight[vCtrl[i].Idx_R];
      // blank out the line we just moved
      if vCtrl[i].Idx_R<>i then  vRight[vCtrl[i].Idx_R]:=vBlankRecord;
      // blank Left line
      vLeft[i].BlankLine := true;
    end;
  end;
end;

Answer 1

更新:将解决方案更改为伪代码。

您不需要临时数组，您可以就地完成。

假设左右数组有足够的空间并且它们的大小相同。

对于每个数组，您需要跟踪数组中的最后一个元素。让我们称之为数据指针。使用名为 endPointer 的计数器对数组进行反向循环。

1. 在循环的每一步检查两个数组的 array[dataPointer] == endPointer + minElement。
2. 如果为真，array[endPointer] = endPointer + minElement 并递减 dataPointer。
3. 如果为假，array[endPointer] = skip_value。

4. 这样做直到 endPointer 越过数组的开头。

   skip_value = 0
   
   //Handles our assumptions.
   function setup(left,right)
       left.sort()
       right.sort()
       ldPointer = len(left)-1
       rdPointer = len(right)-1
       maxElement = max(left[ldPointer],right[rdPointer])
       //This is 1 in your examples. You can hard code this number.
       minElement = min(left[0],right[0])
       padLength = maxElement - minElement + 1
       pad(left,padLength)
       pad(right,padLength)
       return ldPointer,rdPointer,minElement
   
   //Aligns the arrays.
   function align(left,right)
       ldPointer,rdPointer,minElement = setup(left,right)
       for endPointer = len(left)-1; endPointer >= 0; i--
           //Look at the left element.
           if left[ldPointer] == endPointer+minElement
               left[endPointer] = endPointer+minElement
               ldPointer = ldPointer - 1
           else
               left[endPointer] = skip_value
           //Look at the right element.
           if right[rdPointer] == endPointer+minElement
               right[endPointer] = endPointer+minElement
               rdPointer = rdPointer - 1
           else
               right[endPointer] = skip_value
   

如果您想自己尝试该算法，请点击这里的 repo 链接。 https://github.com/cleor41/StackOverflow_AlignArrays .

我对 Delphi 一点也不了解，但我尝试用 Delphi 编写它，因此也许您可以更好地理解它。我也不明白需要控制数组。

procedure AlignArraysBackwards(var vLeft, vRight: TArray<TData>);
var
  endPointer: Integer;
  vBlankRecord: TData;
  // Assumes the arrays have at least 1 element
  ldPointer: Length(vLeft)-1;
  rdPointer: Length(vRight)-1;
  maxElement: Max(vLeft[ldPointer].DataID,vRight[rdPointer].DataID);
  // Set this to 1 if arrays should always be 1 alligned
  // Else it aligns arrays starting from the array with the smallest value.
  minElement: Min(vLeft[0].DataID,vRight[0].DataID);
  padLength: maxElement - minElement + 1;
begin

  // set blank record to blank out the moved line
  vBlankRecord.DataID:=0;
  vBlankRecord.DataName:='';
  vBlankRecord.BlankLine:=True;

  // set length for arrays
  SetLength(vLeft, padLength);
  SetLength(vRight, padLength);

  // align - starting from the bottom up
  for endPointer := High(vLeft) downto 0 do
  begin
    // Start Left array
    if vLeft[ldPointer].DataID = endPointer + minElement
    then
      begin
        vLeft[endPointer] := vLeft[ldPointer];
        ldPointer := ldPointer - 1;
      end
    else
      begin
        vLeft[endPointer] := vBlankRecord;
      end;
    // End Left Array
    // Start Right array
    if vRight[rdPointer].DataID = endPointer + minElement
    then
      begin
        vRight[endPointer] := vRight[rdPointer];
        rdPointer := rdPointer - 1;
      end
    else
      begin
        vRight[endPointer] := vBlankRecord;
      end;
    // End Right Array
  end;
end;