abstraction is a mechanism and practice to reduce and factor out details so that one can focus on a few concepts at a time.
Back in my college days, we studied this intently. The languages available at the time didn't support the concept as well as the languages do today. But we did the best we could using the languages that we had available.
One of my favorite courses was data structures, in that class we studied different ways to store data to achieve different goals. We studied, linked lists, stacks, queues and the like. We were given the opportunity to develop our own data structures based on the problem we were given.
The primary teaching language for teaching computer science at that time was Pascal, but we were exposed to many different languages. In my last semester, the teacher was pushing a class in the Ada language (a huge language developed by the DoD), on a whim I also took a class in an emerging language called C.
Although I've never heard of a job requesting experience in the Ada language, I'm grateful for the class. The Ada language was the first object oriented language we studied (this was 1986) and allowed advanced concepts like like operator overloading and generics. The Ada compilers were in beta testing at that time so actually developing a program in Ada was difficult, but the concepts were crucial.
Today, C# provides a lot of the same features that we studied back then, so I've taken a little bit of time to dig into generics. Generics are the ultimate level of abstraction because the algorithm is completely divorced from the data type. If you look at the concept of the simple List
But simple collections are not the only application of generics, any data structure that you may want create can be created such that the data structure and its associated operations are completely divorced from the class that is stored in it.
I'm sure there are thousands of implementations of the mathematical concept of sets out there, but this was one of the first generic data structure that I decided to implement. Below is the code, the namespace is a reference to my roots in the Pascal language...
For definition of some of the basic mathematical concepts check out Set theory basic concepts
using System;
using System.Collections.Generic;
using System.Text;
namespace ccg.paslib
{
public class Set<T>
{
List<T> _internallist = new List<T>();
// add a member
public void Add(T parm)
{
_internallist.Add(parm);
}
// remove a member
public void Remove(T parm)
{
_internallist.Remove(parm);
}
// is the supplied value a member of this set?
public bool Contains(T parm)
{
return _internallist.Contains(parm);
}
// returns the Union of two sets
public Set<T> Union(Set<T> parm)
{
Set<T> retval = new Set<T>();
foreach (T val in _internallist)
retval.Add(val);
foreach (T val in parm)
if (!retval.Contains(val))
retval.Add(val);
return retval;
}
// returns the intersection of two sets
public Set<T> Intersection(Set<T> parm)
{
Set<T> retval = new Set<T>();
foreach (T val in _internallist)
if (parm.Contains(val))
retval.Add(val);
return retval;
}
// returns the difference between two sets
public Set<T> Difference(Set<T> parm)
{
Set<T> retval = new Set<T>();
foreach (T val in _internallist)
if (!parm.Contains(val))
retval.Add(val);
return retval;
}
// return members that are in one set but not both
public Set<T> ExclusiveOr(Set<T> parm)
{
Set<T> retval = new Set<T>();
foreach (T s in this)
if (!parm.Contains(s))
retval += s;
foreach (T s in parm)
if (!this.Contains(s))
retval += s;
return retval;
}
// return an enumerator for the set
public List<T>.Enumerator GetEnumerator()
{
return _internallist.GetEnumerator();
}
// return the number of members in the set
public int Count
{
get { return _internallist.Count; }
}
#region operators
public static Set<T> operator +(Set<T> set, T value)
{
set.Add(value);
return set;
}
public static Set<T> operator +(Set<T> set1, Set<T> set2)
{
return set1.Union(set2);
}
public static Set<T> operator -(Set<T> set1, Set<T> set2)
{
return set1.Difference(set2);
}
public static Set<T> operator *(Set<T> set1, Set<T> set2)
{
return set1.Intersection(set2);
}
public static Set<T> operator ^(Set<T> set1, Set<T> set2)
{
return set1.ExclusiveOr(set2);
}
#endregion
}
// generic class to create an ordered pair of objects for the Catesian Product
public class OrderedPair<T, S>
{
public T A;
public S B;
}
// Generic static class to implement the catesian product
public class CartesianProduct<T,S>
{
public static Set<OrderedPair<T,S>> Product(Set<T> a,Set<S> b)
{
Set<OrderedPair<T,S>> retval = new Set<OrderedPair<T,S>>();
foreach(T i in a)
foreach(S j in b)
{
OrderedPair<T,S> value = new OrderedPair<T,S>();
value.A = i;
value.B = j;
retval.Add(value);
}
return retval;
}
}
}
So, how can this be used? Does the mathematical concept of a set have anything to do with software development? Absolutely....at its core, a relational database is based on set theory. Below are some of the NUnit tests that I wrote for testing this class.
[Test]
public void uniontest()
{
Set<Color> set1 = new Set<Color>();
Set<Color> set2 = new Set<Color>();
set1.Add(Color.Red);
set1.Add(Color.Blue);
set2.Add(Color.Green);
set2.Add(Color.White);
Setset3 = set1.Union(set2);
Assert.AreEqual(set3.Count, 4);
foreach (Color val in set3)
Assert.IsTrue(set1.Contains(val) || set2.Contains(val));
}
[Test]
public void intersectiontest()
{
Set<Color> set1 = new Set<Color>();
Set<Color> set2 = new Set<Color>();
set1.Add(Color.Red);
set1.Add(Color.Blue);
set2.Add(Color.Blue);
set2.Add(Color.Green);
set2.Add(Color.White);
Set<Color> set3 = set1.Intersection(set2);
Assert.IsTrue(set3.Count == 1);
foreach (Color val in set3)
Assert.IsTrue(val.Equals(Color.Blue));
}
[Test]
// test some of the operators
public void exclusiveortest()
{
Set<Color> set1 = new Set<Color>();
Set<Color> set2 = new Set<Color>();
set1 += Color.Red;
set1 += Color.Blue;
set2 += Color.Blue;
set2 += Color.Green;
set2 += Color.White;
Set<Color> set3 = set1 ^ set2;
Assert.IsTrue(set3.Count == 3);
Assert.IsTrue(set3.Contains(Color.Red));
Assert.IsTrue(set3.Contains(Color.Green));
Assert.IsTrue(set3.Contains(Color.White));
}
The OrderedPair<T, S> and CartesianProduct<T,S> classes are pretty interesting. Below is a test that I wrote for that class.
[Test]
public void caresianproducttest()
{
Set<DateTime> set1 = new Set<DateTime>();
for (int i = 0; i < 10; i++)
set1.Add(new DateTime(2009, 1, 1).AddDays(i));
Set<Color> set2 = new Set<Color>();
set2.Add(Color.Blue);
set2.Add(Color.Red);
set2.Add(Color.Green);
Set<OrderedPair<DateTime, Color>> set3 = CartesianProduct<DateTime, Color>.Product(set1, set2);
Assert.AreEqual(set3.Count, set1.Count * set2.Count);
}
So, now what? Just like the List<T> generics, the Set<T> generic can be used with custom written classes. There is a caution here though. The default implementation of the Equals() method tests that the reference of two objects are equal. In other words, if you have two instances of a class that contain the same data, the default implementation of Equals() will return false because they are different instances. For the Set<T> generic to work as expected on custom classes, you must override the default implementation of Equals. Below is an example...
public class Customer
{
// public member variable violate the concept of abstraction,
// but this is just a test, not production code
public int ID;
public string Name;
public Customer(int id, string name)
{
ID = id;
Name = name;
}
public override bool Equals(object obj)
{
Customer objvalue = (Customer)obj;
return this.ID == objvalue.ID;
}
}
[Test]
public void CustomObjectTest()
{
Set<Customer> set1 = new Set<Customer>();
set1 += new Customer(1, "customer 1");
set1 += new Customer(2, "customer 2");
set1 += new Customer(3, "customer 3");
Set<Customer> set2 = new Set<Customer>();
set2 += new Customer(2, "customer 2");
// without overriding Equals() set3 contains all three members
Set<Customer> set3 = set1 - set2;
Assert.AreEqual(set3.Count, 2);
Assert.IsTrue(set3.Contains(new Customer(1,"customer 1")));
Assert.IsTrue(set3.Contains(new Customer(3,"customer 3")));
}
Combining custom objects with the concepts of Set Theory, allows some sophisticated operations to be performed using simple mathematical operators.
0 comments:
Post a Comment