* Apply http://opensimulator.org/mantis/view.php?id=3165

* Corrects behaviour of llListSort()
* Thanks DoranZemlja!

2 files changed, 110 insertions, 125 deletions

diff --git a/CONTRIBUTORS.txt b/CONTRIBUTORS.txt
index b89d328..28ede78 100644
--- a/CONTRIBUTORS.txt
+++ b/CONTRIBUTORS.txt
@@ -46,6 +46,7 @@ Patches
 * ChrisDown
 * Chris Yeoh
 * Daedius
+* DoranZemlja
 * daTwitch 
 * devalnor-#708
 * dmiles (Daxtron Labs)
diff --git a/OpenSim/Region/ScriptEngine/Shared/LSL_Types.cs b/OpenSim/Region/ScriptEngine/Shared/LSL_Types.cs
index 05f254a..e5e097b 100644
--- a/OpenSim/Region/ScriptEngine/Shared/LSL_Types.cs
+++ b/OpenSim/Region/ScriptEngine/Shared/LSL_Types.cs
@@ -372,6 +372,11 @@ namespace OpenSim.Region.ScriptEngine.Shared
                 return !(lhs == rhs);
             }
 
+            public static double Mag(Quaternion q)
+            {
+                return Math.Sqrt(q.x * q.x + q.y * q.y + q.z * q.z + q.s * q.s);
+            }
+
             #endregion
 
             public static Quaternion operator +(Quaternion a, Quaternion b)
@@ -742,95 +747,72 @@ namespace OpenSim.Region.ScriptEngine.Shared
                 }
             }
 
-            private class AlphanumComparatorFast : IComparer
+            private static int compare(object left, object right, int ascending)
             {
-                public int Compare(object x, object y)
+                if (!left.GetType().Equals(right.GetType()))
                 {
-                    string s1 = x as string;
-                    if (s1 == null)
-                    {
-                        return 0;
-                    }
-                    string s2 = y as string;
-                    if (s2 == null)
-                    {
-                        return 0;
-                    }
-
-                    int len1 = s1.Length;
-                    int len2 = s2.Length;
-                    int marker1 = 0;
-                    int marker2 = 0;
-
-                    // Walk through two the strings with two markers.
-                    while (marker1 < len1 && marker2 < len2)
-                    {
-                        char ch1 = s1[marker1];
-                        char ch2 = s2[marker2];
-
-                        // Some buffers we can build up characters in for each chunk.
-                        char[] space1 = new char[len1];
-                        int loc1 = 0;
-                        char[] space2 = new char[len2];
-                        int loc2 = 0;
-
-                        // Walk through all following characters that are digits or
-                        // characters in BOTH strings starting at the appropriate marker.
-                        // Collect char arrays.
-                        do
-                        {
-                            space1[loc1++] = ch1;
-                            marker1++;
-
-                            if (marker1 < len1)
-                            {
-                                ch1 = s1[marker1];
-                            }
-                            else
-                            {
-                                break;
-                            }
-                        } while (char.IsDigit(ch1) == char.IsDigit(space1[0]));
+                    // unequal types are always "equal" for comparison purposes.
+                    // this way, the bubble sort will never swap them, and we'll
+                    // get that feathered effect we're looking for
+                    return 0;
+                }
 
-                        do
-                        {
-                            space2[loc2++] = ch2;
-                            marker2++;
+                int ret = 0;
 
-                            if (marker2 < len2)
-                            {
-                                ch2 = s2[marker2];
-                            }
-                            else
-                            {
-                                break;
-                            }
-                        } while (char.IsDigit(ch2) == char.IsDigit(space2[0]));
+                if (left is key)
+                {
+                    key l = (key)left;
+                    key r = (key)right;
+                    ret = String.CompareOrdinal(l.value, r.value);
+                }
+                else if (left is LSLString)
+                {
+                    LSLString l = (LSLString)left;
+                    LSLString r = (LSLString)right;
+                    ret = String.CompareOrdinal(l.m_string, r.m_string);
+                }
+                else if (left is LSLInteger)
+                {
+                    LSLInteger l = (LSLInteger)left;
+                    LSLInteger r = (LSLInteger)right;
+                    ret = Math.Sign(l.value - r.value);
+                }
+                else if (left is LSLFloat)
+                {
+                    LSLFloat l = (LSLFloat)left;
+                    LSLFloat r = (LSLFloat)right;
+                    ret = Math.Sign(l.value - r.value);
+                }
+                else if (left is Vector3)
+                {
+                    Vector3 l = (Vector3)left;
+                    Vector3 r = (Vector3)right;
+                    ret = Math.Sign(Vector3.Mag(l) - Vector3.Mag(r));
+                }
+                else if (left is Quaternion)
+                {
+                    Quaternion l = (Quaternion)left;
+                    Quaternion r = (Quaternion)right;
+                    ret = Math.Sign(Quaternion.Mag(l) - Quaternion.Mag(r));
+                }
 
-                        // If we have collected numbers, compare them numerically.
-                        // Otherwise, if we have strings, compare them alphabetically.
-                        string str1 = new string(space1);
-                        string str2 = new string(space2);
+                if (ascending == 0)
+                {
+                    ret = 0 - ret;
+                }
 
-                        int result;
+                return ret;
+            }
 
-                        if (char.IsDigit(space1[0]) && char.IsDigit(space2[0]))
-                        {
-                            int thisNumericChunk = int.Parse(str1);
-                            int thatNumericChunk = int.Parse(str2);
-                            result = thisNumericChunk.CompareTo(thatNumericChunk);
-                        }
-                        else
-                        {
-                            result = str1.CompareTo(str2);
-                        }
+            class HomogeneousComparer : IComparer
+            {
+                public HomogeneousComparer()
+                {
+                }
 
-                        if (result != 0)
-                        {
-                            return result;
-                        }
-                    }
-                    return len1 - len2;
+                public int Compare(object lhs, object rhs)
+                {
+                    return compare(lhs, rhs, 1);
                 }
             }
 
@@ -839,68 +821,70 @@ namespace OpenSim.Region.ScriptEngine.Shared
                 if (Data.Length == 0)
                     return new list(); // Don't even bother
 
-                string[] keys;
+                object[] ret = new object[Data.Length];
+                Array.Copy(Data, 0, ret, 0, Data.Length);
 
-                if (stride == 1) // The simple case
+                if (stride <= 0)
                 {
-                    Object[] ret=new Object[Data.Length];
-
-                    Array.Copy(Data, 0, ret, 0, Data.Length);
-
-                    keys=new string[Data.Length];
+                    stride = 1;
+                }
 
-                    for (int k = 0; k < Data.Length; k++)
-                        keys[k] = Data[k].ToString();
+                // we can optimize here in the case where stride == 1 and the list
+                // consists of homogeneous types
 
-                    Array.Sort( keys, ret, new AlphanumComparatorFast() );
+                if (stride == 1)
+                {
+                    bool homogeneous = true;
+                    int index;
+                    for (index = 1; index < Data.Length; index++)
+                    {
+                        if (!Data[0].GetType().Equals(Data[index].GetType()))
+                        {
+                            homogeneous = false;
+                            break;
+                        }
+                    }
 
-                    if (ascending == 0)
-                        Array.Reverse(ret);
-                    return new list(ret);
+                    if (homogeneous)
+                    {
+                        Array.Sort(ret, new HomogeneousComparer());
+                        if (ascending == 0)
+                        {
+                            Array.Reverse(ret);
+                        }
+                        return new list(ret);
+                    }
                 }
 
-                int src=0;
-
-                int len=(Data.Length+stride-1)/stride;
-
-                keys=new string[len];
-                Object[][] vals=new Object[len][];
+                // Because of the desired type specific feathered sorting behavior
+                // requried by the spec, we MUST use a non-optimized bubble sort here.
+                // Anything else will give you the incorrect behavior.
 
+                // begin bubble sort...
                 int i;
+                int j;
+                int k;
+                int n = Data.Length;
 
-                while (src < Data.Length)
+                for (i = 0; i < (n-stride); i += stride)
                 {
-                    Object[] o=new Object[stride];
-
-                    for (i = 0; i < stride; i++)
+                    for (j = i + stride; j < n; j += stride)
                     {
-                        if (src < Data.Length)
-                            o[i]=Data[src++];
-                        else
+                        if (compare(ret[i], ret[j], ascending) > 0)
                         {
-                            o[i]=new Object();
-                            src++;
+                            for (k = 0; k < stride; k++)
+                            {
+                                object tmp = ret[i + k];
+                                ret[i + k] = ret[j + k];
+                                ret[j + k] = tmp;
+                            }
                         }
                     }
-
-                    int idx=src/stride-1;
-                    keys[idx]=o[0].ToString();
-                    vals[idx]=o;
                 }
 
-                Array.Sort(keys, vals, new AlphanumComparatorFast());
-                if (ascending == 0)
-                {
-                    Array.Reverse(vals);
-                }
-
-                Object[] sorted=new Object[stride*vals.Length];
+                // end bubble sort
 
-                for (i = 0; i < vals.Length; i++)
-                    for (int j = 0; j < stride; j++)
-                        sorted[i*stride+j] = vals[i][j];
-
-                return new list(sorted);
+                return new list(ret);
             }
 
             #region CSV Methods