InsertElement() and DeleteElement()

[RichardL]

It would be very useful to be able to insert an element into an array at a specified position, all higher items being moved up. The top element goes into the byte bucket:

InsertElement( ArrayName.l(15) = 100)

and the matching DeleteElement() which pulls all higher elements down, placing a NULL element at the top.

DeleteElement(ArrayName.l(100))

What would be really excellent would be for this to work with StructuredArray(), even if InsertElement() just put a NULL value in each of the corresponding elements.

Any views anyone?

RichardL

[Trond]

Excellent idea, but people will complain that it's slow. And how do you plan to handle multi-dimensional arrays?

[Kaeru Gaman]

for Arrays you have to code such things on your own.
there are no functions to handle Arrays at all.

HowTo:

Code: Select all

#ArrayMax = 99

Dim test.l(#ArrayMax)
For n=0 To 99 : test(n) = n : Next   ; fill

;*** Debug complete Array
For n=0 To 9
  out$ = ""
  For t=0 To 9
    CO = t + 10 * n
    out$ + RSet(Str(CO),2) + " > " + RSet(Str(test(CO)),2) + "    "
  Next
  Debug out$
Next
Debug "------------------"

InsertPos = 64
InsertValue = 42

;*** Insert Array Element
For ArrayCount = #ArrayMax To InsertPos Step -1
  test(ArrayCount) = test(ArrayCount-1)
Next
test(InsertPos) = InsertValue
;***

;*** Debug complete Array
For n=0 To 9
  out$ = ""
  For t=0 To 9
    CO = t + 10 * n
    out$ + RSet(Str(CO),2) + " | " + RSet(Str(test(CO)),2) + "    "
  Next
  Debug out$
Next

speed test:

Code: Select all

#ArrayMax = 999999
DisableDebugger

Dim test.l(#ArrayMax)
timer = ElapsedMilliseconds()
For n=0 To 99 : test(n) = n : Next   ; fill
timer = ElapsedMilliseconds() - timer

MessageRequester("Report 1","Time to Fill 4MB Array : "+Str(timer)+"ms")

InsertPos = 1
InsertValue = 42

;*** Insert Array Element
timer = ElapsedMilliseconds()
For ArrayCount = #ArrayMax To InsertPos Step -1
  test(ArrayCount) = test(ArrayCount-1)
Next
test(InsertPos) = InsertValue
timer = ElapsedMilliseconds() - timer
;***

MessageRequester("Report 2","Time to shift 4MB Array : "+Str(timer)+"ms")

note that is an really easy little loop, so I doubt it qould make much sense to write a Proc for it.

as Trond already mentioned,
with multidimensional arrays would be the question how to handle it,
shift all elements one up or insert a complete new line.
wich solution to chose would depend really specifically on the given problem.
so, the Procedure would not handle this accurately,
you'll need one additional Proc for multidimensional.

for structured elements just more complicated,
you'll need another additional Procedure that takes the size of the elements into account.

PS:
note that for deleting you need to count the loop in the other direction:

Code: Select all

For ArrayCount = DeletePos To #ArrayMax 
  test(ArrayCount) = test(ArrayCount+1)
Next

[Demivec]

Here's code that's faster:

Code: Select all

;*** Insert Array Element
CopyMemory(test()+InsertPos*SizeOf(Long),test()+(InsertPos+1)*SizeOf(Long),(#ArrayMax-InsertPos)*SizeOf(Long))
test(InsertPos) = InsertValue


;*** Delete Array Element
CopyMemory(test()+(DeletePos+1)*SizeOf(Long),test()+DeletetPos*SizeOf(Long),(#ArrayMax-DeletePos)*SizeOf(Long))
test(#ArrayMax) = 0

You would change the "SizeOf(Long)" to the size for the element type you are using. This would work with structured types too (you will have to customize the assignment of the new element, or null though). This does not address what the desired effect would be in a multidimensional array.

It's so simple, there's definately no need for a new command. Try it in Kaeru's time test.

[Joakim Christiansen]

It's so simple, there's definately no need for a new command.

Yes, if you know how to do it then it is. But this language is mostly for people who is new to programming and then commands like these should be included I think.

[RichardL]

Hi,

First, I must admit that my interest is primarily in single dimensioned arrays... I'm re-working some code that was written with GFA basic, which had both commands.

Both functions would easy to code with the knowledge the PB developers have regarding how their application works; including the structured array version.

Yes, using a loop to insert an element by moving all the higher ones up etc.... is not a problem and the same process works with strings and numbers. However, strings would be slow. Delete is much the same, but moving the other way.

If I remember correctly you can get the address of the array of pointers that define the string locations with *p=@ArrayName()

You can 'move' all the strings above an element by just moving the pointers with a simple memory move function. This is very quick; I might even risk saying that it could not be done faster

Deleting is a little risky... where do you point the top pointer to?

I made both of these work with PB3.94, but because it depends on PB remaing the same internally I did not want to risk going any further.

Recently I used a structured array with 11 items defined in the structure and wrote a very neat application, being able to SORT on my choice of element was great, but the nastiest bit in te whole app was inserting and deleting elements.

[Kaeru Gaman]

well, in my opinion handling such things with Arrays is basicmost knowledge with Arrays.

Arrays are made to handle Mem a bit more conveniant and not need to rely on pointers.

the way my loop is made is a simple logical question:

how can I scroll elements?
- I replace one element with another, one index up or below.

how have I to count the loop?
- in the direction that enables me to not overwrite all elements with the same.


perhaps it would be a good idea to write some basic tutorials about such things,
but I don't think it would be a good idea to add hundreds of new commands for beginners that are dead slow.

[edit]
@RichardL

well ok, so you are surely no beginner at all

sure it would be not the big problem to create such a command.
I just doubt it would be fast enough if it has to check what kind of array it is and how big the elements are.

[RichardL]

Joakim,

I would argue that PB is a language for those new to programming... in my case its well over twenty years. New?

Many years ago I made language extension plug-in ROMS for Commodore PET computers. Once I had the source files for the language it was easy to make new versions and I must admit it kept the family finances going for some time; as did the 6502 editor/assembler I wrote first.

Primarily I want reliable, fast and elegent code, with a reliable and efficient development environment. Pure BASIC and jaPBe offer this.

[Kaeru Gaman]

as did the 6502 editor/assembler I wrote first.

hey cool. I learned Assembler on the C64.

[RichardL]

Kaeru,

The core of most functions like this is a simple loop that runs between start and end points... or a block move that can be carried out with a single assembler instruction.

Most of the work goes into calculating the limits; but it only has to be done once.

[Demivec]

@RichardL: I admit I did overlook the effects of having strings in the Array. The code I gave above, using a block move, would only have to be changed slightly to be effective if the Array contained any strings.

Code: Select all

#ArrayMax=99
Dim test.s(#ArrayMax)
;Do initialization here.

; Insert Element for array of strings
tempElement=AllocateMemory(SizeOf(String))
If tempElement = 0:MessageRequester("Error","No memory for array function"):EndIf
test(#ArrayMax)="" ;erase element that will be placed in byte bucket
CopyMemory(test()+#ArrayMax*SizeOf(String),tempElement,SizeOf(String)) ;copy element going into bucket
CopyMemory(test()+InsertPos*SizeOf(String),test()+(InsertPos+1)*SizeOf(String),(#ArrayMax-InsertPos)*SizeOf(String))
CopyMemory(tempElement,test()+InsertPos*SizeOf(String),SizeOf(String)) ;copy element from bucket to maintain string pointers
test(InsertPos) = InsertValue ;set new values
FreeMemory(newElement)

; Delete Element for array of strings
DeletePos=64
tempElement=AllocateMemory(SizeOf(String))
If tempElement = 0:MessageRequester("Error","No memory for array function"):EndIf
test(DeletePos)="" ;erase element being deleted
CopyMemory(test()+DeletePos*SizeOf(String),tempElement,SizeOf(String)) ;copy element being deleted
CopyMemory(test()+(DeletePos+1)*SizeOf(String),test()+DeletePos*SizeOf(String),(#ArrayMax-DeletePos)*SizeOf(String))
CopyMemory(tempElement,test()+#ArrayMax*SizeOf(String),SizeOf(String)) ;copy deleted element to new position at end of array to maintain string pointers
FreeMemory(tempElement) 

You could make it slightly easier by leaving the memory for the tempElement copy always allocated (do it right after the Dim). If the element was structured you would have to set each of the strings to an Null string before deleting, or to their new value after insertion. This handles the string pointers by merely moving them and not destroying them. This method does not zero the other non-string elements. That is a simple case though.

Note, you can obtain the address of an array by either @array() or simply array(). These both return the same value.

[RichardL]

Work in progress... but it shows the merit of moving pointers instead of moving data.
I will sort the bugs next time round

Code: Select all

Procedure ElementInsert(*PointerArray,ArrayDim.l,Size.l,Insertpos.l)
  tempElement     = AllocateMemory(Size.l) 
  If tempElement  = 0 : MessageRequester("Error","No memory for array function") : EndIf 
  CopyMemory(*PointerArray+ ArrayDim * Size.l, tempElement, Size.l) 
  CopyMemory(*PointerArray+ Insertpos * Size.l, *PointerArray+(Insertpos+1) * Size.l,(ArrayDim-Insertpos) * Size) 
  CopyMemory(tempElement,*PointerArray + Insertpos * Size, Size)  
  FreeMemory(tempElement)
EndProcedure

Procedure ElementDelete(*PointerArray,ArrayDim.l,Size.l,DeletePos.l)
  tempElement = AllocateMemory(Size) 
  If tempElement = 0 : MessageRequester("Error","No memory for array function") : EndIf 
  CopyMemory(*PointerArray+ DeletePos * Size.l,tempElement, Size) 
  CopyMemory(*PointerArray+(DeletePos+1) * Size.l,*PointerArray+DeletePos * Size,(ArrayDim-DeletePos) * Size) 
  CopyMemory(tempElement,*PointerArray + ArrayDim * Size, Size)  
  FreeMemory(tempElement)
EndProcedure

#ArrayMax = 999999 
InsertValue.s = "fred" 
Insertpos = 64 

;================== BASIC METHOD ===================================
; Make test array and fill it
Dim test.s(#ArrayMax) 
For n=0 To #ArrayMax:  test.s(n) = "Some typical test data " + Str(n)  : Next



timer = ElapsedMilliseconds() 
For cycle = 1 To 100
  For ArrayCount = #ArrayMax To Insertpos Step -1 
    test(ArrayCount) = test(ArrayCount-1) 
  Next 
  test(Insertpos) = InsertValue.s
Next
timer = ElapsedMilliseconds() - timer 
MessageRequester("Report","100  x Basic method: "+Str(timer)+"ms")

; =============== BLOCK MOVE POINTERS ===================================
; Make array and fill it
Dim test2.s(#ArrayMax) 
For n = 0 To #ArrayMax : test2.s(n) = "Some typical test data " + Str(n): Next

; INSERT
; ======
timer = ElapsedMilliseconds()
For cycle = 1 To 100
  test2(#ArrayMax) = ""                                
  ElementInsert(@test2(),#ArrayMax,SizeOf(String),Insertpos)
  test2(1) = InsertValue.s  
Next
timer = ElapsedMilliseconds() - timer 
MessageRequester("Report","100 x Pointer move:"+Str(timer)+"ms")

; =======================================================================

[blueznl]

Hey, another former GfaBasic user, and with 6502 backgrounds as well... (I've started with a Vic20, then continued on the Atari 400/800/XL range.)

[Demivec]

Here's a small change that would slim up things a little for the pointers:

Code: Select all

Timer = ElapsedMilliseconds()
For cycle = 1 To 100
  test2(#ArrayMax) = InsertValue.s
  ElementInsert(@test2(),#ArrayMax,SizeOf(String),Insertpos)
Next
Timer = ElapsedMilliseconds() - Timer
MessageRequester("Report","100 x Pointer move:"+Str(Timer)+"ms")

This is how it would look for ElementDelete:

Code: Select all

; DELETE
; ======
For cycle = 1 To 100
  test2(Deletepos) = "" ;this will be the new null element                       
  ElementDelete(@test2(),#ArrayMax,SizeOf(String),Deletepos)
Next