Recipe 11.8. Creating a Set Object Problem You need an object that contains a group of unordered objects. This object must be able to be compared to other objects containing sets of data. In addition, the two must be able to have the following actions performed on them: Union of the items contained by the two objects containing sets of data Intersection of the items contained by the two objects containing sets of data Difference of the items contained by the two objects containing sets of data
Solution Create a Set<T> object, the code for which is shown in Example 11-17. Example 11-17. Set class using System; using System.Collections; using System.Collections.Generic; using System.Text; public class Set<T> : IEnumerable<T> { private List<T> internalSet = new List<T>(); public int Count { get {return (internalSet.Count);} } public T this[int index] { get { return (internalSet[index]); } set { if (internalSet.Contains(value)) { throw (new ArgumentException( "Duplicate object cannot be added to this set.", "index")); } else { internalSet[index] = value; } } } public void Add(T obj) { if (internalSet.Contains(obj)) { throw (new ArgumentException( "Duplicate object cannot be added to this set.", "obj")); } else { internalSet.Add(obj); } } public void Remove(T obj) { if (!internalSet.Contains(obj)) { throw (new ArgumentException("Object cannot be removed from " + "this set because it does not exist in this set.", "obj")); } else { internalSet.Remove(obj); } } public void RemoveAt(int index) { internalSet.RemoveAt(index); } public bool Contains(T obj) { return (internalSet.Contains(obj)); } public static Set<T> operator |(Set<T> lhs, Set<T> rhs) { return (lhs.UnionOf(rhs)); } public Set<T> UnionOf(Set<T> set) { Set<T> unionSet = new Set<T>(); Set<T> sourceSet = null; Set<T> mergeSet = null; if (set.Count > this.Count) // An optimization { sourceSet = set; mergeSet = this; } else { sourceSet = this; mergeSet = set; } // Initialize unionSet with the entire SourceSet. for (int index = 0; index < sourceSet.Count; index++) { unionSet.Add(sourceSet.internalSet[index]); } // mergeSet OR sourceSet for (int index = 0; index < mergeSet.Count; index++) { if (!sourceSet.Contains(mergeSet.internalSet[index])) { unionSet.Add(mergeSet.internalSet[index]); } } return (unionSet); } public static Set<T> operator &(Set<T> lhs, Set<T> rhs) { return (lhs.IntersectionOf(rhs)); } public Set<T> IntersectionOf(Set<T> set) { Set<T> intersectionSet = new Set<T>(); Set<T> sourceSet = null; Set<T> mergeSet = null; if (set.Count > this.Count) // An optimization { sourceSet = set; mergeSet = this; } else { sourceSet = this; mergeSet = set; } // mergeSet AND sourceSet for (int index = 0; index < mergeSet.Count; index++) { if (sourceSet.Contains(mergeSet.internalSet[index])) { intersectionSet.Add(mergeSet.internalSet[index]); } } return (intersectionSet); } public static Set<T> operator ^(Set<T> lhs, Set<T> rhs) { return (lhs.DifferenceOf(rhs)); } public Set<T> DifferenceOf(Set<T> set) { Set<T> differenceSet = new Set<T>(); // mergeSet XOR sourceSet for (int index = 0; index < set.Count; index++) { if (!this.Contains(set.internalSet[index])) { differenceSet.Add(set.internalSet[index]); } } for (int index = 0; index < this.Count; index++) { if (!set.Contains(internalSet[index])) { differenceSet.Add(internalSet[index]); } } return (differenceSet); } public static bool operator ==(Set<T> lhs, Set<T> rhs) { return (lhs.Equals(rhs)); } public static bool operator !=(Set<T> lhs, Set<T> rhs) { return (!lhs.Equals(rhs)); } public override bool Equals(object obj) { bool isEquals = false; if (obj != null) { if (obj is Set<T>) { if (this.Count == ((Set<T>)obj).Count) { if (this.IsSubsetOf((Set<T>)obj) && ((Set<T>)obj).IsSubsetOf(this)) { isEquals = true; } } } } return (isEquals); } public override int GetHashCode() { return (internalSet.GetHashCode()); } public bool IsSubsetOf(Set<T> set) { for (int index = 0; index < this.Count; index++) { if (!set.Contains(internalSet[index])) { return (false); } } return (true); } public bool IsSupersetOf(Set<T> set) { for (int index = 0; index < set.Count; index++) { if (!this.Contains(set.internalSet[index])) { return (false); } } return (true); } public string DisplaySet() { if (this.Count == 0) { return ("{}"); } else { StringBuilder displayStr = new StringBuilder("{ "); for (int index = 0; index < (this.Count - 1); index++) { displayStr.Append(internalSet[index]); displayStr.Append(", "); } displayStr.Append(internalSet[internalSet.Count - 1]); displayStr.Append(" }"); return (displayStr.ToString()); } } public IEnumerator GetEnumerator() { for (int cntr = 0; cntr < internalSet.Count; cntr++) { yield return (internalSet[cntr]); } } IEnumerator<T> IEnumerable<T>.GetEnumerator() { for (int cntr = 0; cntr < internalSet.Count; cntr++) { yield return (internalSet[cntr]); } } }
|
The methods defined in Table 11-9 are of particular interest to using a Set<T> object. Table 11-9. Members of the Set<T> classMember | Description |
|---|
Count property | Read-only property to return the number of objects within this Set<T> object. Its syntax is: int Count {get;}
| Indexer | Allows the Set<T> object to operate in a manner similar to an array. Its syntax is: this[int index] {get; set;}
| Add method | Add a new object to the current Set<T> object. Its syntax is: Add(T obj)
where obj is the object of type T to add to this Set. | Remove method | Removes an existing object from the current Set<T> object. Its syntax is: Remove(T obj)
where obj is the object of type T to remove from this Set. | RemoveAt method | Removes an existing object from the current Set<T> object using an index. Its syntax is: Add(int index)
where index is the index where the object to be removed is stored. | Contains method | Returns a Boolean indicating whether the object passed in exists within this Set<T> object. If a true is returned, the object exists; otherwise, it does not. Its syntax is: Contains(T obj)
where obj is the object of type T to be searched for. | UnionOf method | Performs a union operation on the current Set<T> object and a second Set<T> object. A new Set<T> object is returned containing the union of these two Set<T> objects. Its syntax is: UnionOf(Set<T> set)
where set is the second Set<T> object. | Overloaded | operator | This operator delegates its work to the UnionOf method. | IntersectionOf method | Performs an intersection operation on the current Set<T> object and a second Set<T> object. A new Set<T> object is returned containing the intersection of these two Set<T> objects. Its syntax is: IntersectionOf(Set<T> set)
where set is the second Set<T> object. | Overloaded & operator | This operator delegates its work to the IntersectionOf method. | DifferenceOf method | Performs a difference operation on the current Set<T> object and a second Set<T> object. A new Set<T> object is returned containing the difference of these two Set<T> objects. Its syntax is: DifferenceOf(Set<T> set)
where set is the second Set<T> object. | Overloaded ^ operator | This operator delegates its work to the DifferenceOf method. | Overloaded Equals method | Returns a Boolean indicating whether a second Set<T> object is equal to the current Set<T> object. Its syntax is: Equals(object obj)
where obj is the second Set<T> object. | Overloaded == operator | This operator delegates its work to the Equals method. | Overloaded != operator | This operator delegates its work to the Equals method. However, this operator takes the inverse of the Boolean returned from the Equals method and returns this new value. | Overridden GetHashCode method | Returns the hash code of the internal List<T> used to hold the objects contained in this Set<T> object. Its syntax is: GetHashCode( )
| IsSubsetOf method | Returns a Boolean indicating whether the current Set<T> object is a subset of a second Set<T> object. Its syntax is: IsSubsetOf(Set<T> set)
where set is the second Set<T> object. | IsSupersetOf method | Returns a Boolean indicating whether the current Set<T> object is a superset of a second Set<T> object. Its syntax is: IsSupersetOf(Set<T> set)
where set is the second Set<T> object. | DisplaySet method | Displays all objects within the current Set<T> object in the following format: {Obj1, Obj2, Obj3, …}
Its syntax is: DisplaySet( )
|
Example 11-18. Using the Set <T> class Example 11-18. Using the Set <T> class public static void TestSet() { Set<int> set1 = new Set<int>(); Set<int> set2 = new Set<int>(); Set<int> set3 = new Set<int>(); set1.Add(1); set1.Add(2); set1.Add(3); set1.Add(4); set1.Add(5); set1.Add(6); set2.Add(-10); set2.Add(2); set2.Add(40); set3.Add(3); set3.Add(6); foreach (int o in set2) { Console.WriteLine(o.ToString()); } Console.WriteLine("set1.Contains(2): " + set1.Contains(2)); Console.WriteLine("set1.Contains(0): " + set1.Contains(0)); Console.WriteLine("\r\nset1.Count: " + set1.Count); Console.WriteLine(); Console.WriteLine("set1.DisplaySet: " + set1.DisplaySet()); Console.WriteLine("set2.DisplaySet: " + set2.DisplaySet()); Console.WriteLine("set3.DisplaySet: " + set3.DisplaySet()); Console.WriteLine(); Console.WriteLine("set1.UnionOf(set2): " + set1.UnionOf(set2).DisplaySet()); Console.WriteLine("set1.IntersectionOf(set2): " + set1.IntersectionOf(set2).DisplaySet()); Console.WriteLine("set1.DifferenceOf(set2): " + set1.DifferenceOf(set2).DisplaySet()); Console.WriteLine("set1 | set2: " + (set1 | set2).DisplaySet()); Console.WriteLine("set1 & set2: " + (set1 & set2).DisplaySet()); Console.WriteLine("set1 ^ set2: " + (set1 ^ set2).DisplaySet()); Console.WriteLine("set1.Equals(set2): " + set1.Equals(set2)); Console.WriteLine("set1 == set2: " + (set1 == set2)); Console.WriteLine("set1 != set2: " + (set1 != set2)); Console.WriteLine("set1.IsSubsetOf(set2): " + set1.IsSubsetOf(set2)); Console.WriteLine("set1.IsSupersetOf(set2): " + set1.IsSupersetOf(set2)); Console.WriteLine(); Console.WriteLine("set2.UnionOf(set1): " + set2.UnionOf(set1).DisplaySet()); Console.WriteLine("set2.IntersectionOf(set1): "+ set2.IntersectionOf(set1).DisplaySet()); Console.WriteLine("set2.DifferenceOf(set1): " + set2.DifferenceOf(set1).DisplaySet()); Console.WriteLine("set2.Equals(set1): " + set2.Equals(set1)); Console.WriteLine("set2 == set1): " + (set2 == set1)); Console.WriteLine("set2 != set1): " + (set2 != set1)); Console.WriteLine("set2.IsSubsetOf(set1): " + set2.IsSubsetOf(set1)); Console.WriteLine("set2.IsSupersetOf(set1): " + set2.IsSupersetOf(set1)); Console.WriteLine(); Console.WriteLine("set3.UnionOf(set1): " + set3.UnionOf(set1).DisplaySet()); Console.WriteLine("set3.IntersectionOf(set1): " + set3.IntersectionOf(set1).DisplaySet()); Console.WriteLine("set3.DifferenceOf(set1): " + set3.DifferenceOf(set1).DisplaySet()); Console.WriteLine("set3.Equals(set1): " + set3.Equals(set1)); Console.WriteLine("set3 == set1: " + (set3 == set1)); Console.WriteLine("set3 != set1: " + (set3 != set1)); Console.WriteLine("set3.IsSubsetOf(set1): " + set3.IsSubsetOf(set1)); Console.WriteLine("set3.IsSupersetOf(set1): " + set3.IsSupersetOf(set1)); Console.WriteLine("set1.IsSubsetOf(set3): " + set1.IsSubsetOf(set3)); Console.WriteLine("set1.IsSupersetOf(set3): " + set1.IsSupersetOf(set3)); Console.WriteLine(); Console.WriteLine("set3.UnionOf(set2): " + set3.UnionOf(set2).DisplaySet()); Console.WriteLine("set3.IntersectionOf(set2): " + set3.IntersectionOf(set2).DisplaySet()); Console.WriteLine("set3.DifferenceOf(set2): " + set3.DifferenceOf(set2).DisplaySet()); Console.WriteLine("set3 | set2: " + (set3 | set2).DisplaySet()); Console.WriteLine("set3 & set2: " + (set3 & set2).DisplaySet()); Console.WriteLine("set3 ^ set2: " + (set3 ^ set2).DisplaySet()); Console.WriteLine("set3.Equals(set2): " + set3.Equals(set2)); Console.WriteLine("set3 == set2: " + (set3 == set2)); Console.WriteLine("set3 != set2: " + (set3 != set2)); Console.WriteLine("set3.IsSubsetOf(set2): " + set3.IsSubsetOf(set2)); Console.WriteLine("set3.IsSupersetOf(set2): " + set3.IsSupersetOf(set2)); Console.WriteLine(); Console.WriteLine("set3.Equals(set3): " + set3.Equals(set3)); Console.WriteLine("set3 == set3: " + (set3 == set3)); Console.WriteLine("set3 != set3: " + (set3 != set3)); Console.WriteLine("set3.IsSubsetOf(set3): " + set3.IsSubsetOf(set3)); Console.WriteLine("set3.IsSupersetOf(set3): " + set3.IsSupersetOf(set3)); Console.WriteLine("set1[1]: " + set1[1].ToString()); set1[1] = 100; set1.RemoveAt(1); set1.RemoveAt(2); Console.WriteLine("set1: " + set1.DisplaySet()); }
|
The output for this method is shown here: -10 2 40 set1.Contains(2): True set1.Contains(0): False set1.Count: 6 set1.DisplaySet: { 1, 2, 3, 4, 5, 6 } set2.DisplaySet: { -10, 2, 40 } set3.DisplaySet: { 3, 6 } set1.UnionOf(set2): { 1, 2, 3, 4, 5, 6, -10, 40 } set1.IntersectionOf(set2): { 2 } set1.DifferenceOf(set2): { -10, 40, 1, 3, 4, 5, 6 } set1 | set2: { 1, 2, 3, 4, 5, 6, -10, 40 } set1 & set2: { 2 } set1 ^ set2: { -10, 40, 1, 3, 4, 5, 6 } set1.Equals(set2): False set1 == set2: False set1 != set2: True set1.IsSubsetOf(set2): False set1.IsSupersetOf(set2): False set2.UnionOf(set1): { 1, 2, 3, 4, 5, 6, -10, 40 } set2.IntersectionOf(set1): { 2 } set2.DifferenceOf(set1): { 1, 3, 4, 5, 6, -10, 40 } set2.Equals(set1): False set2 == set1): False set2 != set1): True set2.IsSubsetOf(set1): False set2.IsSupersetOf(set1): False set3.UnionOf(set1): { 1, 2, 3, 4, 5, 6 } set3.IntersectionOf(set1): { 3, 6 } set3.DifferenceOf(set1): { 1, 2, 4, 5 } set3.Equals(set1): False set3 == set1: False set3 != set1: True set3.IsSubsetOf(set1): True set3.IsSupersetOf(set1): False set1.IsSubsetOf(set3): False set1.IsSupersetOf(set3): True set3.UnionOf(set2): { -10, 2, 40, 3, 6 } set3.IntersectionOf(set2): {} set3.DifferenceOf(set2): { -10, 2, 40, 3, 6 } set3 | set2: { -10, 2, 40, 3, 6 } set3 & set2: {} set3 ^ set2: { -10, 2, 40, 3, 6 } set3.Equals(set2): False set3 == set2: False set3 != set2: True set3.IsSubsetOf(set2): False set3.IsSupersetOf(set2): False set3.Equals(set3): True set3 == set3: True set3 != set3: False set3.IsSubsetOf(set3): True set3.IsSupersetOf(set3): True set1[1]: 2 set1: { 1, 3, 5, 6 }
Discussion Sets are containers that hold a group of homogeneous object types. Various mathematical operations can be performed on sets, including the following:
Union -
(A  B) Combines all elements of set A and set B into a resulting Set<T> object. If an object exists in both sets, the resulting unioned Set<T> object contains only one of those elements, not both.
Intersection -
(A  B) Combines all elements of set A and set B that are common to both A and B into a resulting Set<T> object. If an object exists in one set and not the other, the element is not added to the intersectioned Set<T> object.
Difference -
(A-B) Combines all elements of set A, except for the elements that are also members of set B, into a resulting Set<T> object. If an object exists in both sets A and B, it is not added to the final differenced Set<T> object. The difference is equivalent to taking the union of both sets and the intersection of both sets and then removing all elements in the unioned set that exist in the intersectioned set.
Subset -
(A  B) Returns TRue if all elements of set A are contained in a second set B; otherwise, it returns false. Set B may contain elements not found in A.
Superset -
(A  B) Returns true if all elements of set A are contained in a second set B; otherwise, it returns false. Set A may contain elements not found in B.
Equivalence -
(A == B) Returns true if both Set<T> objects contain the same number of elements and the same value for each element; otherwise, it returns false. This is equivalent to stating that (A B) and (B A). Nonequivalence is defined by the != operator. Note that the .NET Equals method can be used to test for equivalence.
The Set<T> class wraps a List<T> (internalSet), which contains all elements of that set. Many of the methods exposed by the Set<T> class are delegated to the internalSet List<T>. Of these wrapped methods, the Add method requires some discussion. This method prevents a duplicate object from being added to the Set<T> object. This is a property of setsno set may contain duplicate elements at any time. Calling the Contains method of the internalSet List<T>, to determine whether the new object is already contained in this Set<T> object, performs this check. This check is also performed in the set accessor of the indexer. The following code creates and populates two Set<T> objects: Set<int> set1 = new Set<int>(); Set<int> set2 = new Set<int>(); set1.Add(1); set1.Add(2); set1.Add(3); set1.Add(4); set1.Add(5); set1.Add(6); set2.Add(-10); set2.Add(2); set2.Add(40);
The union operation can be performed in one of two ways. The first is to use the UnionOf method and pass in a Set<T> with which to union this Set<T>. The Set<T> class also overrides the | operator to provide this same functionality. Notice that the OR operator is shorthand for the union operation. Essentially, the resulting set contains elements that exist in either of the two Set<T> objects or both Set<T> objects. The following code shows how both of these operations are performed: Set<int> resultingUnionSet = set1.UnionOf(set2); resultingUnionSet = set1 | set2;
The intersection operation is set up similarly to the union operation. There are two ways to perform an intersection between two Set<T> objects: the first is to use the IntersectionOf method; the second is to use the overloaded & operator. Once again, notice that the logic of the AND operator is the same as the intersection operation. Essentially, an element must be in both Set<T> A and Set<T> B in order for it to be placed in the resulting Set<T> object. The following code demonstrates the intersection operation: Set<int> resultingIntersectSet = set1.IntersectionOf(set2); resultingIntersectSet = set1 & set2;
The difference operation is performed either through the overloaded ^ operator or the DifferenceOf method. Notice that the XOR operation is similar to taking the difference of two sets. Essentially, only elements in either set, but not both, are placed in the resulting set. The following code demonstrates the difference operation: Set<int> resultingDiffSet = set1.DifferenceOf(set2); resultingDiffSet = set1 ^ set2;
The subset operation is performed only through a single method called IsSubsetOf. The superset operation is also performed using a single method called IsSupersetOf. The following code demonstrates these two operations: bool isSubset = set1.IsSubsetOf(set2); bool isSuperset = set1.IsSupersetOf(set2);
The equivalence operation is performed using either the overloaded == operator or the Equals method. Since the == operator was overloaded, the != operator must also be overloaded. The != operator returns the inverse of the == operator or Equals method. The following code demonstrates these three operations: bool isEqual = set1.Equals(set2); isEqual = set1 == set2; bool isNotEqual = set1 != set2;
See Also See the "List<T> Class," "Overloadable Operators," and "Operator Overloading Tutorial" topics in the MSDN documentation. |
