diff options
| -rw-r--r-- | ChangeLog | 17 | ||||
| -rw-r--r-- | eval.c | 5 | ||||
| -rw-r--r-- | lib.c | 74 | ||||
| -rw-r--r-- | lib.h | 3 | ||||
| -rw-r--r-- | txr.1 | 2 | ||||
| -rw-r--r-- | txr.vim | 2 |
6 files changed, 95 insertions, 8 deletions
@@ -1,3 +1,20 @@ +2012-02-22 Kaz Kylheku <kaz@kylheku.com> + + * eval.c (eval_init): Intrinsic bindings for sub, ref, refset + and replace. + + * lib.c (do_sort): Static function renamed to sort_list. + (swap, quicksort, sort_vec): New static functions. + (sort): Made generic over lists, vectors and strings. + (refset): New function. + + * lib.h (sort): Declaration updated (parameter name change). + (refset): Declared. + + * txr.1: Mention refset. + + * txr.vim: Updated with refset. + 2012-02-21 Kaz Kylheku <kaz@kylheku.com> * eval.c (eval_init): Third argument of gethash becomes optional. @@ -2235,6 +2235,11 @@ void eval_init(void) reg_fun(intern(lit("length"), user_package), func_n1(length)); + reg_fun(intern(lit("sub"), user_package), func_n3o(sub, 1)); + reg_fun(intern(lit("ref"), user_package), func_n2(ref)); + reg_fun(intern(lit("refset"), user_package), func_n3(refset)); + reg_fun(intern(lit("replace"), user_package), func_n4o(replace, 2)); + reg_fun(intern(lit("symbol-function"), user_package), func_n1(symbol_function)); reg_fun(intern(lit("func-get-form"), user_package), func_n1(func_get_form)); reg_fun(intern(lit("func-get-env"), user_package), func_n1(func_get_env)); @@ -3530,7 +3530,7 @@ val merge(val list1, val list2, val lessfun, val keyfun) return out; } -static val do_sort(val list, val lessfun, val keyfun) +static val sort_list(val list, val lessfun, val keyfun) { if (list == nil) return nil; @@ -3560,18 +3560,61 @@ static val do_sort(val list, val lessfun, val keyfun) list2 = cdr(bisect); *cdr_l(bisect) = nil; - return merge(do_sort(list, lessfun, keyfun), - do_sort(list2, lessfun, keyfun), + return merge(sort_list(list, lessfun, keyfun), + sort_list(list2, lessfun, keyfun), lessfun, keyfun); } } -val sort(val list, val lessfun, val keyfun) +static void swap(val vec, val i, val j) { + if (i != j) { + val temp = ref(vec, i); + refset(vec, i, ref(vec, j)); + refset(vec, j, temp); + } +} + +static void quicksort(val vec, val lessfun, val keyfun, cnum from, cnum to) +{ + if (to - from >= 2) { + cnum pivot = (to - from) / 2; + cnum i, j; + val pval = ref(vec, num_fast(pivot)); + val pkval = funcall1(keyfun, pval); + + swap(vec, num_fast(pivot), num_fast(to - 1)); + + for (j = 0, i = 0; i < to; i++) + if (funcall2(lessfun, funcall1(keyfun, ref(vec, num_fast(i))), pkval)) + swap(vec, num_fast(i), num_fast(j++)); + + swap(vec, num_fast(j), num_fast(to - 1)); + + quicksort(vec, lessfun, keyfun, from, j); + quicksort(vec, lessfun, keyfun, j + 1, to); + } +} + +static void sort_vec(val vec, val lessfun, val keyfun) +{ + cnum len = c_num(length(vec)); + quicksort(vec, lessfun, keyfun, 0, len); +} + +val sort(val seq, val lessfun, val keyfun) +{ + if (!seq) + return nil; + if (!keyfun) keyfun = identity_f; - return do_sort(list, lessfun, keyfun); + if (consp(seq)) + return sort_list(seq, lessfun, keyfun); + + sort_vec(seq, lessfun, keyfun); + return seq; } val find(val list, val key, val testfun, val keyfun) @@ -3670,6 +3713,27 @@ val ref(val seq, val ind) } } +val refset(val seq, val ind, val newval) +{ + if (seq == nil) + goto list; + + else switch (type(seq)) { + case CONS: + case LCONS: + list: + return *listref_l(seq, ind) = newval; + case LIT: + case STR: + return chr_str_set(seq, ind, newval); + case VEC: + return *vecref_l(seq, ind) = newval; + default: + type_mismatch(lit("ref: ~s is not a sequence"), cons, nao); + } + return newval; +} + val replace(val seq, val items, val from, val to) { if (seq == nil) @@ -560,12 +560,13 @@ val mapcar(val fun, val list); val mapcon(val fun, val list); val mappend(val fun, val list); val merge(val list1, val list2, val lessfun, val keyfun); -val sort(val list, val lessfun, val keyfun); +val sort(val seq, val lessfun, val keyfun); val find(val list, val key, val testfun, val keyfun); val set_diff(val list1, val list2, val testfun, val keyfun); val length(val seq); val sub(val seq, val from, val to); val ref(val seq, val ind); +val refset(val seq, val ind, val newval); val replace(val seq, val items, val from, val to); val env(void); val obj_print(val obj, val stream); @@ -6644,7 +6644,7 @@ Certain object types have a custom equal function. .SS Function length -.SS Functions sub, ref and replace +.SS Functions sub, ref, refset and replace .SS Function symbol-function @@ -74,7 +74,7 @@ syn keyword txl_keyword contained list-vector copy-vec sub-vec cat-vec syn keyword txl_keyword contained replace-vec assoc assq acons acons-new syn keyword txl_keyword contained aconsq-new alist-remove alist-nremove copy-cons syn keyword txl_keyword contained copy-alist merge sort find set-diff length -syn keyword txl_keyword contained sub ref replace +syn keyword txl_keyword contained sub ref replace refset syn keyword txl_keyword contained symbol-function func-get-form func-get-env syn keyword txl_keyword contained functionp interp-fun-p *random-state* |