Die Menge ganzer Zahlen: Klasse IntegerSet

1. Aufgabe

Erstellen Sie eine Klasse IntegerSet, die eine Menge ganzer Zahlen mit zentralen Operationen wie das Einfügen oder Löschen von Elementen realisiert. In der Realisierung sind bzgl. der Ablage der Zahlen in einem IntegerSet-Objekt verschiedene Strategien möglich. Wenn Sie den Umgang mit C#-Arrays erlernen und vertiefen wollen, bietet sich ein einfaches int-Array an. Da C#-Arrays nach ihrer Allokation in ihrer Größe festgelegt sind, müssen Sie bei jeder Größenänderung eines IntegerSet-Objekts intern ein neues int-Array der passenden Größe allokieren und den Inhalt des alten Arrays in das Neue umkopieren. Dieser Realisierungsansatz ist sicherlich nicht der eleganteste, bietet sich aber für Einsteiger an, um die Grundlagen der Programmiersprache C# besser zu verstehen.

Der Realisierungsansatz auf Basis eines int-Arrays kann sogar optimiert werden, um die vielen Allokationen neuer int-Arrays zu reduzieren. So müssen Sie beispielsweise die Größe des int-Arrays nicht passgenau auf die Anzahl der Elemente in der Menge zuschneiden, sondern können diese beispielsweise in Vielfachen von 16, also 16, 32, 64, 128, usw. allokieren. Auf diese Weise müssen Sie in der Implementierung der (mengentheoretischen) Methoden der Klasse geringfügig mehr Aufwand spendieren, haben aber das Laufzeitverhalten von IntegerSet-Objekten erheblich verbessert.

All diese konzeptionellen Ideen, die in den zuvor beschriebenen Realisierungsansätzen skizziert wurden, finden Sie natürlich auch in bereits vorhandenen Utility-Klassen des .NET-Frameworks bereits realisiert vor. Sie dürfen Ihre Implementierung gerne auch auf dem Fundament eines List<>-Objekts angehen. Beachten Sie dabei: Listen dieses Typs sind streng typisiert, d.h., alle Methoden zum Einfügen oder Entfernen von Elementen erlauben in diesem Beispiel nur int-Werte – was in Bezug auf die Aufgabenstellung ja keinen Nachteil darstellt. Der C#-Compiler meldet bereits zur Übersetzungszeit Fehler, wenn Sie aktuelle Parameter falschen Typs verwenden.

Damit kommen wir auf die öffentliche Schnittstelle der IntegerSet-Klasse zu sprechen. Die Konstruktoren der Klasse haben wir in Tabelle 1 zusammengestellt:

Schnittstelle und Beschreibung

public IntegerSet ();

Der Standardkonstruktor legt eine leere Menge an.

public IntegerSet (int[] elements);

Durch den Parameter elements wird ein Array mit ganzen Zahlen übergeben. Vor der Aufnahme der Werte in das Mengenobjekt ist zu überprüfen, ob diese alle verschieden sind.

Tabelle 1. Konstruktoren der Klasse IntegerSet.


Die öffentlichen Methoden der Klasse IntegerSet finden Sie in Tabelle 2 vor:

Methode

Schnittstelle und Beschreibung

Contains

public bool Contains (int n);

Prüft das Vorhandensein eines Elements n in der Menge. Der Rückgabewert true bedeutet „Element ist in der Menge vorhanden“, false das Gegenteil.

Insert

public bool Insert (int n);

Fügt eine ganze Zahl n in die Menge ein. Ist die Zahl in der Menge bereits enthalten, liefert Insert den Wert false zurück, andernfalls true.

Remove

public bool Remove (int n);

Entfernt ein Element n aus der Menge. Ist die ganze Zahl in der Menge nicht enthalten, liefert Remove den Wert false zurück, andernfalls true.

Tabelle 2. Öffentliche Methoden der Klasse IntegerSet.


Die zwei Eigenschaften (Properties) Size und IsEmpty der Klasse IntegerSet sind in Tabelle 3 erläutert:

Eigenschaft

Schnittstelle und Beschreibung

Size

public int Size { get; };

Liefert die Anzahl der in der Menge enthaltenen Elemente zurück.

IsEmpty

public bool IsEmpty { get; };

Liefert bei einer leeren Menge true zurück, andernfalls false.

Tabelle 3. Öffentliche Eigenschaften (Properties) der Klasse IntegerSet.


Im Zusammenspiel mit dem .NET-Objektmodell sind minimal die zwei Methoden Equals und ToString aus der Vaterklasse System.Object geeignet zu überschreiben. Um zusätzliche Warnungen des C#-Compilers zu vermeiden, sollte man auch die Methode GetHashCode in Tabelle 4 mit einbeziehen:

Methode

Schnittstelle und Beschreibung

Equals

public override bool Equals (Object o);

Testet zwei IntegerSet-Objekte auf Gleichheit. Die Equals-Methode und der ==-Operator sind geeignet aufeinander abzustimmen.

ToString

public override String ToString ();

Die Menge sollte im folgenden Format durch ein String-Objekt dargestellt werden:

{1, 2, 3, 4, 5}

GetHashCode

public override int GetHashCode ();

Für das Zusammenspiel mit Hashtabellen liefert GetHashCode einen eindeutigen Index zurück.

Tabelle 4. Kontrakt mit der Basisklasse System.Object.


Für elementare mengentheoretische Operationen wie das Bilden einer Vereinigungs- und Schnittmenge oder das Testen der Teilmengenrelation bietet sich die Realisierung durch Operatoren an. Tabelle 5 beschreibt die gängigsten Operatoren im Umfeld der elementaren Mengenlehre:

Operator

Schnittstelle und Beschreibung

operator+

public static IntegerSet operator+ (IntegerSet s1, IntegerSet s2);

Das Resultatobjekt ist die Vereinigungsmenge der beiden Operanden s1 und s2.

operator-

public static IntegerSet operator- (IntegerSet s1, IntegerSet s2);

Das Resultatobjekt ist die Differenzmenge der beiden Operanden s1 und s2.

operator^

public static IntegerSet operator^ (IntegerSet s1, IntegerSet s2);

Das Resultatobjekt ist die Schnittmenge der beiden Operanden s1 und s2.

operator<=

public static bool operator <= (IntegerSet s1, IntegerSet s2);

Prüft, ob die Menge s1 in der Menge s2 enthalten ist (Rückgabewert true) oder nicht (Rückgabewert false).

operator<

public static bool operator < (IntegerSet s1, IntegerSet s2);

Prüft, ob die Menge s1 in der Menge s2 echt enthalten ist (Rückgabewert true) oder nicht (Rückgabewert false).

operator==

public static bool operator== (IntegerSet s1, IntegerSet s2);

Vergleicht zwei Mengenobjekte auf Gleichheit. Zu beachten ist: Die beiden Mengen { 1, 3, 5 } und { 5, 3, 1 } sind im Sinne der Mengentheorie gleich, die Reihenfolge ihrer Elemente spielt keine Rolle.

operator!=

public static bool operator!= (IntegerSet s1, IntegerSet s2);

Vergleicht zwei Mengenobjekte auf Ungleichheit.

Tabelle 5. Mengentheoretische Operationen der Klasse IntegerSet.


Zum Abschluss dieser Betrachtungen sollte die Klasse IntegerSet natürlich noch mit einem Indexer ausgestattet sein, siehe Tabelle 6:

Schnittstelle und Beschreibung

public int this [int index] { get; }

Ermöglicht den indizierten Zugriff auf ein Mengenobjekt. Mit Hilfe von Size und dem Indexer lassen sich die Elemente einer Menge einzeln aufzählen. Veränderungen an einem Mengenobjekt sollten konzeptionell nur mit Hilfe der beiden Methoden Insert und Remove erfolgen, aus diesem Grund ist der Indexer nur lesend konzipiert.

Tabelle 6. Indexer der Klasse IntegerSet.


Es folgen einige Hinweise zur Realisierung. Da ein IntegerSet-Objekt prinzipiell eine Menge beliebiger Größe beherbergen soll, müssen die Mengenelemente in einem dynamisch allokierten Datenbereich abgelegt werden, etwa einem mit new angelegten Array. Eine gangbare Implementierung der Klasse IntegerSet kommt folglich mit einer Instanzvariablen aus, etwa einer Referenzvariablen elements, die die Adresse des dynamischen Datenpuffers enthält (Abbildung 1). Die Länge dieses Puffers ist implizit in dem dynamisch allokierten Array-Objekt (als Eigenschaft Length) abgelegt und muss deshalb nicht zusätzlich im Instanzvariablenbereich der IntegerSet-Klasse mit verwaltet werden.

Instanzdatenbereich eines IntegerSet-Objekts mit einem dynamisch allokierten Datenpuffer.

Abbildung 1. Instanzdatenbereich eines IntegerSet-Objekts mit einem dynamisch allokierten Datenpuffer.


Bei jedem Einfügen und Entfernen von Mengenelementen stehen wir vor dem Problem, dass sich der Umfang der Menge verändert. Um den nachfolgenden Lösungsvorschlag möglichst elementar zu halten, beschreiten wir einen sehr einfachen Ansatz. Der dynamisch allokierte Puffer wird hierbei bei jeder Mengenoperation in seiner Größe exakt an die Anzahl der Mengenelemente angepasst. Dies hat zwar zur Folge, dass bei jedem Einfügen oder Entfernen von Mengenelementen intern ein neuer Puffer zu allokieren ist, dessen Elemente mit Ausnahme eines einzigen Elements identisch zum alten Puffer sind. Der Nachteil der daraus resultierenden unzufriedenstellenden Performance auf Grund der vielen new-Aufrufe und Garbage Collections wird jedoch durch eine vergleichsweise einfache Implementierung ausgeglichen, wie wir im nachfolgend vorgestellten Quellcode sehen werden. Die Arbeitsweise der Insert-Methode finden Sie in Abbildung 2 exemplarisch skizziert vor.

Arbeitsweise der Insert-Methode: Aufruf mit dem Aktualparameter 2.

Abbildung 2. Arbeitsweise der Insert-Methode: Aufruf mit dem Aktualparameter 2.


Beim Einfügen eines neuen Mengenelements ist intern ein neuer – um ein Element größerer – Datenpuffer zu allokieren. Der alte Datenpuffer ist Element für Element in den neuen Puffer zu kopieren, das neu einzufügende Element kann am Ende des neuen Datenpuffers abgelegt werden. Für das Entfernen eines Mengenelements geht man ähnlich vor (siehe Abbildung 3).

Arbeitsweise der Remove-Methode: Aufruf mit dem Aktualparameter 7.

Abbildung 3. Arbeitsweise der Remove-Methode: Aufruf mit dem Aktualparameter 7.


Ein Aufruf der Remove-Methode zieht wiederum das Allokieren eines neuen Datenpuffers nach sich, der dieses Mal um ein Element kleiner ist als der alte Puffer. Mit Ausnahme des zu entfernenden Elements sind alle Elemente des alten Puffers in den neuen Puffer umzukopieren. In Abbildung 4 können Sie die Arbeitsweise der beiden Methoden Insert und Remove an Hand des Codefragments

IntegerSet s;
s.Insert(1);
s.Insert(2);
s.Insert(3);
s.Remove(1);
s.Remove(2);

studieren.

Arbeitsweise der Insert- und Remove-Methode im Zusammenspiel.

Abbildung 4. Arbeitsweise der Insert- und Remove-Methode im Zusammenspiel.

2. Lösung

Quellcode: Siehe auch github.com/peterloos/github.com/peterloos/CSharp_IntegerSet.git.

Nach diesen vorbereitenden Erläuterungen kommen wir nun in Listing 1 auf die Implementierung auf Basis der diskutierten Vorgehensweise zu sprechen:

001: using System;
002: using System.Collections;
003: using System.Text;
004: 
005: namespace IntegerSet_Array
006: {
007:     public class IntegerSet : ICloneable, IEnumerable
008:     {
009:         // private member data
010:         private int[] elements;
011: 
012:         // c'tors
013:         public IntegerSet()
014:         {
015:             this.elements = new int[0];
016:         }
017: 
018:         public IntegerSet(int[] elements) : this()
019:         {
020:             for (int i = 0; i < elements.Length; i++)
021:                 this.Insert(elements[i]);
022:         }
023: 
024:         // public properties
025:         public int Size
026:         {
027:             get
028:             {
029:                 return this.elements.Length;
030:             }
031:         }
032: 
033:         public bool IsEmpty
034:         {
035:             get
036:             {
037:                 return this.elements.Length == 0;
038:             }
039:         }
040: 
041:         // indexer
042:         public int this[int index]
043:         {
044:             get
045:             {
046:                 // check parameter
047:                 if (index < 0)
048:                     throw new IndexOutOfRangeException();
049:                 if (index >= this.elements.Length)
050:                     throw new IndexOutOfRangeException();
051: 
052:                 // return element
053:                 return this.elements[index];
054:             }
055:         }
056: 
057:         // public methods
058:         public bool Contains(int n)
059:         {
060:             // search element
061:             for (int i = 0; i < this.elements.Length; i++)
062:                 if (this.elements[i] == n)
063:                     return true;
064: 
065:             return false;
066:         }
067: 
068:         public bool Insert(int n)
069:         {
070:             // element already exists
071:             if (Contains(n))
072:                 return false;
073: 
074:             // allocate new buffer
075:             int[] tmp = new int[this.elements.Length + 1];
076: 
077:             // copy old buffer into new one
078:             for (int i = 0; i < this.elements.Length; i++)
079:                 tmp[i] = this.elements[i];
080: 
081:             // insert new element at end of buffer
082:             tmp[this.elements.Length] = n;
083: 
084:             // switch to new buffer
085:             this.elements = tmp;
086: 
087:             return true;
088:         }
089: 
090:         public bool Remove(int n)
091:         {
092:             // element already exists
093:             if (!Contains(n))
094:                 return false;
095: 
096:             // allocate new buffer
097:             int[] tmp = new int[this.elements.Length - 1];
098: 
099:             // copy old buffer into new one
100:             for (int i = 0, k = 0; i < this.elements.Length; i++)
101:             {
102:                 if (this.elements[i] == n)
103:                     continue;
104: 
105:                 tmp[k] = this.elements[i];
106:                 k++;
107:             }
108: 
109:             // switch to new buffer
110:             this.elements = tmp;
111: 
112:             return true;
113:         }
114: 
115:         // comparison operators
116:         public static bool operator ==(IntegerSet s1, IntegerSet s2)
117:         {
118:             return s1.Equals(s2);
119:         }
120: 
121:         public static bool operator !=(IntegerSet s1, IntegerSet s2)
122:         {
123:             return !(s1 == s2);
124:         }
125: 
126:         public static bool operator <=(IntegerSet s1, IntegerSet s2)
127:         {
128:             // compare both sets element per element
129:             for (int i = 0; i < s1.Size; i++)
130:                 if (!s2.Contains(s1[i]))
131:                     return false;
132: 
133:             return true;
134:         }
135: 
136:         public static bool operator >=(IntegerSet s1, IntegerSet s2)
137:         {
138:             return s2 <= s1;
139:         }
140: 
141:         public static bool operator <(IntegerSet s1, IntegerSet s2)
142:         {
143:             return (s1 <= s2) && (s1 != s2);
144:         }
145: 
146:         public static bool operator >(IntegerSet s1, IntegerSet s2)
147:         {
148:             return !(s1 <= s2);
149:         }
150: 
151:         // conversion operator
152:         public static implicit operator IntegerSet(int n)
153:         {
154:             IntegerSet s = new IntegerSet();
155:             s.Insert(n);
156:             return s;
157:         }
158: 
159:         // set theory specific operators
160:         public static IntegerSet operator +(IntegerSet s1, IntegerSet s2)
161:         {
162:             IntegerSet s = (IntegerSet)s1.Clone();
163:             for (int i = 0; i < s2.elements.Length; i++)
164:                 s.Insert(s2.elements[i]);
165: 
166:             return s;
167:         }
168: 
169:         public static IntegerSet operator -(IntegerSet s1, IntegerSet s2)
170:         {
171:             IntegerSet s = (IntegerSet)s1.Clone();
172:             for (int i = 0; i < s2.elements.Length; i++)
173:                 s.Remove(s2.elements[i]);
174: 
175:             return s;
176:         }
177: 
178:         public static IntegerSet operator ^(IntegerSet s1, IntegerSet s2)
179:         {
180:             IntegerSet s = new IntegerSet();
181:             for (int i = 0; i < s1.elements.Length; i++)
182:             {
183:                 int n = s1.elements[i];
184:                 if (s2.Contains(n))
185:                     s.Insert(n);
186:             }
187: 
188:             return s;
189:         }
190: 
191:         // contract with base class 'Object'
192:         public override bool Equals(Object o)
193:         {
194:             if (!(o is IntegerSet))
195:                 return false;
196: 
197:             IntegerSet s = (IntegerSet)o;
198: 
199:             // compare sizes
200:             if (this.elements.Length != s.elements.Length)
201:                 return false;
202: 
203:             // compare both sets element per element
204:             for (int i = 0; i < this.elements.Length; i++)
205:             {
206:                 if (s.Contains(this.elements[i]))
207:                     continue;
208: 
209:                 return false;
210:             }
211: 
212:             return true;
213:         }
214: 
215:         public override String ToString()
216:         {
217:             StringBuilder sb = new StringBuilder();
218:             sb.Append('{');
219:             for (int i = 0; i < this.elements.Length; i++)
220:             {
221:                 sb.Append(this.elements[i]);
222:                 if (i < this.elements.Length - 1)
223:                     sb.Append(',');
224:             }
225:             sb.AppendFormat("{0}[{1}]", '}', this.elements.Length);
226:             return sb.ToString();
227:         }
228: 
229:         public override int GetHashCode()
230:         {
231:             return this.elements.GetHashCode();
232:         }
233: 
234:         // implementation of interface 'ICloneable'
235:         public Object Clone()
236:         {
237:             return new IntegerSet(this.elements);
238:         }
239: 
240:         // implementation of interface 'IEnumerable'
241:         public IEnumerator GetEnumerator()
242:         {
243:             return new IntegerSetEnumerator(this);
244:         }
245:     }
246: 
247:     class IntegerSetEnumerator : IEnumerator
248:     {
249:         private IntegerSet set;
250:         private int pos;
251: 
252:         public IntegerSetEnumerator(IntegerSet set)
253:         {
254:             this.set = set;
255:             this.pos = -1;
256:         }
257: 
258:         // implementation of interface 'IEnumerator'
259:         public Object Current
260:         {
261:             get
262:             {
263:                 return this.set[this.pos];
264:             }
265:         }
266: 
267:         public bool MoveNext()
268:         {
269:             this.pos++;
270:             if (this.pos == this.set.Size)
271:             {
272:                 this.Reset();
273:                 return false;
274:             }
275:             else
276:             {
277:                 return true;
278:             }
279:         }
280: 
281:         public void Reset()
282:         {
283:             this.pos = -1;
284:         }
285:     }
286: }

Beispiel 1. Klasse IntegerSet.


Sie finden in Listing 1 einige weitere Aspekte berücksichtigt vor, die wir hier nur kurz in tabellarischer Form ansprechen:

  • Schnittstelle ICloneable:

    Das Kopieren von Objekten erfolgt in .NET konform zum .NET-Objektmodell durch eine Implementierung der ICloneable-Schnittstelle. Diese definiert nur eine einzige Methode, sie heißt sinnigerweise Clone:

    public Object Clone();
  • Aufzählung von IntegerSet-Objekten:

    Das Aufzählen aller Elemente eines IntegerSet-Objekts sollte in .NET wiederum unter Berücksichtigung des .NET-Objektmodells erfolgen. Zu diesem Zweck gibt es die beiden Schnittstellen IEnumerable und IEnumerator:

    public interface IEnumerable
    {
        IEnumerator GetEnumerator ();
    }

    und

    public interface IEnumerator
    {
        Object Current { get; }
        bool MoveNext ();
        void Reset ();
    }
  • Konvertierungsoperator:

    In C# lassen sich – im Gegensatz zu C++ – die beiden Operatoren += und -= nicht überladen. Das heißt aber noch lange nicht, dass man Ausdrücke der Form

    IntegerSet s;
    ...
    s += 1;
    s -= 2;

    in C# nicht formulieren kann. Mit Hilfe eines Konvertierungskonstruktors kann man ganze Zahlen in ein-elementige Mengen transformieren, der +=- bzw. -=-Operator findet dann auf beiden Seiten ein IntegerSet-Objekt vor. Der C#-Compiler zerlegt den Ausdruck dann in eine +- bzw. --Operation mit anschließender Wertzuweisung.

Zum Testen der Klasse IntegerSet zeigen wir exemplarisch die Testmethoden für die Konstruktoren und Operatoren:

001: class Program
002: {
003:     public static void Main()
004:     {
005:         TestingCtorsDtor();
006:         TestingMethods();
007:         TestingRemove();
008:         TestingInsert();
009:         TestingOperators();
010:         TestingArithmeticAssignmentOperators();
011:         TestingIndexOperator();
012:         TestingICloneable();
013:         TestingIEnumerable();
014:     }
015: 
016:     private static void TestingCtorsDtor()
017:     {
018:         Console.WriteLine("Testing c'tors / d'tor: ");
019: 
020:         IntegerSet s1 = new IntegerSet();
021:         Console.WriteLine("s1: {0}", s1);
022: 
023:         int[] elems1 = { -2, -1, 0, 1, 2, -1, -2 };
024:         IntegerSet s2 = new IntegerSet(elems1);
025:         Console.WriteLine("s2: {0}", s2);
026: 
027:         int[] elems2 = { -1, 1, 2, 3, 1, 2, 3, 1, 2, 3, -1 };
028:         IntegerSet s3 = new IntegerSet(elems2);
029:         Console.WriteLine("s3: {0}", s3);
030: 
031:         Console.WriteLine("s1.IsEmpty: {0}", s1.IsEmpty);
032:         Console.WriteLine("s2.IsEmpty: {0}", s2.IsEmpty);
033:         Console.WriteLine("s3.IsEmpty: {0}", s3.IsEmpty);
034:     }
035: 
036:     private static void TestingMethods()
037:     {
038:         Console.WriteLine("Testing methods: ");
039: 
040:         IntegerSet s = new IntegerSet();
041:         Console.WriteLine("s: {0}", s);
042: 
043:         // testing 'Insert'
044:         s.Insert(1);
045:         s.Insert(2);
046:         s.Insert(3);
047:         s.Insert(4);
048:         s.Insert(5);
049:         s.Insert(6);
050:         Console.WriteLine("s: {0}", s);
051: 
052:         // testing 'Remove'
053:         s.Remove(3);
054:         s.Remove(4);
055:         s.Remove(5);
056:         s.Remove(6);
057:         Console.WriteLine("s: {0}", s);
058: 
059:         s.Insert(10);
060:         s.Insert(11);
061:         s.Insert(12);
062: 
063:         s.Insert(13);
064:         s.Insert(14);
065:         s.Insert(15);
066:         s.Insert(16);
067:         s.Insert(17);
068:         s.Insert(18);
069:         s.Insert(19);
070:         s.Insert(20);
071:         s.Insert(21);
072:         s.Insert(22);
073:         s.Insert(23);
074:         Console.WriteLine("s: {0}", s);
075: 
076:         s.Insert(24);
077:         Console.WriteLine("s: {0}", s);
078: 
079:         s.Remove(11);
080:         Console.WriteLine("s: {0}", s);
081: 
082: 
083:         // testing 'Contains'
084:         Console.WriteLine("Contains(1): {0}", s.Contains(1));
085:         Console.WriteLine("Contains(5): {0}", s.Contains(5));
086:         Console.WriteLine("Contains(10): {0}", s.Contains(10));
087:     }
088: 
089:     private static void TestingRemove()
090:     {
091:         IntegerSet s = new IntegerSet();
092:         for (int i = 0; i < 20; i++)
093:             s.Insert(i);
094:         Console.WriteLine("s: {0}", s);
095: 
096:         s.Remove(5);
097:         s.Remove(1);
098:         s.Remove(8);
099:         Console.WriteLine("s: {0}", s);
100: 
101:         s.Remove(11);
102:         Console.WriteLine("s: {0}", s);
103: 
104:         s.Remove(16);
105:         Console.WriteLine("s: {0}", s);
106: 
107:         s.Remove(19);
108:         Console.WriteLine("s: {0}", s);
109:     }
110: 
111:     private static void TestingInsert()
112:     {
113:         IntegerSet s = new IntegerSet();
114:         for (int i = 0; i < 16; i++)
115:             s.Insert(i);
116:         Console.WriteLine("s: {0}", s);
117: 
118:         s.Insert(16);
119:         Console.WriteLine("s: {0}", s);
120:     }
121: 
122:     private static void TestingOperators()
123:     {
124:         // testing union set
125:         IntegerSet s1 = new IntegerSet();
126:         IntegerSet s2 = new IntegerSet();
127:         for (int i = 0; i < 7; i++)
128:             s1.Insert(i);
129:         for (int i = 2; i < 9; i++)
130:             s2.Insert(i);
131:         Console.WriteLine("s1: {0}", s1);
132:         Console.WriteLine("s2: {0}", s2);
133:         Console.WriteLine("s1+s2: {0}", s1 + s2);
134: 
135:         // testing intersection set
136:         Console.WriteLine("s1^s2: {0}", s1 ^ s2);
137: 
138:         // testing ==-operator
139:         Console.WriteLine("s1 == s2: {0}", s1 == s2);
140:         s2.Insert(0);
141:         s2.Insert(1);
142:         s2.Remove(7);
143:         s2.Remove(8);
144:         Console.WriteLine("s2: {0}", s2);
145:         Console.WriteLine("s1 == s2: {0}", s1 == s2);
146:         Console.WriteLine("s1 != s2: {0}", s1 != s2);
147: 
148:         // testing subset operator
149:         Console.WriteLine("s1: {0}", s1);
150:         Console.WriteLine("s2: {0}", s2);
151:         Console.WriteLine("s1 <= s2: {0}", s1 <= s2);
152:         s1.Insert(7);
153:         Console.WriteLine("s1: {0}", s1);
154:         Console.WriteLine("s1 <= s2: {0}", s1 <= s2);
155:     }
156: 
157:     private static void TestingArithmeticAssignmentOperators()
158:     {
159:         int[] elements = { 1, 2, 3 };
160:         IntegerSet s = new IntegerSet(elements);
161:         Console.WriteLine("s: {0}", s);
162:         s += 4;
163:         Console.WriteLine("s: {0}", s);
164:         s -= 1;
165:         Console.WriteLine("s: {0}", s);
166:     }
167: 
168:     private static void TestingIndexOperator()
169:     {
170:         int[] elements = { 9, 8, 7, 6, 5, 4, 3, 2, 1 };
171:         IntegerSet s = new IntegerSet(elements);
172: 
173:         for (int i = 0; i < s.Size; i++)
174:             Console.WriteLine("Element at {0}: {1}", i, s[i]);
175:     }
176: 
177:     private static void TestingICloneable()
178:     {
179:         int[] elements = { 1, 2, 3, 4, 5 };
180:         IntegerSet s1 = new IntegerSet(elements);
181:         Console.WriteLine("s1: {0}", s1);
182: 
183:         IntegerSet s2 = (IntegerSet)s1.Clone();
184:         Console.WriteLine("s2: {0}", s2);
185:         s2.Remove(5);
186:         Console.WriteLine("s2: {0}", s2);
187:     }
188: 
189:     private static void TestingIEnumerable()
190:     {
191:         int[] elements = { 1, 2, 3, 4, 5 };
192:         IntegerSet set = new IntegerSet(elements);
193:         Console.WriteLine("s: {0}", set);
194: 
195:         foreach (int n in set)
196:         {
197:             Console.WriteLine("next element: {0}", n);
198:         }
199:     }
200: }

Beispiel 2. Klasse IntegerSet: Testrahmen.


Der Testrahmen aus Listing 2 führt bei der Ausführung zu folgenden Resultaten:

Testing c'tors / d'tor:
s1: {}[0]
s2: {-2,-1,0,1,2}[5]
s3: {-1,1,2,3}[4]
s1.IsEmpty: True
s2.IsEmpty: False
s3.IsEmpty: False
Testing methods:
s: {}[0]
s: {1,2,3,4,5,6}[6]
s: {1,2}[2]
s: {1,2,10,11,12,13,14,15,16,17,18,19,20,21,22,23}[16]
s: {1,2,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24}[17]
s: {1,2,10,12,13,14,15,16,17,18,19,20,21,22,23,24}[16]
Contains(1): True
Contains(5): False
Contains(10): True
s: {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19}[20]
s: {0,2,3,4,6,7,9,10,11,12,13,14,15,16,17,18,19}[17]
s: {0,2,3,4,6,7,9,10,12,13,14,15,16,17,18,19}[16]
s: {0,2,3,4,6,7,9,10,12,13,14,15,17,18,19}[15]
s: {0,2,3,4,6,7,9,10,12,13,14,15,17,18}[14]
s: {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}[16]
s: {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16}[17]
s1: {0,1,2,3,4,5,6}[7]
s2: {2,3,4,5,6,7,8}[7]
s1+s2: {0,1,2,3,4,5,6,7,8}[9]
s1^s2: {2,3,4,5,6}[5]
s1 == s2: False
s2: {2,3,4,5,6,0,1}[7]
s1 == s2: True
s1 != s2: False
s1: {0,1,2,3,4,5,6}[7]
s2: {2,3,4,5,6,0,1}[7]
s1 <= s2: True
s1: {0,1,2,3,4,5,6,7}[8]
s1 <= s2: False
s: {1,2,3}[3]
s: {1,2,3,4}[4]
s: {2,3,4}[3]
Element at 0: 9
Element at 1: 8
Element at 2: 7
Element at 3: 6
Element at 4: 5
Element at 5: 4
Element at 6: 3
Element at 7: 2
Element at 8: 1
s1: {1,2,3,4,5}[5]
s2: {1,2,3,4,5}[5]
s2: {1,2,3,4}[4]
s: {1,2,3,4,5}[5]
next element: 1
next element: 2
next element: 3
next element: 4
next element: 5

Die in Listing 1 vorgestellte Realisierung ist sicherlich auf Grund der starken Beanspruchung der dynamischen Speicherverwaltung nicht optimal. Ein alternativer Realisierungsansatz besteht darin, dass man die Größe des internen Arrays an Hand eines fest vorgegebenen Werts allokiert, der bei Bedarf zu verdoppeln ist, also zum Beispiel 16, 32, 64, 128, usw. Beim Einfügen von Elementen in die Menge können so etliche neue Elemente aufgenommen werden, ohne dass eine Anforderung an die dynamische Speicherverwaltung gestellt werden muss (Abbildung 5).

IntegerSet-Mengenobjekt mit den Elementen 5, 9, 1, 7, und 3 und einem internen Datenpuffer der Länge 16.

Abbildung 5. IntegerSet-Mengenobjekt mit den Elementen 5, 9, 1, 7, und 3 und einem internen Datenpuffer der Länge 16.


Achtet man ferner darauf, dass alle Mengenelemente stets am Anfang des Arrays platziert sind, lassen sich auch bei dieser Strategie das Einfügen und Entfernen von Elementen verhältnismäßig einfach implementieren. In Abbildung 5 erkennt man, dass wir zu diesem Zweck jetzt eine weitere Instanzvariable zur Verwaltung des internen Arrays benötigen: Die Instanzvariable number beschreibt die aktuelle Anzahl der Elemente in der Menge. Die tatsächliche Größe des internen Puffers (häufig als „Kapazität“ bezeichnet) finden wir nach wie vor in der Length-Eigenschaft des Array-Objekts vor. Erst wenn number größer als die Kapazität wird, muss dynamisch ein neues Array allokiert werden.

Das Einfügen eines neuen Elements ist nun äußerst einfach. Es ist der erste unbenutzte Eintrag des internen Arrays zu verwenden, sofern noch freie Einträge vorhanden sind. Nur für den Fall, dass bereits vor der Einfügeoperation der Wert von number gleich der Puffergröße des internen Arrays ist, muss ein größerer Datenpuffer allokiert werden (Abbildung 6).

Arbeitsweise der Insert-Methode: Aufruf mit dem Aktualparameter 2.

Abbildung 6. Arbeitsweise der Insert-Methode: Aufruf mit dem Aktualparameter 2.


Beim Entfernen eines Mengenelements steht man vor dem Problem, dass in dem internen Array eine Lücke entsteht (sofern nicht zufälligerweise das letzte Element zu löschen ist). Wir behelfen uns an dieser Stelle mit einem kleinen Trick: An die Position des zu löschenden Elements wird einfach das letzte Mengenelement umkopiert (Abbildung 7). Es sind so nach wie vor alle Mengenelemente dicht am Anfang des Arrays abgelegt und es entstehen keine Lücken. Nachfolgende Einfügeoperationen können auf diese Weise wieder trivial wie zuvor beschrieben ausgeführt werden.

Arbeitsweise der Remove-Methode: Aufruf mit dem Aktualparameter 7.

Abbildung 7. Arbeitsweise der Remove-Methode: Aufruf mit dem Aktualparameter 7.


Werden im Zuge der Mengenoperationen mehr Lösch- wie Einfügeoperationen durchgeführt, sollte man den internen Datenpuffer wieder verkleinern. Man verhindert so, dass der Speicherplatz eines IntegerSet-Objekts nicht ausschließlich zunimmt.

Zum Abschluss dieser Betrachtungen demonstrieren wir in Abbildung 8, wie sich sowohl beim Einfügen wie auch beim Entfernen von Elementen in ein IntegerSet-Objekt das dynamische Anlegen neuer Datenpuffer stark reduziert.

Arbeitsweise der Insert- und Remove-Methode bei geblocktem Datenpuffer.

Abbildung 8. Arbeitsweise der Insert- und Remove-Methode bei geblocktem Datenpuffer.


Bei der zweiten Realisierungsstrategie ändert sich die Schnittstelle der IntegerSet-Klasse minimal. Wir fügen einen zusätzlichen Konstruktor

private IntegerSet (int capacity);

hinzu, der es gestattet, die Größe des internen Datenpuffers bei der Objekterzeugung vorab festzulegen. In der Realisierung sollte darauf geachtet werden, dass der Parameter capacity auf ein Vielfaches von 16 angepasst wird. Sie werden in der Realisierung sehen, dass dieser Konstruktor für die Clone-Methode erforderlich ist.

Bei den Instanzvariablen ist es nun relevant, zwischen der Anzahl der Elemente in der Menge und der Größe des internen Puffers zu unterscheiden. Wir benötigen deshalb eine zusätzliche Instanzvariable number, die die obere Grenze der tatsächlich im internen Datenpuffer relevanten Elemente festhält:

// private member data
private int[] elements;  // array of elements
private int number;      // current number of elements

Es folgt in Listing 3 die Implementierung des alternativen Lösungsvorschlags:

001: using System;
002: using System.Collections;
003: using System.Text;
004: 
005: namespace IntegerSet_ArrayEx
006: {
007:     class IntegerSet : ICloneable, IEnumerable
008:     {
009:         // private member data
010:         private int[] elements;  // array of elements
011:         private int number;      // current number of elements
012: 
013:         // c'tors
014:         public IntegerSet()
015:         {
016:             // allocate buffer
017:             this.number = 0;
018:             this.elements = new int[16];
019:         }
020: 
021:         public IntegerSet(int[] elements) : this()
022:         {
023:             for (int i = 0; i < elements.Length; i++)
024:                 this.Insert(elements[i]);
025:         }
026: 
027:         private IntegerSet(int capacity)
028:         {
029:             this.number = 0;
030: 
031:             // compute appropriate buffer size
032:             int size = 16;
033:             while (size < capacity)
034:                 size *= 2;
035: 
036:             // allocate buffer
037:             this.elements = new int[size];
038:         }
039: 
040:         // public properties
041:         public int Size
042:         {
043:             get
044:             {
045:                 return this.number;
046:             }
047:         }
048: 
049:         public bool IsEmpty
050:         {
051:             get
052:             {
053:                 return this.number == 0;
054:             }
055:         }
056: 
057:         // indexer
058:         public int this[int index]
059:         {
060:             get
061:             {
062:                 // check parameter
063:                 if (index < 0)
064:                     throw new IndexOutOfRangeException();
065:                 if (index >= this.elements.Length)
066:                     throw new IndexOutOfRangeException();
067: 
068:                 // return element
069:                 return this.elements[index];
070:             }
071:         }
072: 
073:         // public methods
074:         public bool Contains(int n)
075:         {
076:             // search element
077:             for (int i = 0; i < this.number; i++)
078:                 if (this.elements[i] == n)
079:                     return true;
080: 
081:             return false;
082:         }
083: 
084:         public bool Insert(int n)
085:         {
086:             // element already exists
087:             if (Contains(n))
088:                 return false;
089: 
090:             // if current buffer is full, allocate a new one
091:             if (this.elements.Length == this.number)
092:             {
093:                 int[] tmp = new int[this.elements.Length * 2];
094: 
095:                 // copy old buffer into new one
096:                 for (int i = 0; i < this.number; i++)
097:                     tmp[i] = this.elements[i];
098: 
099:                 // switch to new buffer
100:                 this.elements = tmp;
101:             }
102: 
103:             // insert new element at end of buffer
104:             this.elements[this.number] = n;
105:             this.number++;
106: 
107:             return true;
108:         }
109: 
110:         public bool Remove(int n)
111:         {
112:             // element already exists
113:             if (!Contains(n))
114:                 return false;
115: 
116:             // remove element
117:             for (int i = 0; i < this.number; i++)
118:             {
119:                 if (this.elements[i] == n)
120:                 {
121:                     // remove element - and copy last element into gap
122:                     this.elements[i] = this.elements[this.number - 1];
123:                     this.number--;
124:                 }
125:             }
126: 
127:             // reduce current buffer, if necessary
128:             if ((this.elements.Length > 16) &&
129:                 (2 * this.number <= this.elements.Length))
130:             {
131:                 // allocate new buffer
132:                 int[] tmp = new int[this.elements.Length / 2];
133: 
134:                 // copy old buffer into new one
135:                 for (int i = 0; i < this.number; i++)
136:                     tmp[i] = this.elements[i];
137: 
138:                 // switch to new buffer
139:                 this.elements = tmp;
140:             }
141: 
142:             return true;
143:         }
144: 
145:         // comparison operators
146:         public static bool operator==(IntegerSet s1, IntegerSet s2)
147:         {
148:             return s1.Equals(s2);
149:         }
150: 
151:         public static bool operator!=(IntegerSet s1, IntegerSet s2)
152:         {
153:             return !(s1 == s2);
154:         }
155: 
156:         public static bool operator<=(IntegerSet s1, IntegerSet s2)
157:         {
158:             // compare both sets element per element
159:             for (int i = 0; i < s1.Size; i++)
160:                 if (!s2.Contains(s1[i]))
161:                     return false;
162: 
163:             return true;
164:         }
165: 
166:         public static bool operator>=(IntegerSet s1, IntegerSet s2)
167:         {
168:             return s2 <= s1;
169:         }
170: 
171:         public static bool operator<(IntegerSet s1, IntegerSet s2)
172:         {
173:             return (s1 <= s2) && (s1 != s2);
174:         }
175: 
176:         public static bool operator>(IntegerSet s1, IntegerSet s2)
177:         {
178:             return !(s1 <= s2);
179:         }
180: 
181:         // conversion operator
182:         public static implicit operator IntegerSet(int n)
183:         {
184:             IntegerSet s = new IntegerSet();
185:             s.Insert(n);
186:             return s;
187:         }
188: 
189:         // set theory specific operators
190:         public static IntegerSet operator+(IntegerSet s1, IntegerSet s2)
191:         {
192:             IntegerSet s = (IntegerSet)s1.Clone();
193:             for (int i = 0; i < s2.Size; i++)
194:                 s.Insert(s2.elements[i]);
195: 
196:             return s;
197:         }
198: 
199:         public static IntegerSet operator-(IntegerSet s1, IntegerSet s2)
200:         {
201:             IntegerSet s = (IntegerSet)s1.Clone();
202:             for (int i = 0; i < s2.Size; i++)
203:                 s.Remove(s2.elements[i]);
204: 
205:             return s;
206:         }
207: 
208:         public static IntegerSet operator^(IntegerSet s1, IntegerSet s2)
209:         {
210:             IntegerSet s = new IntegerSet();
211: 
212:             for (int i = 0; i < s1.Size; i++)
213:             {
214:                 int n = s1.elements[i];
215:                 if (s2.Contains(n))
216:                     s.Insert(n);
217:             }
218: 
219:             return s;
220:         }
221: 
222:         // contract with base class 'Object'
223:         public override bool Equals(Object o)
224:         {
225:             if (!(o is IntegerSet))
226:                 return false;
227: 
228:             IntegerSet s = (IntegerSet)o;
229: 
230:             // compare sizes
231:             if (this.Size != s.Size)
232:                 return false;
233: 
234:             // compare both sets element per element
235:             for (int i = 0; i < this.Size; i++)
236:             {
237:                 if (s.Contains(this.elements[i]))
238:                     continue;
239: 
240:                 return false;
241:             }
242: 
243:             return true;
244:         }
245: 
246:         public override String ToString()
247:         {
248:             StringBuilder sb = new StringBuilder();
249:             sb.Append('{');
250:             for (int i = 0; i < this.number; i++)
251:             {
252:                 sb.Append(this.elements[i]);
253:                 if (i < this.number - 1)
254:                     sb.Append(',');
255:             }
256:             sb.AppendFormat("{0}[{1},{2}]", '}',
257:                 this.number, this.elements.Length);
258: 
259:             return sb.ToString();
260:         }
261: 
262:         public override int GetHashCode()
263:         {
264:             return this.elements.GetHashCode();
265:         }
266: 
267:         // implementation of interface 'ICloneable'
268:         public Object Clone()
269:         {
270:             IntegerSet s = new IntegerSet(this.elements.Length);
271: 
272:             for (int i = 0; i < this.Size; i++)
273:                 s.Insert(this[i]);
274: 
275:             return s;
276:         }
277: 
278:         // implementation of interface 'IEnumerable'
279:         public IEnumerator GetEnumerator()
280:         {
281:             for (int i = 0; i < this.number; i++)
282:                 yield return this.elements[i];
283:         }
284:     }
285: }

Beispiel 3. Klasse IntegerSet: Alternative Implementierung.


In Listing 3 finden Sie in den Zeilen 279 bis 283 eine alternative Realisierung zum Aufzählen aller Elemente eines IntegerSet-Objekts vor. Um es kurz zu sagen: Die Realisierung in den Zeilen 247 bis 285 aus Listing 1 – also 38 Codezeilen – in Gestalt einer Hilfsklasse IntegerSetEnumerator zum Implementieren der .NET-Standardschnittstelle IEnumerator wurde nun auf ganze 2 Zeilen (for-Schleife in 281 und 282 eingestampft! Das Problem bei der Realisierung der Klasse IntegerSetEnumerator aus Listing 1 besteht darin, dass es manchmal durchaus mühsam sein kann, die Schnittstelle IEnumerator manuell zu implementieren, da sie intern einen oder mehrere Zustände verwalten muss, die zum Beschreiben der aktuellen Position in der Aufzählung erforderlich sind. Dieser interne Zustand kann für eine Klasse mit Daten vom Typ eines eindimensionalen Arrays recht einfach sein. Hier reicht ein Index für die aktuelle Position aus. Für Datenstrukturen, die einen rekursiven Durchlauf erfordern (z. B. binäre Strukturen) kann das Traversieren eine recht komplizierte Angelegenheit werden. Damit die Herausforderungen beim Implementieren des Aufzählungsverhaltens nicht zu groß werden, wurde in C# 2.0 das Schlüsselwort yield hinzugefügt, damit es einfacher für eine Klasse wird, die Art und Weise vorzuschreiben, wie die foreach-Schleife durch ihre Inhalte iteriert. Der Gebrauch von yield in einer Anweisung zeigt an, dass die Methode (Klasse), in der dies vorkommt, zu einem IEnumerator wird. Wird eine Aufzählung mit Hilfe von yield definiert, ist eine zweite zusätzliche Klasse (die Klasse, die den Zustand für eine Enumeration enthält und verwaltet, siehe beispielsweise IntegerSetEnumerator aus Listing 1) nicht mehr erforderlich.

Es zieht sich fast wie ein roter Faden durch diesen Lösungsvorschlag: Die bisweilen länglichen und auch umständlicheren Realisierungen tragen besser zum Verständnis des Quellcodes bei. Die kurzen, übersichtlichen und typischerweise auch weniger fehleranfälligen Lösungssequenzen besitzen einen höheren Abstraktionsgrad und erschließen deshalb nicht immer auf den ersten Blick!

Zum Abschluss wollen wir natürlich auch eine Realisierung vorstellen, die – frei nach der DRY-Code-Philosophie „Don't repeat yourself“ – eine adäquate Utility-Klasse aus der .NET-Klassenbibliothek in die Implementierung mit einbezieht. In unserem Fall bietet sich zur Ablage der Mengenelemente ein List<int>-Objekt an. In Listing 4 können Sie erkennen, dass dieser dritte Lösungsvorschlag erheblich kürzer und übersichtlicher ausfällt:

001: using System;
002: using System.Collections;
003: using System.Collections.Generic;
004: using System.Text;
005: 
006: namespace IntegerSet_List
007: {
008:     class IntegerSet : ICloneable, IEnumerable
009:     {
010:         // private member data
011:         private List<int> elements;  // list of elementss
012: 
013:         // c'tors
014:         public IntegerSet()
015:         {
016:             // allocate buffer
017:             this.elements = new List<int>();
018:         }
019: 
020:         public IntegerSet(int[] elements) : this()
021:         {
022:             for (int i = 0; i < elements.Length; i++)
023:                 this.Insert(elements[i]);
024:         }
025: 
026:         private IntegerSet(List<int> elements) : this()
027:         {
028:             for (int i = 0; i < elements.Count; i++)
029:                 this.Insert(elements[i]);
030:         }
031: 
032:         // public properties
033:         public int Size
034:         {
035:             get
036:             {
037:                 return this.elements.Count;
038:             }
039:         }
040: 
041:         public bool IsEmpty
042:         {
043:             get
044:             {
045:                 return this.elements.Count == 0;
046:             }
047:         }
048: 
049:         // indexer
050:         public int this[int index]
051:         {
052:             get
053:             {
054:                 // check parameter
055:                 if (index < 0)
056:                     throw new IndexOutOfRangeException();
057:                 if (index >= this.elements.Count)
058:                     throw new IndexOutOfRangeException();
059: 
060:                 // return element
061:                 return this.elements[index];
062:             }
063:         }
064: 
065:         // public methods
066:         public bool Contains(int n)
067:         {
068:             // search element
069:             if (this.elements.Contains(n))
070:                 return true;
071: 
072:             return false;
073:         }
074: 
075:         public bool Insert(int n)
076:         {
077:             // element already exists
078:             if (Contains(n))
079:                 return false;
080: 
081:             // insert new element
082:             this.elements.Add(n);
083:             return true;
084:         }
085: 
086:         public bool Remove(int n)
087:         {
088:             // element already exists
089:             if (!Contains(n))
090:                 return false;
091: 
092:             // remove element
093:             this.elements.Remove(n);
094:             return true;
095:         }
096: 
097:         // comparison operators
098:         public static bool operator==(IntegerSet s1, IntegerSet s2)
099:         {
100:             return s1.Equals(s2);
101:         }
102: 
103:         public static bool operator!=(IntegerSet s1, IntegerSet s2)
104:         {
105:             return !(s1 == s2);
106:         }
107: 
108:         public static bool operator<=(IntegerSet s1, IntegerSet s2)
109:         {
110:             // compare both sets element per element
111:             for (int i = 0; i < s1.Size; i++)
112:                 if (!s2.Contains(s1[i]))
113:                     return false;
114: 
115:             return true;
116:         }
117: 
118:         public static bool operator>=(IntegerSet s1, IntegerSet s2)
119:         {
120:             return s2 <= s1;
121:         }
122: 
123:         public static bool operator<(IntegerSet s1, IntegerSet s2)
124:         {
125:             return (s1 <= s2) && (s1 != s2);
126:         }
127: 
128:         public static bool operator>(IntegerSet s1, IntegerSet s2)
129:         {
130:             return !(s1 <= s2);
131:         }
132: 
133:         // conversion operator
134:         public static implicit operator IntegerSet(int n)
135:         {
136:             IntegerSet s = new IntegerSet();
137:             s.Insert(n);
138:             return s;
139:         }
140: 
141:         // set theory specific operators
142:         public static IntegerSet operator+(IntegerSet s1, IntegerSet s2)
143:         {
144:             IntegerSet s = (IntegerSet)s1.Clone();
145:             for (int i = 0; i < s2.Size; i++)
146:                 s.Insert(s2.elements[i]);
147: 
148:             return s;
149:         }
150: 
151:         public static IntegerSet operator-(IntegerSet s1, IntegerSet s2)
152:         {
153:             IntegerSet s = (IntegerSet)s1.Clone();
154:             for (int i = 0; i < s2.Size; i++)
155:                 s.Remove(s2.elements[i]);
156: 
157:             return s;
158:         }
159: 
160:         public static IntegerSet operator^(IntegerSet s1, IntegerSet s2)
161:         {
162:             IntegerSet s = new IntegerSet();
163: 
164:             for (int i = 0; i < s1.Size; i++)
165:             {
166:                 int n = s1.elements[i];
167:                 if (s2.Contains(n))
168:                     s.Insert(n);
169:             }
170: 
171:             return s;
172:         }
173: 
174:         // contract with base class 'Object'
175:         public override bool Equals(Object o)
176:         {
177:             if (!(o is IntegerSet))
178:                 return false;
179: 
180:             IntegerSet s = (IntegerSet)o;
181: 
182:             // compare sizes
183:             if (this.Size != s.Size)
184:                 return false;
185: 
186:             // compare both sets element per element
187:             for (int i = 0; i < this.Size; i++)
188:             {
189:                 if (s.Contains(this.elements[i]))
190:                     continue;
191: 
192:                 return false;
193:             }
194: 
195:             return true;
196:         }
197: 
198:         public override String ToString()
199:         {
200:             StringBuilder sb = new StringBuilder();
201:             sb.Append('{');
202:             for (int i = 0; i < this.elements.Count; i++)
203:             {
204:                 sb.Append(this.elements[i]);
205:                 if (i < this.elements.Count - 1)
206:                     sb.Append(',');
207:             }
208:             sb.AppendFormat("{0}[{1}]", '}', this.elements.Count);
209:             return sb.ToString();
210:         }
211: 
212:         public override int GetHashCode()
213:         {
214:             return this.elements.GetHashCode();
215:         }
216: 
217:         // implementation of interface 'ICloneable'
218:         public Object Clone()
219:         {
220:             return new IntegerSet(this.elements);
221:         }
222: 
223:         // implementation of interface 'IEnumerable'
224:         public IEnumerator GetEnumerator()
225:         {
226:             for (int i = 0; i < this.elements.Count; i++)
227:                 yield return this.elements[i];
228:         }
229:     }
230: }

Beispiel 4. Klasse IntegerSet: Implementierung mit einem List<int>-Objekt.