Programming in C#: Understanding the SortedDictionary Class

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.