Figure 1 - Painting a Collection of Strings sorted by Position
Another summer is upon us and all I can seem to think about is when is the next time I can get to the beach. Admittedly sunny summer days are not conducive to work, but you've gotta make a living somehow. Anyway, there is always the weekend.
In this article we will examine a cousin to the Dictionary class, the SortedDictionary. The SortedDictionary gives us all of the benefits of a hash table with the additional bonus of keeping the collection of key-value pairs sorted by the key. Table 1 shows you some of the members of the SortedDictionary class and how to use them:
Table 1 - Members of the SortedDictionary Class
| Member |
Description |
Usage |
SortedDictionary<key type, value type>()
SortedDictionary<key type, value type>(IComparer comparer) |
Constructs a SortedDictionary.
The first constructor uses the key's IComparable interface for sorting.
The second constructor takes an IComparer implementation to determine how items are sorted.
|
SortedDictionary<SortablePoint, string> positionDictionary = new SortedDictionary<Point, string>();
SortedDictionary<SortablePoint, string> positionDictionary = new SortedDictionary<SortablePoint, string>(new MyComparer()); |
| Add (key, value) |
Adds a key-value pair to the sorted dictionary |
dictionary.Add(new SortablePoint(50, -45), "hello"); |
| Count |
Get's the number of key-value pairs in the dictionary |
int count = dictionary.Count; |
| Values |
Returns a collection of values sorted by key |
foreach( string s in dictionary.Values)
{
Console.WriteLine("Next Value =
{0}", s);
}
|
| Keys |
Returns a sorted list of keys. Each key must support an IComparable interface |
foreach( SortablePoint p in dictionary.Keys)
{
Console.WriteLine("Next Key =
{0},{1}", p.X, p.Y);
}
|
| ContainsKey(key) |
Finds a key inside the SortedDictionary |
if (dictionary.ContainsKey(new SortablePoint(5, 15))
{
return "yup, that key is there";
} |
| Remove(key) |
Removes the element in the dictionary with the passed in key |
dictionary.Remove("Bill"); |
| Clear() |
Removes all of the elements from the dictionary |
dictionary.Clear(); |
| CopyTo(KeyValuePair<key type, value type>[] array, int index) |
Copies the sorted dictionary into a KeyValuePair array of the same key-value types as the dictionary (starting at an index in the array). The dictionary must be smaller than the span of elements from the index to the end of the array. |
KeyValuePair<SortablePoint, Keys>[] pairs = new KeyValuePair<SortablePoint, Keys>[15];
dictionary.CopyTo (pairs, 2); |
Example of using a SortedDictionary
In order to demonstrate a simple usage of the SortedDictionary, we'll create a SortedDictionary of point-string pairs. The pairs will be sorted by the distance the point is from the upper-left hand corner of a Windows Form (0,0). We'll then display those points on the Windows Form in random colors.
In order to illustrate our example, we need to be able to sort the points in the SortedDictionary. In creating the sortability of the dictionary we have a choice. We can either sort the points through an IComparer object passed into the constructor of the SortedDictionary, or we can create a sortable Point for the key in our dictionary.
Using IComparer
Figure 2 - Implementing IComparer for a Point, UML Reverse Engineered using WithClass.
We can use the generic IComparer interface to create a class that will allow us to compare points in order to sort by distance from the origin of the form. The PointsComparer class shown in listing 1 implements IComparer<Point>. We need to implement the Compare method for IComparer to compare distances. The distance between the origin and a point is equal to the sqrt ( (x - 0)^2 + (y-0)^2 ). We don't need to compute the square root because we only need to do a comparison between points. Therefore we'll just take the sum of the squares of the points in question or
x^2 + y^2
Listing 1: Implementing IComparer for a Point
|
using System;
using System.Collections.Generic;
using System.Text;
using System.Drawing;
namespace PaintSortedPoints
{
class PointsComparer : IComparer<Point>
{
// compare the distance from the origin of one point and another point.
public int Compare(Point x, Point y)
{
if (Distance(x) > Distance(y))
{
return 1;
}
else
{
return -1;
}
}
// compute the square of the distance of the point from the origin of the form
private int Distance(Point p)
{
return (p.X * p.X + p.Y * p.Y);
}
}
} |
Now we can construct our SortedDictionary based on the PointsComparer.
| SortedDictionary<Point, string> pointDictionary = new SortedDictionary<Point, string>(new PointsComparer()); |
Listing 2 shows the full implementation of the point-name sorting program using IComparer. After adding the key-value pairs (of points and names) to the SortedDictionary, the form is invalidated to force a painting of the screen. The names of each person in the SortedDictionary are painted at their associated point on the form. As we loop through the foreach structure for a SortedDictionary, the names are spit out in the order determined by the IComparer object. We display the counter value on the form so you can see that the order of names is indeed related to the distance from the upper-left hand corner of the form.
Listing 2 - Sorting Points in the Sorted Dictionary using the IComparer
|
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Text;
using System.Windows.Forms;
namespace PaintSortedPoints
{
public partial class Form1 : Form
{
// create a sorted dictionary with points as the keys
// and strings as the values (use an IComparer implementation)
SortedDictionary<Point, string> pointDictionary = new SortedDictionary<Point, string>(
new PointsComparer());
public Form1()
{
InitializeComponent();
AddPositionedStrings();
Invalidate();
}
/// <summary>
/// Add Sortable Points to the collection
/// </summary>
private void AddPositionedStrings()
{
pointDictionary.Add(new Point(10, 25), "Bob");
pointDictionary.Add(new Point(15, 230), "Bill");
pointDictionary.Add(new Point(75, 35), "Tim");
pointDictionary.Add(new Point(18, 175), "Jan");
pointDictionary.Add(new Point(21, 105), "Jill");
pointDictionary.Add(new Point(0, 0), "Sarah");
pointDictionary.Add(new Point(100, 125), "Ann");
pointDictionary.Add(new Point(50, 85), "Alex");
pointDictionary.Add(new Point(150, 45), "John");
foreach (string s in pointDictionary.Values)
{
Console.Write("{0},", s);
}
Console.WriteLine(pointDictionary.Values.ToString());
}
Random r = new Random((int)DateTime.Now.Ticks);
private void Form1_Paint(object sender, PaintEventArgs e)
{
int count = 0;
// loop through each point-string pair and paint the string at the point location.
// number each name, so we can see the order according to distance from the origin
foreach (KeyValuePair<Point, string> pair in pointDictionary)
{
count++;
Brush brush = new SolidBrush(Color.FromArgb(r.Next(255), r.Next(255), r.Next(255)));
e.Graphics.FillEllipse(Brushes.White, pair.Key.X - 2, pair.Key.Y, Font.Height, Font.Height);
e.Graphics.DrawEllipse(Pens.Red, pair.Key.X - 2, pair.Key.Y, Font.Height, Font.Height);
e.Graphics.DrawString(count.ToString() + "-" + pair.Value, this.Font, brush, pair.Key.X,
pair.Key.Y);
brush.Dispose();
}
}
}
} |
Using IComparable
Figure 3 - SortablePoint using IComparable, Reverse Engineered using WithClass
The other choice we mentioned for sorting inside our SortedDictionary is to make the key implement IComparable. For this case, we will create a new Point class called SortablePoint, that implements the IComparable interface. The IComparable interface implements one method called CompareTo. This method compares the object passed to it to the object in the current instance. Here we will use the same Distance formula to compare the two points in question that we need to sort.
Listing 3 - Creating a SortablePoint with IComparable
|
namespace PaintSortedPoints
{
class SortablePoint : IComparable
{
public int X = 0;
public int Y = 0;
public SortablePoint(int x, int y)
{
X = x;
Y = y;
}
// Compare the existing point with the point passed for sorting
// using the Distance method
public int CompareTo(object obj)
{
SortablePoint otherPoint = (SortablePoint)obj;
if (Distance(otherPoint.X, otherPoint.Y) > Distance(this.X, this.Y))
{
return -1;
}
else
{
return 1;
}
}
private int Distance(int p, int p_2)
{
return (p * p + p_2 * p_2);
}
}
} |
Now that we have a sortable key, we can just construct our SortedDictionary with the default constructor:
| SortedDictionary<SortablePoint, string> pointDictionary = new SortedDictionary<SortablePoint, string>(); |
The full form code for painting our SortedDictionary that uses the IComparable implementation is shown in listing 4. Note that all of the code is identical to Listing 2 except (1) we are using a different constructor for the SortedDictionary that does not require an IComparer object and (2) All Point objects are replaced with SortablePoint objects that implement IComparable.
Listing 4 - Implementing the SortedDictionary using a SortablePoint as a key
|
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Text;
using System.Windows.Forms;
namespace PaintSortedPoints
{
public partial class Form1 : Form
{
// create a sorted dictionary with points as the keys
// and strings as the values
SortedDictionary<SortablePoint, string> pointDictionary = new SortedDictionary<SortablePoint, string>();
public Form1()
{
InitializeComponent();
AddPositionedStrings();
Invalidate();
}
/// <summary>
/// Add Sortable Points to the collection
/// </summary>
private void AddPositionedStrings()
{
pointDictionary.Add(new SortablePoint(10, 25), "Bob");
pointDictionary.Add(new SortablePoint(15, 230), "Bill");
pointDictionary.Add(new SortablePoint(75, 35), "Tim");
pointDictionary.Add(new SortablePoint(18, 175), "Jan");
pointDictionary.Add(new SortablePoint(21, 105), "Jill");
pointDictionary.Add(new SortablePoint(0, 0), "Sarah");
pointDictionary.Add(new SortablePoint(100, 125), "Ann");
pointDictionary.Add(new SortablePoint(50, 85), "Alex");
pointDictionary.Add(new SortablePoint(150, 45), "John");
foreach (string s in pointDictionary.Values)
{
Console.Write("{0},", s);
}
Console.WriteLine(pointDictionary.Values.ToString());
}
Random r = new Random((int)DateTime.Now.Ticks);
private void Form1_Paint(object sender, PaintEventArgs e)
{
int count = 0;
// loop through each point-string pair and paint the string at the point location.
// number each name, so we can see the order according to distance from the origin
foreach (KeyValuePair<SortablePoint, string> pair in pointDictionary)
{
count++;
Brush brush = new SolidBrush(Color.FromArgb(r.Next(255), r.Next(255), r.Next(255)));
e.Graphics.FillEllipse(Brushes.White, pair.Key.X - 2, pair.Key.Y, Font.Height, Font.Height);
e.Graphics.DrawEllipse(Pens.Red, pair.Key.X - 2, pair.Key.Y, Font.Height, Font.Height);
e.Graphics.DrawString(count.ToString() + "-" + pair.Value, this.Font, brush, pair.Key.X,
pair.Key.Y);
brush.Dispose();
}
}
}
} |
Conclusion
The SortedDictionary provides us with a great collection for managing a bunch of sorted associated pairs. Because the SortedDictionary is a template, we can manipulate the key-value pair using their specific types. To sort the items in the dictionary, we can either provide an implemented IComparer interface to the SortedDictionary object, or provide a key that implements the IComparable interface. Either way, if you find yourself in a state of sorted affairs, C# and .NET can help you find your way out.