From 4e3e4e1ccc60331ff8ff4c1c139e9da3c95e2272 Mon Sep 17 00:00:00 2001
From: Kaz Kylheku <kaz@kylheku.com>
Date: Mon, 24 Aug 2015 06:37:19 -0700
Subject: New function: shuffle.

* eval.c (eval_init): Register shuffle as intrinsic.

* lib.c (shuffle): New function.

* lib.h (shuffle): Declared.
---
 eval.c |  1 +
 lib.c  | 43 +++++++++++++++++++++++++++++++++++++++++++
 lib.h  |  1 +
 txr.1  | 21 +++++++++++++++++++++
 4 files changed, 66 insertions(+)

diff --git a/eval.c b/eval.c
index 47e3285c..3800c6ca 100644
--- a/eval.c
+++ b/eval.c
@@ -4543,6 +4543,7 @@ void eval_init(void)
   reg_fun(intern(lit("prop"), user_package), func_n2(getplist));
   reg_fun(intern(lit("merge"), user_package), func_n4o(merge_wrap, 2));
   reg_fun(intern(lit("sort"), user_package), func_n3o(sort, 1));
+  reg_fun(intern(lit("shuffle"), user_package), func_n1(shuffle));
   reg_fun(intern(lit("find"), user_package), func_n4o(find, 2));
   reg_fun(intern(lit("multi-sort"), user_package), func_n3o(multi_sort, 2));
   reg_fun(intern(lit("find-if"), user_package), func_n3o(find_if, 2));
diff --git a/lib.c b/lib.c
index a39c7a09..27b77808 100644
--- a/lib.c
+++ b/lib.c
@@ -6166,6 +6166,49 @@ val sort(val seq_in, val lessfun, val keyfun)
   return seq;
 }
 
+val shuffle(val seq)
+{
+  switch (type(seq)) {
+  case NIL:
+    return nil;
+  case CONS:
+  case LCONS:
+    if (cdr(seq))
+    {
+      val v = shuffle(vector_list(seq));
+      val i, l;
+
+      for (l = seq, i = zero; l; i = succ(i), l = cdr(l))
+        rplaca(l, ref(v, i));
+    }
+    return seq;
+  case LIT:
+    uw_throwf(error_s, lit("shuffle: ~s is a literal"), seq, nao);
+  case STR:
+  case LSTR:
+  case VEC:
+    {
+      val rs = random_state;
+      val n = length(seq);
+      val i;
+
+      if (n == zero || n == one)
+        return seq;
+
+      for (i = pred(n); ge(i, one); i = pred(i)) {
+        val j = random(rs, succ(i));
+        val t = ref(seq, i);
+        refset(seq, i, ref(seq, j));
+        refset(seq, j, t);
+      }
+
+      return seq;
+    }
+  default:
+    type_mismatch(lit("shuffle: ~s is not a sequence"), seq, nao);
+  }
+}
+
 static val multi_sort_less(val funcs_cons, val llist, val rlist)
 {
   cons_bind (funcs, key_funcs, funcs_cons);
diff --git a/lib.h b/lib.h
index bcd92954..6372370c 100644
--- a/lib.h
+++ b/lib.h
@@ -835,6 +835,7 @@ val mapdo(val fun, val list);
 val interpose(val sep, val seq);
 val merge(val list1, val list2, val lessfun, val keyfun);
 val sort(val seq, val lessfun, val keyfun);
+val shuffle(val seq);
 val multi_sort(val lists, val funcs, val key_funcs);
 val sort_group(val seq, val keyfun, val lessfun);
 val unique(val seq, val keyfun, struct args *hashv_args);
diff --git a/txr.1 b/txr.1
index 33fe9c35..374e1f31 100644
--- a/txr.1
+++ b/txr.1
@@ -19544,6 +19544,27 @@ For strings and vectors,
 .code sort
 is not stable.
 
+.coNP Function @ shuffle
+.synb
+.mets (shuffle << sequence )
+.syne
+.desc
+The
+.code shuffle
+function pseudo-randomly rearranges the elements of
+.metn sequence .
+This is performed in place:
+.meta sequence
+object is modified.
+
+The return value is
+.meta sequence
+itself.
+
+The rearrangement depends on pseudo-random numbers obtained from the
+.code rand
+function.
+
 .coNP Function @ sort-group
 .synb
 .mets (sort-group < sequence >> [ keyfun <> [ lessfun ]])
-- 
cgit v1.2.3