B4J Question Get next free key in Map

[Blueforcer]

I generate a map whose keys consist of numbers.
Since the user can delete individual keys and later add a new object, I want to find out which number is the next free key.

So if the map looks like this:

0=Object 0
1=Object 1
3=Object 3
4=Object 4

My function should return the value 2 as a free key.
My attempts didn't go as planned until now. Therefore I contact the community. maybe someone can help me.

thanks

 

[LucaMs]

If your map is not too big, you can use, of course, a simple For-Next loop;

For i = 0 to MyMap.Size - 1
    If Not(MyMap.ContainsKey(i)) Then
        MyMap.Put(i, Something) ' or: NextKey = i : Exit, if you define NextKey somewhere before
        Exit
    End If
Next

 

[Roycefer]

I think there's at least two ways to go about this.

1. Keep a List of deleted keys, adding to the list as keys are deleted and removing them from the List as the keys are reused. Sort the List (ascending) to the get the smallest available key.
2. Run a for-loop from 0 to Map.Size-1 calling Map.ContainsKey and use the first one that returns False as your next key.

I recommend option 1. It will scale better.

 

[LucaMs]

Keep a List of deleted keys, adding to the list as keys are deleted and removing them from the List as the keys are reused. Sort the List (ascending) to the get the smallest available key.

A class to do it. NOTE: not tested enough !!!
[Also, there are mCallback and mEvenName not used just because you can use them if you wanted to add events]

 

[Blueforcer]

I think this wont work in my case,
Because i saving my map to a file every change, and if the user restart the app the mDeletedKeys will be empty.
i tried the first solution and this work.
There will be max 10 items in this map
note you have to count do map.size not -1

Sub getFreeID As Int
    For i = 0 To deviceMap.Size
        If Not(deviceMap.ContainsKey(Main.obj2Str(i))) Then
            Return(i)
            Exit
        End If
    Next
End Sub

 

[LucaMs]

Because i saving my map to a file every change, and if the user restart the app the mDeletedKeys will be empty.

save also mDeletedKeys

 

[LucaMs]

The main question is: which is the quickest method?

A For-Next loop is "slow", but if you have to use a sorted list... maybe the For-Next becomes the quickest method.

 

[LucaMs]

note you have to count do map.size not -1

Are you sure?

0=Object 0
1=Object 1
3=Object 3
4=Object 4

 

[LucaMs]

And many many thanks.

 

[Blueforcer]

Yeah because if the map is:

0=Object 0
1=Object 1

you wont count to 2, so you need to count one step more. and because you will never ask for the key(2) of the map (wich not exists) there will be no error. If the freeIndey is found i will exit the loop. so no problem

i still testing different situations now. and it always worked so far.
I think this is the best and easiest solution, since there are alway max 10 items in the map.
Thanks everybody for your help

 

[Daestrum]

... 
 Log("next key to use = "&nextKey(m))
End Sub
Sub nextKey(theMap As Map) As Object
 Dim lastKey As Int = 0   ' key type Int first key = 0
 For Each k As Object In theMap.keys
  If k<>lastKey Then Exit
  lastKey = lastKey + 1
 Next
 Return lastKey
End Sub

 

[ilan]

i would do it like this:

Sub Process_Globals
    Private fx As JFX
    Private MainForm As Form
    Dim map1 As Map
End Sub

Sub AppStart (Form1 As Form, Args() As String)
    MainForm = Form1
    MainForm.Show
   
    map1.Initialize
    map1.Put(0,"object0")
    map1.Put(1,"object1")
    map1.Put(3,"object3")
    map1.Put(4,"object4")
   
    Log("Next free key is: " & getNextFreeKey)
End Sub

Sub getNextFreeKey As Int
    For i = 0 To 1000
        Dim obj As Object = map1.Get(i)
        If obj = Null Then Return i
    Next
    Return -1
End Sub

logs:

Waiting for debugger to connect...
Program started.
Next free key is: 2

 

[stevel05]

IF you have a know number of items and sequential int keys, it sounds to me like an array would be better. Something like:

'Initialize
Dim A(10) As Object
For i = 0 To 9
        A(i) = Null
    Next


'Load Data
    For i = 0 To 9
        A(i) = True
    Next

    'Remove object at index 2
    A(2) = Null

Then to find the next key:

For i = 0 To A.Length - 1
            If A(i) <> Null Then Continue
            NextKey = i
            Exit
        Next