arraysalgorithmdelphidelphi-xe7
How to align 2 arrays without temporary arrays?
I have 2 arrays that I need to align lines. I prepare the 'control' array which has the info on how to align arrays and then I do it, with help of temp arrays.
See in picture the arrays and result as aligned arrays:
Here is the code that I use, as 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;
As I use the same or similar code for a lot of arrays, I'm trying to refactor and simplify it with AlignArrays function:
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;
Question: Can this be better refactored and is it possible to work on the arrays without temp arrays?
EDIT:
From comments and answers it seems I waste too much time preparing MCVE, I should better explain the problem I have. But, from an CleoR's answer I got an idea to align arrays by starting in he last line and aligning to the top. Adn it seems to work, and here is why: Because control array has instructions on how to align lines, I know exactly what the size of arrays is. And since aligning means 'stretchin' array/inserting new blank lines where needed, if I start from the bottom up, I don't need to insert anything, only move the lines that need to be moved.
Simple and it works - without temp arrays:
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;
Solution
UPDATE: Changed the solution to pseudocode.
You don't need a temp array, you can do it in place.
Lets assume the left and right arrays have enough space and they are the same size.
For each array you'll need to keep track of the last element in the array. Lets call this the dataPointer. Reverse loop over the arrays with a counter called endPointer.
- At each step in the loop check if array[dataPointer] == endPointer + minElement for both arrays.
- If true, array[endPointer] = endPointer + minElement and decrement the dataPointer.
- If false, array[endPointer] = skip_value.
Do this until endPointer goes past the beginning of the array.
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
In case you want to try the algorithm out for yourself, heres a link to the repo. https://github.com/cleor41/StackOverflow_AlignArrays.
I don't know an ounce of Delphi but I tried to write it in Delphi so maybe you can understand it better. I also don't understand the need to have the control array.
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;