diff options
author | Stephen Dolan <mu@netsoc.tcd.ie> | 2012-11-30 20:27:16 +0000 |
---|---|---|
committer | Stephen Dolan <mu@netsoc.tcd.ie> | 2012-11-30 20:27:16 +0000 |
commit | 9e743d517a047566996181549f05383948c0d0c0 (patch) | |
tree | 8b1f2cf797aae03cf821d34bc91e62139482cb52 | |
parent | 2dad2bdd974e6964e739f9bd09c7ad2c4025d00b (diff) |
Sort function and more general comparison operators.
-rw-r--r-- | builtin.c | 66 | ||||
-rw-r--r-- | jv_aux.c | 190 | ||||
-rw-r--r-- | jv_aux.h | 6 | ||||
-rw-r--r-- | testdata | 4 |
4 files changed, 219 insertions, 47 deletions
@@ -3,6 +3,7 @@ #include "compile.h" #include "parser.h" #include "locfile.h" +#include "jv_aux.h" enum { CMP_OP_LESS, @@ -127,22 +128,11 @@ static void f_notequal(jv input[], jv output[]) { static void order_cmp(jv input[], jv output[], int op) { jv_free(input[0]); - jv a = input[2]; - jv b = input[1]; - if (jv_get_kind(a) == JV_KIND_NUMBER && jv_get_kind(b) == JV_KIND_NUMBER) { - double da = jv_number_value(a); - double db = jv_number_value(b); - output[0] = jv_bool((op == CMP_OP_LESS && da < db) || - (op == CMP_OP_LESSEQ && da <= db) || - (op == CMP_OP_GREATEREQ && da >= db) || - (op == CMP_OP_GREATER && da > db)); - } else { - output[0] = jv_invalid_with_msg(jv_string_fmt("Attempted to compare order of %s wrt %s", - jv_kind_name(jv_get_kind(a)), - jv_kind_name(jv_get_kind(b)))); - jv_free(a); - jv_free(b); - } + int r = jv_cmp(input[2], input[1]); + output[0] = jv_bool((op == CMP_OP_LESS && r < 0) || + (op == CMP_OP_LESSEQ && r <= 0) || + (op == CMP_OP_GREATEREQ && r >= 0) || + (op == CMP_OP_GREATER && r > 0)); } static void f_less(jv input[], jv output[]) { @@ -222,38 +212,9 @@ static void f_tostring(jv input[], jv output[]) { } } -static int string_cmp(const void* pa, const void* pb){ - const jv* a = pa; - const jv* b = pb; - int lena = jv_string_length(jv_copy(*a)); - int lenb = jv_string_length(jv_copy(*b)); - int minlen = lena < lenb ? lena : lenb; - int r = memcmp(jv_string_value(*a), jv_string_value(*b), minlen); - if (r == 0) r = lena - lenb; - return r; -} - static void f_keys(jv input[], jv output[]) { - if (jv_get_kind(input[0]) == JV_KIND_OBJECT) { - int nkeys = jv_object_length(jv_copy(input[0])); - jv* keys = malloc(sizeof(jv) * nkeys); - int kidx = 0; - jv_object_foreach(i, input[0]) { - keys[kidx++] = jv_object_iter_key(input[0], i); - } - qsort(keys, nkeys, sizeof(jv), string_cmp); - output[0] = jv_array_sized(nkeys); - for (int i = 0; i<nkeys; i++) { - output[0] = jv_array_append(output[0], keys[i]); - } - free(keys); - jv_free(input[0]); - } else if (jv_get_kind(input[0]) == JV_KIND_ARRAY) { - int n = jv_array_length(input[0]); - output[0] = jv_array(); - for (int i=0; i<n; i++){ - output[0] = jv_array_set(output[0], i, jv_number(i)); - } + if (jv_get_kind(input[0]) == JV_KIND_OBJECT || jv_get_kind(input[0]) == JV_KIND_ARRAY) { + output[0] = jv_keys(input[0]); } else { output[0] = jv_invalid_with_msg(jv_string_fmt("'keys' only supports object, not %s", jv_kind_name(jv_get_kind(input[0])))); @@ -261,6 +222,16 @@ static void f_keys(jv input[], jv output[]) { } } +static void f_sort(jv input[], jv output[]){ + if (jv_get_kind(input[0]) == JV_KIND_ARRAY) { + output[0] = jv_sort(input[0], jv_copy(input[0])); + } else { + output[0] = jv_invalid_with_msg(jv_string_fmt("only arrays may be sorted, not %s", + jv_kind_name(jv_get_kind(input[0])))); + jv_free(input[0]); + } +} + static void f_type(jv input[], jv output[]) { output[0] = jv_string(jv_kind_name(jv_get_kind(input[0]))); jv_free(input[0]); @@ -284,6 +255,7 @@ static struct cfunction function_list[] = { {f_length, "length", CALL_BUILTIN_1_1}, {f_type, "type", CALL_BUILTIN_1_1}, {f_add, "add", CALL_BUILTIN_1_1}, + {f_sort, "sort", CALL_BUILTIN_1_1}, }; static struct symbol_table cbuiltins = {function_list, sizeof(function_list)/sizeof(function_list[0])}; @@ -1,4 +1,6 @@ #include "jv_aux.h" +#include <string.h> +#include <stdlib.h> jv jv_lookup(jv t, jv k) { jv v; @@ -60,3 +62,191 @@ jv jv_insert(jv root, jv value, jv* path, int pathlen) { return jv_modify(root, jv_copy(*path), jv_insert(jv_lookup(jv_copy(root), jv_copy(*path)), value, path+1, pathlen-1)); } + + +static int string_cmp(const void* pa, const void* pb){ + const jv* a = pa; + const jv* b = pb; + int lena = jv_string_length(jv_copy(*a)); + int lenb = jv_string_length(jv_copy(*b)); + int minlen = lena < lenb ? lena : lenb; + int r = memcmp(jv_string_value(*a), jv_string_value(*b), minlen); + if (r == 0) r = lena - lenb; + return r; +} + +jv jv_keys(jv x) { + if (jv_get_kind(x) == JV_KIND_OBJECT) { + int nkeys = jv_object_length(jv_copy(x)); + jv* keys = malloc(sizeof(jv) * nkeys); + int kidx = 0; + jv_object_foreach(i, x) { + keys[kidx++] = jv_object_iter_key(x, i); + } + qsort(keys, nkeys, sizeof(jv), string_cmp); + jv answer = jv_array_sized(nkeys); + for (int i = 0; i<nkeys; i++) { + answer = jv_array_append(answer, keys[i]); + } + free(keys); + jv_free(x); + return answer; + } else if (jv_get_kind(x) == JV_KIND_ARRAY) { + int n = jv_array_length(x); + jv answer = jv_array(); + for (int i=0; i<n; i++){ + answer = jv_array_set(answer, i, jv_number(i)); + } + return answer; + } else { + assert(0 && "jv_keys passed something neither object nor array"); + return jv_invalid(); + } +} + +int jv_cmp(jv a, jv b) { + if (jv_get_kind(a) != jv_get_kind(b)) { + int r = (int)jv_get_kind(a) - (int)jv_get_kind(b); + jv_free(a); + jv_free(b); + return r; + } + int r = 0; + switch (jv_get_kind(a)) { + default: + assert(0 && "invalid kind passed to jv_cmp"); + case JV_KIND_NULL: + case JV_KIND_FALSE: + case JV_KIND_TRUE: + // there's only one of each of these values + r = 0; + break; + + case JV_KIND_NUMBER: { + double da = jv_number_value(a), db = jv_number_value(b); + + // handle NaN as though it were null + if (da != da) r = jv_cmp(jv_null(), jv_number(db)); + else if (db != db) r = jv_cmp(jv_number(da), jv_null()); + else if (da < db) r = -1; + else if (da == db) r = 0; + else r = 1; + break; + } + + case JV_KIND_STRING: { + r = string_cmp(&a, &b); + break; + } + + case JV_KIND_ARRAY: { + // Lexical ordering of arrays + int i = 0; + while (r == 0) { + int a_done = i >= jv_array_length(jv_copy(a)); + int b_done = i >= jv_array_length(jv_copy(b)); + if (a_done || b_done) { + r = b_done - a_done; //suddenly, logic + break; + } + jv xa = jv_array_get(jv_copy(a), i); + jv xb = jv_array_get(jv_copy(b), i); + r = jv_cmp(xa, xb); + i++; + } + break; + } + + case JV_KIND_OBJECT: { + jv keys_a = jv_keys(jv_copy(a)); + jv keys_b = jv_keys(jv_copy(b)); + r = jv_cmp(jv_copy(keys_a), keys_b); + if (r == 0) { + for (int i=0; i<jv_array_length(jv_copy(keys_a)); i++) { + jv key = jv_array_get(jv_copy(keys_a), i); + jv xa = jv_object_get(jv_copy(a), jv_copy(key)); + jv xb = jv_object_get(jv_copy(b), key); + r = jv_cmp(xa, xb); + if (r) break; + } + } + jv_free(keys_a); + break; + } + } + + jv_free(a); + jv_free(b); + return r; +} + + +struct sort_entry { + jv object; + jv key; +}; + +static int sort_cmp(const void* pa, const void* pb) { + const struct sort_entry* a = pa; + const struct sort_entry* b = pb; + int r = jv_cmp(jv_copy(a->key), jv_copy(b->key)); + // comparing by address if r == 0 makes the sort stable + return r ? r : (int)(a - b); +} + +static struct sort_entry* sort_items(jv objects, jv keys) { + assert(jv_get_kind(objects) == JV_KIND_ARRAY); + assert(jv_get_kind(keys) == JV_KIND_ARRAY); + assert(jv_array_length(jv_copy(objects)) == jv_array_length(jv_copy(keys))); + int n = jv_array_length(jv_copy(objects)); + struct sort_entry* entries = malloc(sizeof(struct sort_entry) * n); + for (int i=0; i<n; i++) { + entries[i].object = jv_array_get(jv_copy(objects), i); + entries[i].key = jv_array_get(jv_copy(keys), i); + } + jv_free(objects); + jv_free(keys); + qsort(entries, n, sizeof(struct sort_entry), sort_cmp); + return entries; +} + +jv jv_sort(jv objects, jv keys) { + assert(jv_get_kind(objects) == JV_KIND_ARRAY); + assert(jv_get_kind(keys) == JV_KIND_ARRAY); + assert(jv_array_length(jv_copy(objects)) == jv_array_length(jv_copy(keys))); + int n = jv_array_length(jv_copy(objects)); + struct sort_entry* entries = sort_items(objects, keys); + jv ret = jv_array(); + for (int i=0; i<n; i++) { + jv_free(entries[i].key); + ret = jv_array_set(ret, i, entries[i].object); + } + free(entries); + return ret; +} + +jv jv_group(jv objects, jv keys) { + assert(jv_get_kind(objects) == JV_KIND_ARRAY); + assert(jv_get_kind(keys) == JV_KIND_ARRAY); + assert(jv_array_length(jv_copy(objects)) == jv_array_length(jv_copy(keys))); + int n = jv_array_length(jv_copy(objects)); + struct sort_entry* entries = sort_items(objects, keys); + jv ret = jv_array(); + jv curr_key = entries[0].key; + jv group = jv_array_append(jv_array(), entries[0].object); + for (int i = 1; i < n; i++) { + if (jv_equal(jv_copy(curr_key), jv_copy(entries[i].key))) { + jv_free(entries[i].key); + } else { + jv_free(curr_key); + curr_key = entries[i].key; + ret = jv_array_append(ret, group); + group = jv_array(); + } + group = jv_array_append(group, entries[i].object); + } + jv_free(curr_key); + ret = jv_array_append(ret, group); + free(entries); + return ret; +} @@ -7,5 +7,11 @@ jv jv_lookup(jv t, jv k); jv jv_modify(jv t, jv k, jv v); jv jv_insert(jv root, jv value, jv* path, int pathlen); +jv jv_keys(jv /*object or array*/); +int jv_cmp(jv, jv); + +jv jv_group(jv objects, jv keys); +jv jv_sort(jv objects, jv keys); + #endif @@ -425,3 +425,7 @@ true {foo: {baz: 12, blap: {bar: 13}}, bar: 14} contains {bar: 14, foo: {blap: {bar: 14}}} {} false + +sort +[42,[2,5,3,11],10,{"a":42,"b":2},{"a":42},true,2,[2,6],"hello",null,[2,5,6],{"a":[],"b":1},"abc","ab",[3,10],{},false,"abcd",null] +[null,null,false,true,2,10,42,"ab","abc","abcd","hello",[2,5,3,11],[2,5,6],[2,6],[3,10],{},{"a":42},{"a":42,"b":2},{"a":[],"b":1}] |