From ddc30c996a3d14e0163df6946ba96c9bcf73bd2f Mon Sep 17 00:00:00 2001 From: Dmitry Antipov Date: Thu, 15 May 2014 18:59:02 +0400 Subject: [PATCH] * src/fns.c (Fnreverse): Allow vectors and bool vectors. * doc/lispref/lists.texi (Building Cons Cells and Lists): Remove description of `nreverse' and generalize it... * doc/lispref/sequences.texi (Sequences): ...for sequences here. * tests/automated/fns-tests.el (fns-tests-nreverse) (fns-tests-nreverse-bool-vector): New tests. --- doc/lispref/ChangeLog | 2 +- doc/lispref/lists.texi | 52 ---------------------------- doc/lispref/sequences.texi | 69 +++++++++++++++++++++++++++++++++++++ src/ChangeLog | 1 + src/fns.c | 60 ++++++++++++++++++++++++-------- test/ChangeLog | 2 ++ test/automated/fns-tests.el | 32 +++++++++++++++++ 7 files changed, 150 insertions(+), 68 deletions(-) diff --git a/doc/lispref/ChangeLog b/doc/lispref/ChangeLog index d5fe02d2398..7d85e4059c9 100644 --- a/doc/lispref/ChangeLog +++ b/doc/lispref/ChangeLog @@ -1,7 +1,7 @@ 2014-05-15 Dmitry Antipov * lists.texi (Building Cons Cells and Lists): Remove - description of `reverse' and generalize it... + description of `reverse' and `'nreverse' to generalize them... * sequences.texi (Sequences): ...for sequences here. 2014-05-14 Glenn Morris diff --git a/doc/lispref/lists.texi b/doc/lispref/lists.texi index 882dd440491..f724d5bd902 100644 --- a/doc/lispref/lists.texi +++ b/doc/lispref/lists.texi @@ -1124,58 +1124,6 @@ each time you run it! Here is what happens: @end smallexample @end defun -@defun nreverse list -@cindex reversing a list - This function reverses the order of the elements of @var{list}. -Unlike @code{reverse}, @code{nreverse} alters its argument by reversing -the @sc{cdr}s in the cons cells forming the list. The cons cell that -used to be the last one in @var{list} becomes the first cons cell of the -value. - - For example: - -@example -@group -(setq x '(a b c)) - @result{} (a b c) -@end group -@group -x - @result{} (a b c) -(nreverse x) - @result{} (c b a) -@end group -@group -;; @r{The cons cell that was first is now last.} -x - @result{} (a) -@end group -@end example - - To avoid confusion, we usually store the result of @code{nreverse} -back in the same variable which held the original list: - -@example -(setq x (nreverse x)) -@end example - - Here is the @code{nreverse} of our favorite example, @code{(a b c)}, -presented graphically: - -@smallexample -@group -@r{Original list head:} @r{Reversed list:} - ------------- ------------- ------------ -| car | cdr | | car | cdr | | car | cdr | -| a | nil |<-- | b | o |<-- | c | o | -| | | | | | | | | | | | | - ------------- | --------- | - | -------- | - - | | | | - ------------- ------------ -@end group -@end smallexample -@end defun - @defun sort list predicate @cindex stable sort @cindex sorting lists diff --git a/doc/lispref/sequences.texi b/doc/lispref/sequences.texi index c96f1222f3f..da53990b449 100644 --- a/doc/lispref/sequences.texi +++ b/doc/lispref/sequences.texi @@ -260,6 +260,75 @@ x @end example @end defun +@defun nreverse seq +@cindex reversing a list +@cindex reversing a vector + This function reverses the order of the elements of @var{seq}. +If @var{seq} is a list, @code{nreverse} alters its by reversing the @sc{cdr}s +in the cons cells. The cons cell that used to be the last one in @var{seq} +becomes the first cons cell of the value. If @var{seq} is a vector or +bool vector, its items are placed in the same vector in a reversed order. + + For example: + +@example +@group +(setq x '(a b c)) + @result{} (a b c) +@end group +@group +x + @result{} (a b c) +(nreverse x) + @result{} (c b a) +@end group +@group +;; @r{The cons cell that was first is now last.} +x + @result{} (a) +@end group +@end example + + To avoid confusion, we usually store the result of @code{nreverse} +back in the same variable which held the original list: + +@example +(setq x (nreverse x)) +@end example + + Here is the @code{nreverse} of our favorite example, @code{(a b c)}, +presented graphically: + +@smallexample +@group +@r{Original list head:} @r{Reversed list:} + ------------- ------------- ------------ +| car | cdr | | car | cdr | | car | cdr | +| a | nil |<-- | b | o |<-- | c | o | +| | | | | | | | | | | | | + ------------- | --------- | - | -------- | - + | | | | + ------------- ------------ +@end group +@end smallexample + + For the vector, it is even simpler because you don't need setq: + +@example +(setq x [1 2 3 4]) + @result{} [1 2 3 4] +(nreverse x) + @result{} [4 3 2 1] +x + @result{} [4 3 2 1] +@end example + +Note that unlike @code{reverse}, this function doesn't work with strings. +Although you can alter string data by using @code{aset}, it is strongly +encouraged to treat strings as immutable. + +@end defun + @node Arrays @section Arrays @cindex array diff --git a/src/ChangeLog b/src/ChangeLog index ce51b26cf43..f82a6a298ae 100644 --- a/src/ChangeLog +++ b/src/ChangeLog @@ -1,6 +1,7 @@ 2014-05-15 Dmitry Antipov * fns.c (Freverse): Allow vectors, bool vectors and strings. + (Fnreverse): Allow vectors and bool vectors. 2014-05-14 Dmitry Antipov diff --git a/src/fns.c b/src/fns.c index 8f9734cd7cc..1694f1c798d 100644 --- a/src/fns.c +++ b/src/fns.c @@ -1697,25 +1697,55 @@ changing the value of a sequence `foo'. */) } DEFUN ("nreverse", Fnreverse, Snreverse, 1, 1, 0, - doc: /* Reverse LIST by modifying cdr pointers. -Return the reversed list. Expects a properly nil-terminated list. */) - (Lisp_Object list) + doc: /* Reverse order of items in a list or vector SEQ. +If SEQ is a list, it should be nil-terminated, and reversed +by modifying cdr pointers. Return the reversed SEQ. + +Note that unlike `reverse', this function doesn't work with strings. +It is strongly encouraged to treat them as immutable. */) + (Lisp_Object seq) { - register Lisp_Object prev, tail, next; + if (NILP (seq)) + return seq; + else if (CONSP (seq)) + { + Lisp_Object prev, tail, next; - if (NILP (list)) return list; - prev = Qnil; - tail = list; - while (!NILP (tail)) + for (prev = Qnil, tail = seq; !NILP (tail); tail = next) + { + QUIT; + CHECK_LIST_CONS (tail, tail); + next = XCDR (tail); + Fsetcdr (tail, prev); + prev = tail; + } + seq = prev; + } + else if (VECTORP (seq)) { - QUIT; - CHECK_LIST_CONS (tail, tail); - next = XCDR (tail); - Fsetcdr (tail, prev); - prev = tail; - tail = next; + ptrdiff_t i, size = ASIZE (seq); + + for (i = 0; i < size / 2; i++) + { + Lisp_Object tem = AREF (seq, i); + ASET (seq, i, AREF (seq, size - i - 1)); + ASET (seq, size - i - 1, tem); + } } - return prev; + else if (BOOL_VECTOR_P (seq)) + { + ptrdiff_t i, size = bool_vector_size (seq); + + for (i = 0; i < size / 2; i++) + { + bool tem = bool_vector_bitref (seq, i); + bool_vector_set (seq, i, bool_vector_bitref (seq, size - i - 1)); + bool_vector_set (seq, size - i - 1, tem); + } + } + else + wrong_type_argument (Qarrayp, seq); + return seq; } DEFUN ("reverse", Freverse, Sreverse, 1, 1, 0, diff --git a/test/ChangeLog b/test/ChangeLog index cd5398e9b99..3fed9759ca7 100644 --- a/test/ChangeLog +++ b/test/ChangeLog @@ -1,6 +1,8 @@ 2014-05-15 Dmitry Antipov * automated/fns-tests.el: New file. + * automated/fns-tests.el (fns-tests-nreverse) + (fns-tests-nreverse-bool-vector): New tests. 2014-05-08 Glenn Morris diff --git a/test/automated/fns-tests.el b/test/automated/fns-tests.el index 2e71854261e..577298cddf4 100644 --- a/test/automated/fns-tests.el +++ b/test/automated/fns-tests.el @@ -28,12 +28,44 @@ (should-error (reverse)) (should-error (reverse 1)) (should-error (reverse (make-char-table 'foo))) + (should (equal [] (reverse []))) + (should (equal [0] (reverse [0]))) (should (equal [1 2 3 4] (reverse (reverse [1 2 3 4])))) + (should (equal '(a b c d) (reverse (reverse '(a b c d))))) (should (equal "xyzzy" (reverse (reverse "xyzzy")))) (should (equal "こんにちは / ｺﾝﾆﾁﾊ" (reverse (reverse "こんにちは / ｺﾝﾆﾁﾊ"))))) +(ert-deftest fns-tests-nreverse () + (should-error (nreverse)) + (should-error (nreverse 1)) + (should-error (nreverse (make-char-table 'foo))) + (should-error (nreverse "xyzzy")) + (let ((A [])) + (nreverse A) + (should (equal A []))) + (let ((A [0])) + (nreverse A) + (should (equal A [0]))) + (let ((A [1 2 3 4])) + (nreverse A) + (should (equal A [4 3 2 1]))) + (let ((A [1 2 3 4])) + (nreverse A) + (nreverse A) + (should (equal A [1 2 3 4]))) + (let* ((A [1 2 3 4]) + (B (nreverse (nreverse A)))) + (should (equal A B)))) + (ert-deftest fns-tests-reverse-bool-vector () (let ((A (make-bool-vector 10 nil))) (dotimes (i 5) (aset A i t)) (should (equal [nil nil nil nil nil t t t t t] (vconcat (reverse A)))) (should (equal A (reverse (reverse A)))))) + +(ert-deftest fns-tests-nreverse-bool-vector () + (let ((A (make-bool-vector 10 nil))) + (dotimes (i 5) (aset A i t)) + (nreverse A) + (should (equal [nil nil nil nil nil t t t t t] (vconcat A))) + (should (equal [t t t t t nil nil nil nil nil] (vconcat (nreverse A)))))) -- 2.39.5