C# binarysearch a list<T> by a member of T

Question

I have a baseclass Event with a DateTime member TimeStamp. Lots of other event-classes will derive from this.

I want to be able to search a list of events fast, so I'd like to use a binary search.

(The list-data is sorted on timestamp, but there might be duplicate timestamps for events that occurred simultaneously)

So I started out writing something like this :

public class EventList<T> : List<T> where T : Event
{
   private IComparer<T> comparer = (x, y) => Comparer<DateTime>.Default.Compare(x.TimeStamp, y.TimeStamp);

   public IEnumerable<T> EventsBetween(DateTime inFromTime, DateTime inToTime)
   {
       // Find the index for the beginning. 
       int index = this.BinarySearch(inFromTime, comparer);

       // BLAH REST OF IMPLEMENTATION
   }
}

The problem is that the BinarySearch only accepts T (so - an Event type) as parameter, while I want to search based on a member of T - the TimeStamp.

What would be a good way to approach this ?

Answer 1

I think that you already are on the right way with your comparer function. It compares two T's by comparing the dates of them.

To handle the inFromTime parameter to BinarySearch you can create a dummy Event which has the correct TimeStamp and pass that dummy to BinarySearch.

Also, just to make sure: Is the list sorted on the time field? Otherwise binarysearch won't work.

Edit

This problem is more complex than I first thought. A solution that would help you is:

• Make an adapter class which exposes your EventList as an IList.
• Use a BinarySearch extension method on IList to do the search.

Unfortunately there is no built in BinarySearch extension method, so you will have to write your own. In case you write your own search it might not be worth the extra effort to put it in an extension method. In that case just implementing a custom BinarySearch algorithm yourself in your EventList class is probably the best you can do.

Another option would be if there was a form of BinarySearch that accepted a delegate that extracts the relevant key from T, but that is not available either.

Answer 2

The easiest way is to define a small helper class which implements IComparer<T>.

public class CompUtil : IComparer<T> {
  public int Compare(T left, T right) { 
    return left.TimeStamp.CompareTo(right.TimeStamp);
  }
}

You can then use it as follows

int index = this.BinarySearch(inFromTime, new CompUtil());

Answer 3

If your Event class contains the property you want to sort on, your approach will be fine. The compiler can then verify that whatever T is being passed in, it will inherit from Event and contain the DateTime property. If Event does not contain the DateTime property, you would probably want to add it to event, or constrain T to be a more specific type, which contains the property needed for your search.

Remember to make sure your list is sorted before applying BinarySearch.

Answer 4

public class EventList<TEvent, TData>
   : List<TEvent> where TEvent : Event, TData: DataTime
{
   class Comparer : IComparer<TData> { } // as JaredPar mentioned above

   public IEnumerable<TEvent> EventsBetween(TData from, TData to) { }
}

Answer 5

Maybe you could consider using SortedList as base class instead of List. You could then use IndexOfKey method to search for a specified TimeStamp. That method does a binary search.