aboutsummaryrefslogtreecommitdiffstatshomepage
path: root/OpenSim
diff options
context:
space:
mode:
authorJustin Clarke Casey2009-02-16 16:31:07 +0000
committerJustin Clarke Casey2009-02-16 16:31:07 +0000
commit9dadf7adfd3ede794ef3bf1ff9d65cf8ab6a9455 (patch)
tree582ac577c891c1228677f56c815d3d8c8202e32f /OpenSim
parent* minor: print out status messages at start and end of inventory archive load... (diff)
downloadopensim-SC_OLD-9dadf7adfd3ede794ef3bf1ff9d65cf8ab6a9455.zip
opensim-SC_OLD-9dadf7adfd3ede794ef3bf1ff9d65cf8ab6a9455.tar.gz
opensim-SC_OLD-9dadf7adfd3ede794ef3bf1ff9d65cf8ab6a9455.tar.bz2
opensim-SC_OLD-9dadf7adfd3ede794ef3bf1ff9d65cf8ab6a9455.tar.xz
* Apply http://opensimulator.org/mantis/view.php?id=3165
* Corrects behaviour of llListSort() * Thanks DoranZemlja!
Diffstat (limited to 'OpenSim')
-rw-r--r--OpenSim/Region/ScriptEngine/Shared/LSL_Types.cs234
1 files changed, 109 insertions, 125 deletions
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
372 return !(lhs == rhs); 372 return !(lhs == rhs);
373 } 373 }
374 374
375 public static double Mag(Quaternion q)
376 {
377 return Math.Sqrt(q.x * q.x + q.y * q.y + q.z * q.z + q.s * q.s);
378 }
379
375 #endregion 380 #endregion
376 381
377 public static Quaternion operator +(Quaternion a, Quaternion b) 382 public static Quaternion operator +(Quaternion a, Quaternion b)
@@ -742,95 +747,72 @@ namespace OpenSim.Region.ScriptEngine.Shared
742 } 747 }
743 } 748 }
744 749
745 private class AlphanumComparatorFast : IComparer 750 private static int compare(object left, object right, int ascending)
746 { 751 {
747 public int Compare(object x, object y) 752 if (!left.GetType().Equals(right.GetType()))
748 { 753 {
749 string s1 = x as string; 754 // unequal types are always "equal" for comparison purposes.
750 if (s1 == null) 755 // this way, the bubble sort will never swap them, and we'll
751 { 756 // get that feathered effect we're looking for
752 return 0; 757 return 0;
753 } 758 }
754 string s2 = y as string;
755 if (s2 == null)
756 {
757 return 0;
758 }
759
760 int len1 = s1.Length;
761 int len2 = s2.Length;
762 int marker1 = 0;
763 int marker2 = 0;
764
765 // Walk through two the strings with two markers.
766 while (marker1 < len1 && marker2 < len2)
767 {
768 char ch1 = s1[marker1];
769 char ch2 = s2[marker2];
770
771 // Some buffers we can build up characters in for each chunk.
772 char[] space1 = new char[len1];
773 int loc1 = 0;
774 char[] space2 = new char[len2];
775 int loc2 = 0;
776
777 // Walk through all following characters that are digits or
778 // characters in BOTH strings starting at the appropriate marker.
779 // Collect char arrays.
780 do
781 {
782 space1[loc1++] = ch1;
783 marker1++;
784
785 if (marker1 < len1)
786 {
787 ch1 = s1[marker1];
788 }
789 else
790 {
791 break;
792 }
793 } while (char.IsDigit(ch1) == char.IsDigit(space1[0]));
794 759
795 do 760 int ret = 0;
796 {
797 space2[loc2++] = ch2;
798 marker2++;
799 761
800 if (marker2 < len2) 762 if (left is key)
801 { 763 {
802 ch2 = s2[marker2]; 764 key l = (key)left;
803 } 765 key r = (key)right;
804 else 766 ret = String.CompareOrdinal(l.value, r.value);
805 { 767 }
806 break; 768 else if (left is LSLString)
807 } 769 {
808 } while (char.IsDigit(ch2) == char.IsDigit(space2[0])); 770 LSLString l = (LSLString)left;
771 LSLString r = (LSLString)right;
772 ret = String.CompareOrdinal(l.m_string, r.m_string);
773 }
774 else if (left is LSLInteger)
775 {
776 LSLInteger l = (LSLInteger)left;
777 LSLInteger r = (LSLInteger)right;
778 ret = Math.Sign(l.value - r.value);
779 }
780 else if (left is LSLFloat)
781 {
782 LSLFloat l = (LSLFloat)left;
783 LSLFloat r = (LSLFloat)right;
784 ret = Math.Sign(l.value - r.value);
785 }
786 else if (left is Vector3)
787 {
788 Vector3 l = (Vector3)left;
789 Vector3 r = (Vector3)right;
790 ret = Math.Sign(Vector3.Mag(l) - Vector3.Mag(r));
791 }
792 else if (left is Quaternion)
793 {
794 Quaternion l = (Quaternion)left;
795 Quaternion r = (Quaternion)right;
796 ret = Math.Sign(Quaternion.Mag(l) - Quaternion.Mag(r));
797 }
809 798
810 // If we have collected numbers, compare them numerically. 799 if (ascending == 0)
811 // Otherwise, if we have strings, compare them alphabetically. 800 {
812 string str1 = new string(space1); 801 ret = 0 - ret;
813 string str2 = new string(space2); 802 }
814 803
815 int result; 804 return ret;
805 }
816 806
817 if (char.IsDigit(space1[0]) && char.IsDigit(space2[0])) 807 class HomogeneousComparer : IComparer
818 { 808 {
819 int thisNumericChunk = int.Parse(str1); 809 public HomogeneousComparer()
820 int thatNumericChunk = int.Parse(str2); 810 {
821 result = thisNumericChunk.CompareTo(thatNumericChunk); 811 }
822 }
823 else
824 {
825 result = str1.CompareTo(str2);
826 }
827 812
828 if (result != 0) 813 public int Compare(object lhs, object rhs)
829 { 814 {
830 return result; 815 return compare(lhs, rhs, 1);
831 }
832 }
833 return len1 - len2;
834 } 816 }
835 } 817 }
836 818
@@ -839,68 +821,70 @@ namespace OpenSim.Region.ScriptEngine.Shared
839 if (Data.Length == 0) 821 if (Data.Length == 0)
840 return new list(); // Don't even bother 822 return new list(); // Don't even bother
841 823
842 string[] keys; 824 object[] ret = new object[Data.Length];
825 Array.Copy(Data, 0, ret, 0, Data.Length);
843 826
844 if (stride == 1) // The simple case 827 if (stride <= 0)
845 { 828 {
846 Object[] ret=new Object[Data.Length]; 829 stride = 1;
847 830 }
848 Array.Copy(Data, 0, ret, 0, Data.Length);
849
850 keys=new string[Data.Length];
851 831
852 for (int k = 0; k < Data.Length; k++) 832 // we can optimize here in the case where stride == 1 and the list
853 keys[k] = Data[k].ToString(); 833 // consists of homogeneous types
854 834
855 Array.Sort( keys, ret, new AlphanumComparatorFast() ); 835 if (stride == 1)
836 {
837 bool homogeneous = true;
838 int index;
839 for (index = 1; index < Data.Length; index++)
840 {
841 if (!Data[0].GetType().Equals(Data[index].GetType()))
842 {
843 homogeneous = false;
844 break;
845 }
846 }
856 847
857 if (ascending == 0) 848 if (homogeneous)
858 Array.Reverse(ret); 849 {
859 return new list(ret); 850 Array.Sort(ret, new HomogeneousComparer());
851 if (ascending == 0)
852 {
853 Array.Reverse(ret);
854 }
855 return new list(ret);
856 }
860 } 857 }
861 858
862 int src=0; 859 // Because of the desired type specific feathered sorting behavior
863 860 // requried by the spec, we MUST use a non-optimized bubble sort here.
864 int len=(Data.Length+stride-1)/stride; 861 // Anything else will give you the incorrect behavior.
865
866 keys=new string[len];
867 Object[][] vals=new Object[len][];
868 862
863 // begin bubble sort...
869 int i; 864 int i;
865 int j;
866 int k;
867 int n = Data.Length;
870 868
871 while (src < Data.Length) 869 for (i = 0; i < (n-stride); i += stride)
872 { 870 {
873 Object[] o=new Object[stride]; 871 for (j = i + stride; j < n; j += stride)
874
875 for (i = 0; i < stride; i++)
876 { 872 {
877 if (src < Data.Length) 873 if (compare(ret[i], ret[j], ascending) > 0)
878 o[i]=Data[src++];
879 else
880 { 874 {
881 o[i]=new Object(); 875 for (k = 0; k < stride; k++)
882 src++; 876 {
877 object tmp = ret[i + k];
878 ret[i + k] = ret[j + k];
879 ret[j + k] = tmp;
880 }
883 } 881 }
884 } 882 }
885
886 int idx=src/stride-1;
887 keys[idx]=o[0].ToString();
888 vals[idx]=o;
889 } 883 }
890 884
891 Array.Sort(keys, vals, new AlphanumComparatorFast()); 885 // end bubble sort
892 if (ascending == 0)
893 {
894 Array.Reverse(vals);
895 }
896
897 Object[] sorted=new Object[stride*vals.Length];
898 886
899 for (i = 0; i < vals.Length; i++) 887 return new list(ret);
900 for (int j = 0; j < stride; j++)
901 sorted[i*stride+j] = vals[i][j];
902
903 return new list(sorted);
904 } 888 }
905 889
906 #region CSV Methods 890 #region CSV Methods