Kleinster Wert in einem Set

[Amateurprofi]

Mal zwei Fragen zu Sets.
Ich habe deklariert

Delphi-Quellcode:

type
   TDirection=(drLeft,drRight,drUp,drDown);
   TDirections=Set of TDirection;

var 
   directions:TDirections;

Ich möchte wissen
1) Wieviel Werte stehen gerade in directions.
2) Welches ist der kleinste Wert, der gerade in directions enthalten ist.

(1) könnte man durch zählen der Bits in direction herausfinden.
(2) löse ich zur Zeit so

Delphi-Quellcode:

var dr:TDirection;
    smallestdr:TDirection;
begin
smallestdr:=[];
for dr in directions do begin
   smallestdr:=dr;
   break;
end

;

Weiß jemand eine elegantere Lösung ?

[Shaman]

Hey there

Hier zwei allgemeine Lösungen:

Delphi-Quellcode:

function ElemCount(const ASet; const Size: Cardinal): Byte;
var
  X, I: Integer;
begin
  Result:= 0;
  X:= Cardinal(ASet);
  for I:= 0 to Pred(Size shl 3) do
  begin
    if Odd(X) then Inc(Result);
    X:= X shr 1;
  end;
end;

function SmallestElem(const ASet; const Size: Cardinal; out Elem): Boolean;
var
  X, I: Integer;
begin
  Result:= False;
  X:= Cardinal(ASet);
  for I:= 0 to Pred(Size shl 3) do
  begin
    if Odd(X) then
    begin
      Byte(Elem):= I;
      Result:= True;
      Exit;
    end;
    X:= X shr 1;
  end;
end;

Gruss
Shaman

[Hawkeye219]

Hallo.

In der Funktion SmallestElem fehlt das Schieben von X nach rechts innerhalb der Schleife.

Beide Funktion funktionieren nicht für alle Mengen, da ein Set je nach Umfang zwischen 1 und 32 Bytes im Speicher belegt. Der TypeCast in einen Cardinal-Wert ist also nur für die Mengen korrekt, die genau 4 Bytes belegen.

Die sauberste (und von der internen Darstellung der Mengen unabhängige) Lösung dürfte wohl mit einer Schleife arbeiten und mit dem Operator IN die einzelnen Elemente prüfen.

Gruß Hawkeye

[Shaman]

hey there

Zitat von Hawkeye219:

In der Funktion SmallestElem fehlt das Schieben von X nach rechts innerhalb der Schleife.

Ups

Zitat von Hawkeye219:

Beide Funktion funktionieren nicht für alle Mengen, da ein Set je nach Umfang zwischen 1 und 32 Bytes im Speicher belegt. Der TypeCast in einen Cardinal-Wert ist also nur für die Mengen korrekt, die genau 4 Bytes belegen.

Ich war wohl müde... auch korrigiert. Der Cast in der ersten Funktion ist ok, da ich einfach einen ordinalen Typ benötige, in der Schleife aber die tatsächliche Grösse berücksichtig wird.

Zitat von Hawkeye219:

Die sauberste (und von der internen Darstellung der Mengen unabhängige) Lösung dürfte wohl mit einer Schleife arbeiten und mit dem Operator IN die einzelnen Elemente prüfen.

Das stimmt, aber diese Lösung ist nicht vom Settyp unabhängig, und das wollte ich mit meiner erreichen.

Gruss
Shaman

[Hawkeye219]

Hallo Shaman,

habe ich beim ersten Mal die fehlende Initialisierung der Variablen X in der zweiten Funktion übersehen, oder ist sie der Überarbeitung zum Opfer gefallen?

Nach wie vor schiebst du in beiden Routinen einen 32-Bit-Wert nach rechts, Mengen mit mehr als 32 Elementen werden also nicht vollständig verarbeitet. Eine Lösung mit dem Assemblerbefehl BT wäre denkbar, letzten Endes würdest du aber immer nur versuchen, dir Laufzeitroutine von Delphi nachzuprogrammieren.

Gruß Hawkeye

[Shaman]

Zitat von Hawkeye219:

habe ich beim ersten Mal die fehlende Initialisierung der Variablen X in der zweiten Funktion übersehen, oder ist sie der Überarbeitung zum Opfer gefallen?

Sie ist...

Okee, die beiden Funktionen sind nur für Mengen mit nicht mehr als 32 Elementen geeignet. Sollte für den Normalgebrauch auch reichen, für grössere Mengen wird man eh TBits verwenden.

Gruss
Shaman

[generic]

helfen euch die funktionen low() high() ord() nicht?

Delphi-Quellcode:

type
   TDirection = (drLeft, drRight, drUp, drDown);
   TDirections = Set of TDirection;

procedure TForm1.Button1Click(Sender: TObject);
var
  i: integer;
  anzahl, lowwert: integer;

  a: TDirections;

  // kann leider nicht leer sein, also ist immer noch eine prüfung auf
  // lowwert>-1 notwendig!
  lowordwert: TDirection;
begin
  a:=[drRight,drDown];
  anzahl:=0;
  lowwert:=-1;

  for i:=ord(low(TDirection)) to ord(high(TDirection)) do
  begin
    if TDirection(i) in a then
    begin
      //wert gefunden
      inc(anzahl);
 
      // niedrigsten wert merken
      if (lowwert=-1) then
      begin
        lowwert:=i;
        lowordwert:=TDirection(i);
      end;
    end;
  end;
  caption:=format('%d %d', [anzahl, lowwert]);
end;

[Hawkeye219]

Hallo generic,

die Funktionen helfen in diesem Fall nicht:

• sie sind nur auf Mengentypen anwendbar, nicht auf Mengenvariablen.
• Low und High liefern den ersten bzw. letzten möglichen Wert der Menge, Klaus wollte aber den kleinsten enthaltenen Wert ermitteln.

Gruß Hawkeye

[marabu]

Hallo.

Klaus hat für seinen Anwendungsfall schon eine sehr elegante Lösung, die allerdings so nicht auf ältere Versionen von Object Pascal übertragen werden kann. Eine allgemeingültige Lösung für die Suche nach dem "kleinsten" member könnte so aussehen:

Delphi-Quellcode:

function MinMember(const ASet; const ASize: Byte): Integer;
type
  TByteArray = array [0..31] of Byte;
  PByteArray = ^TByteArray;
var
  iByte, iBit, iOrd: Integer;
  pba: PByteArray;
  b: Byte;
begin
  pba := @ASet;
  iOrd := 0;
  for iByte := 0 downto Pred(ASize) do
    if pba[iByte] = 0 then Inc(iOrd, 8) else
    begin
      b := pba[iByte];
      while not Odd(b) do
      begin
        Inc(iOrd);
        b := b shr 1;
      end;
    end;
  if iOrd < ASize shl 3
    then Result := iOrd
    else Result := -1;
end;

Da hierbei auf Delphi-Implementierungsdetails zurückgegriffen wird, ist das aber nicht sehr professionell. Das darf Borland machen, aber wir nicht. Selbst Schuld, wer es doch tut.

Grüße vom marabu

[generic]

ich habe ein codebeispiel in meinen post oben angefügt.

Hawkeye219 man kann doch nicht immer gleich die lösung verraten.

btw. zu den anderen codebeispielen. habt ihr alle zuviel c++ und c gemacht?
das konnte sogar das std. pascal von 1970.