Dynamic arrays concatenation, insertion and deletion of elements

[lainz]

1) What would be an %u201Cideal%u201D, but real life example of using these dynamic arrays features?

For example, when writing a game you use TInventory to store player's items.

Code: Pascal  [Select][+][-]

1. const
2.   MaxItemID = 7;
3.   HPBig     = 1; // big healing potion
4.   HPSmall   = 2; // small healing potion
5.   MPBig     = 3; // big mana potion
6.   MPSmall   = 4; // small mana potion
7.   Sw        = 5; // common sword
8.   SwSmall   = 6; // small sword
9.   SwLong    = 7; // long sword
10.  
11. type
12.   TInventory = array of Byte;
13.  
14. var
15.   Inventory = TInventory;
16.    
17. // Give some bonus items if player finish a quest
18. procedure BonusItems;
19. begin
20.   Inventory := Inventory + [HPSmall, MPSmall] + [Random(MaxItemID)+1];
21. end;

It just quickly written example. For better coding I probably will use enum type for the items' IDs.

I think it depends on the size of the game inventory.
There are games with thousands of items.

I think arrays are useful when doing intensive computing that needs to run fast. For anything else there are lists that are easier to use (using arrays or not internally).

[Handoko]

Yes, you're right. For most cases we should use list but for beginners who just start to learn building games, array is good enough for simple games like Pacman. That will make them better understand how data being stored and manipulated in memory. Lists are more practical and easier but they miss the chance of learning the low-level process.

[Kwadrum]

Hi, it's been a while, but I am back with more questions :-)
I have finally found some use for the this type of operations, but as usual, some things do not work as I expected and I am not able to figure out where the error is.
So, if I use deletions of the elements of the array in the main program like this, everything works as expected:

Code: Pascal  [Select][+][-]

1. program dyn_array_records_filtering;
2.      
3. {$mode objfpc} {$H+} {$modeSwitch arrayOperators+}
4.      
5.     uses
6.     SysUtils;
7.      
8.     type
9.       DataRec=
10.         record
11.         level : byte;
12.         dwell : double;
13.         end;
14.    
15.     var
16.     AR : array of DataRec;
17.     i : byte;
18.      
19.     BEGIN
20.        
21.         SetLength(AR,11);
22.        // filling the array manually for testing
23.        // then printing the array values  
24.        
25.          for i := 1 to (High(AR)-1) do
26.                begin   
27.                  if AR[i].level = 0 then
28.                     begin
29.                       AR[i-1].dwell := AR[i-1].dwell + AR[i].dwell/2;
30.                       AR[i+1].dwell := AR[i+1].dwell + AR[i].dwell/2;
31.                       Delete(AR,i,1);
32.                     end;
33.                end;    
34.          
35.         for i := 1 to (High(AR)-1) do  
36.                begin                                                                                           
37.                  if AR[i].level = AR[i-1].level then
38.                     begin        
39.                       AR[i-1].dwell := AR[i-1].dwell + AR[i].dwell;
40.                       Delete(AR,i,1);
41.                     end;
42.                end;
43.  
44.       // printing the array values here
45.  
46.    END.
47.  

However, if I try to put this chunk of code into a separate procedure, like this:

Code: Pascal  [Select][+][-]

1. program dyn_array_records_filtering_procedure;
2.      
3. {$mode objfpc} {$H+} {$modeSwitch arrayOperators+}
4.      
5.     uses
6.     SysUtils;
7.      
8.     type
9.       DataRec=
10.         record
11.         level : byte;
12.         dwell : double;
13.         end;
14.    
15.     var
16.     AR : array of DataRec;
17.     i : byte;
18.    
19.     procedure Array_filter(var A: array of DataRec);
20.                
21.     var
22.     k : byte;
23.                
24.     begin
25.                          
26.         for k := 1 to (High(A)-1) do   
27.              begin                                                                                                     
28.                  if A[k].level = 0 then
29.                     begin
30.                         A[k-1].dwell := A[k-1].dwell + A[k].dwell/2;
31.                         A[k+1].dwell := A[k+1].dwell + A[k].dwell/2;
32.                         Delete(A,k,1);                                              //first error shows up here
33.                     end;
34.              end;    
35.          
36.         for k := 1 to (High(A)-1) do   
37.              begin                                                                                             
38.                 if A[k].level = A[k-1].level then
39.                    begin        
40.                        A[k-1].dwell := A[k-1].dwell + A[k].dwell;
41.                        Delete(A,k,1);                                               //first error shows up here
42.                    end;
43.              end;
44.                
45.     end;
46.          
47.     BEGIN
48.        
49.         SetLength(AR,11);
50.         // filling the array manually for testing
51.        // then printing the array values
52.        
53.        Array_filter(AR);
54.        // printing the array values here
55.  
56.    END.
57.  

I get a bunch of compiler's errors, starting with:

Code: Pascal  [Select][+][-]

1. Dyn_array_records_filtering_procedure.pas(33,23) Error: Wrong number of parameters specified for call to "Delete"

at the lines where I trim the array: Delete(A,k,1);

I realize I do not understand something, so may I ask someone to help me with this?

Thank you.

[howardpc]

Slightly adapted:

Code: Pascal  [Select][+][-]

1. program dyn_array_records_filtering_procedure;
2.  
3. {$mode objfpc} {$H+} {$modeSwitch arrayOperators+}
4. {$ModeSwitch advancedrecords}
5.  
6. uses
7.   SysUtils;
8.  
9. type
10.   TDataRec = record
11.     level: Byte;
12.     dwell: Double;
13.     procedure WriteValues;
14.   end;
15.  
16.   TDataRecArray = array of TDataRec;
17.  
18. var
19.   AR: TDataRecArray;
20.   dr: TDataRec;
21.  
22.   procedure Array_filter(var A: TDataRecArray);
23.   var
24.     k: Byte;
25.   begin
26.     for k := Pred(High(A)) downto 1 do
27.       if A[k].level = 0 then
28.         begin
29.           A[k-1].dwell := A[k-1].dwell + A[k].dwell/2;
30.           A[k+1].dwell := A[k+1].dwell + A[k].dwell/2;
31.           Delete(A,k,1);
32.         end;
33.  
34.     for k := Pred(High(A)) downto 1 do
35.       if A[k].level = A[k-1].level then
36.         begin
37.           A[k-1].dwell := A[k-1].dwell + A[k].dwell;
38.           Delete(A,k,1);
39.         end;
40.     end;
41.  
42. procedure TDataRec.WriteValues;
43. begin
44.   WriteLn('level: ',level,' dwell: ',dwell:2:2);
45. end;
46.  
47. begin
48.   SetLength(AR, 11); // filling the array manually for testing
49.   Array_filter(AR);
50.  
51.   for dr in AR do
52.     dr.WriteValues; // printing the array values here
53.   ReadLn;
54. end.

Two points -
When deleting array items, loop from High() using downto, otherwise you end up trying to delete a non-existent item index.

"array of xxx" as a parameter type has a different meaning from "array of xxx" in a type declaration. The former is an "open array", not (as you might think) a dynamic array.

So declare the dynamic array as  named type so you can avoid "array of" in the parameter type declaration since in this case it is not what you want.

[Kwadrum]

howardpc

Thank you very much!
I understand the point about the type mismatch (open vs dynamic arrays), and special thanks for the hint on the $ModeSwitch advancedrecords!

However I did not get the reason for using downto instead of to. As far as I can see, High(A) always returns the actual index of the top element of the array, i.e. if (pseudocode):
High(A) = 10;
Delete(A,2,1); // deletes the element with a shift
High(A) = 9;

UPD. Sorry, I think I got it finally - reading forward may result in leaping over a newly shifted element... is that what you meant?

[howardpc]

Yes, this example illustrates the point that setting a fixed upper limit to a for loop and then deleting items within the loop heads for disaster unless you design the loop intelligently.
You can easily cut off the branch you are sitting on.

Code: Pascal  [Select][+][-]

1. program DeleteExample;
2.  
3. {$mode objfpc}{$H+}
4. {$ModeSwitch advancedrecords}
5. {$RangeChecks On}
6.  
7. type
8.  
9.   TNameRec = record
10.     name: String;
11.     id: Integer;
12.     procedure Init(aID: Integer);
13.     procedure WriteValue;
14.   end;
15.  
16.   TNameRecArray = array of TNameRec;
17.  
18.   procedure ListValues(const aArr: TNameRecArray);
19.   var
20.     nr: TNameRec;
21.   begin
22.     for nr in aArr do
23.       nr.WriteValue;
24.     WriteLn;
25.   end;
26.  
27.   procedure DeleteOdds(var aArr: TNameRecArray);
28.   var
29.     i: Integer;
30.   begin
31.     for i := 0 to High(aArr)-1 do // the value of High(aArr) decreases as the loop deletes items
32.                                   // so you soon reach a value of i that is higher than the new
33.                                   // High() value. But the for loop continues to increase i to
34.                                   // the original value you specified
35.       if Odd(aArr[i].id) then
36.         Delete(aArr, i, 1);
37.   end;
38.  
39.   procedure DeleteOddsDownto(var aArr: TNameRecArray);
40.   var
41.     i: Integer;
42.   begin
43.     for i := High(aArr) downto 0 do
44.       if Odd(aArr[i].id) then
45.         Delete(aArr, i, 1);
46.   end;
47.  
48. { TNameRec }
49.  
50. procedure TNameRec.Init(aID: Integer);
51. begin
52.   id := aID;
53.   WriteStr(name, aID);
54. end;
55.  
56. procedure TNameRec.WriteValue;
57. begin
58.   WriteLn(name);
59. end;
60.  
61. var
62.   arr: TNameRecArray = Nil;
63.   i: Integer;
64.  
65. begin
66.   SetLength(arr, 10);
67.   for i := 0 to High(arr) do
68.     arr[i].Init(i);
69.   WriteLn('Initial values:');
70.   ListValues(arr);
71.  
72.   WriteLn('DeleteOdds:');
73.   DeleteOddsDownto(arr);  //DeleteOdds(arr); if you enable this you will raise an exception
74.   ListValues(arr);
75.  
76.   WriteLn('Press Enter to finish');
77.   ReadLn;
78. end.

[Kwadrum]

I see what the problem is, thanks to you :-). I did not realize that High(A) is set once before the loop begins and it doesn't change till the end... So in my particular case the program returns a correct result due to the structure of my data and those specific operations I was using, it just makes some extra unnecessary work dealing with the "data" outside the valid array range, right? I'm asking not in order to justify the mistakes I've done, I'm curious why the output is still correct :-).
On the other hand, there is probably one even more obvious error with my code - I indeed could have leaped over a newly shifted array value, and again, due to the specific structure of my data the output was still correct :-).
Anyway, I understood the error, thank you very much!

[BobDog]

Freepascal has it's own insert / delete, which I have just tested here.
Also generic templating which I also test here.

Code: Pascal  [Select][+][-]

1.  
2. {$mode delphi}
3. {$rangeChecks on}
4.  
5.  
6. type TDataRec = record
7.    level: Byte;
8.    dwell: Double;
9.    function Init:TDataRec;
10.    procedure WriteValues;
11.  end;
12.  
13.  
14.  function TDataRec.Init;
15. begin
16. level:=random(255);
17. dwell:=level*10;
18. exit(self);
19. end;
20.  
21.   procedure TDataRec.WriteValues;
22. begin
23.   WriteLn('level: ',level,' dwell: ',dwell:2:2);
24. end;
25.  
26. type aos=array of string;
27. type aoi=array of integer;
28. type aod=array of TDataRec;
29.  
30. var
31. TDataRecArray:aod;
32. a1:aos;
33. i1:aoi;
34. tmp:TDataRec;
35. i:int32;
36.  
37.  
38. procedure push<T>(var a :T;index:int32;insertion:T);
39. begin
40. insert(insertion,a,index);
41. end;
42.  
43. procedure pop<T>(var a:T;index:array of int32);
44. var
45. i:int32;
46. begin
47. for i:=0 to high(index)  do delete(a,index[i],1);
48. end;
49.  
50. begin
51.  
52. a1:=['a','b','c','x','y','z'];
53. for i:=0 to high(a1) do write(a1[i],' ');
54. writeln('  original strings');
55. push<aos>(a1,4,['9','10','11','12']);
56. for i:=0 to high(a1) do write(a1[i],' ');
57. writeln(' add 9 10 11 12 at position 4 ');
58. pop<aos>(a1,[3]);
59. for i:=0 to high(a1) do write(a1[i],' ');
60. writeln('  delete position 3');
61. setlength(TDataRecArray,3);
62. writeln('objects');
63. for i:=0 to high(TDataRecArray) do TDataRecArray[i].init;
64. for i:=0 to high(TDataRecArray) do TDataRecArray[i].WriteValues;
65. writeln;
66.  
67. push<aod>(TDataRecArray,2,[tmp.init,tmp.init]);
68. writeln('push another two into position 2');
69. for i:=0 to high(TDataRecArray) do TDataRecArray[i].WriteValues;
70. writeln;
71. writeln('pop the first one');
72. pop<aod>(TDataRecArray,[0]);
73. for i:=0 to high(TDataRecArray) do TDataRecArray[i].WriteValues;
74. writeln;
75. writeln('integers');
76. i1:=[random(100),random(100),random(100),random(100)];
77. for i:=0 to high(i1) do write(i1[i],' ');
78. writeln;
79. push<aoi>(i1,3,[5,5,5,5,5,5]);
80. writeln('push six fives into position 3');
81. for i:=0 to high(i1) do write(i1[i],' ');
82. writeln;
83. pop<aoi>(i1,[0,0,0,0,0,0,0,0,0]);
84. writeln('pop all but one');
85. for i:=0 to high(i1) do write(i1[i],' ');
86. writeln;
87. writeln('Press return to end . . .');
88. readln;
89. end.
90.  
91.  

[Kwadrum]

BobDog

Sorry, I am not familiar with this kind of definitions:

Code: Pascal  [Select][+][-]

1. procedure push<T>(var a :T;index:int32;insertion:T);
2. begin
3. insert(insertion,a,index);
4. end;

Does it mean one doesn't have to specify the exact type of T? Is there any specific term for this operation so I could search for it online?

Thank you.

[PascalDragon]

Sorry, I am not familiar with this kind of definitions:

Code: Pascal  [Select][+][-]

1. procedure push<T>(var a :T;index:int32;insertion:T);
2. begin
3. insert(insertion,a,index);
4. end;

Does it mean one doesn't have to specify the exact type of T? Is there any specific term for this operation so I could search for it online?

These are called “generics” or more specially in this case “generic routines”. T is a placeholder for a type and if you look at BobDog's code again you can see further down that they use the following:

Code: Pascal  [Select][+][-]

1. push<aos>(a1,4,['9','10','11','12']);
2.  

That means that the generic push<> is specialized with the aos type at compile time. Type checking will apply (so if you do something inside push<> that is not supported by aos (e.g. calling Writeln on it) then the compiler will generate an error.

Side note: if you use FPC's default mode (aka fpc) or mode ObjFPC instead of mode Delphi then the syntax is like this:

Code: Pascal  [Select][+][-]

1. generic procedure push<T>(var a :T;index:int32;insertion:T);
2. begin
3. insert(insertion,a,index);
4. end;
5.  
6. // calling it:
7. specialize push<aos>(a1,4,['9','10','11','12']);

[BobDog]

I am using version 3.2.2 64 bits win.
I think you need either this or the previous version for generics
 
https://wiki.freepascal.org/Generics

[PascalDragon]

I am using version 3.2.2 64 bits win.
I think you need either this or the previous version for generics
 
https://wiki.freepascal.org/Generics

As the linked article mentions you need to differentiate here: generic routines were introduced with 3.2, but generic types are much older (initially 2.2 with further improvements down the road (especially improved Delphi compatibility)).

[BobDog]

PascalDragon.
The generic examples and methods are hard to follow (for me anyway) in the link.
If I didn't already use them in c++ I would still be trying to fathom them out.
Luckily they are almost identical to c++.
The gmax function for instance, I don't really need any class or use specialize.
And the template section is also hard to follow, especially when it delves into units.
Simplified a bit.

Code: Pascal  [Select][+][-]

1. {$mode delphi}
2.  
3. procedure switch<T>(var a, b: T);
4. var temp: T;
5. begin
6.   temp := a; a := b; b := temp;
7. end;
8.  
9. function gmax<T>(a,b:T):T;
10.   begin
11.     if a > b then
12.       exit (a)
13.     else
14.       exit (b);
15.   end;
16.  
17. var
18. a,b:integer;
19. c,d:ansistring;
20. e,f:real;
21.  
22. begin
23.  
24. a:=1;b:=2;
25. switch<integer>(a,b);
26. writeln(a,'  ',b,'  max = ',gmax<integer>(a,b));
27. c:='Hello';d:='Goodbye';
28. switch<ansistring>(c,d);
29. writeln(c,'  ',d,'  max = ',gmax<ansistring>(c,d));
30. e:=-10;f:=10;
31. switch<real>(e,f);
32. writeln(e,'  ',f,'  max = ',gmax<real>(e,f));
33. writeln('Press return to finish . . .');
34. readln;
35. end.
36.  

[PascalDragon]

The generic examples and methods are hard to follow (for me anyway) in the link.
If I didn't already use them in c++ I would still be trying to fathom them out.
Luckily they are almost identical to c++.

The official documentation about generics is available here (though generic routines are not yet mentioned there). Maybe someone can improve the wiki article however.

The gmax function for instance, I don't really need any class or use specialize.

Because you're using mode Delphi. In the other modes you need to use the generic and specialize keywords.