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

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