Die nächstkleinste freie Zahl in einer Liste finden

[NicTheQuick]

Hab mir den Code nicht genau angeschaut, aber ich glaube Nic's Code macht genau das, dem Kommentar unter dem Code nach zu urteilen.

So sieht's aus.

[DrShrek]

Hab mir den Code nicht genau angeschaut, aber ich glaube Nic's Code macht genau das, dem Kommentar unter dem Code nach zu urteilen.

Shit. Wusste doch das ich da was vergessen hatte. Kein Kommentare und damit macht meine Idee natürlich nicht das was Derren erwartet. *grins*

[Derren]

Was is?

Deine Idee hat doch rein gar nichts mit meiner/Nics zu tun.

Da gibt's nix zu "erwarten". Dein Post war Clip und Klar. Warum sollte ich da irgendwas kommentieren?

[Bisonte]

Ok... Der Code von Nic funktioniert, nur so wirklich begriffen hab ich das ganze noch nicht.

@Nic: Könntest du vielleicht Kommentare in dein Beispiel packen, was da so im einzelnen passiert ?
Das würde mir evt. beim Verständnis etwas auf die Sprünge helfen ...

Edit:

Da ich das noch nicht blicke... wie kann ich denn nun eine ID hinzufügen ?

Sagen wir, der User schreibt : OpenWindow(2, .... dann muss ich die 2 doch irgendwie in die Liste kriegen, auch wenn da noch nichts
drinsteht. (Oder selbst wenn die 2 schon besetzt ist!)

Wenn er danach OpenWindow(#PB_Any,... schreibt, soll natürlich 0 als erste freie ID rauskommen... Wie realisiere ich das jetzt ?

[matbal]

Sinn und Zweck der Übung ist es eine Art Objektverwaltung wie PB zu realisieren. Also wenn ein Objekt mit
#PB_Any erstellt wird, eine freie Nummer zu bekommen. Es wird also laufend etwas hinzugefügt und entfernt. deswegen auch am besten
immer die kleinste Nummer.... Heisst natürlich aber auch, das da keine doppelten Nummern existieren dürfen.

Ich verstehe gerade nicht den Sinn dahinter, für die dynamischen Objekte unbedingt kleine ID Nummern zu vergeben. Man arbeitet bei dynamischen Objekten doch sowieso nicht mit den Nummern direkt, da man die nicht kennt, sondern mit Variablen, die die Nummern enthalten. Und da ist die Größe der Nummer irrelevant.

Würde es nicht genügen, einfach die Speicheradresse des Objekts als ID zu benutzen? Die ist immer eindeutig.

[NicTheQuick]

Dann ist das wieder viel komplizierter zu machen, wenn es auch noch schnell sein soll.
Dann würde ich lieber vorschlagen es so zu machen wie es PB auch macht. Bei '#PB_Any' werden nämlich keine freien IDs zurück gegeben, sondern einfach Stellen im Speicher. Also im Grunde gibt es für PB zwei ID-Listen. Ein statisches Array, was die selbst festgelegten IDs verwaltet und maximal bis 10000 Einträge geht. Und eine Liste für die dynamisch erzeugten IDs, die man mit '#PB_Any' bekommt.
Falls du es aber doch gerne so haben willst, wie du es die ganze Zeit beschreibst, dann wird es wie gesagt komplizierter. Daran kann ich mich aber auch gerne versuchen.

//Edit: Hat matbal eigentlich auch gerade so vorgeschlagen.

[Bisonte]

Das klingt ja schon irgendwie interessanter

Ich habe eigentlich vor, eine FTP Lib zu machen.
Da natürlich mehrere Verbindungen möglich sein sollen, sollen diese auch getrennt ansprechbar sein.

Ich wollte das natürlich PB konform machen, will sagen, mit ID's und der #PB_Any Methode. Nur fällt mir da nicht
wirklich eine Lösung zu ein.

PB hat das OpenFTP(#FTP... da haben wir dann also das Objekt. Mal kann man es mit einer direkten Nummer nehmen, mal aber auch mit
#PB_Any.

Ich werde mich mit dem Statischen Array und der 2. Liste für SpeicherObjekte auseinandersetzen. Vielleicht krieg ich da ja was gebacken ...

Aber Du kannst gerne was zaubern ... hab ich (und wohl der Rest des Forums) nichts dagegen

[CSHW89]

Falls du es doch so machen willst: ich hab irgendwann mal das gleiche Problem gehabt, und dafür im Internet ne, wie ich finde, sehr schöne Lösung gefunden. Allerdings arbeitet die Funktion mit Arrays nicht mit Listen. Außerdem müssen die Zahlen alle größer 0 sein.

Der Code ist in C++, ich hab gerade kein PureBasic parat. Falls es Probleme gibt, kann ichs auch später übersetzen:

Code: Alles auswählen

/* Find the smallest positive missing number in an array that contains
 * all positive integers
 */
int findMissingPositive(int arr[], int size)
{
    int i;
    
    // Mark arr[i] as visited by making arr[arr[i] - 1] negative. Note that
    // 1 is subtracted because index start from 0 and positive numbers start from 1
    for(i = 0; i < size; i++) {
        if (abs(arr[i]) - 1 < size && arr[abs(arr[i]) - 1] > 0) {
            arr[abs(arr[i]) - 1] = -arr[abs(arr[i]) - 1];
        }
    }
    
    // Return the first index value at which is positive
    for(i = 0; i < size; i++) {
        if (arr[i] > 0) {
            return i+1;  // 1 is added becuase indexes start from 0
        }
    }
    
    return size+1;
}

lg Kevin

[NicTheQuick]

Ich habe gerade mal die PB-Methode nachgebaut. Es funktioniert intern allerdings nur so ähnlich, da statt eines Arrays eine Map benutzt wird.

Code: Alles auswählen

DeclareModule IDAny
	Global NewMap *staticID()
	Global NewList *dynamicID()
	Declare.i newID(id.i = #PB_Any, *handle = -1)
	Declare.i freeID(id.i)
	Declare.i getHandle(id.i)
EndDeclareModule

Module IDAny
	Procedure.i newID(id.i = #PB_Any , *handle = -1)
		If (id = #PB_Any)
			If AddElement(*dynamicID())
				*dynamicID() = *handle
				ProcedureReturn @*dynamicID()
			Else
				ProcedureReturn #False
			EndIf
		ElseIf (id > 10000)
			Debug "Bitte keine statischen IDs über 10000 nutzen!"
			ProcedureReturn #False
		Else
			If (FindMapElement(*staticID(), Str(id)))
				*staticID() = *handle
			ElseIf (AddMapElement(*staticID(), Str(id), #PB_Map_NoElementCheck))
				*staticID() = *handle
			Else
				ProcedureReturn #False
			EndIf
			ProcedureReturn *handle
		EndIf
	EndProcedure
	
	Procedure.i freeID(id.i)
		If (id > 10000)
			;Geht davon aus, dass die id tatsächlich gültig ist.
			ChangeCurrentElement(*dynamicID(), id)
			DeleteElement(*dynamicID())
		ElseIf (id >= 0)
			DeleteMapElement(*staticID(), Str(id))
		EndIf
	EndProcedure
	
	Procedure getHandle(id.i)
		If (id > 10000)
			ProcedureReturn PeekI(id)
		ElseIf (id >= 0)
			ProcedureReturn *staticID(Str(id))
		EndIf
	EndProcedure
EndModule


Debug "IDAny"
UseModule IDAny

dynID1.i = newID(#PB_Any, 123)
dynID2.i = newID(#PB_Any, 456)
newID(0, 789)
newID(10, 999)

Debug "dynID1: " + dynID1
Debug "dynID2: " + dynID2
Debug "dynID1 handle: " + getHandle(dynID1)
Debug "dynID2 handle: " + getHandle(dynID2)
Debug "statID1 handle: " + getHandle(0)
Debug "statID2 handle: " + getHandle(10)

[DrShrek]

Code: Alles auswählen

Procedure NewMapId(Map id.s())
  Static key.s = ""
  Repeat 
    key = Str(ElapsedMilliseconds())
    result = FindMapElement(id(), key)
  Until Not(result)
  AddMapElement(id(), key)
EndProcedure





NewMap id.s()




For n = 1 To 20
  newMapId(id())
  Debug MapKey(id())
Next

Debug MapSize(id())