6 using SCG = System.Collections.Generic;
\r
8 namespace SortingPermutation
\r
12 public static void Main(String[] args)
\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
36 // Fast for array lists and similar, but not stable; slow for linked lists
\r
38 public static ArrayList<int> GetPermutation1<T>(IList<T> lst)
\r
39 where T : IComparable<T>
\r
41 ArrayList<int> res = new ArrayList<int>(lst.Count);
\r
42 for (int i = 0; i < lst.Count; i++)
\r
44 res.Sort(new DelegateComparer<int>
\r
45 (delegate(int i, int j) { return lst[i].CompareTo(lst[j]); }));
\r
49 // Stable and fairly fast both for array lists and linked lists,
\r
50 // but does copy the collection's items.
\r
52 public static ArrayList<int> GetPermutation2<T>(IList<T> lst)
\r
53 where T : IComparable<T>
\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
66 private class KeyValueComparer<T> : SCG.IComparer<KeyValuePair<T, int>>
\r
67 where T : IComparable<T>
\r
69 private readonly IList<T> lst;
\r
70 public KeyValueComparer(IList<T> lst)
\r
74 public int Compare(KeyValuePair<T, int> p1, KeyValuePair<T, int> p2)
\r
76 return p1.Key.CompareTo(p2.Key);
\r