List type and arrays
List type and arrays
Just stumbled over a post by Lost Zergling where he urges that "list support is a very important feature".
I open a new thread because the FreeBASIC Discussion December 2017 thread clearly has a different intention. But I am curious: Since I have never used the list type in the last 30 years, what have I missed?
Wikipedia has an entry, and from what I have understood the most common case of a "list" is what I have called so far an array, and for what I always used the Dim keyword:
Dim x$()
Dim MyInt() As DWORD
Dim MyDoubles() As REAL8
Dim MyRectangles() As RECT
etc
There are usually commands to Insert or Delete array elements. Rumours say that linked lists are more efficient at this than arrays, measurements often say the contrary. Sorting is yet another story.
So my question really is: what makes the list type different from ordinary arrays, what are its advantages in real life applications?
I open a new thread because the FreeBASIC Discussion December 2017 thread clearly has a different intention. But I am curious: Since I have never used the list type in the last 30 years, what have I missed?
Wikipedia has an entry, and from what I have understood the most common case of a "list" is what I have called so far an array, and for what I always used the Dim keyword:
Dim x$()
Dim MyInt() As DWORD
Dim MyDoubles() As REAL8
Dim MyRectangles() As RECT
etc
There are usually commands to Insert or Delete array elements. Rumours say that linked lists are more efficient at this than arrays, measurements often say the contrary. Sorting is yet another story.
So my question really is: what makes the list type different from ordinary arrays, what are its advantages in real life applications?
-
- Posts: 564
- Joined: Sep 27, 2016 18:20
- Location: Valencia, Spain
Re: List type and arrays
They are arrays with some additional methods. All we will need to have "lists" with FB would be to do like PowerBasic and implement natively some intrinsic functions, such Delete, Insert, Scan and Sort, that work with all kind of arrays.
We can do it ourselves, but because FB does not support templates, we would need to have procedures or classes for each kind of data type.
We can do it ourselves, but because FB does not support templates, we would need to have procedures or classes for each kind of data type.
Re: List type and arrays
It's more a question of convenience. Java has something called an arrayList object, that's implemented internally with arrays:
I use it a lot in some of my code, as they are more comfortable to use than a nude array, and if you like the OOP paradigm, they are essentially equivalent. There's also the benefit that's an object, so you can toss it around with a pointer if you need to pass them to other objects/functions.
Code: Select all
#include once "crt.bi" '' needed for memcpy
#ifdef class
#undef class
#define class type
#endif
#define max( a, b ) iif( a > b, a, b )
#define min( a, b ) iif( a < b, a, b )
/'
simple java-like ArrayList class
responsibility: represents a collection of objects, accessed and indexed
as an array
mutability: immutable
note that these classes aren't meant to do garbage collection,
merely to conveniently index and traverse a collection of objects
also the classes aren't optimized, as they are meant to be
used as a reference implementation (there's almost no error handling)
'/
class ArrayList extends object 'inherits ICollection
'' public interface
public:
declare constructor()
declare function get( byval index as uinteger ) as any ptr
declare function count() as uinteger
declare sub add( byval e as any ptr )
declare sub insert( byval e as any ptr, byval before as uinteger )
declare function remove( byval index as uinteger ) as any ptr
declare function remove( byval item as any ptr ) as any ptr
declare function removeLast() as any ptr
declare function removeFirst() as any ptr
'' state members
protected:
as any ptr m_element( any )
as uinteger m_count = any
/'
convenience macro for brevity
this macro resizes the m_element array by v elements, either positive or negative
if v is positive, the array expands
if v is negative, the array shrinks
the code uses +1 and -1 for further clarify the meaning of the expression
'/
#macro resizeElements( v )
m_count += v :
redim preserve m_element( 0 to m_count - 1 )
#endmacro
end class
constructor ArrayList()
m_count = 0
end constructor
function ArrayList.count() as uinteger
return( m_count )
end function
function ArrayList.get( byval index as uinteger ) as any ptr
/'
gets the element of the list indicated by index
note that there is no error checking on this one, for this can
mask out of bound errors
if the list tries to access an item out of bounds, the application deserves to
fail miserably
'/
return( m_element( index ) )
end function
sub ArrayList.add( byval e as any ptr )
resizeElements( +1 )
m_element( m_count - 1 ) = e
end sub
sub ArrayList.insert( byval e as any ptr, byval before as uinteger )
'' don't allow insertion out of bounds
before = min( m_count, max( 0, before ) )
'' trivial case, inserting at the end of the list
if( before = m_count - 1 ) then
resizeElements( +1 )
m_element( m_count - 1 ) = m_element( m_count - 2 )
m_element( m_count - 2 ) = e
else
resizeElements( +1 )
'' calculate number of elements to move
dim as uinteger elem = m_count - 1 - before
'' and move them to make space for the inserted item
memcpy( @m_element( before + 1 ), @m_element( before ), elem * sizeOf( any ptr ) )
m_element( before ) = e
end if
end sub
function ArrayList.remove( byval item as any ptr ) as any ptr
'' removes an item from the list by pointer
dim as any ptr ret = 0
dim as integer elem = -1 '' assume not found
'' search it (inefficiently)
for i as uinteger = 0 to m_count - 1
if( item = m_element( i ) ) then
'' found it
elem = i
exit for
end if
next
'' if found, return it, else return nothing
if( elem <> -1 ) then
return( remove( elem ) )
else
return( 0 )
end if
end function
function ArrayList.remove( byval index as uinteger ) as any ptr
'' removes an item from the list by index
'' don't allow removal out of bounds
index = min( m_count - 1, max( 0, index ) )
dim as any ptr ret = m_element( index )
if( index = m_count - 1 ) then
'' trivial removal, the last item
resizeElements( -1 )
return( ret )
end if
'' only 2 elements to remove remaining
if( ( index = 0 ) andAlso ( m_count < 3 ) ) then
m_element( 0 ) = m_element( 1 )
resizeElements( -1 )
return( ret )
end if
'' general case (elements > 2)
'' number of elements to move
dim as uinteger elem = m_count - 1 - index
'' move the rest of the elements
memcpy( @m_element( index ), @m_element( index + 1 ), elem * sizeOf( any ptr ) )
resizeElements( -1 )
return( ret )
end function
function ArrayList.removeLast() as any ptr
'' convenience function for removing the last element of the list
dim as any ptr ret = m_element( m_count - 1 )
resizeElements( -1 )
return( ret )
end function
function ArrayList.removeFirst() as any ptr
'' convenience function for removing the first element of the list
dim as any ptr ret = m_element( 0 )
'' there's only one element remaining
if( m_count = 1 ) then
m_count -= 1
redim m_element( 0 )
return( ret )
end if
'' there's 2 elements remaining
if( m_count = 2 ) then
m_element( 0 ) = m_element( 1 )
resizeElements( -1 )
return( ret )
end if
'' general case
'' calculate number of elements to move
dim as uinteger elem = m_count - 1
'' move the remaining elements to their new position
memcpy( @m_element( 0 ), @m_element( 1 ), elem * sizeOf( any ptr ) )
'' and resize the member array
resizeElements( -1 )
return( ret )
end function
'' some code for unit testing
class test extends object
public:
as integer value = any
declare constructor()
declare constructor( byval v as integer )
declare destructor()
end class
constructor test()
value = 0
end constructor
constructor test( byval v as integer )
value = v
end constructor
destructor test()
print "Destructor "; value; " called."
end destructor
dim as ArrayList al
dim as test ptr t
dim as integer numElements = 10
dim as any ptr what
for i as integer = 1 to numElements
dim as test ptr t = new test( i )
al.add( t )
if( i = 5 ) then
what = t
end if
next
al.insert( new test( 343 ), al.count - 2 )
t = al.remove( 8798 )
delete t
t = al.removeLast()
delete t
t = al.remove( what )
delete t
'' show the elements
for i as integer = 0 to al.count - 1
t = al.get( i )
print t->value
next
'' delete all elements
do while( al.count > 0 )
t = al.removeFirst
delete( t )
t = 0
loop
'' this code should never be executed if everything went ok
for i as integer = 0 to al.count - 1
t = al.get( i )
print t->value
next
sleep()
Last edited by paul doe on Dec 17, 2017 11:59, edited 1 time in total.
Re: List type and arrays
Unfortunately, yes. But depending on what paradigm one favors (OOP/Procedural) this may or may not be an issue. If (like me) you favor the OOP paradigm, you simply wrap the class with the datatype you want (the flexible way). Or, you can do some sort of crude 'templating' using macros (the efficient way).Josep Roca wrote:We can do it ourselves, but because FB does not support templates, we would need to have procedures or classes for each kind of data type.
Re: List type and arrays
Thanks. So things like ArraySort() are not (yet) native. What would Scan do? Look for the first occurence of a value etc?Josep Roca wrote:They are arrays with some additional methods. All we will need to have "lists" with FB would be to do like PowerBasic and implement natively some intrinsic functions, such Delete, Insert, Scan and Sort, that work with all kind of arrays.
-
- Posts: 564
- Joined: Sep 27, 2016 18:20
- Location: Valencia, Spain
Re: List type and arrays
> What would Scan do? Look for the first occurence of a value etc?
Yes. You can name it Find or whatever you prefer.
Yes. You can name it Find or whatever you prefer.
Re: List type and arrays
Thanks, Josep. Just found it here at PB: ARRAY SCAN statement
Re: List type and arrays
Based on what has been posted, by paul doe:Josep Roca wrote:We can do it ourselves, but because FB does not support templates, we would need to have procedures or classes for each kind of data type.
I don't really *see* a problem, because:
everybody (having a need for a ListType) is able, to write a class library (in native FB) him-/herself ...
Thus, extending the Language, without cluttering up, the Base-Language.
Which we all, would be *paying* for, with speed decreases, if it was part, of the Base-Lauguage.
Re: List type and arrays
insert/remove for a general array.
memcpy can be used, but for simplicity:
memcpy can be used, but for simplicity:
Code: Select all
#macro arrayinsert(a,index,insert)
If index>=Lbound(a) And index<=Ubound(a)+1 Then
Var index2=index-Lbound(a)
Redim Preserve a(Lbound(a) To Ubound(a)+1)
For x As Integer= Ubound(a) To Lbound(a)+index2+1 Step -1
a(x)=a(x-1)
Next x
a(Lbound(a)+index2)=insert
End If
#endmacro
#macro arraydelete(a,index)
If index>=Lbound(a) And index<=Ubound(a) Then
For x As Integer=index To Ubound(a)-1
a(x)=a(x+1)
Next x
Redim Preserve a(Lbound(a) To Ubound(a)-1)
End If
#endmacro
#macro printarray(b)
for n as long=lbound(b) to ubound(b)
print b(n);
next
print
#endmacro
'===========
dim as string a(...)={"F","r","e","e","B","A","S","I","C"}
redim as string b(lbound(a) to ubound(a))
for n as long=lbound(a) to ubound(a)
b(n)=a(n)
next n
printarray(b)
dim as string p="Power"
for n as long=0 to len(p)-1
arraydelete(b,(n))
arrayinsert(b,(n),chr(p[n]))
printarray(b)
next
arrayinsert(b,5,"B")
printarray (b)
sleep
Last edited by dodicat on Dec 17, 2017 16:52, edited 1 time in total.
Re: List type and arrays
You mean if Insert or Delete were built into the language, they would be slower? Why that?MrSwiss wrote:Which we all, would be *paying* for, with speed decreases, if it was part, of the Base-Lauguage.
Re: List type and arrays
Inside the 'arrayinsert()' macro, 'a(x)=a(x-1)' can be used instead of 'Swap a(x),a(x-1)' for simplicity, as you used inside the 'arraydelete()' macro.dodicat wrote:insert/remove for a general array.
memcpy can be used, but for simplicity:
Re: List type and arrays
Why do you not stick, with the whole post?jj2007 wrote:You mean if Insert or Delete were built into the language, they would be slower? Why that?
That's what was meant, not your "details": ListType (as a whole implementation!)
Covering all possible Data-Types ...
(Btw: Delete is already a FB keyword)
Re: List type and arrays
To be tested, but swapping pointers could be faster than assigning them.fxm wrote:Inside the 'arrayinsert()' macro, 'a(x)=a(x-1)' can be used instead of 'Swap a(x),a(x-1)' for simplicity, as you used inside the 'arraydelete()' macro.
I'm so sorry for the misunderstanding. So why would their be a decrease in performance if the ListType (as a whole implementation!) would be built into the Base-Lauguage?MrSwiss wrote:That's what was meant, not your "details": ListType (as a whole implementation!)
> (Btw: Delete is already a FB keyword)
From the manual: The array version of Delete, Delete[], is used to destroy an array of objects
Now everything is clear, thank you.
Re: List type and arrays
As with all additions to the Language:jj2007 wrote:So why would their be a decrease in performance if the ListType (as a whole implementation!) would be built into the Base-Lauguage?
- 1) larger executables (especially unwanted, for libraries: .a, .dll/.so)
2) more complexity in compiler (=> longer compile time)
3) therefore, more chances for "bugs" (nobody, wants that)
4) chances that FBC becomes "bloatware"
Re: List type and arrays
Thanks fxm
It is very old code.
I just copied and pasted without looking.
In my more up to date macros I don't use swap.
It is very old code.
I just copied and pasted without looking.
In my more up to date macros I don't use swap.