[linqbridge] push by azizatif - Fixes issue #23: Nondeterministic keySelector in OrderBy on 2012-04-16 17:07 GMT

[linqb...@googlecode.com]

Revision: b09ed8a618f6
Author: azizatif
Date: Mon Apr 16 08:51:59 2012
Log: Fixes issue #23: Nondeterministic keySelector in OrderBy
http://code.google.com/p/linqbridge/source/detail?r=b09ed8a618f6

Added:
/src/DelegatingComparer.cs
Deleted:
/src/Tuple.cs
Modified:
/src/LINQBridge.csproj
/src/OrderedEnumerable.cs
/test/LINQBridge.Tests/EnumerableFixture.cs

=======================================
--- /dev/null
+++ /src/DelegatingComparer.cs Mon Apr 16 08:51:59 2012
@@ -0,0 +1,51 @@
+#region License, Terms and Author(s)
+//
+// LINQBridge
+// Copyright (c) 2007-9 Atif Aziz, Joseph Albahari. All rights reserved.
+//
+// Author(s):
+//
+// Atif Aziz, http://www.raboof.com
+//
+// This library is free software; you can redistribute it and/or modify it
+// under the terms of the New BSD License, a copy of which should have
+// been delivered along with this distribution.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
+// PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+//
+#endregion
+
+// $Id$
+
+namespace LinqBridge
+{
+ #region Imports
+
+ using System;
+ using System.Collections.Generic;
+
+ #endregion
+
+ internal sealed class DelegatingComparer<T> : IComparer<T>
+ {
+ private readonly Func<T, T, int> _comparer;
+
+ public DelegatingComparer(Func<T, T, int> comparer)
+ {
+ if (comparer == null) throw new
ArgumentNullException("comparer");
+ _comparer = comparer;
+ }
+
+ public int Compare(T x, T y) { return _comparer(x, y); }
+ }
+}
=======================================
--- /src/Tuple.cs Sat Apr 30 12:58:58 2011
+++ /dev/null
@@ -1,77 +0,0 @@
-#region License, Terms and Author(s)
-//
-// LINQBridge
-// Copyright (c) 2007-9 Atif Aziz, Joseph Albahari. All rights reserved.
-//
-// Author(s):
-//
-// Atif Aziz, http://www.raboof.com
-//
-// This library is free software; you can redistribute it and/or modify it
-// under the terms of the New BSD License, a copy of which should have
-// been delivered along with this distribution.
-//
-// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
-// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
-// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
-// PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
-// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
-// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
-// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
-// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
-// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
-// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
-// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
-//
-#endregion
-
-// $Id: Tuple.cs 96c90603bdff 2011-04-30 12:48:09Z azizatif $
-
-namespace LinqBridge
-{
- #region Imports
-
- using System;
- using System.Collections.Generic;
- using System.Text;
-
- #endregion
-
- [ Serializable ]
- internal struct Tuple<TFirst, TSecond> : IEquatable<Tuple<TFirst,
TSecond>>
- {
- public TFirst First { get; private set; }
- public TSecond Second { get; private set; }
-
- public Tuple(TFirst first, TSecond second) : this()
- {
- First = first;
- Second = second;
- }
-
- public override bool Equals(object obj)
- {
- return obj != null
- && obj is Tuple<TFirst, TSecond>
- && base.Equals((Tuple<TFirst, TSecond>) obj);
- }
-
- public bool Equals(Tuple<TFirst, TSecond> other)
- {
- return EqualityComparer<TFirst>.Default.Equals(other.First,
First)
- &&
EqualityComparer<TSecond>.Default.Equals(other.Second, Second);
- }
-
- public override int GetHashCode()
- {
- var num = 0x7a2f0b42;
- num = (-1521134295 * num) +
EqualityComparer<TFirst>.Default.GetHashCode(First);
- return (-1521134295 * num) +
EqualityComparer<TSecond>.Default.GetHashCode(Second);
- }
-
- public override string ToString()
- {
- return string.Format(@"{{ First = {0}, Second = {1} }}",
First, Second);
- }
- }
-}
=======================================
--- /src/LINQBridge.csproj Tue Feb 7 18:32:48 2012
+++ /src/LINQBridge.csproj Mon Apr 16 08:51:59 2012
@@ -37,6 +37,7 @@
</ItemGroup>
<ItemGroup>
<Compile Include="Action.cs" />
+ <Compile Include="DelegatingComparer.cs" />
<Compile Include="Enumerable.cs" />
<Compile Include="Enumerable.g.cs">
<AutoGen>True</AutoGen>
@@ -52,7 +53,6 @@
<Compile Include="OrderedEnumerable.cs" />
<Compile Include="Properties\AssemblyInfo.cs" />
<Compile Include="Public.cs" />
- <Compile Include="Tuple.cs" />
</ItemGroup>
<ItemGroup>
<Service Include="{B4F97281-0DBD-4835-9ED8-7DFB966E87FF}" />
=======================================
--- /src/OrderedEnumerable.cs Sat Apr 30 12:58:58 2011
+++ /src/OrderedEnumerable.cs Mon Apr 16 08:51:59 2012
@@ -34,6 +34,7 @@
using System;
using System.Collections;
using System.Collections.Generic;
+ using System.Diagnostics;
using System.Linq;

#endregion
@@ -41,98 +42,67 @@
internal sealed class OrderedEnumerable<T, K> : IOrderedEnumerable<T>
{
private readonly IEnumerable<T> _source;
- private readonly List<Comparison<T>> _comparisons;
+ private readonly Func<T[], IComparer<int>, IComparer<int>>
_comparerComposer;

public OrderedEnumerable(IEnumerable<T> source,
Func<T, K> keySelector, IComparer<K> comparer, bool
descending) :
- this(source, null, keySelector, comparer, descending) {}
-
- private OrderedEnumerable(IEnumerable<T> source,
List<Comparison<T>> comparisons,
+ this(source, (_, next) => next, keySelector, comparer,
descending) {}
+
+ private OrderedEnumerable(IEnumerable<T> source,
+ Func<T[], IComparer<int>, IComparer<int>> parent,
Func<T, K> keySelector, IComparer<K> comparer, bool descending)
{
if (source == null) throw new ArgumentNullException("source");
if (keySelector == null) throw new
ArgumentNullException("keySelector");
-
+ Debug.Assert(parent != null);
+
_source = source;

comparer = comparer ?? Comparer<K>.Default;
-
- if (comparisons == null)
- comparisons = new List<Comparison<T>>(/* capacity */ 4);
-
- comparisons.Add((x, y)
- => (descending ? -1 : 1) *
comparer.Compare(keySelector(x), keySelector(y)));
-
- _comparisons = comparisons;
+ var direction = descending ? -1 : 1;
+
+ _comparerComposer = (items, next) =>
+ {
+ Debug.Assert(items != null);
+ Debug.Assert(next != null);
+
+ var keys = new K[items.Length];
+ for (var i = 0; i < items.Length; i++)
+ keys[i] = keySelector(items[i]);
+
+ return parent(items, new DelegatingComparer<int>((i, j) =>
+ {
+ var result = direction * comparer.Compare(keys[i],
keys[j]);
+ return result != 0 ? result : next.Compare(i, j);
+ }));
+ };
}

public IOrderedEnumerable<T> CreateOrderedEnumerable<KK>(
Func<T, KK> keySelector, IComparer<KK> comparer, bool
descending)
{
- return new OrderedEnumerable<T, KK>(_source, _comparisons,
keySelector, comparer, descending);
+ return new OrderedEnumerable<T, KK>(_source,
_comparerComposer, keySelector, comparer, descending);
}

public IEnumerator<T> GetEnumerator()
{
//
- // We sort using List<T>.Sort, but docs say that it performs an
+ // Sort using Array.Sort but docs say that it performs an
// unstable sort. LINQ, on the other hand, says OrderBy
performs
- // a stable sort. So convert the source sequence into a
sequence
- // of tuples where the second element tags the position of the
- // element from the source sequence (First). The position is
- // then used as a tie breaker when all keys compare equal,
- // thus making the sort stable.
+ // a stable sort. Use the item position then as a tie
+ // breaker when all keys compare equal, thus making the sort
+ // stable.
//

- var list = _source.Select(new Func<T, int, Tuple<T,
int>>(TagPosition)).ToList();
-
- list.Sort((x, y) =>
- {
- //
- // Compare keys from left to right.
- //
-
- var comparisons = _comparisons;
- for (var i = 0; i < comparisons.Count; i++)
- {
- var result = comparisons[i](x.First, y.First);
- if (result != 0)
- return result;
- }
-
- //
- // All keys compared equal so now break the tie by their
- // position in the original sequence, making the sort
stable.
- //
-
- return x.Second.CompareTo(y.Second);
- });
-
- return list.Select(new Func<Tuple<T, int>,
T>(GetFirst)).GetEnumerator();
-
- }
-
- /// <remarks>
- /// See <a
href="http://code.google.com/p/linqbridge/issues/detail?id=11">issue #11</a>
- /// for why this method is needed and cannot be expressed as a
- /// lambda at the call site.
- /// </remarks>
-
- private static Tuple<T, int> TagPosition(T e, int i)
- {
- return new Tuple<T, int>(e, i);
- }
-
- /// <remarks>
- /// See <a
href="http://code.google.com/p/linqbridge/issues/detail?id=11">issue #11</a>
- /// for why this method is needed and cannot be expressed as a
- /// lambda at the call site.
- /// </remarks>
-
- private static T GetFirst(Tuple<T, int> pv)
- {
- return pv.First;
- }
+ var items = _source.ToArray();
+ var positionComparer = new DelegatingComparer<int>((i, j) =>
i.CompareTo(j));
+ var comparer = _comparerComposer(items, positionComparer);
+ var keys = new int[items.Length];
+ for (var i = 0; i < keys.Length; i++)
+ keys[i] = i;
+ Array.Sort(keys, items, comparer);
+ return ((IEnumerable<T>) items).GetEnumerator();
+ }

IEnumerator IEnumerable.GetEnumerator()
{
=======================================
--- /test/LINQBridge.Tests/EnumerableFixture.cs Sat Apr 30 12:06:40 2011
+++ /test/LINQBridge.Tests/EnumerableFixture.cs Mon Apr 16 08:51:59 2012
@@ -1492,6 +1492,16 @@
Assert.That(e.MoveNext(), Is.False);
}
}
+
+ [Test(Description
= "http://code.google.com/p/linqbridge/issues/detail?id=23")]
+ public void OrderBy_KeySelector_Deterministic()
+ {
+ var values = "abcd".ToCharArray();
+ var key = values.Length;
+ values = values.OrderBy(_ => key--).ToArray();
+ Assert.AreEqual("dcba", new String(values));
+ Assert.AreEqual(0, key, "Key for every element is computed
only once");
+ }

[Test]
public void
ThenBy_KeySelector_DataWithDuplicateKeys_YieldsStablySortedData()