Recent

Author Topic: Dynamic arrays concatenation, insertion and deletion of elements  (Read 4920 times)

lainz

  • Hero Member
  • *****
  • Posts: 3884
Re: Dynamic arrays concatenation, insertion and deletion of elements
« Reply #15 on: October 03, 2020, 04:43:53 am »
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

  • Hero Member
  • *****
  • Posts: 4429
  • My goal: build my own game engine using Lazarus
Re: Dynamic arrays concatenation, insertion and deletion of elements
« Reply #16 on: October 03, 2020, 05:17:32 am »
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

  • New Member
  • *
  • Posts: 17
Re: Dynamic arrays concatenation, insertion and deletion of elements
« Reply #17 on: November 08, 2021, 10:43:13 pm »
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

  • Hero Member
  • *****
  • Posts: 3856
Re: Dynamic arrays concatenation, insertion and deletion of elements
« Reply #18 on: November 08, 2021, 11:46:27 pm »
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

  • New Member
  • *
  • Posts: 17
Re: Dynamic arrays concatenation, insertion and deletion of elements
« Reply #19 on: November 09, 2021, 12:50:27 am »
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?
« Last Edit: November 09, 2021, 04:47:32 am by Kwadrum »

howardpc

  • Hero Member
  • *****
  • Posts: 3856
Re: Dynamic arrays concatenation, insertion and deletion of elements
« Reply #20 on: November 09, 2021, 10:00:40 am »
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

  • New Member
  • *
  • Posts: 17
Re: Dynamic arrays concatenation, insertion and deletion of elements
« Reply #21 on: November 10, 2021, 06:04:41 pm »
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!
« Last Edit: November 10, 2021, 06:07:20 pm by Kwadrum »

BobDog

  • Full Member
  • ***
  • Posts: 181
Re: Dynamic arrays concatenation, insertion and deletion of elements
« Reply #22 on: November 10, 2021, 09:33:29 pm »

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

  • New Member
  • *
  • Posts: 17
Re: Dynamic arrays concatenation, insertion and deletion of elements
« Reply #23 on: November 11, 2021, 04:33:34 am »
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

  • Hero Member
  • *****
  • Posts: 3631
  • Compiler Developer
Re: Dynamic arrays concatenation, insertion and deletion of elements
« Reply #24 on: November 11, 2021, 09:00:42 am »
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

  • Full Member
  • ***
  • Posts: 181
Re: Dynamic arrays concatenation, insertion and deletion of elements
« Reply #25 on: November 11, 2021, 09:06:56 am »

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

  • Hero Member
  • *****
  • Posts: 3631
  • Compiler Developer
Re: Dynamic arrays concatenation, insertion and deletion of elements
« Reply #26 on: November 11, 2021, 09:18:07 am »
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

  • Full Member
  • ***
  • Posts: 181
Re: Dynamic arrays concatenation, insertion and deletion of elements
« Reply #27 on: November 11, 2021, 11:58:22 am »

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

  • Hero Member
  • *****
  • Posts: 3631
  • Compiler Developer
Re: Dynamic arrays concatenation, insertion and deletion of elements
« Reply #28 on: November 11, 2021, 01:35:15 pm »
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.
« Last Edit: November 11, 2021, 09:11:24 pm by PascalDragon »

 

TinyPortal © 2005-2018