Interval Dictionary Library Published

I have published an alpha version of my new project: the Interval Dictionary.  This collection is similar in function to System.Collections.Generic.Dictionary<TKey,TValue> but rather than associating values to keys, a value is associated to an interval.  This allows O(log n) retrieval of values based on a key that would fall within an interval.

Consider the following example code:

IntervalDictionary<int, string> months = new IntervalDictionary<int, string>();

// Add the month's first and last day-of-year values as the interval bounds and the month name as the value
months.Add(1, 31, "January");
months.Add(32, 59, "February");
months.Add(60, 90, "March");
months.Add(91, 120, "April");
months.Add(121, 151, "May");
months.Add(152, 181, "June");
months.Add(182, 212, "July");
months.Add(213, 243, "August");
months.Add(244, 273, "September");
months.Add(274, 304, "October");
months.Add(305, 334, "November");
months.Add(335, 365, "December");

// Gets the name of the month which is associated with the 264th day of the year
string month = months[264];

In the example, an interval dictionary provides the functionality to look up the name of a month (element value) based on a day-of-year value because each month is defined by a day-of-year interval and a month name value.  Without this type of data structure, worst case evaluation would be O(n) because a user would have to iterate through each month evaluating whether the key (264 in the example) in contained in the interval for the month.  On the back end, the Interval Dictionary implements a self-balancing AVL-tree.  Each tree node represents an interval defined by an upper and lower bound. A value can then be associated with each tree node.  Thus, one can search the tree in O(log n) for an interval that contains a specified key and then get the associated value.

The source code for this project is published on CodePlex. Installation is available through NuGet.

Posted on March 23, 2013 at 1:49 pm by Steve Konves · Permalink
In: Interval Dictionary, Projects

Leave a Reply