Objekte sortieren mit TArray<T>.BinarySearch

[Zacherl]

Hallo zusammen,

ich habe eine Liste von Objekten und möchte diese per TArray<T>.BinarySearch in eine absolute Ordnung bringen und dabei sämtliche Duplikate eliminieren. Soweit so gut ... hier ein Auszug aus meinem Code:

Delphi-Quellcode:

if (not TArray.BinarySearch<T>(FItems, V, J, Comparer, N, C - N)) then
begin
  for K := C downto J + 1 do
  begin
    FItems[K] := FItems[K - 1];
  end;
  FItems[J] := V;
  Inc(C);
end;

C ist hierbei die Anzahl der Items im Array und N ist ein Offset für den Fall, dass meine Liste ein paar vorwegstehende Default-Elemente besitzen soll (braucht in diesem Falle nicht zu interessieren). FItems wird am Anfang auf die gesamte Anzahl der Objekte festgelegt - hat also garantiert genug Platz.

Zum eigentlichen Problem: Für den Vergleich implementiere ich mir eine CompareTo Funktion, welche ich dann im Comparer aufrufe:

Delphi-Quellcode:

function TMyClass.CompareTo(Other: TMyClass): Integer;
var
  I: Integer;
begin
  Result := (Length(FFlags) + 1) * (Ord(FAccess) - Ord(Other.FAccess));
  for I := Low(FFlags) to High(FFlags) do
  begin
    Result := Result + (I + 1) * (Ord(FFlags[I]) - Ord(Other.FFlags[I]));
  end;
end;

FAccess ist hierbei ein Enum und FFlags ein array[0..N] of Enum .

Beobachtung: Nachdem ich von einem "normalen" EqualityComparer zum Eliminieren der Duplikate auf die Methode mit BinarySearch umgestellt habe und ins Git committen wollte, ist mir aufgefallen, dass 57 Zeilen entfernt, aber nur 53 hinzugefügt wurden (ein Objekt pro Zeile). Aus irgendeinem Grund fehlen mir demnach 4 Datensätze.

Ist meine Vorgehensweise - also über die Multiplikation eine Wertung herzustellen - so überhaupt korrekt?
Falls ja, gibt es da bessere Ansätze, die weniger anfällig für Integer Overflows sind?

Kann mir hier irgendjemand auf die Sprünge helfen?

Viele Grüße
Zacherl

[Uwe Raabe]

Zitat von Zacherl:

Ist meine Vorgehensweise - also über die Multiplikation eine Wertung herzustellen - so überhaupt korrekt?

Vermutlich nicht.

Nehmen wir statt Enums einfach Zahlen 0..9 und N = 1. A und B seien die beiden Flags-Arrays mit den Werten A=[0,2] und B=[1,0]. Die for-Schleife geht nun für I von 0 bis 1 und ermittelt:

result = 1*(0-2) + 2*(1-0) = -2 + 2 = 0

Der Comparer hält also die beiden Flag-Arrays für gleich.

[Zacherl]

Zitat von Uwe Raabe:

Zitat von Zacherl:

Ist meine Vorgehensweise - also über die Multiplikation eine Wertung herzustellen - so überhaupt korrekt?

Vermutlich nicht.
[...]
Der Comparer hält also die beiden Flag-Arrays für gleich.

Macht Sinn. Bloß wie könnte ich es korrekt machen?

Edit: Alle CompareTo Implementierungen, die ich gefunden habe, geben lediglich Werte im Bereich [-1, 0, 1] zurück. Habe mir nun einen Testcode gebastelt, der auch wunderbar funktioniert.

Delphi-Quellcode:

type
  TTest = record
    A, B, C: Integer;
  end;

const
  A: array[0..4] of TTest = (
    (A:0; B:4; C:5),
    (A:3; B:4; C:5),
    (A:1; B:4; C:5),
    (A:0; B:1; C:5),
    (A:0; B:5; C:5)
  );

var
  B: TArray<TTest>;
  I, J, C, K: Integer;
begin
  SetLength(B, Length(A));
  FillChar(B[0], SizeOf(B), #0);
  C := 0;
  for I := Low(A) to High(A) do
  begin
    if not TArray.BinarySearch<TTest>(B, A[I], J, TComparer<TTest>.Construct(
      function(const Left, Right: TTest): Integer
      begin
        if (Left.A < Right.A) then Exit(-1) else if (Left.A > Right.A) then Exit(1);
        if (Left.B < Right.B) then Exit(-1) else if (Left.B > Right.B) then Exit(1);
        if (Left.C < Right.C) then Exit(-1) else if (Left.C > Right.C) then Exit(1);
      end), 0, C) then
    begin
      for K := C downto J + 1 do
      begin
        B[K] := B[K - 1];
      end;
      B[J] := A[I];
      Inc(C);
    end;
  end;
end;

Wenn ich das aber im Grunde 1 zu 1 auf mein richtiges Problem übertrage, kommt wieder nur Murks raus

Delphi-Quellcode:

function TMyClass.CompareTo(Other: TMyClass): Integer;
var
  I: Integer;
begin
  Result := 0;
  if (Ord(FAccess) < Ord(Other.FAccess)) then Exit(-1) else
  if (Ord(FAccess) > Ord(Other.FAccess)) then Exit(1);
  for I := Low(FFlags) to High(FFlags) do
  begin
    if (Ord(FFlags[I]) < Ord(Other.FFlags[I])) then Exit(-1) else
    if (Ord(FFlags[I]) > Ord(Other.FFlags[I])) then Exit(1);
  end;
end;

Ich erhalte z.b.:

Code:

[3, 7, 3, 3, 1]
[3, 7, 2, 3, 1]
[3, 7, 3, 3, 5]

gewüscht wäre aber:

Code:

[3, 7, 2, 3, 1]
[3, 7, 3, 3, 1]
[3, 7, 3, 3, 5]

[Uwe Raabe]

Delphi-Quellcode:

  Result := CompareValue(Ord(FAccess, Ord(Other.FAccess)));
  if Result <> 0 then begin
    for I := Low(FFlags) to High(FFlags) do
    begin
      Result := CompareValue(Ord(FFlags[I]), Ord(Other.FFlags[I]));
      if Result <> 0 then Break;
    end;
  end;

[Zacherl]

Danke Uwe, so funktioniert es

Meine reineditierte Methode mit manueller Rückgabe von [-1, 0, 1] funktioniert tatsächlich auch. Ein weiteres Problem neben der Multiplikation aus dem ersten Post war nämlich, dass FAccess zwar zum Objekt gehört, ich dieses Feld allerdings gar nicht als Sortierkriterium aufnehmen darf, da es keine Auswirkung auf den generierten Datensatz hat. Dadurch sahen die Werte dann beim Sichten so zufällig aus