mcs/class/Mono.C5/UserGuideExamples/SortingPermutation.cs

   1 // C5 example
   2 // 2004-11
   3
   4 using System;
   5 using C5;
   6 using SCG = System.Collections.Generic;
   7
   8 namespace SortingPermutation
   9 {
  10   class MyTest
  11   {
  12     public static void Main(String[] args)
  13     {
  14       String[] cities =
  15       { "Tokyo", "Beijing", "Hangzhou", "Kyoto", "Beijing", "Copenhagen", "Seattle" };
  16       IList<String> alst = new ArrayList<String>();
  17       alst.AddAll<String>(cities);
  18       foreach (int i in MySort.GetPermutation1(alst))
  19         Console.Write("{0} ", i);
  20       Console.WriteLine();
  21       IList<String> llst = new LinkedList<String>();
  22       llst.AddAll<String>(cities);
  23       foreach (int i in MySort.GetPermutation2(llst))
  24         Console.Write("{0} ", i);
  25       Console.WriteLine();
  26       Console.WriteLine("The rank of the cities:");
  27       ArrayList<int> res = MySort.GetPermutation1(MySort.GetPermutation2(llst));
  28       foreach (int i in res)
  29         Console.Write("{0} ", i);
  30       Console.WriteLine();
  31     }
  32   }
  33
  34   class MySort
  35   {
  36     // Fast for array lists and similar, but not stable; slow for linked lists
  37
  38     public static ArrayList<int> GetPermutation1<T>(IList<T> lst)
  39       where T : IComparable<T>
  40     {
  41       ArrayList<int> res = new ArrayList<int>(lst.Count);
  42       for (int i = 0; i < lst.Count; i++)
  43         res.Add(i);
  44       res.Sort(new DelegateComparer<int>
  45                (delegate(int i, int j) { return lst[i].CompareTo(lst[j]); }));
  46       return res;
  47     }
  48
  49     // Stable and fairly fast both for array lists and linked lists,
  50     // but does copy the collection's items.
  51
  52     public static ArrayList<int> GetPermutation2<T>(IList<T> lst)
  53       where T : IComparable<T>
  54     {
  55       int i = 0;
  56       IList<KeyValuePair<T, int>> zipList =
  57         lst.Map<KeyValuePair<T, int>>
  58             (delegate(T x) { return new KeyValuePair<T, int>(x, i++); });
  59       zipList.Sort(new KeyValueComparer<T>(lst));
  60       ArrayList<int> res = new ArrayList<int>(lst.Count);
  61       foreach (KeyValuePair<T, int> p in zipList)
  62         res.Add(p.Value);
  63       return res;
  64     }
  65
  66     private class KeyValueComparer<T> : SCG.IComparer<KeyValuePair<T, int>>
  67       where T : IComparable<T>
  68     {
  69       private readonly IList<T> lst;
  70       public KeyValueComparer(IList<T> lst)
  71       {
  72         this.lst = lst;
  73       }
  74       public int Compare(KeyValuePair<T, int> p1, KeyValuePair<T, int> p2)
  75       {
  76         return p1.Key.CompareTo(p2.Key);
  77       }
  78     }
  79   }
  80 }