List type and arrays

General FreeBASIC programming questions.
jj2007
Posts: 1111
Joined: Oct 23, 2016 15:28
Location: Roma, Italia
Contact:

List type and arrays

Postby jj2007 » Dec 17, 2017 10:43

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
Posts: 414
Joined: Sep 27, 2016 18:20
Location: Valencia, Spain

Re: List type and arrays

Postby Josep Roca » Dec 17, 2017 11:39

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
Posts: 885
Joined: Jul 25, 2017 17:22
Location: Argentina

Re: List type and arrays

Postby paul doe » Dec 17, 2017 11:43

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.
Last edited by paul doe on Dec 17, 2017 11:59, edited 1 time in total.
paul doe
Posts: 885
Joined: Jul 25, 2017 17:22
Location: Argentina

Re: List type and arrays

Postby paul doe » Dec 17, 2017 11:50

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.

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
Posts: 1111
Joined: Oct 23, 2016 15:28
Location: Roma, Italia
Contact:

Re: List type and arrays

Postby jj2007 » Dec 17, 2017 12:00

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.

Thanks. So things like ArraySort() are not (yet) native. What would Scan do? Look for the first occurence of a value etc?
Josep Roca
Posts: 414
Joined: Sep 27, 2016 18:20
Location: Valencia, Spain

Re: List type and arrays

Postby Josep Roca » Dec 17, 2017 12:15

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

Yes. You can name it Find or whatever you prefer.
jj2007
Posts: 1111
Joined: Oct 23, 2016 15:28
Location: Roma, Italia
Contact:

Re: List type and arrays

Postby jj2007 » Dec 17, 2017 12:23

Thanks, Josep. Just found it here at PB: ARRAY SCAN statement
MrSwiss
Posts: 2995
Joined: Jun 02, 2013 9:27
Location: Switzerland

Re: List type and arrays

Postby MrSwiss » Dec 17, 2017 14:02

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.
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
Posts: 5655
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: List type and arrays

Postby dodicat » Dec 17, 2017 14:15

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

 
Last edited by dodicat on Dec 17, 2017 16:52, edited 1 time in total.
jj2007
Posts: 1111
Joined: Oct 23, 2016 15:28
Location: Roma, Italia
Contact:

Re: List type and arrays

Postby jj2007 » Dec 17, 2017 14:22

MrSwiss wrote: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
Posts: 8801
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: List type and arrays

Postby fxm » Dec 17, 2017 15:43

dodicat wrote: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
Posts: 2995
Joined: Jun 02, 2013 9:27
Location: Switzerland

Re: List type and arrays

Postby MrSwiss » Dec 17, 2017 15:46

jj2007 wrote: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
Posts: 1111
Joined: Oct 23, 2016 15:28
Location: Roma, Italia
Contact:

Re: List type and arrays

Postby jj2007 » Dec 17, 2017 16:19

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.

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

MrSwiss wrote: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
Posts: 2995
Joined: Jun 02, 2013 9:27
Location: Switzerland

Re: List type and arrays

Postby MrSwiss » Dec 17, 2017 16:32

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?
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
Posts: 5655
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: List type and arrays

Postby dodicat » Dec 17, 2017 16:51

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.

Return to “General”

Who is online

Users browsing this forum: No registered users and 3 guests