Mega Code Archive
A simple stable sorting routine - far from being efficient, only for small collections
<![CDATA[
#region License
/*
* Copyright 2002-2005 the original author or authors.
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
#endregion
#region Imports
using System;
using System.Collections;
using System.Reflection;
#endregion
namespace Spring.Util
{
/// <summary>
/// Miscellaneous collection utility methods.
/// </summary>
/// <remarks>
/// Mainly for internal use within the framework.
/// </remarks>
/// <author>Mark Pollack (.NET)</author>
public sealed class CollectionUtils
{
/// <summary>
/// A callback method used for comparing to items.
/// </summary>
/// <remarks>
/// </remarks>
/// <param name="left">the first object to compare</param>
/// <param name="right">the second object to compare</param>
/// <returns>Value Condition Less than zero x is less than y. Zero x equals y. Greater than zero x is greater than y.</returns>
/// <seealso cref="IComparer.Compare"/>
/// <seealso cref="CollectionUtils.StableSort(IEnumerable,CompareCallback)"/>
public delegate int CompareCallback(object left, object right);
/// <summary>
/// A simple stable sorting routine - far from being efficient, only for small collections.
/// </summary>
/// <param name="input"></param>
/// <param name="comparer"></param>
/// <returns></returns>
public static ICollection StableSort(IEnumerable input, IComparer comparer)
{
return StableSort(input, new CompareCallback(comparer.Compare));
}
/// <summary>
/// A simple stable sorting routine - far from being efficient, only for small collections.
/// </summary>
/// <remarks>
/// Sorting is not(!) done in-place. Instead a sorted copy of the original input is returned.
/// </remarks>
/// <param name="input">input collection of items to sort</param>
/// <param name="comparer">the <see cref="CompareCallback"/> for comparing 2 items in <paramref name="input"/>.</param>
/// <returns>a new collection of stable sorted items.</returns>
public static ICollection StableSort(IEnumerable input, CompareCallback comparer)
{
ArrayList ehancedInput = new ArrayList();
IEnumerator it = input.GetEnumerator();
int index = 0;
while (it.MoveNext())
{
ehancedInput.Add(new Entry(index, it.Current));
index++;
}
ehancedInput.Sort(Entry.GetComparer(comparer));
for (int i = 0; i < ehancedInput.Count; i++)
{
ehancedInput[i] = ((Entry)ehancedInput[i]).Value;
}
return ehancedInput;
}
/// <summary>
/// A simple stable sorting routine - far from being efficient, only for small collections.
/// </summary>
/// <remarks>
/// Sorting is not(!) done in-place. Instead a sorted copy of the original input is returned.
/// </remarks>
/// <param name="input">input collection of items to sort</param>
/// <param name="comparer">the <see cref="IComparer"/> for comparing 2 items in <paramref name="input"/>.</param>
/// <returns>a new collection of stable sorted items.</returns>
public static void StableSortInPlace(IList input, IComparer comparer)
{
StableSortInPlace(input, new CompareCallback(comparer.Compare));
}
/// <summary>
/// A simple stable sorting routine - far from being efficient, only for small collections.
/// </summary>
/// <remarks>
/// Sorting is not(!) done in-place. Instead a sorted copy of the original input is returned.
/// </remarks>
/// <param name="input">input collection of items to sort</param>
/// <param name="comparer">the <see cref="CompareCallback"/> for comparing 2 items in <paramref name="input"/>.</param>
/// <returns>a new collection of stable sorted items.</returns>
public static void StableSortInPlace(IList input, CompareCallback comparer)
{
ArrayList ehancedInput = new ArrayList();
IEnumerator it = input.GetEnumerator();
int index = 0;
while (it.MoveNext())
{
ehancedInput.Add(new Entry(index, it.Current));
index++;
}
ehancedInput.Sort(Entry.GetComparer(comparer));
for (int i = 0; i < ehancedInput.Count; i++)
{
input[i] = ((Entry)ehancedInput[i]).Value;
}
}
#region StableSort Utility Classes
private class Entry
{
private class EntryComparer : IComparer
{
private readonly CompareCallback innerComparer;
public EntryComparer(CompareCallback innerComparer)
{
this.innerComparer = innerComparer;
}
public int Compare(object x, object y)
{
Entry ex = (Entry)x;
Entry ey = (Entry)y;
int result = innerComparer(ex.Value, ey.Value);
if (result == 0)
{
result = ex.Index.CompareTo(ey.Index);
}
return result;
}
}
public static IComparer GetComparer(CompareCallback innerComparer)
{
return new EntryComparer(innerComparer);
}
public readonly int Index;
public readonly object Value;
public Entry(int index, object value)
{
Index = index;
Value = value;
}
}
#endregion
}
}
]]>