C# Discussion Boards - CodeProject

NuclearMan8521-Nov-12 7:12

21-Nov-12 7:12

I have been thinking about this for a while and have not come up with any simple and beautiful ways to solve this problem. What I would like to have done is a nice way to sort Lists along side other Lists. Such as shown in the example:

I have a generic amount of Lists (let us just say 4) and they are independent of each other but are of same length.
listOne = [09,06,04,03]
listTwo = [20,50,40,30]
listThree = [15,45,85,65]
listFour = [89,39,19,99]

Now I would like to organize listOne but also move the indices of listTwo and listThree:
listOne = [03,04,06,09]
listTwo = [30,40,50,20]
listThree = [65,85,45,15]

I then work with these lists as I see fit. Now I would like to organize listFour but move listOne, listTwo and listThree with it:
listFour = [19,39,89,99]
listOne = [06,04,03,09]
listTwo = [50,40,30,20]
listThree = [45,85,65,15]

Is there already a development that does something like this? A way to organize any list and move the indexes of any number of extra lists with the organization of the first list. Right now I use the Dictionary type and have each indexed, then when one is organized, move the others with respect to the new Dictionary index. But that seems to be very sloppy.

Re: Specialized List Sorting question

Richard Deeming21-Nov-12 8:03

Richard Deeming

21-Nov-12 8:03

Option 1:
It's not clean, but if you want to sort the lists, this should work:

static void Sort<T>(IList<T> sortKey, params IList<T>[] otherLists)
{
   // TODO: Validate the arguments:
   // - None of the lists are null;
   // - All of the lists have the same length;

   Action<IList<T>, IDictionary<int, int>> sortList = (list, keys) =>
   {
      var values = list
         .Select((value, i) => new { key = keys[i], value })
         .OrderBy(p => p.key).Select(p => p.value);

      int index = 0;
      foreach (T value in values)
      {
         list[index++] = value;
      }
   };

   // Key is the index in the input list;
   // Value is the index in the output list.
   var indices = Enumerable.Range(0, sortKey.Count)
      .OrderBy(i => sortKey[i])
      .Select((key, value) => new { key, value })
      .ToDictionary(p => p.key, p => p.value);

   sortList(sortKey, indices);
   foreach (var list in otherLists)
   {
      sortList(list, indices);
   }
}

Edit:
Missed a ToList call in the anonymous delegate which would prevent this from working. Option 2 is probably a better approach. Smile | :)

Edit 2:
Nope, the ToList call isn't needed - the OrderBy call ensures that the entire sequence is evaluated on the first call to MoveNext. D'Oh! | :doh:

It still ends up creating a copy of the list, so option 2 is still better.

"These people looked deep within my soul and assigned me a number based on the order in which I joined."
- Homer

modified 22-Nov-12 7:15am.

Re: Specialized List Sorting question

SledgeHammer0121-Nov-12 8:06

SledgeHammer01

21-Nov-12 8:06

Your issue is that you are trying to sort your lists as 4 different lists when they aren't. It's a single list of x items.

So just have:

class SomeObject
{
int Data[4];
}

List<SomeObject> lst;

When you sort, you would provide a custom compare function that'll look like:

int Compare(SomeObject x, SomeObject y)
{
compare x.Data[0] vs. y.Data[0] or whatever
}

and all "columns" will move together.

Re: Specialized List Sorting question

Richard Deeming21-Nov-12 8:32

Richard Deeming

21-Nov-12 8:32

Option 2:
Wrap your lists with a class which applies the sort order where necessary:

public sealed class ListHelper<T> : IEnumerable<IList<T>>
{
   private int _sortIndex = -1;
   private IDictionary<int, int> _indexMap; // Source to target
   private IDictionary<int, int> _reverseIndexMap; // Target to source
   private readonly List<MappedList> _lists = new List<MappedList>();
   
   public int SortIndex
   {
      get
      {
         return _sortIndex;
      }
      set
      {
         if (value < -1 || value >= _lists.Count) 
         {
            throw new ArgumentOutOfRangeException();
         }
         
         if (-1 == value)
         {
            if (0 != _lists.Count)
            {
               int size = _lists[0].Count;
               _indexMap = Enumerable.Range(0, size).ToDictionary(i => i);
               _reverseIndexMap = _indexMap;
            }
         }
         else
         {
            IList<T> sortKey = _lists[value].InnerList;
            
            _indexMap = Enumerable.Range(0, sortKey.Count)
               .OrderBy(i => sortKey[i])
               .Select((key, v) => new { key, value = v })
               .ToDictionary(p => p.key, p => p.value);
            
            _reverseIndexMap = _indexMap.ToDictionary(p => p.Value, p => p.Key);
         }
      }
   }
   
   public int Count
   {
      get { return _lists.Count; }
   }
   
   public IList<T> this[int index]
   {
      get { return _lists[index]; }
   }
   
   public void Add(IList<T> listToAdd)
   {
      if (_indexMap == null)
      {
         _indexMap = Enumerable.Range(0, listToAdd.Count).ToDictionary(i => i);
         _reverseIndexMap = _indexMap;
      }
      else if (_indexMap.Count != listToAdd.Count)
      {
         throw new ArgumentException("Invalid list size!", "list");
      }

      _lists.Add(new MappedList(listToAdd, this));
   }
   
   public IEnumerator<IList<T>> GetEnumerator()
   {
      return _lists.GetEnumerator();
   }
   
   IEnumerator IEnumerable.GetEnumerator()
   {
      return GetEnumerator();
   }
   
   private sealed class MappedList : IList<T>
   {
      private readonly IList<T> _list;
      private readonly ListHelper<T> _parent;
      
      public MappedList(IList<T> list, ListHelper<T> parent)
      {
         _list = list;
         _parent = parent;;
      }
      
      public IList<T> InnerList
      {
         get { return _list; }
      }
      
      public T this[int index] 
      { 
         get
         {
            int realIndex = _parent._reverseIndexMap[index];
            return _list[realIndex];
         }
         set
         {
            int realIndex = _parent._reverseIndexMap[index];
            _list[realIndex] = value;
         }
      }
      
      public int Count
      {
         get { return _list.Count; }
      }
      
      public bool IsReadOnly
      {
         get { return _list.IsReadOnly; }
      }
      
      public IEnumerator<T> GetEnumerator()
      {
         for (int i = 0; i < _list.Count; i++)
         {
            int index = _parent._reverseIndexMap[i];
            yield return _list[index];
         }
      }
      
      IEnumerator IEnumerable.GetEnumerator()
      {
         return GetEnumerator();
      }
      
      public int IndexOf(T item)
      {
         int result = _list.IndexOf(item);
         return -1 == result ? -1 : _parent._indexMap[result];
      }
      
      public void CopyTo(T[] array, int arrayIndex)
      {
         foreach (T item in this)
         {
            array[arrayIndex++] = item;
         }
      }
      
      public bool Contains(T item)
      {
         return _list.Contains(item);
      }
      
      public void Add(T item)
      {
         throw new NotSupportedException();
      }
      
      public void Insert(int index, T item)
      {
         throw new NotSupportedException();
      }
      
      public bool Remove(T item)
      {
         throw new NotSupportedException();
      }
      
      public void RemoveAt(int index)
      {
         throw new NotSupportedException();
      }
      
      public void Clear()
      {
         throw new NotSupportedException();
      }
   }
}

...

var helper = new ListHelper<int>
{
   new[] { 04, 09, 03, 06 },
   new[] { 20, 50, 40, 30 },
   new[] { 15, 45, 85, 65 },
   new[] { 89, 39, 19, 99 },
};

helper.SortIndex = 0;

foreach (IList<T> list in helper)
{
   // Either foreach or for will work here:
   for (int index = 0; index < list.Count; index++)
   {
      // Each list will be sorted based on the order of the first list:
      Console.WriteLine(list[index]);
   }
}

"These people looked deep within my soul and assigned me a number based on the order in which I joined."
- Homer

Re: Specialized List Sorting question

PIEBALDconsult21-Nov-12 8:57

PIEBALDconsult

21-Nov-12 8:57

Perhaps have a List of Lists, where the first sub-list is the list of all the first values, etc.:

{
  { 09 , 20 , 15 , 89 }
  { 06 , 50 , 45 , 39 }
  { 04 , 40 , 85 , 19 }
  { 03 , 30 , 65 , 99 }
}

Then sort the outer list by the first (or whatever) element of each:

{
  { 03 , 30 , 65 , 99 }
  { 04 , 40 , 85 , 19 }
  { 06 , 50 , 45 , 39 }
  { 09 , 20 , 15 , 89 }
}

P.S. Could have made this a Friday Programming Challenge.

modified 21-Nov-12 15:14pm.

Re: Specialized List Sorting question

BobJanova21-Nov-12 22:50

BobJanova

21-Nov-12 22:50

Make a wrapper class that you can use to preserve the order:

class OrderHelper<T> : IComparable<OrderHelper<T>> {
 public T Item {get; private set;}
 public int Order {get; private set;}

 public OrderHelper(T item, int order) { this.Item = item; this.Order = order; }

 public int CompareTo(OrderHelper<T> other) {
  return Comparer<T>.Default.Compare(Item, other.Item);
 }
}

Create a list of these from your primary sort list:

int index = 0;
List<OrderHelper<int>> orderedList = listOne.Select(i => new OrderHelper(i, index++)).ToList();

Sort that list, and then you can retrieve the index list:

orderedList.Sort();
List<int> indices = orderedList.Select(oi => oi.Order).ToList();

Finally you can order the other lists by that index set:

public static List<T> OrderBy(List<T> list, List<int> indices){
 List<T> r = new List<T>(indices.Count);
 for(int i = 0; i < r.Count; i++){
  r[i] = list[indices[i]];
 }  
 return r;
}

// ...
listTwo = OrderBy(listTwo, indicies);
listThree = OrderBy(listThree, indicies);
// etc

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.