toggle shuffle mode

[SpaceCadet2000]

toggle shuffle mode

[phillipberndt]

That's a neat idea, but not trivial to implement due to the way --shuffle works: pqiv stores its file list in a binary search tree. Normally, files are indexed by an increasing integer sequence. In sort mode, the file names are used as indices. In shuffle mode, random integegers are used. This obviously doesn't readily allow to toggle between random and sequential image movement at runtime, because the tree would have to be completely regenerated, which is way too expensive.

pqiv woks this way to allow the program to insert new and remove deleted images at runtime without reshuffling all images and to allow the user to navigate forward and backward through the shuffled images without changing the order (thus to be able to navigate away from an image and then reliably back to it). I'd want any alternative solution to retain that.

Some preminilary ideas:

• We could store a permutation of the image ranks (= sequential index within the search tree) as a doubly linked list and use that for relative image movements.
• We could use a LCG or some other prng whose state only depends on the last random number and which generates full cycles for relative image movements

I'll have to think about a good solution for this. Suggestions are very welcome.. ;-)

[SpaceCadet2000]

Ah I imagined that it would not be as trivial as it sounds :) Programming is not my trade, so I'm afraid I can't really be helpful with the implementation.

I do remember that older versions of the original qiv supported this behavior, up until version 1.6 I believe. Perhaps you could find inspiration in the source code? As a matter of fact, I kept an old qiv binary around for a long time because of this. It stopped working on recent distributions, because the libraries it depends on are no longer supported, hence the reason why I'm looking for a replacement :)

[phillipberndt]

As a quick progress update, here's some further thoughts on this. Don't expect anything too soon, this problem is even more complex than I imagined. The first part of this comment is a question, the second one is rather technical and probably not of interest to you.

How should the mechanism work?

For one, I thought about how the toggle option should work. If you initially had shuffle mode enabled, and then disabled it and looked at some images in sequential order, and then reenable it - what should be the next images displayed to the user? Should that choice be made on the basis of the last image that was displayed before shuffle was disabled, or the one that is currently displayed? Here's an example: Let's say you have 10 images. pqiv generates a random order, say

3 5 6 4 2 1 8 7 9 10

You start looking at the images until image 6 and then switch to sequential order until image 8, then reenable shuffle mode. Which images should be displayed now, in which order? Reasonable answers include

3 5 6 (switch) 7 8 (switch) 7 9 10 3 5 6 ..    (i.e. continue from 8)
3 5 6 (switch) 7 8 (switch) 4 2 1 8 7 9 10 ..  (i.e. continue from 6)
3 5 6 (switch) 7 8 (switch) 4 2 1 9 10 3 ..    (i.e. continue from 6, but skip those that the user already saw) 
3 5 6 (switch) 7 8 (switch) 4 2 1 9 10 xx ..   (i.e. continue from 6, but skip those that the user already saw, and generate a new random permutation when all images have been seen) 

The last option feels best to me, because it doesn't display any image twice before all the images have been shown, but it is also by far the hardest to implement. What do you think?

Implementation

I think that the best solution is to use a linear congruential generator as suggested above. The benefit over better generators is that we can easily invert the formula using the extended euclidean algorithm, thus move backwards through the images without having to store the actual sequence of images. We should use the actual number of images as the modulus (at least limit it to some constant times that number, as there are some O(m) operations involved in moving to the next image) and generate the generator's parameters on the fly from rand() (of course under the well-known constraints for full-cycles) to ensure that the order changes. Images that have been visited should be marked as "seen" and random forward movement through the images should be limited to images that have not. Once all images have been "seen", the meaning of the flag is inverted and a new sequence is generated.

With this solution,

• the memory overhead is minimal (one flag as opposed to multiple lists or a tree)
• the amount of new code required is minimal
• random backward image movement doesn't neccessarily show the image that a user viewed before the current one, because the previous image in random order might be one that has already been seen in sequential order
• there is no "random index" to keep track of - the problem of finding the next/previous random order image from the current sequential index is trivial, because the current image's index is the seed for the random generator
• adding/removing images will change the order of the images - but it is guaranteed that new images are shown before the image sequence starts over

The major reason why I favor this are the first two points.

[phillipberndt]

If you want to test what I suggested above, try compiling from the random_toggle branch:

https://github.com/phillipberndt/pqiv/archive/random_toggle.zip

[SpaceCadet2000]

Hi Phillip, thanks for the update.

In regards to your question about how it should work:

For me the second option is definitely the most logical. When resuming shuffle mode, I'd like to just continue where I left off and just ignore the fact that some images were already viewed in sequential mode.

[phillipberndt]

Good to hear. That option is much simpler, so let's go with that one. I've implemented it in the random_toggle_2 branch. Does this work as you'd expect it to?

Here's the direct download link for the source code: https://github.com/phillipberndt/pqiv/archive/random_toggle_2.zip Let me know if you'd like to have a binary.

[phillipberndt]

I'll merge this in the near future. Any change requests? :-)

[phillipberndt]

Merged. The current binary (see readme) already includes these changes.