tags:

views:

107

answers:

7

I have a class that has multiple List<> contained within it. Its basically a table stored with each column as a List<>. Each column does not contain the same type. Each list is also the same length (has the same number of elements).

For example:

I have 3 List<> objects; one List, two List, and three List.

//Not syntactically correct
List<DateTime> one = new List...{4/12/2010, 4/9/2006, 4/13/2008};
List<double> two = new List...{24.5, 56.2, 47.4};
List<string> three = new List...{"B", "K", "Z"};

I want to be able to sort list one from oldest to newest: one = {4/9/2006, 4/13/2008, 4/12/2010};

So to do this I moved element 0 to the end.

I then want to sort list two and three the same way; moving the first to the last.

So when I sort one list, I want the data in the corresponding index in the other lists to also change in accordance with how the one list is sorted.

I'm guessing I have to overload IComparer somehow, but I feel like there's a shortcut I haven't realized.

+2  A: 

First you should create a Data object to hold everything.

private class Data
{
    public DateTime DateTime { get; set; }
    public int Int32 { get; set; }
    public string String { get; set; }
}

Then you can sort like this.

var l = new List<Data>();
l.Sort(
    (a, b) =>
    {
        var r = a.DateTime.CompareTo(b);
        if (r == 0)
        {
            r = a.Int32.CompareTo(b);
            if (r == 0)
            {
                r = a.String.CompareTo(b);
            }
        }
        return r;
    }
);
ChaosPandion
So I iterate through the entirety of each list and create a Data struct from the data. Then I sort the data, then I put it back into the lists. This makes sense, but it doesn't seem that efficient. It will at least work and thats better than what I currently have. Thanks. Edit: I don't neccesarily know that there are 3 items so I can't use a struct. A list could probably work but would I have to worry about casting on the big sort?
John Gitzlsan
@John - Do you receive these lists from an uncontrollable source?
ChaosPandion
Yeah, the List<> objects I recieve cannot be changed; they can be sorted in place though.
John Gitzlsan
+3  A: 

I've handled this design in the past by keeping or creating a separate index list. You first sort the index list, and then use it to sort (or just access) the other lists. You can do this by creating a custom IComparer for the index list. What you do inside that IComparer is to compare based on indexes into the key list. In other words, you are sorting the index list indirectly. Something like:

// This is the compare function for the separate *index* list.
int Compare (object x, object y)
{
  KeyList[(int) x].CompareTo(KeyList[(int) y])
}

So you are sorting the index list based on the values in the key list. Then you can use that sorted key list to re-order the other lists. If this is unclear, I'll try to add a more complete example when I get in a situation to post one.

TechNeilogy
+1. This is an excellent approach. I have exactly this kind of "indirect list" in my personal library; it's useful for many things. Sample code [here](http://nitolinq.codeplex.com/SourceControl/changeset/view/57003#1161747).
Stephen Cleary
A: 

Using generic arrays, this can get a bit cumbersome.

One alternative is using the Array.Sort() method that takes an array of keys and an array of values to sort. It first sorts the key array into ascending order and makes sure the array of values is reorganized to match this sort order.

If you're willing to incur the cost of converting your List<T>s to arrays (and then back), you could take advantage of this method.

Alternatively, you could use LINQ to combine the values from multiple arrays into a single anonymous type using Zip(), sort the list of anonymous types using the key field, and then split that apart into separate arrays.

If you want to do this in-place, you would have to write a custom comparer and create a separate index array to maintain the new ordering of items.

LBushkin
+4  A: 

I am sorry to say, but this feels like a bad design. Especially because List<T> does not guarantee element order before you have called one of the sorting operations (so you have a problem when inserting):

From MSDN:

The List is not guaranteed to be sorted. You must sort the List before performing operations (such as BinarySearch) that require the List to be sorted.

In many cases you won't run into trouble based on this, but you might, and if you do, it could be a very hard bug to track down. For example, I think the current framework implementation of List<T> maintains insert order until sort is called, but it could change in the future.

I would seriously consider refactoring to use another data structure. If you still want to implement sorting based on this data structure, I would create a temporary object (maybe using an anonymous type), sort this, and re-create the lists (see this excellent answer for an explanation of how).

driis
I agree there are better designs. The main situations in which I've run into this in the past is where I didn't have ownership of the original arrays and they were too big to make separate copies. If you have ownership, by all means re-factor this into an IComparable class or structure with all the data.
TechNeilogy
I can't really change this but here's the application. Basically the List<> objects contain data and that data is passed to math functions. The math functions then pass the result back and are appended to the table class. Would it be better to store this stuff row-wise and project out the columns using LINQ? That makes the insert much more complicated however.
John Gitzlsan
Yes, I certainly think it would be better to store row-wise. I don't see how inserts would be more complicated by that; but then again, I don't know about the entire application and your constraints.
driis
A: 

I hope this could help :

one = one.Sort(delegate(DateTime d1, DateTime d2)
{
    return Convert.ToDateTime(d2).CompareTo(Convert.ToDateTime(d1));
});
Rawhi
A: 

I wrote a sort algorithm that does this for Nito.LINQ (not yet released). It uses a simple-minded QuickSort to sort the lists, and keeps any number of related lists in sync. Source code starts here, in the IList<T>.Sort extension method.

Alternatively, if copying the data isn't a huge concern, you could project it into a LINQ query using the Zip operator (requires .NET 4.0 or Rx), order it, and then pull each result out:

List<DateTime> one = ...;
List<double> two = ...;
List<string> three = ...;
var combined = one.Zip(two, (first, second) => new { first, second })
    .Zip(three, (pair, third) => new { pair.first, pair.second, third });
var ordered = combined.OrderBy(x => x.first);
var orderedOne = ordered.Select(x => x.first);
var orderedTwo = ordered.Select(x => x.second);
var orderedThree = ordered.Select(x => x.third);

Naturally, the best solution is to not separate related data in the first place.

Stephen Cleary
A: 

Here's a way to do it using LINQ and projections. The first query generates an array with the original indexes reordered by the datetime values; in your example, the newOrdering array would have members:

{ 4/9/2006, 1 }, { 4/13/2008, 2 }, { 4/12/2010, 0 }

The second set of statements generate new lists by picking items using the reordered indexes (in other words, items 1, 2, and 0, in that order).

var newOrdering = one
    .Select((dateTime, index) => new { dateTime, index })
    .OrderBy(item => item.dateTime)
    .ToArray();

// now, order each list
one = newOrdering.Select(item => one[item.index]).ToList();
two = newOrdering.Select(item => two[item.index]).ToList();
three = newOrdering.Select(item => three[item.index]).ToList();
Ben M
I like this solution, but is it efficient? I don't know that much about prjection performance;
John Gitzlsan
Only one way to find out - :-)
Ben M