Click here to Skip to main content
65,938 articles
CodeProject is changing. Read more.
Articles
(untagged)

Another C# sets this time generic ones

0.00/5 (No votes)
19 Feb 2006 1  
How to easily implement generic sets within C# for .NET Framework 2.0

Introduction

Hi everyone who's interested in what I hope is a fully functional "Delphi" sets implementation.

Background

I really needed some decent sets in C# and I came across the two very fine articles here. But those didn't satisfied me so I've written my own generic sets.. This time I hope it's a definite version.

Let's start somewhere

With my special kind of arrogance let's implement the class here: (Of course you can namespace it depending on your taste but I found it very practical this way :)

using System;
using System.Collections;
using System.Collections.Generic;

namespace System.Collections.Generic
{
    public class Set<T> : IEnumerable<T>
    {

Now we'll need something to store "set" values in:

private Dictionary<T, T> fItems = 
               new Dictionary<T, T>();

That's nice but there's more to make a functional sets. For example override C# operators to get all the comfort we deserve (and which Microsoft denied us).

So let's take one after another:

Somewhat this way may our "include element into set" operator be implemented:

public static Set<T> operator +(Set<T> pSource, T pElement)
{
    try
    {
        Set<T> result = new Set<T>();
        result = (Set<T>)pSource.MemberwiseClone();
        result.fItems[pElement] = default(T);
        return result;
    }
    catch (Exception E)
    {
        throw new Exception("Set<T> - INCLUDE" + 
              " operation : Error while" + 
              " including element into set", E);
    }
}

Do you think that this is not a C# language ? Do you think that this not a C# code? And it will never compile? Well I thought that myself for the first time.

Let's return to our code. Now we possible want to implement an "exclude" operator (which is similar):

public static Set<T> operator -(Set<T> pSource, T pElement)
{
    try
    {
        Set<T> result = new Set<T>();
        result = (Set<T>)pSource.MemberwiseClone();
        pSource.fItems.Remove(pElement);
        return result;
    }
    catch (Exception E)
    {
        throw new Exception("Set<T> - EXCLUDE" + 
              " operation : Error while" + 
              " excluding element from set", E);
    }
}

Ofcourse it wouldn't be sets without "contains" operator and it's counterpart "not contains" one:

public static Boolean operator ==(Set<T> pSource, T pElement)
{
    return pSource.fItems.ContainsKey(pElement);
}
   
public static Boolean operator !=(Set<T> pSource, T pElement)
{
    return !(pSource == pElement);
}

You might say that those are easy then I have to tell you.. yeah they really are. Ok. Now for some real code here. Because we still need set operators. And here they go. As a first one an "union" operator:

public static Set<T> operator +(Set<T> pSource, 
                                   Set<T> pDestiny)
{
     Set<T> result = new Set<T>();
     IEnumerator<T> listEnum = null;

     try
     {
         listEnum = pSource.fItems.Keys.GetEnumerator();
         listEnum.Reset();


         while (listEnum.MoveNext())
         {
             result.fItems[listEnum.Current] = default(T);
         }
     }
     catch (Exception E)
     {
         throw new Exception("Set<T> -" + 
               " UNION operation : Error while" + 
               " joining first set", E);
     }
     
     try
     {
         listEnum = pDestiny.fItems.Keys.GetEnumerator();
         listEnum.Reset();

         while (listEnum.MoveNext())
         {
             if (!pSource.fItems.ContainsKey(listEnum.Current))
             {
                 result.fItems[listEnum.Current] = default(T);
             }
         }
     }
     catch (Exception E)
     {
         throw new Exception("Set<T> - UNION" + 
               " operation : Error while" + 
               " joining second set", E);
     }
     
     return result;
}

And here goes.. yeah it's a "difference" operator:

public static Set<T> operator -(Set<T> pSource, 
                                   Set<T> pDestiny)
 {
     Set<T> result = new Set<T>();
     IEnumerator<T> listEnum = null;
     
     try
     {
         listEnum = pSource.fItems.Keys.GetEnumerator();
         listEnum.Reset();
         
         while (listEnum.MoveNext())
         {
             if (!pDestiny.fItems.ContainsKey(listEnum.Current))
             {
                 result.fItems[listEnum.Current] = default(T);
             }
         }
     }
     catch (Exception E)
     {
         throw new Exception("Set<T> - DIFFERENCE" + 
               " operation : Error while forward" + 
               " comparing two sets for difference", E);
     }
     
     try
     {
         listEnum = pDestiny.fItems.Keys.GetEnumerator();
         listEnum.Reset();
         
         while (listEnum.MoveNext())
         {
             if (!pSource.fItems.ContainsKey(listEnum.Current))
             {
                 result.fItems[listEnum.Current] = default(T);
             }
         }
     }
     catch (Exception E)
     {
         throw new Exception("Set<T> - DIFFERENCE" + 
               " operation : Error while backward " + 
               "comparing two sets for difference", E);
     }
     
     return result;
}

and that last but not in a way the least an "intersection" operator:

public static Set<T> operator *(Set<T> pSource, 
                                   Set<T> pDestiny)
{
     Set<T> result = new Set<T>();
     IEnumerator<T> listEnum = null;
     
     try
     {
         listEnum = pSource.fItems.Keys.GetEnumerator();
         listEnum.Reset();
       
         while (listEnum.MoveNext())
         {
             if (pDestiny.fItems.ContainsKey(listEnum.Current))
             {
                 result.fItems[listEnum.Current] = default(T);
             }
         }
     }
     catch (Exception E)
     {
         throw new Exception("Set<T> - INTERSECTION" + 
               " operation : Error while comparing " + 
               "two sets for intersection", E);
     }
  
     return result;
}

Now for some cream

Well we have the basics done and now.. that you're so good audience I'll give you some more :P One thing I've found really nice is indexing the set because sometimes you just want to know what elements are in the set and it's boring to go thru all the elements and test them for being inside the set. You all surely know where I'm heading. So now we're ready to implement an indexer:

public T this[int ItemIndex]
{
     get
     {
         if (ItemIndex < fItems.Keys.Count)
         {
             IEnumerator<T> listEnum = fItems.Keys.GetEnumerator();
             listEnum.Reset();
             
             for (int a = 0; a < fItems.Keys.Count; a++)
             {
                 if (a == ItemIndex)
                 {
                     return listEnum.Current;
                 }
                 listEnum.MoveNext();
             }
         }
      
         return default(T);
     } 
}

Another good thing is to have some intelligent constructors around when working with the classes. These'd do it:

public static Set<T> Empty()
{
     return new Set<T>();
}

public static Set<T> Define(params T[] pElements)
{
     Set<T> result = new Set<T>();
    
     foreach (T element in pElements)
     {
         result += element;
     }
 
     return result;
}

OK, mom, I'll do it!

So we have successfully added some operators and some specials and what's next.. Well not to lie you it's all. But we still have to implement some minor "may be/have to be" things. Such as the implementation of an interface we've declared in the beginning:

public IEnumerator<T> GetEnumerator()
{
     return fItems.Keys.GetEnumerator();
}

IEnumerator IEnumerable.GetEnumerator()
{
     return fItems.Keys.GetEnumerator();
}

And ofcourse it's a good habit to override some of the basal methods. Because we don't want the warnings to fly everywhere around:

public override bool Equals(object obj)
{
     return (this == (Set<T>)obj);
}

public override int GetHashCode()
{
     return base.GetHashCode();
}

public override string ToString()
{
     String result = string.Empty;
     IEnumerator<T> listEnum = null;
     
     try
     {
         listEnum = fItems.Keys.GetEnumerator();
         listEnum.Reset();
    
         while (listEnum.MoveNext())
         {
             if (result == string.Empty)
             {
                 result = listEnum.Current.ToString();
             }
             else
             {
                 result += "," + listEnum.Current.ToString();
             }
         }
        
         return ("{" + result + "}");
     }
     catch (Exception E)
     {
         throw new Exception("Set<T> - TOSTRING" + 
               " operation : Error while exporting" + 
               " set to string", E);
     }
}

Something's still missing

Let's take a look at some examples of how these little beast can be used:

// our testing sets make your Set<YourType>


Set<MyEnum> first = 
      Set<MyEnum>.Define(new MyEnum[] 
      { MyEnum.One, MyEnum.Two });
Set<MyEnum> second = 
      Set<MyEnum>.Define(new MyEnum[] 
      { MyEnum.Two, MyEnum.Three });
Set<MyEnum> result = null;

// flag of containment


Boolean contains = false;
result = first + second; // UNION


// now the result contains {One, Two, Three}

result = first - second; // DIFFERENCE


// now the result contains {One, Three}

result = first * second; // INTERSECTION


// now the result contains {Two} 

contains = first == MyEnum.Three;

// contains is now FALSE because

// it doesn't contain {Three}

 
first += MyEnum.Three; // INCLUDE

contains = first == MyEnum.Three;

// contains is now TRUE because

// we added {Three} before


first -= MyEnum.Three;
contains = first == MyEnum.Three;

// contains is now FALSE again because

// we deleted {Three} element

That's all for today I hope you'll find these sets practical for you or maybe they'll inspire you to make some better ones. I'll be checking the forum :))

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here