TransWikia.com

Can the ring data structure really be rotated?

Emacs Asked on September 2, 2021

According to the doc page describing Emacs Lisp’s ring data structure, rings "support […] rotation". However, the word "rotate" appears nowhere else on the page, and none of the documented interface functions appear to perform it.

When I visit ring.el I find this in the header comments: You can insert to, remove from, and rotate a ring. But again, the word "rotate" appears nowhere else in the file, and none of the functions defined there (some of which are not mentioned on the web page above) do rotation, as far as I can tell.

Am I missing something, or is the documentation wrong?

Obviously a one-place rotation in one particular direction is possible by doing (ring-insert ring (ring-remove ring)), and probably quite efficiently at that, but it seems like a far cry from "supporting" rotation.

One Answer

Yes. Functions ring-next and ring-previous do what you're asking, forward and backward, respectively.

It may not be obvious, but invoking ring-next on the last ring element cycles/rotates to the first element: wrap-around. Similarly, for ring-previous on the first element: it rotates to the last element.

I've filed Emacs bug #42430, to ask that the Elisp manual mention these functions. Thx.


To respond to your comment:

simple indexed access modulo the length of the structure isn't what I'd call "rotation." To me, "you can rotate a ring" sounds like a mutating action that takes a distance N and has the effect that every element previously at index I is now at index I - N (modulo the length of the ring, of course). For example, given a ring with elements (1 2 3 4 5), I'd expect to have a function like (ring-rotate my-ring 2) and have the ring now contain (3 4 5 1 2).

No, that functionality is not offered as such, nor is it really needed, in general. It's not what was meant by "rotating" a ring. Perhaps that word isn't the best one for what is meant.

A ring in Elisp is not a list whose order matters. It's an instance of an abstract data type, if you like. This is true of kill-ring, search-ring, etc.

You have access to the ring elements by ring position, not implementation-list position, and you can change the position of a given element if you need to (as you suggested, with insertion and deletion). But the more typical operations are insertion at the head, deletion of a given element, accessing an element by its position/index, and accessing the next/previous ring element.

Something like this seems to be what you're looking for:

(defun ring-rotate (ring &optional n)
  "Rotate RING N places.
N defaults to 1.
Moves ring element 2 to position 1, 3 to 2, 4 to 3, etc.
Moves element 1 to the end of the ring."
  (setq n  (or n  1))
  (let ((rng  ring))
    (dotimes (ii n rng)
      (ring-insert rng (ring-remove rng)))))

Update: FYI, Emacs bug #42430 was closed by the Emacs maintainer, with this comment:

The manual says:

For yanking, one entry in the kill ring is designated the front of the ring. Some yank commands rotate the ring by designating a different element as the front. But this virtual rotation doesn’t change the list itself—the most recent entry always comes first in the list.

That's all. I don't see any reason to expand this description of a "virtual rotation", since that would require bringing many internal details into the ELisp manual, with no apparent gain.

Answered by Drew on September 2, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP