Dynamic array as type member not allowed.. why not? WHY!!

For other topics related to the FreeBASIC project or its community.
codeFoil
Posts: 255
Joined: Dec 22, 2011 4:45
Location: United States
Contact:

Re: Dynamic array as type member not allowed.. why not? WHY!

Postby codeFoil » Mar 13, 2012 23:51

... and to address this issue, we would need syntax in the parameter list to specify which type of array maybe passed, which would require run time information to correctly enforce such a rule when parameter are passed from separate compiliation units. This would result in both cumbersome syntax and a performance penalty. This might be restricted to special cases at the cost of complicating the compiler code and introducing a maintenance burden on the developers.

More importantly, this would bind the compiler generated code even stronger to the run time library. I don't think that is a good idea.
AGS
Posts: 1284
Joined: Sep 25, 2007 0:26
Location: the Netherlands

Postby AGS » Mar 19, 2012 19:16

I checked out the fb source code implementing dynamic arrays. And I think having a dynamic array inside a UDT is (at least at this point) something I'd like to have. But lets start a little 'lower'. I noticed that in the source code redim preserve does not preserve a thing. It just reallocates the array but does not move data around. Suppose you go from (0 to 1,0 to 1) to (0 to 1, 0 to 2).
In the beginning you have this: ((0,0) = 1, (0,1) = 2, (1,0) = 3, (1,1) = 4)):

Code: Select all

0     1 
1  2  3   4


Then after redim preserve you get this

Code: Select all

0         1
1  2  3   4  x x


where x denotes 'fresh memory' (the part that got reallocated). (1.0) used to be 3 but now it has turned into 4. Reason being the way data is layed out in memory (the way the address of (1,0) gets calculated). The calculation is correct, the data returned is not.

Data must be moved to get redim preserve right. The content of the array should look like this

Code: Select all

0          1
1  2   x   3  4  x


where x denotes an empty item. Of course the first x is where the 3 used to be but it was moved (same thing for item 4).

All of this is about dynamic arrays of simple type here. Not dynamic arrays of type UDT nor dynamic arrays as part of an udt.
As a first step it would be great to have a redim preserve that actually preserves. And as far as restrictions go: I looked up what Microsoft has written about the use of dynamic arrays (in vb6)

http://msdn.microsoft.com/en-us/library ... 80%29.aspx

They put some restrictions on redim preserve that seem to make sense.

msdn wrote:Resizing with Preserve. If you use Preserve, you can resize only the last dimension of the array, and for every other dimension you must specify the same bound it already has in the existing array.

For example, if your array has only one dimension, you can resize that dimension and still preserve all the contents of the array, because you are changing the last and only dimension. However, if your array has two or more dimensions, you can change the size of only the last dimension if you use Preserve.


Resizing more than one dimension while trying to preserve memory can lead to difficulties and a lot of moving around of data.
So a restriction on not changing more than one dimension seems like a good idea (the restriction of only being able to change the last dimension I don't get).

When increasing array size data is copied towards the end of the array. First reallocate, then move data.
When decreasing array size data is copied towards the start of the array first and then reallocation needs to take place.

If you would reallocate before copying (when decreasing array size) then data would get lost and preserve would not lead to the right result.

This movement of data, by the way, is needed because the dynamic array keeps data in row major order (you have to keep data in a that order).

Moving the data around into the appropriate position (to make sure redim preserve actually preserves) takes a bit of CPU time. You first get a reallocate and then movement of data (or vice versa). That movement of data cannot be done by using one call to memcpy or memmove. As far as dynamic arrays of type UDT are concerned I don't know if there is that much difference. You have to make sure the size of the items inside a dynamic array stays the same (you can't put variable length records inside a dynamic array).

Why not fix the easy case first and that's redim preserve for simple types (perhaps for strings as well?). It's just a matter of moving data around and prohibiting the user from doing a redim preserve on more than one dimension at a time.

Which dimension gets a change in size should not matter as long as only one gets changed.

If the above turns out to be as easy to implement as I am hoping it is then dynamic arrays of type string/records could be added. If that works it could be made to work on dynamic arrays inside UDTs. Looking at what others have written I'd say there will always be some kind of restrictions in place when it comes to using dynamic arrays.

It would be nice to have as few restrictions as possible. Right now dynamic arrays are mostly usable in the simple case of a one dimensional array of simple type (which, I might add, I use as often as I can). I would love not having to mess around with pointers too much as debugging those segfaults (it's so easy to make a mistake when programming using pointers) gets really annoying after a while (REALLY annoying).
dodicat
Posts: 6766
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: Dynamic array as type member not allowed.. why not? WHY!

Postby dodicat » Mar 20, 2012 11:38

To redim preserve a multi dimensional array safely, only one extra instruction line per loop is needed.
So, it is not hard to implement.
What I find annoying is the obstinateness of constructors to do a job for you, I usually just revert to subs or functions to save myself hassle.
(For your start a little slower)
Example for redim preserve:

Code: Select all

 Redim As double funct(0, 0, 0)

Dim As integer tempx, tempy, tempz 'three extra variables required
dim as integer lower1=1,lower2=1,lower3=1
Dim As Integer upper1=8,upper2=3,upper3=2

'want funct to be (lower1 to upper1,lower2 to upper2,lower3 to upper3)
'i.e. in this case (1 to 8,1 to 3,1 to 2)

For x As Integer = lower1 To upper1
    if tempx<x then tempx=x 
 
  For y As Integer = lower2 To upper2
      if tempy<y then tempy=y

    For z As Integer = lower3 To upper3
        if tempz<z then tempz=z
       
      Redim Preserve funct(lower1 to tempx,lower2 to tempy,lower3 to tempz)
      funct(x,y,z)=x+y+z 'or whatever

    Next z
  Next y
Next x

print
For x As Integer = lower1 To upper1
  For y As Integer = lower2 To upper2
    For z As Integer = lower3 To upper3
        print "   funct(";x;y;z;") =";funct(x,y,z);
    Next z
    Print
  Next y
  Print
Next x
print "funct(";lbound(funct,1);" to"; ubound(funct,1);",";lbound(funct,2);" to"; ubound(funct,2);",";lbound(funct,3);" to"; ubound(funct,3);")"

Sleep
 
fxm
Posts: 10061
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: Dynamic array as type member not allowed.. why not? WHY!

Postby fxm » Mar 20, 2012 12:37

- Similar principle that I proposed previously in this post:
viewtopic.php?p=165907#p165907

- Remark:
Besides, to be compatible with negative upper bound, tempx/tempy/tempz must be initialized with the lower1/lower2/lower3 values:
...
Dim as integer lower1=1,lower2=1,lower3=1
Dim As Integer upper1=8,upper2=3,upper3=2
Dim As integer tempx=lower1, tempy=lower2, tempz=lower3 'three extra variables required
...
Sannaj
Posts: 27
Joined: Dec 19, 2010 16:39

Re: Dynamic array as type member not allowed.. why not? WHY!

Postby Sannaj » Mar 20, 2012 15:48

First of all dynamic arrays should get some type like features like a constructor, witch initialises the array or a "redim" method.


I think it would be very useful to introduce some kind of meta constructor. This is the main constructor of a type/class. It is not written manually, automatically generated for each class and has following jobs:
1. Initialise all of the classes member variables (currently done by the function in witch the type is declared)
2. Calls the constructors for the dynamic member arrays and other members

The main constructor, takes no parameters, and it is called by explicit declared constructors, as their implicit first action or directly by the object creator, if there is no other constructor
dodicat
Posts: 6766
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: Dynamic array as type member not allowed.. why not? WHY!

Postby dodicat » Mar 20, 2012 16:16

Initalizing the temps will make this process general and simple --- FXM
For the workaround for Dynamic arrays as type members I note that much use is made of constructors.
For my own (start a little slower ) regarding automation of a process by constructor, as I mentioned in my previous post, in the main, I just cannot get them to do what I want.

I have two types, a point and a line, which uses two points.
The third member of the line type is an angle (theta).
I would like to automate fetching the associated angle of the line by constructor.
At the moment, in this snippet, I must resort to a function.

If it's a bit off topic I apologize.

Code: Select all

 
Type screenpoint
    As Single x,y
End Type
type screenline
    as screenpoint p1,p2
    as single theta
    'declare constructor(ln as screenline)
end type

#define degrees *180/(4*(atn(1)))

function theta(byval ln as screenline) as single
    dim as single dy=ln.p2.y-ln.p1.y
    dim as single dx=ln.p2.x-ln.p1.x
return atan2(dy,dx) degrees
end function

'constructor screenline(ln as screenline)
'dim as single dy=ln.p2.y-ln.p1.y
'dim as single dx=ln.p2.x-ln.p1.x
'this.theta= atan2(dy,dx) degrees
'end constructor

screen 19
dim as screenline ln(1 to 3)

'need a constructor for theta instead of the function

'approx equilateral triangle
ln(1)=type<screenline>(type<screenpoint>(200,200),type<screenpoint>(500,200)):ln(1).theta=theta(ln(1))
ln(2)=type<screenline>(type<screenpoint>(500,200),type<screenpoint>(350,459.808)):ln(2).theta=theta(ln(2))
ln(3)=type<screenline>(type<screenpoint>(350,459.808),type<screenpoint>(200,200)):ln(3).theta=theta(ln(3))

'display lines, write angle near the middle of each
for z as integer=1 to 3
line(ln(z).p1.x,ln(z).p1.y)-(ln(z).p2.x,ln(z).p2.y)
draw string((ln(z).p1.x+ln(z).p2.x)/2,(ln(z).p1.y+ln(z).p2.y)/2),str(ln(z).theta)
next z

sleep



 
fxm
Posts: 10061
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: Dynamic array as type member not allowed.. why not? WHY!

Postby fxm » Mar 20, 2012 17:47

Code: Select all

Type screenpoint
    As Single x,y
End Type
type screenline
    as screenpoint p1,p2
    as single theta
    declare constructor(byval pt1 as screenpoint=(0,0), byval pt2 as screenpoint=(0,0))
end type

#define degrees *180/(4*(atn(1)))

constructor screenline(byval pt1 as screenpoint=(0,0), byval pt2 as screenpoint=(0,0))
    this.p1=pt1
    this.p2=pt2
    dim as single dy=pt2.y-pt1.y
    dim as single dx=pt2.x-pt1.x
    this.theta=atan2(dy,dx) degrees
end constructor

screen 19
dim as screenline ln(1 to 3)

'approx equilateral triangle
ln(1)=type(type(200,200),type(500,200))
ln(2)=type(type(500,200),type(350,459.808))
ln(3)=type(type(350,459.808),type(200,200))

'display lines, write angle near the middle of each
for z as integer=1 to 3
line(ln(z).p1.x,ln(z).p1.y)-(ln(z).p2.x,ln(z).p2.y)
draw string((ln(z).p1.x+ln(z).p2.x)/2,(ln(z).p1.y+ln(z).p2.y)/2),str(ln(z).theta)
next z

sleep
Merick
Posts: 1038
Joined: May 28, 2007 1:52

Re: Dynamic array as type member not allowed.. why not? WHY!

Postby Merick » Mar 20, 2012 18:39

If you make theta into a property, then it will give you the angle even if you've changed one of the points on the line:

Code: Select all

Type screenpoint
    As Single x,y
End Type
type screenline
    as screenpoint p1,p2
    declare property theta() as single
    declare constructor(byval pt1 as screenpoint=(0,0), byval pt2 as screenpoint=(0,0))
end type

#define degrees *180/(4*(atn(1)))

constructor screenline(byval pt1 as screenpoint=(0,0), byval pt2 as screenpoint=(0,0))
    this.p1=pt1
    this.p2=pt2
end constructor

property screenline.theta() as single
    dim as single dy=p2.y-p1.y
    dim as single dx=p2.x-p1.x
    theta=atan2(dy,dx) degrees
end property

screen 19
dim as screenline ln(1 to 3)

'approx equilateral triangle
ln(1)=type(type(200,200),type(500,200))
ln(2)=type(type(500,200),type(350,459.808))
ln(3)=type(type(350,459.808),type(200,200))

'display lines, write angle near the middle of each
for z as integer=1 to 3
line(ln(z).p1.x,ln(z).p1.y)-(ln(z).p2.x,ln(z).p2.y)
draw string((ln(z).p1.x+ln(z).p2.x)/2,(ln(z).p1.y+ln(z).p2.y)/2),str(ln(z).theta)
next z

sleep
fxm
Posts: 10061
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: Dynamic array as type member not allowed.. why not? WHY!

Postby fxm » Mar 20, 2012 18:43

Well done!
Or also a member function.
dodicat
Posts: 6766
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: Dynamic array as type member not allowed.. why not? WHY!

Postby dodicat » Mar 20, 2012 22:01

Thanks fxm, Merick.
So a constructor, member property or member function can automatically fill other UDT members, or be UDT members which automatically create their own values when UDT is created by dim, or simply show a value when requested.
I've added a triangle type, tested on both codes fxm/Merick.
Here's fxm's snippet with the added triangle type which displays the triangle's area, and added a member function to line type giving the line's length.
You may continue now AGS, uninterupted.
Thanks again fxm and Merick

Code: Select all

 Type screenpoint
    As Single x,y
End Type

type screenline
    as screenpoint p1,p2
    as single theta
    declare function length() as single
    declare constructor(byval pt1 as screenpoint=(0,0), byval pt2 as screenpoint=(0,0))
end type

type triangle
as screenline line1,line2,line3
declare property area() as single
end type

#define degrees *180/(4*(atn(1)))

constructor screenline(byval pt1 as screenpoint=(0,0), byval pt2 as screenpoint=(0,0))
    this.p1=pt1
    this.p2=pt2
    dim as single dy=pt2.y-pt1.y
    dim as single dx=pt2.x-pt1.x
    this.theta=atan2(dy,dx) degrees
end constructor


function screenline.length() as single
    length=sqr((p2.y-p1.y)^2+(p2.x-p1.x)^2)
end function

property triangle.area() as single
dim as single a=line1.length
dim as single b=line2.length
dim as single c=line3.length
dim as single s=(a+b+c)/2
area=sqr(s*(s-a)*(s-b)*(s-c))
end property

screen 19
dim as screenline ln(1 to 3)
dim as triangle t



'approx equilateral triangle
ln(1)=type<screenline>(type<screenpoint>(200,200),type<screenpoint>(500,200))
ln(2)=type<screenline>(type<screenpoint>(500,200),type<screenpoint>(350,459.808))
ln(3)=type<screenline>(type<screenpoint>(350,459.808),type<screenpoint>(200,200))
 t.line1=ln(1)
 t.line2=ln(2)
 t.line3=ln(3)
 '''t=type<triangle>(ln(1),ln(2),ln(3)) '?? no work!
 
'display lines, write angle near the middle of each
for z as integer=1 to 3
line(ln(z).p1.x,ln(z).p1.y)-(ln(z).p2.x,ln(z).p2.y)
draw string((ln(z).p1.x+ln(z).p2.x)/2-50,(ln(z).p1.y+ln(z).p2.y)/2),str(ln(z).theta & " len= " & int(ln(z).length))
next z
draw string (100,50),"AREA " &(int(t.area))
sleep
 
fxm
Posts: 10061
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: Dynamic array as type member not allowed.. why not? WHY!

Postby fxm » Mar 20, 2012 22:59

dodicat wrote: '''t=type<triangle>(ln(1),ln(2),ln(3)) '?? no work!

You must define constructor in this case (because constructor in screenline).

Code: Select all

Type screenpoint
    As Single x,y
End Type

type screenline
    as screenpoint p1,p2
    as single theta
    declare function length() as single
    declare constructor
    declare constructor(byval pt1 as screenpoint, byval pt2 as screenpoint)
end type

type triangle
    as screenline line1,line2,line3
    declare property area() as single
    declare constructor
    declare constructor(byval l1 as screenline, byval l2 as screenline, byval l3 as screenline)
end type

#define degrees *180/(4*(atn(1)))

constructor screenline
end constructor

constructor screenline(byval pt1 as screenpoint, byval pt2 as screenpoint)
    this.p1=pt1
    this.p2=pt2
    dim as single dy=pt2.y-pt1.y
    dim as single dx=pt2.x-pt1.x
    this.theta=atan2(dy,dx) degrees
end constructor

function screenline.length() as single
    length=sqr((p2.y-p1.y)^2+(p2.x-p1.x)^2)
end function

property triangle.area() as single
dim as single a=line1.length
dim as single b=line2.length
dim as single c=line3.length
dim as single s=(a+b+c)/2
area=sqr(s*(s-a)*(s-b)*(s-c))
end property

constructor triangle
end constructor

constructor triangle(byval l1 as screenline, byval l2 as screenline, byval l3 as screenline)
    this.line1=l1
    this.line2=l2
    this.line3=l3
end constructor

screen 19
dim as screenline ln(1 to 3)
dim as triangle t



'approx equilateral triangle
ln(1)=type<screenline>(type<screenpoint>(200,200),type<screenpoint>(500,200))
ln(2)=type<screenline>(type<screenpoint>(500,200),type<screenpoint>(350,459.808))
ln(3)=type<screenline>(type<screenpoint>(350,459.808),type<screenpoint>(200,200))
t=type<triangle>(ln(1),ln(2),ln(3))

'display lines, write angle near the middle of each
for z as integer=1 to 3
line(ln(z).p1.x,ln(z).p1.y)-(ln(z).p2.x,ln(z).p2.y)
draw string((ln(z).p1.x+ln(z).p2.x)/2-50,(ln(z).p1.y+ln(z).p2.y)/2),str(ln(z).theta & " len= " & int(ln(z).length))
next z
draw string (100,50),"AREA " &(int(t.area))
sleep
AGS
Posts: 1284
Joined: Sep 25, 2007 0:26
Location: the Netherlands

Postby AGS » Mar 28, 2012 21:57

I've thought a bit about redim preserve across all eight possible dimensions in one function call to redim preserve. It would require memory reallocation to the biggest amount of memory needed (so all data movements can succeed). That way only two reallocations are needed to handle all the different data movements. One before the movement of data and one after. The best solution would be to calculate the minimal amount of necessary data movements to copy the data to where the user would expect it. This would not solve the reallocation problem but no data would get moved unnecessary.

The simple version of re-dimming one dimension at a time does not involve any (potentially?) intricate algorithm. Function calls are reasonably cheap. The choice here is between eight calls to a simple redim preserve routine versus one call to a less simple version of redim preserve.

Negative indices and redim preserve can lead to nice results as going from positive indices to negative indices is something that can lead to reallocation-less redim preserve.

Going from (0 to 2,0 to 1) to (-1 to 1, 0 to 1) takes no reallocation. But it does take some movement of data.

Code: Select all

0 1 2
010101
123456


to

Code: Select all

-10 1
010101
xx1234


Move data to the right (memmove), no reallocation and then clear the first two items. And there you go: shr by means of redim preserve. And of course the opposite works as well.

I looked at the rtlib source code to see what happens when you go from negative indices to positive indices or vice versa (something like the example above). There is always a call to realloc regardless of an increase/decrease in size. No data gets moved.

The nice thing about freebasic and the fb rtlib is that it's open source and the implementation of any kind of redim preserve scheme is only one hack away :) If you can program in C you can create your own 'private' version of redim preserve. You could even program the new version of redim preserve in fb, compile it and link it with the rtlib. By using the gcc back end and saving the resulting C (use -R) file you can even get your version of redim preserve in C. You could include that with the rest of the rtlib and then compile rtlib using your version of redim preserve related functions.
fxm
Posts: 10061
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: Dynamic array as type member not allowed.. why not? WHY!

Postby fxm » Apr 08, 2012 18:42

To resize an array structure (of 'N' dimensions) with complete preservation, it is simpler to code a pointer indexes structure (pt.array[i][j]...) instead of a real array structure (array(i, j, ...)) when the all indexes remain referenced from the base "0" (0 To ...).
Indeed, a true array has its data in memory with a serial structure (stored in row-major order) while a pointer indexes corresponds to a tree structure more easily re-sizable.

Example of two-dimensions pointer indexes re-sizing:

Code: Select all

Type UDT_array
  Dim As Integer Ptr Ptr array
  Dim As Integer bound1 = -1, bound2 = -1
End Type
Declare Sub Redim_Pointer_Indexes2 (Byref p As UDT_array, _
                                    Byval bound1 As Integer, _
                                    Byval bound2 As Integer)
Declare Sub Print_Pointer_Indexes2(Byval pt_array As Integer Ptr Ptr, _
                                   Byval bound1 As Integer, _
                                   Byval bound2 As Integer)
Dim pt As UDT_array


' Dim array(0 to 2, 0 to 3)
Redim_Pointer_Indexes2(pt, 2, 3)
Print_Pointer_Indexes2(pt.array, 2, 3)

For i As Integer = 0 To 2
  For j As Integer = 0 To 3
    pt.array[i][j] = (i + 1) * 10 + J + 1
  Next j
Next I
Print_Pointer_Indexes2(pt.array, 2, 3)


' Redim array(0 to 4, 0 to 5)
Redim_Pointer_Indexes2(pt, 4, 5)
Print_Pointer_Indexes2(pt.array, 4, 5)

For i As Integer = 0 To 4
  For j As Integer = 0 To 5
    If i > 2 Or j > 3 Then
      pt.array[i][j] = (i + 1) * 10 + J + 1
    End If
  Next j
Next i
Print_Pointer_Indexes2(pt.array, 4, 5)


' Redim array(0 to 1, 0 to 2)
Redim_Pointer_Indexes2(pt, 1, 2)
Print_Pointer_Indexes2(pT.array, 1, 2)

Sleep


Sub Redim_Pointer_Indexes2 (Byref p As UDT_array, _
                            Byval bound1 As Integer, _
                            Byval bound2 As Integer)
  For i As Integer = bound1 + 1 To p.bound1
    Deallocate(p.array[i])
  Next i
  p.array = Reallocate(p.array, (bound1 + 1) * Sizeof(Integer Ptr))
  For i As Integer = 0 To bound1
    If i > p.bound1 Then
      p.array[i] = 0
    End If
    p.array[i] = Reallocate(p.array[i], (bound2 + 1) * Sizeof(integer))
    For j As Integer = 0 To bound2
      If i > p.bound1 Or j > p.bound2 Then
        p.array[i][j] = 0
      End If
    Next j
  Next i
  p.bound1 = bound1
  p.bound2 = bound2
End Sub

Sub Print_Pointer_Indexes2(Byval pt_array As Integer Ptr Ptr, _
                           Byval bound1 As Integer, _
                           Byval bound2 As Integer)
  For i As Integer = 0 To bound1
    For j As Integer = 0 To bound2
      Print Using "####"; pt_array[i][j];
    Next j
    Print
  Next i
  Print
End Sub

Besides, this pointer indexes structure (tree structure) also allows to easily modify the numbers of the dimensions.
fxm
Posts: 10061
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: Dynamic array as type member not allowed.. why not? WHY!

Postby fxm » Apr 05, 2014 6:13

Good news:
Dynamic array member will be supported in the next fbc revision.
[177b0a]
fxm
Posts: 10061
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: Dynamic array as type member not allowed.. why not? WHY!

Postby fxm » Apr 05, 2014 13:35

General question about dynamic arrays:
Will dynamic array elements guaranteed to be always contiguous in physical memory during runtime?

Return to “Community Discussion”

Who is online

Users browsing this forum: Google [Bot] and 8 guests