List type and arrays

[jj2007]

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?

[Josep Roca]

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.

[paul doe]

It's more a question of convenience. Java has something called an arrayList object, that's implemented internally with arrays:

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()

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.

[paul doe]

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.

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).

[jj2007]

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.

Thanks. So things like ArraySort() are not (yet) native. What would Scan do? Look for the first occurence of a value etc?

[Josep Roca]

> What would Scan do? Look for the first occurence of a value etc?

Yes. You can name it Find or whatever you prefer.

[jj2007]

Thanks, Josep. Just found it here at PB: ARRAY SCAN statement

[MrSwiss]

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.

Based on what has been posted, by paul doe:
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.

[dodicat]

insert/remove for a general array.
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

 

[jj2007]

Which we all, would be *paying* for, with speed decreases, if it was part, of the Base-Lauguage.

You mean if Insert or Delete were built into the language, they would be slower? Why that?

[fxm]

insert/remove for a general array.
memcpy can be used, but for simplicity:

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.

[MrSwiss]

You mean if Insert or Delete were built into the language, they would be slower? Why that?

Why do you not stick, with the whole post?
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)

[jj2007]

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.

To be tested, but swapping pointers could be faster than assigning them.

That's what was meant, not your "details": ListType (as a whole implementation!)

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?

> (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.

[MrSwiss]

So why would their be a decrease in performance if the ListType (as a whole implementation!) would be built into the Base-Lauguage?

As with all additions to the Language:

• 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"

IMHO far better: only link it, if you really need it. (link = include)

[dodicat]

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.