Recipe 10.8 Creating a Set Object

Problem

You 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:

• 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 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.

Table 10-9. Members of the Set class

Member	Description
Count property	Read-only property to return the number of objects within this Set object. Its syntax is: int Count {get;}
Indexer	Allows the Set 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 object. Its syntax is: Add(object obj) where obj is the object to add to this Set.
Remove method	Removes an existing object from the current Set object. Its syntax is: Remove(object obj) where obj is the object to remove from this Set.
RemoveAt method	Removes an existing object from the current Set 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 object. If a true is returned, the object exists; otherwise, it does not. Its syntax is: Contains(int obj) where obj is the object to be searched for.
BinarySearch method	Returns the object searched for, if the object passed in exists within this Set object. Its syntax is: BinarySearch(int obj) where obj is the object to be searched for.
UnionOf method	Performs a union operation on the current Set object and a second Set object. A new Set object is returned containing the union of these two Set objects. Its syntax is: UnionOf(Set set) where set is the second Set object.
Overloaded | operator	This operator delegates its work to the UnionOf method.
IntersectionOf method	Performs an intersection operation on the current Set object and a second Set object. A new Set object is returned containing the intersection of these two Set objects. Its syntax is: IntersectionOf(Set set) where set is the second Set object.
Overloaded & operator	This operator delegates its work to the IntersectionOf method.
DifferenceOf method	Performs a difference operation on the current Set object and a second Set object. A new Set object is returned containing the difference of these two Set objects. Its syntax is: DifferenceOf(Set set) where set is the second Set object.
Overloaded ^ operator	This operator delegates its work to the DifferenceOf method.
Overloaded Equals method	Returns a Boolean indicating whether a second Set object is equal to the current Set object. Its syntax is: Equals(object obj) where obj is the second Set 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 ArrayList used to hold the objects contained in this Set object. Its syntax is: GetHashCode( )
IsSubsetOf method	Returns a Boolean indicating whether the current Set object is a subset of a second Set object. Its syntax is: IsSubsetOf(Set set) where set is the second Set object.
IsSupersetOf method	Returns a Boolean indicating whether the current Set object is a superset of a second Set object. Its syntax is: IsSupersetOf(Set set) where set is the second Set object.
DisplaySet method	Displays all objects within the current Set object in the following format: {Obj1, Obj2, Obj3, ...} Its syntax is: DisplaySet( )

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( ));
}

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 object. If an object exists in both sets, the resulting unioned Set 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 object. If an object exists in one set and not the other, the element is not added to the intersectioned Set 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 object. If an object exists in both sets A and B, it is not added to the final differenced Set 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 objects contain the same number and value of 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 could be used to test for equivalence.

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 Also

See the "ArrayList Class," "Overloadable Operators," and "Operator Overloading Tutorial" topics in the MSDN documentation.