[ Team LiB ] |
Recipe 10.8 Creating a Set ObjectProblemYou need an object that contains a group of unordered objects. This object containing a set of data must be able to be compared to other objects containing sets of data, as well as have the following actions performed on them:
SolutionCreate a Set object, shown here: using System; using System.Collections; using System.Text; public class Set : IEnumerable { private ArrayList internalSet = new ArrayList( ); public int Count { get {return (internalSet.Count);} } public object this[int index] { get { return (internalSet[index]); } set { if (internalSet.Contains(value)) { throw (new ArgumentException( "Duplicate object cannot be added to this set.")); } else { internalSet[index] = value; } } } public void Add(object obj) { if (internalSet.Contains(obj)) { throw (new ArgumentException( "Duplicate object cannot be added to this set.")); } else { internalSet.Add(obj); } } public void Remove(object obj) { if (internalSet.Contains(obj)) { throw (new ArgumentException("Object cannot be removed from " + "this set because it does not exist in this set.")); } else { internalSet.Remove(obj); } } public void RemoveAt(int index) { internalSet.RemoveAt(index); } public bool Contains(object obj) { return (internalSet.Contains(obj)); } public static Set operator |(Set lhs, Set rhs) { return (lhs.UnionOf(rhs)); } public Set UnionOf(Set set) { Set unionSet = new Set( ); Set sourceSet = null; Set 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 operator &(Set lhs, Set rhs) { return (lhs.IntersectionOf(rhs)); } public Set IntersectionOf(Set set) { Set intersectionSet = new Set( ); Set sourceSet = null; Set 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 operator ^(Set lhs, Set rhs) { return (lhs.DifferenceOf(rhs)); } public Set DifferenceOf(Set set) { Set differenceSet = new Set( ); // 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 lhs, Set rhs) { return (lhs.Equals(rhs)); } public static bool operator !=(Set lhs, Set rhs) { return (!lhs.Equals(rhs)); } public override bool Equals(object obj) { bool isEquals = false; if (obj != null) { if (obj is Set) { if (this.Count == ((Set)obj).Count) { if (this.IsSubsetOf((Set)obj) && ((Set)obj).IsSubsetOf(this)) { isEquals = true; } } } } return (isEquals); } public override int GetHashCode( ) { return (internalSet.GetHashCode( )); } public bool IsSubsetOf(Set set) { for (int index = 0; index < this.Count; index++) { if (!set.Contains(internalSet[index])) { return (false); } } return (true); } public bool IsSupersetOf(Set 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( ) { return(new SetEnumerator(this)); } // Nested enumerator class public class SetEnumerator : IEnumerator { public SetEnumerator(Set theSet) { setObj = theSet; } private Set setObj; private int index = -1; public bool MoveNext( ) { index++; if (index >= setObj.Count) { return(false); } else { return(true); } } public void Reset( ) { index = -1; } public object Current { get{return(setObj[index]);} } } } The methods defined in Table 10-9 are of particular interest to using a Set object.
The following code illustrates the use of the Set class: public static void TestSet( ) { Set set1 = new Set( ); Set set2 = new Set( ); Set set3 = new Set( ); 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 (object 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( )); } DiscussionSets are containers that hold a group of homogeneous object types. Various mathematical operations can be performed on sets, including the following:
The Set class wraps an ArrayList (InternalSet), which contains all elements of that set. Many of the methods exposed by the Set class are delegated to the internalSet ArrayList. Of these wrapped methods, the Add method requires some discussion. This method prevents a duplicate object from being added to the Set object. This is a property of sets—no set may contain duplicate elements at any time. Calling the Contains method of the internalSet ArrayList, to determine whether the new object is already contained in this Set object, performs this check. This check is also performed in the set accessor of the indexer. The following code creates and populates two Set objects: Set set1 = new Set( ); Set set2 = new Set( ); 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 with which to union this Set. The Set 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 objects or both Set objects. The following code shows how both of these operations are performed: Set 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 objects: the first is to use the IntersectionOf method; and 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 A and Set B in order for it to be placed in the resulting Set object. The following code demonstrates the intersection operation: Set 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 resultingDiffSet = set1.DifferenceOf(set2); resultingDiffSet = set1 ^ set2; The subset operation is only performed 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 AlsoSee the "ArrayList Class," "Overloadable Operators," and "Operator Overloading Tutorial" topics in the MSDN documentation. |
[ Team LiB ] |