Dictionary Keys that match over a Date Range

Question

I would like to store data in Generic Dictionary with keys that match over Date Ranges.

For instance, I came up with the following idea

public class MyKey : IEquatable<MyKey> 
{
  public int Key { get; set; }
  public DateTime StartDate { get; set; }
  public DateTime EndDate { get; set; }

  public override int GetHashCode() 
  { 
    returns Key;
  }

  // if there is overlap in date range consider them equal
  public bool Equals(MyKey other)
  {
    if (Key!=other.Key)
      return false;
    else if(other.StartDate >=StartDate && other.StartDate <=EndDate) 
      return true;
    else if(other.EndDate >=StartDate && other.EndDate <=EndDate) 
      return true;
    else if(StartDate >=other.StartDate && StartDate <=other.EndDate) 
      return true;
    else if(EndDate >=other.StartDate && EndDate <=other.EndDate) 
      return true;
    else
      return false;
  }
}

Then the I would use a Dictionary as so

var dict = new Dictionary<MyKey,MyClass>();
Populate(dict);

// get an element where the current date is in the daterange of the key
// in the collection
var key = new MyKey();
key.Key=7;
key.StartDate=DateTime.Now;
key.EndDate=key.StartDate;

// retrieve the matching element for the date
var myclass = dict[key];

This was the best I could come up with, however it seems kludgy way to do this. I thought of adding a fourth property called selection date. And would set that to null in the entries in the dictionary but would use it during lookups in the Equals method.

I am wondering if anyone else has come up with an elegant solution to this problem?

I should mention that I will be matching on the key first and then there could be date ranges for the specific key property.

Answer 1

Your implementation of Equals violates the guidelines for overriding Equals. In particular your implementation does not satisfy the transitivity rule:

• if x.Equals(y) && y.Equals(z) returns true, then x.Equals(z) returns true.

Breaking this guideline is a bad idea and can lead to problems and confusion. I would recommend that you do not do this.

I would avoid storing intervals as keys in a dictionary altogether. You can put the list of intervals for a specific key as a value in the dictionary if you like, but it shouldn't be part of the key.

When you are searching to find an interval you can first use the dictionary key to get the list of intervals for that key and then iterate over the intervals to find one that overlaps with your parameter. If the intervals are not overlapping for a specific key then you can sort them and use a binary search to find a specific interval. If the intervals for a specific key can overlap you can look at other data structures such as an interval tree.

Related question

• Data structure for quick time interval look up

Answer 2

For getHashCode return a hash of this.StartDate and this.EndDate and this.Key. See this page for simple hashing ideas. There are better hashing methods out there but that page should get you started.

Add a static method that takes in a int key and a single DateTime as it seems that is how you are using this. (this could take in two DateTimes for a range if you need it) return myDictionary[myDictionary.Keys.Find(x=> value < x.EndDate && value > x.StartDate) && x.Key = key];

For two dates: return myDictionary[myDictionary.Keys.Find(x=> ((date1 < x.EndDate && date1 > x.StartDate)) || (date2 < x.EndDate && date2 > x.StartDate))) && x.Key = key];

Either of these could be made a find all if you are using a range as there may be collisions.

Change your equals conditions to just

return this.StartDate.Equals(o.StartDate) && this.EndDate.Equals(o.EndDate) && this.Key.Equals(o.Key);

Using the above static method you no longer need the concept of overlapping keys.