Mengenoperatoren - ein kleiner Kurs

[Dax]

Jeder Delphi-Benutzer wird in seinem Leben mindestens ein mal mit Mengen(Sets) konfrontiert. Da es für Sets auch noch andere Operatoren als in gibt und die OH zu den Mengenoperatoren fast nichts sagt, habe ich mich entschlossen, ein Tuturial über die Verwendung dieser Operatoren zu schreiben.

Punkt 1: Grundvorraussetzungen dieses Kurses

In diesem Kurs werden des öfteren Bezeichner wie X, Y, A, B, O und P fallen.
Um diese nicht bei jedem Schritt neu hinschreiben zu müssen, werden hier alle auf einmal vereinbart. Wenn es nicht anders geschrieben steht, werden wir diese Werte so benutzen, wie sie hier stehen.

Delphi-Quellcode:

A: set of Byte = [1, 3, 5, 7];
B: set of Byte = [2, 4, 6, 7];

X: set of Byte = [6];
Y: set of Byte = [7];

O: Byte = 4;
P: Byte = 7;

Punkt 2: Die Operatoren

Der Union-Operator +
Der Union-Operator ist der OR-Operator der Sets.
Er erwartet zwei Sets als Operanden und liefert ein Set als Ergebnis.
Form: Set1 + Set2: Set.
Der Opeartor ist Kommutativ, die Reihenfolge der Parameter ändert das Ergebnis nicht.
Dieser Operator liefert alle Elemente der beiden Operanden zurück, jedoch kommt kein Element im Ergebnis doppelt vor. Sollten beide Operanden leer sein, ist das Ergebnis auch leer ([]).
Demzufolge ist

Delphi-Quellcode:

X + Y = [6, 7];
A + B = [1..7];
A + Y = [1, 3, 5, 7];
B + Y = [2, 4, 6, 7];
A + X = [1, 3, 5..7];
B + X = [2, 4, 6, 7]

Der Differenzierungs-Operator -
Der Differenzierungsoperator ist das XOR der Sets.
Er erwartet zwei Sets als Operanden und liefert ein Set als Ergebnis.
Form: Set1 - Set2: Set.
Auch dieser Operator ist Antikommutativ.
Im Ergebnis dieses Operators sind nur Elemente enthalten, die nur der erste Operand enthält. Sind beide Operanden gleich, liefert der Operator das leere Set [] zurück.
Demzufolge ist

Delphi-Quellcode:

X - Y = [6, 7];
A - B = [1, 2, 3, 4, 5, 6];
A - Y = [1, 3, 5];
B - Y = [2, 4, 6];
A - X = [1, 3, 5, 7];
B - X = [2, 4, 7];

Der Intersektions-Operator *
Der Intersektionsoperator ist das AND der Sets.
Er erwartet zwei Sets als Operanden und liefert ein Set als Ergebnis.
Form: Set1 * Set2: Set.
Dieser Operator ist ebenfalls Kommutativ.
Im Ergebnis dieses Operators sind nur Elemente enthalten, die in beiden Operanden enthalten sind. Sollten die beiden Operanden kein gemeinsames Element haben, ist das Ergebnis leer ([]).
Demzufolge ist

Delphi-Quellcode:

X * Y = [];
A * B = [7];
A * Y = [7];
B * Y = [7];
A * X = [];
B * X = [6];

Der Untermengen(Subset)-Operator <=
Der Subset-Operator überprüft, ob ein Set komplett im anderen enthalten ist, und liefert ein Boolean-Ergebnis zurück.
Form: Set1 <= Set2: Boolean.
Dieser Operator ist Antikommutativ, also macht es einen Unterschied, wie die Parameter stehen.
Das Ergebnis ist true, wenn alle Elemente von Set1 in Set2 enthalten sind, ansonsten false.
Demzufolge ist

Delphi-Quellcode:

X <= Y = false;
A <= B = false;
A <= Y = false;
B <= Y = false;
A <= X = false;
B <= X = false;

Y <= X = false;
B <= A = false;
Y <= A = true;
Y <= B = false;
X <= A = false;
X <= B = true;

Der Übermengen(Superset)-Operator >=
Der Superset-Operator überprüft, ob ein Set ein anderes komplett enthält, und liefert ein Boolean-Ergebnis zurück.
Form: Set1 >= Set2: Boolean.
Dieser Operator ist auch Antikommutativ.
Das Ergebnis ist true, wenn Set1 alle Elemente von Set2 enthälz, ansonsten false.
Demzufolge ist

Delphi-Quellcode:

X >= Y = false;
A >= B = false;
A >= Y = true;
B >= Y = false;
A >= X = false;
B >= X = true;

Y >= X = false;
B >= A = false;
Y >= A = false;
Y >= B = false;
X >= A = false;
X >= B = false;

Der Vergleichsoperator =
Der Vergleichsoperator überpfrüft, ob zwei Sets keine unterschiedlichen Elemente enthalten, und liefert ein Boolean-Ergebnis zurück.
Form: Set1 = Set2: Boolean.
Das Ergebnis ist true, wenn die beiden Parameter gleich groß sind und die selben Elemente enthalten, ansonsten false.
Ich denke, Beispiele erübrigen sich hier.

Der Ungleichheitsoperator <>
Der Ungleichheitsoperator überpfrüft, ob zwei Sets nur unterschiedlichen Elemente enthalten, und liefert ein Boolean-Ergebnis zurück.
Form: Set1 <> Set2: Boolean.
Das Ergebnis ist true, wenn die beiden Parameter keine Gemeinsamen Elemente haben, ansonsten false.
Ich denke, Beispiele erübrigen sich hier.

Der in-Operator
Der in-Operator überprüft, ob ein Ordinaler Wert in einem Set enthalten ist, und liefert ein Boolean-Ergebnis.
Form: Ordinal in Set1: Boolean.
Der Ergebnis ist true, wenn Ordinal in Set1 enthalten ist, ansonsten false.
Beispiele:

Delphi-Quellcode:

O in A = false;
O in B = true;
P in A = true;
P in B = true;
5 in A = true;
5 in B = false;

Ende

Ich hoffe, hier sind die Mengenoperatoren ein wenig verständlicher erklärt worden als in der Delphi-OH, da steht ja fast gar nichts.

Edits: Tippfehler verbessert

[jfheins]

Zitat:

Der Differenzierungs-Operator -
Der Differenzierungsoperator ist das XOR der Sets.
Er erwartet zwei Sets als Operanden und liefert ein Set als Ergebnis.
Form: Set1 - Set2: Set.
Auch dieser Operator ist Kommutativ.
Im Ergebnis dieses Operators sind nur Elemente enthalten, die nur ein Operand enthält. Sind beide Operanden gleich, liefert der Operator das leere Set [] zurück.

Ich denke, man kann die Operanden nicht vertauschen, ohne dass sich das Ergebnis ändert.

In der OH steht:

O ist nur in X - Y enthalten, wenn O in X, nicht aber in Y enthalten ist.

Also mit

Delphi-Quellcode:

  A: set of Byte = [1, 3, 5, 7];
  B: set of Byte = [2, 4, 6, 7];

Dann so:

Delphi-Quellcode:

A - B = [1, 3, 5]
B - A = [2, 4, 6]

[1, 2, 3, 4, 5] - [1, 2, 3, 6, 7] = [4, 5]
[1, 2, 3, 6, 7] - [1, 2, 3, 4, 5] = [6, 7]

Korrigiert mich, wenn ich falsch liege ...

[Dax]

Die liegst falsch.

Zitat:

Zitat von jfheins

Zitat:

Zitat von In der OH steht

O ist nur in X - Y enthalten, wenn O in X, nicht aber in Y enthalten ist.

Du könntest X und Y genausogut vertauschen das Ergebnis wäre das selbe, denn der Differenzierungsoperator der Sets und XOR sind de facto das selbe. Es werden die Elemente geliefert, die nur eins der Sets enthält, die anderen werden ausgelassen, wie bei XOR.

[jfheins]

So. Jetzt reichts.
1. Neu > Anwendung
2. Button aufs Formular ziehen.
3. Auf den Button doppelklicken.
4. Folgenden Quellcode einfügen:

Delphi-Quellcode:

 if 6 in ([1, 2, 3, 4, 5] - [1, 2, 3, 6, 7]) then showmessage ('Dax liegt richtig und JFHeins lügt!')
 else showmessage ('JFHeins liegt richtig und Dax lügt!');

5. Meldung hier posten

Ich warte ...

[Dax]

:wall: Wird sofort verbessert

[xineohp]

moin,

Der - Operator ist einwandfrei NICHT kommutativ!

Beweis:

Delphi-Quellcode:

var a,b,c,d: set of byte;
begin
  a := [1,2,3];
  b := [3,4,5];

  c := a-b;    //  meine Erwartung: c=[1,2]
  d := b-a;    //  meine Erwartung: d=[4,5]

  If c=d then showmessage('gleich') else showmessage('ungleich');

  // Ergebnis: c ungleich d !!!
end;

A-B bildet die Differenzmenge von A und B und die ist logischerweise nicht das gleiche wie B-A, das würde ja die gesamte Mengenlehre der Mathematik über den Haufen werfen.

EDIT: zu langsam...

[yankee]

Mal kurz 'ne Frage:
Muss man immer set of verwenden, oder kann man sich dynamisch was erstellen? Also so:

Delphi-Quellcode:

var i1,i2,i3: integer;
i1 in [i2..i3]

[alcaeus]

Hi yankee,

Zitat:

Zitat von yankee

Mal kurz 'ne Frage:
Muss man immer set of verwenden, oder kann man sich dynamisch was erstellen? Also so:

Delphi-Quellcode:

var i1,i2,i3: integer;
i1 in [i2..i3]

Doch, solche Konstrukte funktionieren auch.

Greetz
alcaeus

[Taweluki]

Zitat:

Zitat von Dax

... der Differenzierungsoperator der Sets und XOR sind de facto das selbe. Es werden die Elemente geliefert, die nur eins der Sets enthält, die anderen werden ausgelassen, wie bei XOR.

Wie andere bereits zeigten, ist dem nicht so. Trotzdem, manchmal braucht man auch XOR für Mengen. Leider ist die Mengenunterstützung in Delphi/Object Pascal etwas dürftig ausgefallen (gilt zumindest bis einschließlich D7). So besitzt Delphi - im Gegensatz zu manch anderer Sprache - für die beiden folgenden Mengenoperationen keine eingebauten Operatoren. Wir können sie aber mit Hilfe der vorhandenen Operatoren nachbilden.

Symmetrischen Mengendifferenz
Die symmetrische Mengendifferenz ist das XOR der Sets.
Form: (Set1 - Set2) + (Set2 - Set1): Set
Alternativ: (Set1 + Set2) - (Set1 * Set2): Set
Das Ergebnis enthält all die Elemente, die zu Set1 oder Set2, jedoch nicht zu beiden gehören.

Delphi-Quellcode:

(X - Y) + (Y - X) = [6,7]
(A - B) + (B - A) = [1..6]
(A - Y) + (Y - A) = [1,3,5]
(B - Y) + (Y - B) = [2,4,6]
(A - X) + (X - A) = [1,3,5,6,7]
(B - X) + (X - B) = [2,4,7]

Eine typische Anwendung ist z.B. die Folgende:

Delphi-Quellcode:

type
  TMyOption = (opt1, opt2, opt3, opt4, opt5);
  TMyOptions = set of TMyOption;

  TMyClass = class(TWinControl)
  ...

procedure TMyClass.SetOptions(const Value: TMyOptions);
var
  ChangedOptions: TMyOptions;
const
  NeedRecreate = [opt1, opt3];
  NeedRepaint  = [opt4];
begin
  ChangedOptions := (Value - FOptions) + (FOptions - Value);
  if ChangedOptions <> [] then
  begin
    FOptions := Value;
    if HandleAllocated then 
// bitte, liebe Komponentenersteller: diese Abfrage nie vergessen! Wer nicht weiß, was ich
// meine, der leite mal eine Komponente von TRichEdit ab, die nichts anderes tut, als einen 
// neuen Vorgabewert für die Hintergrundfarbe zu implementieren. Bringt zumindest bis zur 
// ungepatchten D7 echt Laune. ;-)
      if (NeedRecreate * ChangedOptions) <> [] then
        RecreateWnd
      else if (NeedRepaint * ChangedOptions) <> [] then
        Repaint;
  end;
end;

Komplementärmengen
Das NOT der Sets. Wieder besitzt Delphi keinen eigenen Operator, denn der Mengendifferenz-Operator "-" ist - anders als der normale Differenzoperator - nicht unär. Zum Nachbilden benötigen wir eine Hilfskonstante, die Menge aller möglichen Elemente:

Delphi-Quellcode:

const AllElements{: Mengentyp} = [minElement..maxElement];

Leider benötigen wir derartige Konstanten für jeden einzelnen Mengentyp.
Form: AllElements - Set1: Set
Das Ergebnis enthält alle Elemente des Basistyps, die nicht in Set1 enthalten sind.

Delphi-Quellcode:

AllElements: set of Byte = [1..7] // erscheint sinnvoll für die gegebenen A, B, X und Y 
AllElements - X = [1..5,7]
AllElements - Y = [1..6]
AllElements - A = [2,4,6]
AllElements - B = [1,3,5]

Nur mal so am Rande: Das Beispiel für das Mengen-XOR kommt nicht von ungefähr. Vielleicht kennt jemand von euch ja die VirtualShellTools (eine Erweiterung der open source VirtualTree Komponenten). Schaut euch mal die Set..Options Prozeduren im Quelltext von VirtualExplorerTree an. Da war jemand am Werk, der mit Mengenoperatoren deutlich auf Kriegsfuß steht (im Gegensatz zu den VirtualTree Programmierern, die haben das vorbildlich gelöst). Ist aber nur ein kleiner Schönheitsfehler, die Komponenten sind ansonsten ziemlich genial. Zeigt aber, dass ein Kurs wie dieser sinnvoll ist.

Mengen sind für viele Programmierer (insbesondere solche, die C(++/#) gewöhnt sind) ungewohntes Terrain. Dabei kann man mit ihnen vieles deutlich eleganter als mit bitweisen Operatoren lösen.

Delphi-Quellcode:

function ShowOptions(options: TMyOptions): string;
var
  opt: TMyOptions;
  optVal: Integer;
begin
  Result := '';
  for opt := opt1 to opt5 do
    if opt in options then
      Result := Result + IfThen(Result='','',',') + IntToStr(Ord(opt));
  Result := '[' + Result + ']';
end;

finde ich einfach schöner als

Delphi-Quellcode:

function ShowOptions(options: TMyOptions): string;
var
  opt: TMyOptions;
  optVal: Integer; // 2 hoch opt
begin
  Result := '';
  optVal := 1;
  for opt := opt1 to opt5 do
  begin
    if (Byte(options) and optVal) <> 0 then
      Result := Result + IfThen(Result='','',',') + IntToStr(Ord(opt));
    optVal := optVal shl 1; // verdoppeln, bitwise-style
  end;
  Result := '[' + Result + ']';
end;

Mit anderen Worten: Pascal-Sets liegen eine Abstraktionsebene höher als die bitweisen Operatoren. Der Programmierer kann mit einfachen (und daher weniger fehleranfälligen) Aufzählungstypen und Mengenoperatoren arbeiten und das systemnahe Hantieren mit Zweierpotenzen (man sehe sich mal die Werte vieler Windows-Konstanten an - 1,2,4,8,...) getrost dem Compiler überlassen.

[mimi]

ich habe ein problem was ich schon auf
http://www.delphi-forum.de/viewtopic.php?t=40163
gepostet habe dort ist auch eine beispiel anwendung welches das problem beschreibt