Mercurial > vim
changeset 6022:f9ec944e4474 v7.4.351
updated for version 7.4.351
Problem: sort() is not stable.
Solution: When the items are identical, compare the pointers.
| author | Bram Moolenaar <bram@vim.org> |
|---|---|
| date | Wed, 02 Jul 2014 19:06:18 +0200 |
| parents | 9c68b3561d82 |
| children | 65ccaeb4de08 |
| files | src/eval.c src/testdir/test55.in src/testdir/test55.ok src/version.c |
| diffstat | 4 files changed, 24 insertions(+), 7 deletions(-) [+] |
line wrap: on
line diff
--- a/src/eval.c +++ b/src/eval.c @@ -17334,6 +17334,7 @@ static int item_compare_numeric; static char_u *item_compare_func; static dict_T *item_compare_selfdict; static int item_compare_func_err; +static int item_compare_keep_zero; static void do_sort_uniq __ARGS((typval_T *argvars, typval_T *rettv, int sort)); #define ITEM_COMPARE_FAIL 999 @@ -17374,6 +17375,12 @@ item_compare(s1, s2) n2 = strtod((char *)p2, (char **)&p2); res = n1 == n2 ? 0 : n1 > n2 ? 1 : -1; } + + /* When the result would be zero, compare the pointers themselves. Makes + * the sort stable. */ + if (res == 0 && !item_compare_keep_zero) + res = s1 > s2 ? 1 : -1; + vim_free(tofree1); vim_free(tofree2); return res; @@ -17396,7 +17403,7 @@ item_compare2(s1, s2) if (item_compare_func_err) return 0; - /* copy the values. This is needed to be able to set v_lock to VAR_FIXED + /* Copy the values. This is needed to be able to set v_lock to VAR_FIXED * in the copy without changing the original list items. */ copy_tv(&(*(listitem_T **)s1)->li_tv, &argv[0]); copy_tv(&(*(listitem_T **)s2)->li_tv, &argv[1]); @@ -17415,6 +17422,12 @@ item_compare2(s1, s2) if (item_compare_func_err) res = ITEM_COMPARE_FAIL; /* return value has wrong type */ clear_tv(&rettv); + + /* When the result would be zero, compare the pointers themselves. Makes + * the sort stable. */ + if (res == 0 && !item_compare_keep_zero) + res = s1 > s2 ? 1 : -1; + return res; } @@ -17509,6 +17522,7 @@ do_sort_uniq(argvars, rettv, sort) ptrs[i++] = li; item_compare_func_err = FALSE; + item_compare_keep_zero = FALSE; /* test the compare function */ if (item_compare_func != NULL && item_compare2((void *)&ptrs[0], (void *)&ptrs[1]) @@ -17536,6 +17550,7 @@ do_sort_uniq(argvars, rettv, sort) /* f_uniq(): ptrs will be a stack of items to remove */ item_compare_func_err = FALSE; + item_compare_keep_zero = TRUE; item_compare_func_ptr = item_compare_func ? item_compare2 : item_compare;
--- a/src/testdir/test55.in +++ b/src/testdir/test55.in @@ -332,9 +332,9 @@ let l = [0, 1, 2, 3] :$put =string(reverse(sort(l))) :$put =string(sort(reverse(sort(l)))) :$put =string(uniq(sort(l))) -:let l=[7, 9, 18, 12, 22, 10.0e-16, -1, 0xff, 0.22, 'foo'] +:let l=[7, 9, 'one', 18, 12, 22, 'two', 10.0e-16, -1, 'three', 0xff, 0.22, 'four'] :$put =string(sort(copy(l), 'n')) -:let l=[7, 9, 18, 12, 22, 10.0e-16, -1, 0xff, 0, -0, 0.22, 'foo', 'FOOBAR',{}, []] +:let l=[7, 9, 18, 12, 22, 10.0e-16, -1, 0xff, 0, -0, 0.22, 'bar', 'BAR', 'Bar', 'Foo', 'FOO', 'foo', 'FOOBAR', {}, []] :$put =string(sort(copy(l), 1)) :$put =string(sort(copy(l), 'i')) :$put =string(sort(copy(l)))
--- a/src/testdir/test55.ok +++ b/src/testdir/test55.ok @@ -101,10 +101,10 @@ caught a:000[3] [[0, 1, 2], [0, 1, 2], 4, 2, 2, 1.5, 'xaaa', 'x8', 'foo6', 'foo', 'foo', 'A11', '-0'] ['-0', 'A11', 'foo', 'foo', 'foo6', 'x8', 'xaaa', 1.5, 2, 2, 4, [0, 1, 2], [0, 1, 2]] ['-0', 'A11', 'foo', 'foo6', 'x8', 'xaaa', 1.5, 2, 4, [0, 1, 2]] -[-1, 'foo', 1.0e-15, 0.22, 7, 9, 12, 18, 22, 255] -['foo', 'FOOBAR', -1, 0, 0, 0.22, 1.0e-15, 12, 18, 22, 255, 7, 9, [], {}] -['foo', 'FOOBAR', -1, 0, 0, 0.22, 1.0e-15, 12, 18, 22, 255, 7, 9, [], {}] -['FOOBAR', 'foo', -1, 0, 0, 0.22, 1.0e-15, 12, 18, 22, 255, 7, 9, [], {}] +[-1, 'one', 'two', 'three', 'four', 1.0e-15, 0.22, 7, 9, 12, 18, 22, 255] +['bar', 'BAR', 'Bar', 'Foo', 'FOO', 'foo', 'FOOBAR', -1, 0, 0, 0.22, 1.0e-15, 12, 18, 22, 255, 7, 9, [], {}] +['bar', 'BAR', 'Bar', 'Foo', 'FOO', 'foo', 'FOOBAR', -1, 0, 0, 0.22, 1.0e-15, 12, 18, 22, 255, 7, 9, [], {}] +['BAR', 'Bar', 'FOO', 'FOOBAR', 'Foo', 'bar', 'foo', -1, 0, 0, 0.22, 1.0e-15, 12, 18, 22, 255, 7, 9, [], {}] ['aa', 'bb'] ['aa', 'bb'] ['', 'aa', 'bb', '']