Remove items from array without changing the order

General FreeBASIC programming questions.
Tourist Trap
Posts: 2756
Joined: Jun 02, 2015 16:24

Remove items from array without changing the order

Postby Tourist Trap » May 01, 2019 16:49

Hello,

In general, I would remove items from an array by sending them at the upperbound, and then doing a downsizing (redim preserve in a downsize maneer). But what I'm thinking about, it's well known, sends the items from the upperbound to any places inside the array. This is not very bad, until we want to keep the array in its initial order.

First I have a preliminary question that I wanted to ask. Do we need to explicitely mention PRESERVE when we redim downsize without changing the lower bound at all?

Ok, this left aside, here are my naive implementation that solve the issue, but looks like an unefficent way. And then another example that moves blocs of data in a whole. But here it's not easy to me to find a generic form for doing this.

Code: Select all

'1
redim shared as integer arrayOfInteger(8)
for i as integer = 0 to 8
    arrayOfInteger(i) = i
next i

remove item at index 5 by the naive method
for i as integer = (5 + 1) to 8
    arrayOfInteger(i - 1) = arrayOfInteger (i)
next i
redim preserve arrayOfInteger (7)

?
for i as integer = 0 to 7
    ? arrayOfInteger(i)
next i

'(eof)


Code: Select all

'2
redim shared as integer arrayOfInteger(8)
for i as integer = 0 to 8
    arrayOfInteger(i) = i
next i

'remove item 5 on a single buffer move
#macro _BUFFERTYPESIZE(BufferTypeName, FieldtypeName, Sizevalue)
    type BufferTypeName
        as FieldtypeName array(1 to SizeValue)
    end type
#endMacro

_BUFFERTYPESIZE(_BTS, integer, (8 - 5))
dim as integer ptr   buffer1 => allocate(sizeOf(_BTS))
dim as integer ptr   buffer2 => allocate(sizeOf(_BTS))
? sizeOf(_BTS), sizeOf(integer ptr)
buffer1 = @arrayOfInteger(5)
buffer2 = @arrayOfInteger(6)
swap *cptr(_BTS ptr, buffer1), *cptr(_BTS ptr, buffer2)
redim preserve arrayOfInteger (7)
#undef _BTS
deallocate buffer1
deallocate buffer2

?
for i as integer = 0 to 7
    ? arrayOfInteger(i)
next i

'(eof)

The difficulty of the second version is here:
dim as integer ptr buffer1 => allocate(sizeOf(_BTS))
The _BTS type is just a container to set a proper buffer size. It's however not very practical.

To be more precise, it's here that I can't move a bloc of the right size if I don't have a UDT of the right size previously avaiable. Maybe I miss something very obvious, or I'm on the wrong way?
swap *cptr(_BTS ptr, buffer1), *cptr(_BTS ptr, buffer2) <--


If someone knows a better way, or how to improve the things, please share :)

Thanks all.
fxm
Posts: 8975
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: Remove items from array without changing the order

Postby fxm » May 01, 2019 18:14

- Memory allocation is useless.
- In your above code, there is memory leak because your memory deallocation fails (the pointers values from memory allocation have been modified before memory deallocation).

Proposal:

Code: Select all

_BUFFERTYPESIZE(_BTS, integer, (8 - 5))
*cptr(_BTS ptr, @arrayOfInteger(5)) = *cptr(_BTS ptr, @arrayOfInteger(6))
? sizeOf(_BTS), sizeOf(integer ptr)
redim preserve arrayOfInteger (7)
#undef _BTS
Last edited by fxm on May 01, 2019 18:25, edited 1 time in total.
Tourist Trap
Posts: 2756
Joined: Jun 02, 2015 16:24

Re: Remove items from array without changing the order

Postby Tourist Trap » May 01, 2019 18:23

fxm wrote:

Code: Select all

_BUFFERTYPESIZE(_BTS, integer, (8 - 5))
*cptr(_BTS ptr, @arrayOfInteger(5)) = *cptr(_BTS ptr, @arrayOfInteger(6))
redim preserve arrayOfInteger (7)
#undef _BTS

Hi, and thank you fxm for your quick help.

fxm wrote:- Memory allocation is useless.
- In your above code, there is memory leak because your memory deallocation fails (the pointers values from memory allocation have been modified before memory deallocation).

I didn't know that. Did this come from the use of SWAP? (by parenthesis, I used allocate before I introduced the UDT to set up the buffer size). Thanks for pointing out this anyway.
Or ok, I should have used REALLOCATE here?

Code: Select all

buffer1 = @arrayOfInteger(5)


Is there a way to get rid of the UDT created in a rather artificial way in this context. Would CPTR(typeOf(...)) something would do? I can't see any how so far. Any idea from your side?
dodicat
Posts: 5774
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: Remove items from array without changing the order

Postby dodicat » May 01, 2019 18:35

using memcpy

Code: Select all


#include "crt.bi"

#macro arrayinsert(a,index,b)
If index>=Lbound(a) And index<=Ubound(a)+1 Then
    Redim Preserve a(Lbound(a) To Ubound(a)+1)
    memcpy(@a(index)+1, @a(index), (Ubound(a)-index) * Sizeof(a(index)))
    Clear a(index), 0, Sizeof(a(index))
    a(index)=b
End If
#endmacro

#macro arraydelete(a,index)
If (index)>=Lbound(a) And (index)<=Ubound(a) Then
    memcpy(@a(index), @a(index)+1, (Ubound(a)-index) * Sizeof(a(index)))
    Clear a(Ubound(a)), 0, Sizeof(a(index))
    Redim Preserve a(Lbound(a) To Ubound(a)-1)
End If
#endmacro


redim shared as integer arrayOfInteger()
for i as integer = 0 to 100000
    arrayinsert(arrayOfInteger,i,i)
next i

for i as integer = lbound(arrayofinteger) to 12'ubound(arrayofinteger)
    print  arrayofinteger(i);
    next i
print

arraydelete(arrayofinteger,5)

for i as integer = lbound(arrayofinteger) to 12'ubound(arrayofinteger)
    print arrayofinteger(i);
next i

print
print
redim shared as string arrayOfstring()
for i as integer = 0 to 100000
    arrayinsert(arrayOfstring,i,str(i))
next i

for i as integer = lbound(arrayOfstring) to 12'ubound(arrayOfstring)
    write arrayOfstring(i),
    next i
print

arraydelete(arrayOfstring,5)

for i as integer = lbound(arrayOfstring) to 12'ubound(arrayOfstring)
    write arrayOfstring(i),
next i
print
sleep
 
fxm
Posts: 8975
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: Remove items from array without changing the order

Postby fxm » May 01, 2019 19:29

Adding to prevent a memory leak when 'a(index)' is overwritten:

Code: Select all

#macro arraydelete(a,index)
If (index)>=Lbound(a) And (index)<=Ubound(a) Then
    scope
        dim as typeof(a(index)) tt
        a(index) = tt
    end scope
    memcpy(@a(index), @a(index)+1, (Ubound(a)-index) * Sizeof(a(index)))
    Clear a(Ubound(a)), 0, Sizeof(a(index))
    Redim Preserve a(Lbound(a) To Ubound(a)-1)
End If
#endmacro
Tourist Trap
Posts: 2756
Joined: Jun 02, 2015 16:24

Re: Remove items from array without changing the order

Postby Tourist Trap » May 01, 2019 19:33

dodicat wrote:using memcpy

Thanks dodicat. For this issue, it seems that there will be no other workaround than memcopy really available to deal with this in a straightforward manner. Or we still miss it but right now I doubt.
dodicat
Posts: 5774
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: Remove items from array without changing the order

Postby dodicat » May 01, 2019 21:27

Sometimes the old looping ways just as good.
More like basic than C, and avoiding memory problems.
Using fb strings by this method feels safer anyway.

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
        Swap 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

redim shared as integer arrayOfInteger()
for i as integer = 0 to 100000
    arrayinsert(arrayOfInteger,i,i)
next i

for i as integer = lbound(arrayofinteger) to 12'ubound(arrayofinteger)
    print  arrayofinteger(i);
    next i
print

arraydelete(arrayofinteger,5)

for i as integer = lbound(arrayofinteger) to 12'ubound(arrayofinteger)
    print arrayofinteger(i);
next i

print
print
redim shared as string arrayOfstring()
for i as integer = 0 to 100000
    arrayinsert(arrayOfstring,i,str(i))
next i

for i as integer = lbound(arrayOfstring) to 12'ubound(arrayOfstring)
    write arrayOfstring(i),
    next i
print

arraydelete(arrayOfstring,5)

for i as integer = lbound(arrayOfstring) to 12'ubound(arrayOfstring)
    write arrayOfstring(i),
next i
print
sleep
 
Tourist Trap
Posts: 2756
Joined: Jun 02, 2015 16:24

Re: Remove items from array without changing the order

Postby Tourist Trap » May 02, 2019 3:17

dodicat wrote:Sometimes the old looping ways just as good.

Then so, I think we can elaborate on my 1st proposal. We would just need the chunk of data of the good size made available as soon as we declare the array. As far as we can be happy with chunks of fixed sizes, brought to the user in advance, and just in case. Maybe it's useful, after all, it should be faster to move data in a loop, 3 by 3, than 1 by 1.

Code: Select all

 #macro _ARRAYDECLAREONCEWITHCHUNKS(dimOrRedim, arrayVariableName, ArrayTypeName, Parenthesis)
    dimOrRedim as ArrayTypeName arrayVariableName##Parenthesis
    '
    'prepare some UDT to let us run through the array by blocs of size=3
    'can also use typeOf() to some extent
    #ifNdef CHUNKOF3_##ArrayTypeName
        type CHUNKOF3_##ArrayTypeName
            as ArrayTypeName    _arr(1 to 3)
        end type
    #endIf
    #ifNdef CHUNKOF3_typeOf
        #define CHUNKOF3_typeOf(arrayVariableName)  CHUNKOF3_##ArrayTypeName
    #endIf
#endMacro

_ARRAYDECLAREONCEWITHCHUNKS(dim, arr1, single, (1 to 100)={1})  ''test

'back to our example
_ARRAYDECLAREONCEWITHCHUNKS(redim shared, arrayOfInteger, integer, (8))

for i as integer = 0 to 8
    arrayOfInteger(i) = i
next i

*cptr(CHUNKOF3_typeOf(arrayOfInteger) ptr, @arrayOfInteger(5)) = *cptr(CHUNKOF3_typeOf(arrayOfInteger) ptr, @arrayOfInteger(6))
redim preserve arrayOfInteger (7)

?
for i as integer = 0 to 7
    ? arrayOfInteger(i)
next i

'(eof)

Return to “General”

Who is online

Users browsing this forum: No registered users and 2 guests