On 2014/06/26, at 15:40, Jun T. <takimot...@kba.biglobe.ne.jp> wrote: > It would be possible to make vim's sort() function stable if we save the > original > order in a separate array and ...
No, I was wrong; saving in a separate array won't work; the original order
should
be saved in the same array, as in the following *experimental* patch.
This is just an experiment; I have no intention to say that the sort()
function should be stable.
Is there any simple way to make test55 work?
PS.
I have also attached the diff file.
Which is preferred here, inline patch of attached file?
diff -r e11fcef66289 src/eval.c
--- a/src/eval.c Wed Jun 25 22:55:38 2014 +0200
+++ b/src/eval.c Thu Jun 26 20:12:20 2014 +0900
@@ -17328,6 +17328,7 @@
_RTLENTRYF
#endif
item_compare2 __ARGS((const void *s1, const void *s2));
+static int item_compare_stable __ARGS((const void *s1, const void *s2));
static int item_compare_ic;
static int item_compare_numeric;
@@ -17418,6 +17419,25 @@
return res;
}
+/* struct for stable sort */
+typedef struct sdata_S {
+ listitem_T *li;
+ int i; /* original position in the list */
+} sdata_T;
+
+ static int
+item_compare_stable(s1, s2)
+ const void *s1;
+ const void *s2;
+{
+ int ret;
+ if(item_compare_func)
+ ret = item_compare2(&((sdata_T *)s1)->li, &((sdata_T *)s2)->li);
+ else
+ ret = item_compare(&((sdata_T *)s1)->li, &((sdata_T *)s2)->li);
+ return ret==0 ? ((sdata_T *)s1)->i - ((sdata_T *)s2)->i : ret;
+}
+
/*
* "sort({list})" function
*/
@@ -17429,7 +17449,6 @@
{
list_T *l;
listitem_T *li;
- listitem_T **ptrs;
long len;
long i;
@@ -17496,29 +17515,32 @@
}
}
- /* Make an array with each entry pointing to an item in the List. */
- ptrs = (listitem_T **)alloc((int)(len * sizeof(listitem_T *)));
- if (ptrs == NULL)
- return;
-
i = 0;
if (sort)
{
- /* sort(): ptrs will be the list to sort */
- for (li = l->lv_first; li != NULL; li = li->li_next)
- ptrs[i++] = li;
+ sdata_T *sdata;
+ sdata = (sdata_T *)alloc((int)(len * sizeof(sdata_T)));
+ if (sdata == NULL)
+ return;
+
+ /* save the original position i along with the item pointer */
+ for (li = l->lv_first; li != NULL; li = li->li_next) {
+ sdata[i].li = li;
+ sdata[i].i = i;
+ ++i;
+ }
item_compare_func_err = FALSE;
/* test the compare function */
if (item_compare_func != NULL
- && item_compare2((void *)&ptrs[0], (void *)&ptrs[1])
+ && item_compare2((void *)&sdata[0].li, (void *)&sdata[1].li)
== ITEM_COMPARE_FAIL)
EMSG(_("E702: Sort compare function failed"));
else
{
/* Sort the array with item pointers. */
- qsort((void *)ptrs, (size_t)len, sizeof(listitem_T *),
- item_compare_func == NULL ? item_compare : item_compare2);
+ qsort((void *)sdata, (size_t)len, sizeof(sdata_T),
+ item_compare_stable);
if (!item_compare_func_err)
{
@@ -17526,12 +17548,19 @@
l->lv_first = l->lv_last = l->lv_idx_item = NULL;
l->lv_len = 0;
for (i = 0; i < len; ++i)
- list_append(l, ptrs[i]);
- }
- }
- }
- else
- {
+ list_append(l, sdata[i].li);
+ }
+ }
+ vim_free(sdata);
+ }
+ else
+ {
+ listitem_T **ptrs;
+ /* Make an array with each entry pointing to an item in the List. */
+ ptrs = (listitem_T **)alloc((int)(len * sizeof(listitem_T *)));
+ if (ptrs == NULL)
+ return;
+
int (*item_compare_func_ptr)__ARGS((const void *, const void *));
/* f_uniq(): ptrs will be a stack of items to remove */
@@ -17567,9 +17596,9 @@
l->lv_len--;
}
}
- }
-
- vim_free(ptrs);
+ vim_free(ptrs);
+ }
+
}
}
--
--
You received this message from the "vim_dev" maillist.
Do not top-post! Type your reply below the text you are replying to.
For more information, visit http://www.vim.org/maillist.php
---
You received this message because you are subscribed to the Google Groups
"vim_dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to vim_dev+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
stable-sort.diff
Description: Binary data
