New array features

[MrSwiss]

i know, but that´s exactly what i want.

This is totally illogical, as well as contradictory to what you wrote yourself.
Later on you stated clearly in "function like", that you want a useful return.

which sets a local #define or variable for later processing, but cannot be used for returning a value like this

Since this is based on "local" only and, is very well possible for a externally
defined variable, I fail to understand, what you are after ...

[Juergen Kuehlwein]

I fail to understand, what you are after ...

i want it to be valid only in scope of my array macro. Anyway my previous question is obsolete now, because i have a better solution. You will understand, when i´m ready to present code.


JK

[Juergen Kuehlwein]

About naming again - is there a problem or penalty when using long, unusual and underscored names in general as well as for and inside a namespace in order not to pollute the global namespace?

I need some new names in the global namespace, but these are handled "internally", so that the user doesn´t have to deal with them (i.e type them). What is exposed to the user should be short and meaningful, everything else could be handled by macros.

Example:
Defining "up" would consume the name "up" in the global namespace. But inside a macro i can make "array_ext__up" from "up", which is still in the global namespace, but a lot more unusual or unlikely to be used elsewhere. That is i can have a short and meaningful name ("up") without blocking it for other purposes.

Do you see any problems here?


JK

[gothon]

This example is based on variable sized data referenced using the 'Any Ptr' type rather than macros, so it will not generate any significant bloat if it is reused on many different kinds of array.

I made a working version of my example by implementing HeapSort, https://en.wikipedia.org/wiki/Heapsort

This example is in 4 files, but if you prefer not to build 'libBinaryHeap.a', you can glue them together into 1 file and delete the '#include / #inclib' lines.

BinaryHeap.bi

Code: Select all

#Inclib "BinaryHeap"

Type ArrayRange
    FirstElement As Any Ptr
    ElementSize As Integer
    LastElementIdx As Integer
End Type

Type BinaryHeap
    AR As ArrayRange
    LessComp As Function(L As Any Ptr, R As Any Ptr) As Integer
   
  Private:
    Declare Sub SiftDown(I As Integer)
    Declare Sub BuildHeap
   
  Public:
    Declare Constructor(R As ArrayRange, LC As Function(L As Any Ptr, R As Any Ptr) As Integer)
    Declare Sub Insert
    Declare Sub ExtractMax
End Type

#Define ElementArray(ELEMENT, Length) Type<ArrayRange>(@(ELEMENT), SizeOf(ELEMENT), (Length) - 1)
#Define SubArray(ARRAY, LB, UB) Type<ArrayRange>(@ARRAY(LB), SizeOf(ARRAY(LBound(ARRAY))), (UB) - (LB))
#Define WholeArray(ARRAY) SubArray(ARRAY, LBound(ARRAY), UBound(ARRAY))

Declare Sub HeapSort(Range As ArrayRange, LessComp As Function(L As Any Ptr, R As Any Ptr) As Integer)


NumberCompare.bi

Code: Select all

#Macro DefineCompareNumeric(VARTYPE)
    Function VARTYPE##_AscendingCompare(L As Any Ptr, R As Any Ptr) As Integer
        Return *CPtr(VARTYPE Ptr, L) < *CPtr(VARTYPE Ptr, R)
    End Function
   
    Function VARTYPE##_DescendingCompare(L As Any Ptr, R As Any Ptr) As Integer
        Return *CPtr(VARTYPE Ptr, L) > *CPtr(VARTYPE Ptr, R)
    End Function
#EndMacro

#Macro HeapSortNumeric(ARRAYRANGE, ARRAY, DIRECTION)
    #If TypeOf(ARRAY) = Byte
        HeapSort ARRAYRANGE, @Byte_##DIRECTION##Compare
    #ElseIf TypeOf(ARRAY) = UByte
        HeapSort ARRAYRANGE, @UByte_##DIRECTION##Compare
    #ElseIf TypeOf(ARRAY) = Short
        HeapSort ARRAYRANGE, @Short_##DIRECTION##Compare
    #ElseIf TypeOf(ARRAY) = UShort
        HeapSort ARRAYRANGE, @UShort_##DIRECTION##Compare
    #ElseIf TypeOf(ARRAY) = Integer
        HeapSort ARRAYRANGE, @Integer_##DIRECTION##Compare
    #ElseIf TypeOf(ARRAY) = UInteger
        HeapSort ARRAYRANGE, @UInteger_##DIRECTION##Compare
    #ElseIf TypeOf(ARRAY) = Long
        HeapSort ARRAYRANGE, @Long_##DIRECTION##Compare
    #ElseIf TypeOf(ARRAY) = ULong
        HeapSort ARRAYRANGE, @ULong_##DIRECTION##Compare
    #ElseIf TypeOf(ARRAY) = LongInt
        HeapSort ARRAYRANGE, @LongInt_##DIRECTION##Compare
    #ElseIf TypeOf(ARRAY) = ULongInt
        HeapSort ARRAYRANGE, @ULongInt_##DIRECTION##Compare
    #ElseIf TypeOf(ARRAY) = Single
        HeapSort ARRAYRANGE, @Single_##DIRECTION##Compare
    #ElseIf TypeOf(ARRAY) = Double
        HeapSort ARRAYRANGE, @Double_##DIRECTION##Compare
    #Else
        #Print Warning: ARRAY is not of a numeric type and will not be sorted!
    #EndIf
#EndMacro

#Define HeapSortNumericElement(ELEMENT, LENGTH, DIRECTION) HeapSortNumeric(ElementArray(ELEMENT, LENGTH), ELEMENT, DIRECTION)
#Define HeapSortNumericSub(ARRAY, LB, UB, DIRECTION) HeapSortNumeric(SubArray(ARRAY, LB, UB), ARRAY, DIRECTION)
#Define HeapSortNumericWhole(ARRAY, DIRECTION) HeapSortNumeric(WholeArray(ARRAY), ARRAY, DIRECTION)

'Should probably Declare functions here and put defines in a seperate .bas file
DefineCompareNumeric(Byte)
DefineCompareNumeric(UByte)
DefineCompareNumeric(Short)
DefineCompareNumeric(UShort)
DefineCompareNumeric(Integer)
DefineCompareNumeric(UInteger)
DefineCompareNumeric(Long)
DefineCompareNumeric(ULong)
DefineCompareNumeric(LongInt)
DefineCompareNumeric(ULongInt)
DefineCompareNumeric(Single)
DefineCompareNumeric(Double)


Sorting arrays of intrinsic numeric types is good for making demos and tests. I can't think of any other applications however.

BinaryHeap.bas - compile to 'libBinaryHeap.a' with 'fbc -lib BinaryHeap.bas'

Code: Select all

#Include "BinaryHeap.bi"

#Define Element(I) (AR.FirstElement + (I) * AR.ElementSize)
#Define MemSwap(A, B) fb_MemSwap *CPtr(UByte Ptr, A), *CPtr(UByte Ptr, B), AR.ElementSize
#Define Parent(I) ((I) \ 2) 'One Based Heap Array
#Define LChild(I) ((I) * 2)
#Define RChild(I) ((I) * 2 + 1)

'Restore the heap property downward at node I
Sub BinaryHeap.SiftDown(I As Integer)
    Do While LChild(I) <= AR.LastElementIdx
        Var J = I
        Var LeftChild = Element(LChild(I))
        If LessComp(Element(J), LeftChild) Then J = LChild(I)
        If RChild(I) <= AR.LastElementIdx AndAlso LessComp(Element(J), LeftChild + AR.ElementSize) Then J = RChild(I)
        If J = I Then Exit Sub
        MemSwap(Element(I), Element(J))
        I = J
    Loop
End Sub

'Make the unordered elements satisfy the heap property in O(n) time
Sub BinaryHeap.BuildHeap
    For I As Integer = Parent(AR.LastElementIdx) To 1 Step -1
        SiftDown I
    Next I
End Sub

'Take an ArrayRange and a comparison and make it into a BinaryHeap
Constructor BinaryHeap(R As ArrayRange, LC As Function(L As Any Ptr, R As Any Ptr) As Integer)
    AR.FirstElement = R.FirstElement - R.ElementSize 'Now the Heap Array is 1 Based
    AR.ElementSize = R.ElementSize
    AR.LastElementIdx = R.LastElementIdx + 1
    LessComp = LC
   
    BuildHeap
End Constructor

'Decrement the size of the heap by swaping out the max element in O(Log(n)) time
Sub BinaryHeap.ExtractMax
    Assert (AR.LastElementIdx > 0)
    MemSwap(Element(1), Element(AR.LastElementIdx))
    AR.LastElementIdx -= 1
    SiftDown 1
End Sub

'Increment the size of the heap by sifting in the next array element O(1) average time, O(Log(n)) worst case
Sub BinaryHeap.Insert
    'ToDo:
    'AR.LastElementIdx += 1
    'SiftUp AR.LastElementIdx
End Sub

Sub HeapSort(R As ArrayRange, LessComp As Function(L As Any Ptr, R As Any Ptr) As Integer)
    Dim Heap As BinaryHeap = BinaryHeap(R, LessComp)
   
    Do While Heap.AR.LastElementIdx > 1
        Heap.ExtractMax
    Loop
End Sub


ToDo Note: BinaryHeap.Insert() is not implemented, but if it were, you could also use this as a Priority Queue! :-)

TestHeap.bas - main module compile with 'fbc TestHeap.bas'

Code: Select all

#Include "BinaryHeap.bi"
#Include "NumberCompare.bi"

Type MyUDT
    Key As Double
    Value As String
End Type

Function MyUDT_LessComp(L As Any Ptr, R As Any Ptr) As Integer
    Return CPtr(MyUDT Ptr, L)->Key < CPtr(MyUDT Ptr, R)->Key
End Function

Dim MyArray(3) As MyUDT

MyArray(0).Key = 10
MyArray(0).Value = "For I As Integer = 0 To UBound(MyArray)"
MyArray(1).Key = 20
MyArray(1).Value = "    Var J = I + Int(Rnd * (UBound(MyArray) + 1 - I))"
MyArray(2).Key = 30
MyArray(2).Value = "    Swap MyArray(I), MyArray(J)"
MyArray(3).Key = 40
MyArray(3).Value = "Next I"

'Make a random permutation
For I As Integer = 0 To UBound(MyArray)
    Var J = I + Int(Rnd * (UBound(MyArray) + 1 - I))
    Swap MyArray(I), MyArray(J)
Next I

For I As Integer = 0 To UBound(MyArray)
    Print MyArray(I).Key & " " & MyArray(I).Value
Next I
Print

HeapSort WholeArray(MyArray), @MyUDT_LessComp

For I As Integer = 0 To UBound(MyArray)
    Print MyArray(I).Key & " " & MyArray(I).Value
Next I
Print

Dim Nums(20) As Byte

Print "Input Nums Array"
For I As Integer = 0 To UBound(Nums)
    Nums(I) = Int(Rnd * 90) + 10
    Print Nums(I);
Next I
Print
Print

HeapSortNumericWhole(Nums, Descending)

Print "Descending Nums Array"
For I As Integer = 0 To UBound(Nums)
    Print Nums(I);
Next I
Print
Print

HeapSortNumericSub(Nums, 1, UBound(Nums) - 2, Ascending)

Print "Ascending Nums Sub Array"
For I As Integer = 0 To UBound(Nums)
    Print Nums(I);
Next I
Print
Print

Dim pNum As Single Ptr = CAllocate(10, SizeOf(Single))

Print "Manually allocated Array"
For I As Integer = 0 To 9
    pNum[I] = Int(Rnd * 50) / 10
    Print pNum[I];
Next I
Print
Print

HeapSortNumericElement(pNum[0], 10, Ascending)

Print "Sorted manually allocated Array"
For I As Integer = 0 To 9
    Print pNum[I];
Next I

DeAllocate(pNum) 'Remember to free memory

Sleep

'This prints a warning when compiled:
'HeapSortNumericWhole(MyArray, Ascending)


[Juergen Kuehlwein]

A very first version is here for testing.

This first commit includes as a first feature "array(info, ...)" for retrieving values from the array descriptor. The added /bin directory contains the compiled 32 bit and 64 bit executable for fbc and the RTL modules for 32 bit (i cannot compile the RTL for 64 bit currently) for those, who don´t want to compile it themselves. "Array.bi" is the necessary include file, and "array_test.bas" is code for testing, what is currently implemented.

Please note, this is work in progress and things still may change, some other things (array(sort, ...)) only work halfway.

As always, comments, critics, bug reports and ideas for improvement are welcome!


JK

[fxm]

Please correct my initial mistake:

Code: Select all

Type arrayDimensionDescriptor
  Dim As Uinteger nbOfElements  ' number of elements: (highBound-lowBound+1)
  ' Dim As Uinteger lowBound      ' lbound
  Dim As Integer lowBound       ' lbound
  ' Dim As Uinteger highBound     ' ubound
  Dim As Integer highBound      ' ubound
End Type


(changing the data-type of the two fields 'lowBound' and 'highBound' from Uinteger to Integer because they may have negative values)

[Juergen Kuehlwein]

Next version is here for testing.

This commit includes all executables (compiler + RTL 32 and 64 bit) and shows a possible front end (array syntax). See array.bi and test files for more.

As always, comments, critics, bug reports and ideas for improvement are welcome!

JK

[Juergen Kuehlwein]

Next version is here for testing.

I moved all the new stuff (Windows executables, array.bi, test files) into the "new" folder (maybe a better choice than "bin").

This version can detect fixed size arrays and is compatible with old code and binaries. According to my tests old binaries accept the new descriptor without problems. Obviously the new compiler version cannot detect fixed size arrays created by old binaries, but this is what we have right now anyway. I couldn´t find any other incompatibilities.

As always, comments, critics, bug reports and ideas for improvement are welcome!

JK

[Juergen Kuehlwein]

I think, i finally finished my front end. The latest version (0.5.0.5) has all necessary compiler pp changes, future changes should only be adding RTL functions for array processing. Updated (Windows) binaries are in the "New" folder, as well as "array.bi and some test files.

The syntax is as follows:

Code: Select all

'***********************************************************************************************
' array(sort, array)
' array(sort, array, down [, (i1 [, i2 [, ...]]) | pos(i), [, count]])
' array(sort, (array, nocase))
' array(sort, (array1, array2, nocase) [, (i1 [, i2 [, ...]]) | pos(i), [, count]])
' array(sort, (array, nocase), down [, (i1 [, i2 [, ...]]) | pos(i), [, count]])
' array(sort, array, @customsortproc [, (i1 [, i2 [, ...]]) | pos(i), [, count]])
'***********************************************************************************************
' array(insert, array, value [, (i1 [, i2 [, ...]]) | pos(i), [, count]])
'***********************************************************************************************
' array(delete, array [, (i1 [, i2 [, ...]]) | pos(i), [, count]])
'***********************************************************************************************
' u = array(scan, array, for()[, (i1 [, i2 [, ...]]) | pos(i), [, count]]), returns array_index
' for(searchterm [,nocase [,from])
' for(searchterm [,from])
' for(@customproc)
'***********************************************************************************************
' i = array(info, array, specifier), returns requested value as integer
'***********************************************************************************************
' i = array(calc, array, pos, (i1 [, i2 [,...]])) returns linear (one based) position from (array_)index
' p = array(calc, array, ptr, (i1 [, i2 [,...]])) returns memory ptr for this index
' u = array(calc, array, index, pos)              returns array_index from linear position
' u = array(calc, array, index, ptr)              returns array_index from memory ptr
'***********************************************************************************************
' array(attach, array, redim(1 to 5[, 1 to 6 [1,  ...]]), memory ptr)
' array(reset, array)
'***********************************************************************************************


The next step will be to make all of this actually work, array(info, ...) is already functional. Adding more features is possible, but for a start i want to get these working.


JK

[Lost Zergling]

@JK. The new version of Lzle seems to meet much more success than Lzae, and it is not because of not having promoted it or not having put some technicality or functional openings. It's a simple observation. It's a bit disappointing because it was a big part of the thinking and the work, but on the other hand this work will have allowed me to better detect gaps and improve some important features on list engine. Obviously, the theme of arrays actually does not meet a large audience for the moment, despite efforts. Perhaps over time, examples and more refined versions, I don't know. Or perhaps some important point I missed. I will be able to use these array features, but not right away. I shall wish you better success on your side.

[Juergen Kuehlwein]

Made some features work now. Most recent is array sort. As usual you find it here. Next will be array attach/reset and array scan.


JK

[coderJeff]

This looks like that changes are stacking up. This will go better for everyone if the changes are small and incremental.

I only glanced at the code and noticed that you are adding:
- signal handlers and magic numbers getting the the array descriptor info
- new parser keyword REDEF and operators #?#, #?, ###, etc.
- various rtlib changes
- some bug fixes

I'm not sure what you expect from fb team when you eventually create the pull request and we must consider the code for integration. If you find a bug that needs to be fixed, and you can fix it, then create a new branch and just fix that bug. If you think compiler needs a new feature to support your array interface, then create a new branch and write just that new feature.

[Juergen Kuehlwein]

Added Array Attach/Reset - code is here as usual.


@Jeff,

all of this somehow depends on each other, so before making one or more pull requests, i must be sure that all of this actually works together and doesn´t break existing code. This is still work in progress and i had to change many things in between, i initially thought were finished. It´s not a straight line of development from commit to commit, there are dead ends and deviations too.

I made a separate pull request for a bug fix.

When i´m ready, i will break it into manageable and logically related pieces. I hope it will become clear then, why and what for the changes are. There won´t be any magic numbers anymore too.


JK

[coderJeff]

JK, yes please, break it down in to managble chunks. You have creative ways of solving your challenges. It all might be related to your array feature, but I can see several components that could be solved independantly of each other. Thanks. Maybe have a look at basic-macro branch which is a branch created by v1ctor that I keep rebasing on to current master. It may give you some new ideas on how to deal with templates (#macro code generators).

So i made it possible. Now TYPEOF() additionally can return the type of a variable in uppercase letters in regular code too. This solves one of my key problems so far. I hope this doesn´t raise parsing abiguities for the compiler or other problems elsewhere. As far as i could test it, it seems to be safe. It was quite easy, so i´m a bit astonished it hasn´t been done before, maybe nobody thought, it could be useful.

Doing this makes compile-time information available at run-time, which might be useful for something like variants (run-time), though storing the data type as a string is not really all that efficient so we would probably look to have some kind of mapping between an integer type and the represented data type. Regardless, should not be needed for generics (compile-time), or in the case of fbc, pseudo-generics, using #macros as templates and code generators. fbc is pretty good at optimizing out constant expressions, though, so depending on usage maybe doesn't matter that an inefficient string representation of the data type is created at compile time. If it must be stored for later use during run-time seems like a bad design.

So, I look at where it's actually being used: and the only place I see is in arrray.bi at #elseif (TypeOf((data)) < "FUNCTION)") and (TypeOf((data)) > "FUNCTION'") which looks to me a bit of ASCII hackery to know that data is a function ptr.

And this is just one thing that you've added to support the "New array features". So yeah, we will be looking at all the individual pieces to see how they fit in to fbc. They will need to be documented and maintained for years to come.

[coderJeff]

though storing the data type as a string is not really all that efficient so we would probably look to have some kind of mapping between an integer type and the represented data type.

Old VB had the vartype(variable) function that returned an integer. Which is basically what array.bi:a_ext__get_typeof__ () is doing. This is an example of something that could be developed completely separately from the new array features, and would have general purpose usage. Readily available is the "dtype" of a symbol in the compiler. I don't know how useful the raw value from the compiler would be, but it contains a lot of information packed in to one integer type. Data type, pointer level, const bits, byref, etc.