A Set Class? [Ari Weinstein]
Recently, I have heard a number of requests for the addition of a Set<T> class to the System.Collection.Generic namespace. Basic implementation of this class that implements only ICollection<T> would cover all the etremely vital operations a set should implement, but that would just be a weak List<T>. We want to cover more interesting functionality; at least Union, Intersect, Difference, Subset, and Disjoint.
While any person using set would expect these operations from a set class, there are many additional interesting options. Of them are symmetric difference, mapping/correspondence, predicates, min/max, and powersets. Does anyone out there need so much goodness, or is it a bit more than what you would need?
Other questions were more centered around the implementation. A set based on a hash would have extremely good performance with near-constant insert and remove, but would have a slow search time O(n). An ordered set, on the other hand, would probably take O(log n) for insert, search, and remove. This means that for most applications, the unordered list provides better results. Of course, the speed of these operations has serious impact on all of the other set operations. We may implement both.
So again, to solicit some more user comments (and thanks for the past ones!):
· Would the addition of a set class to the BCL make sense for the programs you are writing? Would you rather see something else implemented?
· How much functionality would you like to see in the class; do the members in the prototype below satisfy your needs, or are you looking for more (or less)?
· Do you see yourself using sets for ordered or unordered collections of values, or both?
Here's the source for a simple program that does some basic operation on odd and even sets of integers, it highlights the most basic operations one may want to do with a set:
Check it out and respond up here or send me an email at ArielW@microsoft.com!
using
System;
using
System.Collections;
using
System.Collections.Generic;
class
Starter{
static void Main(){
/* Produces the Following output:
Set of even integers under 10:
0
2
4
6
8
Set of odd integers under 10:
1
3
5
7
9
Do the even and odd sets intesect?
no
Even union odd integers:
0
2
4
6
8
1
3
5
7
9
Are even integers a subset of all integers?
yes
Are all integers a subset of even integers?
no
Difference of All integers from Odd integers:
0
2
4
6
8
*/
Set<
int> EvenSet = new Set<int>();
Set<
int> OddSet = new Set<int>();
for(int i=0; i<10; ++i){
if (i % 2 == 0)
EvenSet.Add(i);
else
OddSet.Add(i);
}
Console.WriteLine("Set of even integers under 10:");
foreach (int i in EvenSet)
Console.WriteLine("\t" + i);
Console.WriteLine("\nSet of odd integers under 10:");
foreach (int i in OddSet)
Console.WriteLine("\t" + i);
Console.WriteLine("\nDo the even and odd sets intesect?");
if(EvenSet.IntersectsSet(OddSet))
Console.WriteLine("\tyes");
else
Console.WriteLine("\tno");
Console.WriteLine("\nEven union odd integers:");
Set<
int> EvenAndOddSet = EvenSet.Union(OddSet);
foreach(int i in EvenAndOddSet)
Console.WriteLine("\t" + i);
Console.WriteLine("\nAre even integers a subset of all integers?");
if (EvenSet.IsSubsetOf(EvenAndOddSet))
Console.WriteLine("\tyes");
else
Console.WriteLine("\tno");
Console.WriteLine("\nAre all integers a subset of even integers?");
if (EvenAndOddSet.IsSubsetOf(EvenSet))
Console.WriteLine("\tyes");
else
Console.WriteLine("\tno");
Console.WriteLine("\nDifference of All integers from Odd integers:");
foreach (int i in EvenAndOddSet.Difference(OddSet))
Console.WriteLine("\t" + i);
}
}
public
class Set<T> : ICollection<T>{
private List<T> list;
public Set()
{
list =
new List<T>();
}
//
//ICollection<T> methods
//
public void Add(T item)
{
if(!list.Contains(item))
list.Add(item);
}
public void Clear()
{
list.Clear();
}
public bool Contains(T item)
{
return list.Contains(item);
}
public void CopyTo(T[] array, int arrayIndex)
{
list.CopyTo(array, arrayIndex);
}
public bool Remove(T item)
{
return list.Remove(item);
}
public int Count
{
get {return list.Count;}
}
public bool IsReadOnly
{
get { return false; }
}
IEnumerator System.Collections.IEnumerable.GetEnumerator()
{
// TODO: Add Class1.System.Collections.IEnumerable.GetEnumerator implementation
return list.GetEnumerator();
}
IEnumerator<T> System.Collections.Generic.IEnumerable<T>.GetEnumerator()
{
return list.GetEnumerator();
}
public Set<T> Union(Set<T> otherSet)
{
Set<T> UnionSet =
new Set<T>();
foreach (T item in this)
UnionSet.Add(item);
foreach (T item in otherSet)
UnionSet.Add(item);
return UnionSet;
}
public Set<T> Intersect(Set<T> otherSet)
{
Set<T> IntersectSet =
new Set<T>();
foreach (T item in this)
if(otherSet.Contains(item))
IntersectSet.Add(item);
return IntersectSet;
}
public Set<T> Difference(Set<T> otherSet){
Set<T> DifferenceSet =
new Set<T>();
foreach (T item in this)
DifferenceSet.Add(item);
foreach (T item in otherSet)
DifferenceSet.Remove(item);
return DifferenceSet;
}
public bool IsSubsetOf(Set<T> otherSet){
foreach (T item in this)
if(!otherSet.Contains(item))
return false;
return true;
}
public bool IntersectsSet(Set<T> otherSet)
{
return !IsDisjointFrom(otherSet);
}
public bool IsDisjointFrom(Set<T> otherSet){
foreach (T item in this)
if(otherSet.Contains(item))
return false;
return true;
}
}