CODEWITHSUNDEEP
c#.netdatetimecollections
artganify
artganify

Reputation: 703

Ordered collection based on DateTime

I'm looking for a way to implement a collection which guarantees order based on a DateTime value. My initial idea was to use a SortedSet<T1> with a custom IComparer<T1> like this:

internal class DateTimeComparer : IComparer<MyType> {
    public int Compare(MyType x, MyType y) {
        return x.DateTimeProp.CompareTo(y.DateTimeProp);
    }
}

var sortedSet = new SortedSet<MyType>(new DateTimeComparer());

However this doesn't work as the set seems to override/replace all items which have the exact timestamp. To validate this assumption, I created two collections, one being a simple list which was sorted using the DateTime property after its was populated, and another one based on the SortedSet<T1> -> The one based on the set had several entries missing which happened to be the ones which had the exact same timestamp.

What other options are there to implement such a collection?

Upvotes: 3

Views: 1143

Answers (1)

Martin Liversage
Martin Liversage

Reputation: 106816

An efficient way to maintain a sorted collection of items is to use a binary search tree. You could of course build your own binary search tree, however the SortedSet<T> class is implemented using a red-black binary search tree so it seems smarter to reuse that class which is exactly what you are trying to do.

The ordering of items in SortedSet<T> is controlled by comparing pairs of items by calling the IComparer<T>.Compare method. If this method returns 0 the two items are considered equal and only one of these items will be stored in the set. In your case with DateTimeComparer you get the problem that only a single MyType instance with a specifiec DateTimeProp can be stored in the set.

To solve this problem you have to make sure that distinct MyType instances never are equal when compared using the DateTimeComparer.Compare method. You can modify your code to achieve this:

class DateTimeComparer : IComparer<MyType> {

    readonly ObjectIDGenerator idGenerator = new ObjectIDGenerator();

    public int Compare(MyType x, MyType y)  {
        if (x.DateTimeProp != y.DateTimeProp)
            return x.DateTimeProp.CompareTo(y.DateTimeProp);
        bool firstTime;
        var xId = idGenerator.GetId(x, out firstTime);
        var yId = idGenerator.GetId(y, out firstTime);
        return xId.CompareTo(yId);
    }
}

If the two instances have different values of DateTimeProp then they should be ordered according to these. This is handled by the initial if statement.

If the two values have the same DateTimeProp values they need to be ordered based on some other criteria. You can use other properties of MyType but there might be cases where these properties are equal and it is important that the method never returns 0 except if x and y refers to the same instances (e.g. ReferenceEquals(x, y) is true).

To handle this you can use an ObjectIDGenerator which will assign unique 64 bit ID values to distinct instances. These can then be compared to provide an ordering.

Note that the ordering of items with same DateTimeProp values will be random but consistent. To control this ordering you can use other properties of MyType but eventually you will have to use the generated ID to provide an ordering when all properties of two different instances are the same.

Upvotes: 2

Related Questions