summaryrefslogtreecommitdiffstatshomepage
path: root/py/objlist.c
diff options
context:
space:
mode:
authorJohn R. Lenton <jlenton@gmail.com>2014-01-07 17:29:16 +0000
committerJohn R. Lenton <jlenton@gmail.com>2014-01-07 17:29:16 +0000
commitc06763a0207dde7f2060f7b1670a0b99298a01f8 (patch)
tree2f28c6e8824849f167a9b133c2d23c3c55c727d9 /py/objlist.c
parent880ce2d7fabc127b4bca7b6f2ea8b82d0977045f (diff)
downloadmicropython-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.c45
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 }, },
};