OoasTools

// C5 example

// 2004-11

using System;

using C5;

using SCG = System.Collections.Generic;

namespace SortingPermutation

{

  class MyTest

  {

    public static void Main(String[] args)

    {

      String[] cities = 

      { "Tokyo", "Beijing", "Hangzhou", "Kyoto", "Beijing", "Copenhagen", "Seattle" };

      IList<String> alst = new ArrayList<String>();

      alst.AddAll<String>(cities);

      foreach (int i in MySort.GetPermutation1(alst))

        Console.Write("{0} ", i);

      Console.WriteLine();

      IList<String> llst = new LinkedList<String>();

      llst.AddAll<String>(cities);

      foreach (int i in MySort.GetPermutation2(llst))

        Console.Write("{0} ", i);

      Console.WriteLine();

      Console.WriteLine("The rank of the cities:");

      ArrayList<int> res = MySort.GetPermutation1(MySort.GetPermutation2(llst));

      foreach (int i in res)

        Console.Write("{0} ", i);

      Console.WriteLine();

    }

  }

  class MySort

  {

    // Fast for array lists and similar, but not stable; slow for linked lists

    public static ArrayList<int> GetPermutation1<T>(IList<T> lst)

      where T : IComparable<T>

    {

      ArrayList<int> res = new ArrayList<int>(lst.Count);

      for (int i = 0; i < lst.Count; i++)

        res.Add(i);

      res.Sort(new DelegateComparer<int>

               (delegate(int i, int j) { return lst[i].CompareTo(lst[j]); }));

      return res;

    }

    // Stable and fairly fast both for array lists and linked lists, 

    // but does copy the collection's items. 

    public static ArrayList<int> GetPermutation2<T>(IList<T> lst)

      where T : IComparable<T>

    {

      int i = 0;

      IList<KeyValuePair<T, int>> zipList =

        lst.Map<KeyValuePair<T, int>>

            (delegate(T x) { return new KeyValuePair<T, int>(x, i++); });

      zipList.Sort(new KeyValueComparer<T>(lst));

      ArrayList<int> res = new ArrayList<int>(lst.Count);

      foreach (KeyValuePair<T, int> p in zipList)

        res.Add(p.Value);

      return res;

    }

    private class KeyValueComparer<T> : SCG.IComparer<KeyValuePair<T, int>>

      where T : IComparable<T>

    {

      private readonly IList<T> lst;

      public KeyValueComparer(IList<T> lst)

      {

        this.lst = lst;

      }

      public int Compare(KeyValuePair<T, int> p1, KeyValuePair<T, int> p2)

      {

        return p1.Key.CompareTo(p2.Key);

      }

    }

  }

}