diff options
author | John R. Lenton <jlenton@gmail.com> | 2014-01-07 17:29:16 +0000 |
---|---|---|
committer | John R. Lenton <jlenton@gmail.com> | 2014-01-07 17:29:16 +0000 |
commit | c06763a0207dde7f2060f7b1670a0b99298a01f8 (patch) | |
tree | 2f28c6e8824849f167a9b133c2d23c3c55c727d9 /py/objlist.c | |
parent | 880ce2d7fabc127b4bca7b6f2ea8b82d0977045f (diff) | |
download | micropython-c06763a0207dde7f2060f7b1670a0b99298a01f8.tar.gz micropython-c06763a0207dde7f2060f7b1670a0b99298a01f8.zip |
This implements a better (more python-conformant) list.sort.
It's not really about that, though; it's about me figuring out a sane
way forward for keyword-argument functions (and function
metadata). But it's useful as is, and shouldn't break any existing
code, so here you have it; I'm going to park it in my mind for a bit
while sorting out the rest of the dict branch.
Diffstat (limited to 'py/objlist.c')
-rw-r--r-- | py/objlist.c | 45 |
1 files changed, 31 insertions, 14 deletions
diff --git a/py/objlist.c b/py/objlist.c index 02a6b1525b..a39586a4cd 100644 --- a/py/objlist.c +++ b/py/objlist.c @@ -8,6 +8,7 @@ #include "mpconfig.h" #include "mpqstr.h" #include "obj.h" +#include "map.h" #include "runtime0.h" #include "runtime.h" @@ -119,14 +120,15 @@ static mp_obj_t list_pop(int n_args, const mp_obj_t *args) { } // TODO make this conform to CPython's definition of sort -static void mp_quicksort(mp_obj_t *head, mp_obj_t *tail, mp_obj_t key_fn) { +static void mp_quicksort(mp_obj_t *head, mp_obj_t *tail, mp_obj_t key_fn, bool reversed) { + int op = reversed ? RT_COMPARE_OP_MORE : RT_COMPARE_OP_LESS; while (head < tail) { mp_obj_t *h = head - 1; mp_obj_t *t = tail; - mp_obj_t v = rt_call_function_1(key_fn, tail[0]); // get pivot using key_fn + mp_obj_t v = key_fn == NULL ? tail[0] : rt_call_function_1(key_fn, tail[0]); // get pivot using key_fn for (;;) { - do ++h; while (rt_compare_op(RT_COMPARE_OP_LESS, rt_call_function_1(key_fn, h[0]), v) == mp_const_true); - do --t; while (h < t && rt_compare_op(RT_COMPARE_OP_LESS, v, rt_call_function_1(key_fn, t[0])) == mp_const_true); + do ++h; while (rt_compare_op(op, key_fn == NULL ? h[0] : rt_call_function_1(key_fn, h[0]), v) == mp_const_true); + do --t; while (h < t && rt_compare_op(op, v, key_fn == NULL ? t[0] : rt_call_function_1(key_fn, t[0])) == mp_const_true); if (h >= t) break; mp_obj_t x = h[0]; h[0] = t[0]; @@ -135,16 +137,31 @@ static void mp_quicksort(mp_obj_t *head, mp_obj_t *tail, mp_obj_t key_fn) { mp_obj_t x = h[0]; h[0] = tail[0]; tail[0] = x; - mp_quicksort(head, t, key_fn); + mp_quicksort(head, t, key_fn, reversed); head = h + 1; } } -static mp_obj_t list_sort(mp_obj_t self_in, mp_obj_t key_fn) { - assert(MP_OBJ_IS_TYPE(self_in, &list_type)); - mp_obj_list_t *self = self_in; +static mp_obj_t list_sort(mp_obj_t *args, mp_map_t *kwargs) { + mp_obj_t *args_items = NULL; + machine_uint_t args_len = 0; + qstr key_idx = qstr_from_str_static("key"); + qstr reverse_idx = qstr_from_str_static("reverse"); + + assert(MP_OBJ_IS_TYPE(args, &tuple_type)); + mp_obj_tuple_get(args, &args_len, &args_items); + assert(args_len >= 1); + if (args_len > 1) { + nlr_jump(mp_obj_new_exception_msg(MP_QSTR_TypeError, + "list.sort takes no positional arguments")); + } + mp_obj_list_t *self = args_items[0]; if (self->len > 1) { - mp_quicksort(self->items, self->items + self->len - 1, key_fn); + mp_map_elem_t *keyfun = mp_qstr_map_lookup(kwargs, key_idx, false); + mp_map_elem_t *reverse = mp_qstr_map_lookup(kwargs, reverse_idx, false); + mp_quicksort(self->items, self->items + self->len - 1, + keyfun ? keyfun->value : NULL, + reverse && reverse->value ? rt_is_true(reverse->value) : false); } return mp_const_none; // return None, as per CPython } @@ -258,11 +275,11 @@ static MP_DEFINE_CONST_FUN_OBJ_3(list_insert_obj, list_insert); static MP_DEFINE_CONST_FUN_OBJ_VAR_BETWEEN(list_pop_obj, 1, 2, list_pop); static MP_DEFINE_CONST_FUN_OBJ_2(list_remove_obj, list_remove); static MP_DEFINE_CONST_FUN_OBJ_1(list_reverse_obj, list_reverse); -static MP_DEFINE_CONST_FUN_OBJ_2(list_sort_obj, list_sort); +static MP_DEFINE_CONST_FUN_OBJ_KW(list_sort_obj, list_sort); const mp_obj_type_t list_type = { - { &mp_const_type }, - "list", + .base = { &mp_const_type }, + .name = "list", .print = list_print, .make_new = list_make_new, .unary_op = NULL, @@ -341,8 +358,8 @@ mp_obj_t list_it_iternext(mp_obj_t self_in) { } static const mp_obj_type_t list_it_type = { - { &mp_const_type }, - "list_iterator", + .base = { &mp_const_type }, + .name = "list_iterator", .iternext = list_it_iternext, .methods = { { NULL, NULL }, }, }; |