Daten auf Einzigartigkeit überprüfen...

[Uwe Raabe]

Es war gestern schon zu spät für ausführliche Erläuterungen, aber nun:

Das Problem mit der sortierten Stringliste ist, daß bei jedem Add die Inizes umsortiert werden können. Daher kann man den von Add zurückgegebenen Index auch nur bis zum nächsten Add gebrauchen.

Statt nur einfach einen String zu der Liste hinzuzufügen, geben ich diesem noch einen Referenzwert, den Index in der Originalliste, mit. Zu diesem Zweck missbrauche ich das Objects-Property der Stringliste, das eigentlich ein TObject hält, aber durch Typecasting auch Integer verkraftet. Der Vorteil der Objects ist, daß sie beim Umsortieren mitgeführt werden.

Bei dupIgnore wird ein bereits vorhandener String bei einem Add nicht in die Liste aufgenommen, insbesondere wird bei AddObject auch das zugehörige Objects-Property nicht geändert. Der nachfolgende Abruf liefert also für den gleichen String auch immer den gleichen Referenzwert zurück. Diesen speichere ich im Index-Array.

Nachdem alle Strings zugefügt wurden, stehen im Index-Array nun allerdings die Werte des jeweiligen Objects-Property des zugehörigen Strings und nicht wie gewünscht der Index in der optimierten Liste. Um dieses Manko zu beheben baue ich einen temporären inversen Index auf, der mir für jeden Referenzwert den zugehörigen Index in slopt liefert. Das geht recht schnell, da hierzu lediglich die slopt durchlaufen werden muss.

Mit diesem temporären Index übersetze ich dann die Einträge des Index-Array in die korrekten Werte.

Übrigens: lineare Laufzeit ist das auch nicht, aber O(n*log n) sollte es schon sein.