Rockbox Technical Forums

Rockbox Development => Feature Ideas => Topic started by: seani on November 05, 2009, 08:19:09 AM

Title: "Binary Search" Mode for Long Tracks / Possible Advantages for Partial Sight
Post by: seani on November 05, 2009, 08:19:09 AM
Canvassing opinion again :-)


Having dipped my toe in the development waters with pause-on-timeout (http://forums.rockbox.org/index.php?topic=23063.0) and at least successfully scratched my own itch - if no-one elses - I'm thinking about the issue of losing your place in a large / long running file.

As usual (selfishly) I'm considering my own situation first: I'm listening to an audio book and fall asleep at some point. With pause-on-timeout bringing the sleep-timer in to play, I don't have problems with the player running all night.

But if the timeout happened automatically, the chances are that the track isn't at the place I last remember, and I want to resume from that place.

Depending on how long my sleep-timeout was, this could be anything from 5 minutes to 5hrs worth of audio to scan through. The accelerated seeking is excellent, but needs a bit of timing and co-ordination.


So I'm thinking about trying a binary search method which would work as follows:

1) If the player shuts down as a result of a sleep-timeout, I (or rather RockBox!) remember this fact and when the player is turned on, it's automatically in "binary-search mode".

2) If I leave the player to play unmolested for a period of time (10 seconds, say, enough to get some context), I'm out of binary-search mode and back to business as usual. And the same thing applies if I pause, play, stop FF or REW, I'm out of binary-search mode.

3) If however I press "previous track" within 10 seconds, I'm binary-searching; any "next track" or "previous track" presses from this point seek only within the current track.

4) The period I start off with is half the period of the sleep timeout. So for convenience imagine my sleep-timeout is, ahem, 64 minutes. "previous track" jumps back 32 minutes. I now have 10 seconds to decide if this is close enough for me to the point where I want to resume.

If I don't act and let it play, I'm out of binary-search mode, and back to normality. If I do act, by pressing "next track" or "previous track", I then skip forwards or backwards within the track by 16 minutes in either direction. The process repeats. This time, I move by 8 minutes. And so on and so on until I hit a snippet of audio I'm happy with.

5) At any time I can pause or FF / REW, and I'm out of binary search mode.


This way, I can "feel" my way to the point I want to get to in the track without having to see a progress bar or have any kind of tricky audio preview.


Aside from my own selfish reasons for wanting to try it, a few other thoughts occur:

1) If there is only a single track in the playlist, this could be the default mode.

2) If a track is above a certain length, this could be the default mode entered when the track is started. Again "normal" mode would be reset if FF / REW / PAUSE was pressed

3) There may be some general advantages for partially sighted / blind people attempting to navigate to a certain point in a long track. I'd guess reading out the position might be an option when a section has been skipped.


Any thoughts?


I'm not certain if there are other combinations that are available in play mode that would mean you can binary-search at any time without a clash? (double "next track" or double "prev track"?).

If there were, general "modeless" binary search could start off with half the remaining time in the forward direction, and half the played time in the backward direction. This would seem like a very fast way to get to a specific point without arcade type reflexes :-)
Title: Re: "Binary Search" Mode for Long Tracks / Possible Advantages for Partial Sight
Post by: gevaerts on November 05, 2009, 08:29:51 AM
Canvassing opinion again :-)


Having dipped my toe in the development waters with pause-on-timeout (http://forums.rockbox.org/index.php?topic=23063.0) and at least successfully scratched my own itch - if no-one elses - I'm thinking about the issue of losing your place in a large / long running file.

As usual (selfishly) I'm considering my own situation first: I'm listening to an audio book and fall asleep at some point. With pause-on-timeout bringing the sleep-timer in to play, I don't have problems with the player running all night.

But if the timeout happened automatically, the chances are that the track isn't at the place I last remember, and I want to resume from that place.

Depending on how long my sleep-timeout was, this could be anything from 5 minutes to 5hrs worth of audio to scan through. The accelerated seeking is excellent, but needs a bit of timing and co-ordination.

I like the idea in general
Quote

So I'm thinking about trying a binary search method which would work as follows:

1) If the player shuts down as a result of a sleep-timeout, I (or rather RockBox!) remember this fact and when the player is turned on, it's automatically in "binary-search mode".
I really don't like this. Settings should not be different depending on how the player was shut down.
Quote
2) If I leave the player to play unmolested for a period of time (10 seconds, say, enough to get some context), I'm out of binary-search mode and back to business as usual. And the same thing applies if I pause, play, stop FF or REW, I'm out of binary-search mode.

3) If however I press "previous track" within 10 seconds, I'm binary-searching; any "next track" or "previous track" presses from this point seek only within the current track.

4) The period I start off with is half the period of the sleep timeout. So for convenience imagine my sleep-timeout is, ahem, 64 minutes. "previous track" jumps back 32 minutes. I now have 10 seconds to decide if this is close enough for me to the point where I want to resume.

If I don't act and let it play, I'm out of binary-search mode, and back to normality. If I do act, by pressing "next track" or "previous track", I then skip forwards or backwards within the track by 16 minutes in either direction. The process repeats. This time, I move by 8 minutes. And so on and so on until I hit a snippet of audio I'm happy with.

5) At any time I can pause or FF / REW, and I'm out of binary search mode.
Do we want timeout-based behaviour switches? I'd like another way to get in and out of this mode. This isn't going to happen often, so maybe the WPS context menu can have an item for this?
Quote


This way, I can "feel" my way to the point I want to get to in the track without having to see a progress bar or have any kind of tricky audio preview.


Aside from my own selfish reasons for wanting to try it, a few other thoughts occur:

1) If there is only a single track in the playlist, this could be the default mode.

2) If a track is above a certain length, this could be the default mode entered when the track is started. Again "normal" mode would be reset if FF / REW / PAUSE was pressed

I think that will be confusing. I prefer the UI to be the same regardless of playlist size or track length.
Quote
3) There may be some general advantages for partially sighted / blind people attempting to navigate to a certain point in a long track. I'd guess reading out the position might be an option when a section has been skipped.

that could work
Quote

Any thoughts?


I'm not certain if there are other combinations that are available in play mode that would mean you can binary-search at any time without a clash? (double "next track" or double "prev track"?).
Maybe on some players, but definitely not in general I think
Quote

If there were, general "modeless" binary search could start off with half the remaining time in the forward direction, and half the played time in the backward direction. This would seem like a very fast way to get to a specific point without arcade type reflexes :-)
Title: Re: "Binary Search" Mode for Long Tracks / Possible Advantages for Partial Sight
Post by: seani on November 05, 2009, 08:43:10 AM
Thanks gevaerts :-)


I realise the automatic-mode-switching stuff is contentious and really very specific to the way *I* would want it to work rather than aiming for overall consistency. I'm still considering trying to get it to work this way for my own education and because there's nothing like actually doing it instead of hand-waving about it.


So to summarise, an entry on the WPS context menu that moves in and out of that mode explicitly as opposed to a heuristic of some kind would be easier to explain, more consistent etc?

This is fair enough, but for the purposes of talking it through:

1) there is a precedent for time-based behaviour - the behaviour of "previous track" when it's in the first few seconds of a track is the obvious example

2) if the "auto-set-to-binary-search-mode" after sleep timeout is a rare occurence, it won't have a generally confusing effect on anyone using it - the change in behaviour is only expressed if a specific key is pressed within 10 seconds.

But I'm very aware this is so far a "vanity" build which is why I was after other opinions, and of course there's code bloat to consider.

Title: Re: "Binary Search" Mode for Long Tracks / Possible Advantages for Partial Sight
Post by: Multiplex on November 05, 2009, 09:33:01 AM
I don't use my player like you do but i see the need - I made a similar recommendation to the manufacturer of the PVR used to have (they didn't do anything about it). On the PVR it has a fixed two minute jump (as well as the ffwd/rwd).

I suggested that the jump stays at two minutes if you carry on jumping in the same direction but halved if you changed direction. So in your example, you would replace the track skip with a two minute (or whatever) skip, you press backward till you recognise something then press forward and you are 1 minute forward, and so on.

Just thought I'd mention it as it might eliminate the concern about timing based behaviour (though of course you need a timer to make the jump go back to two minutes...)
Title: Re: "Binary Search" Mode for Long Tracks / Possible Advantages for Partial Sight
Post by: seani on November 05, 2009, 02:45:13 PM
Hi Multiplex, I think the main concern is that this method seeking, whether based on a fixed time or some sort of binary chop, would be activated in a time dependent way, rather than being explicitly requested by the user.

My TiVo did something similar (ah, happy memories) - when you stop after a FF, it automatically rewinds from the position you stopped at to compensate for overshooting. The rewind time was proportional to the speed you were fast FF'ing at. Something similar  might be useful for standard accelerated RockBox FF / REW come to think of it.


ETA:

No double posting allowed and I think this might complicate my initial post too much, so I'll add it here.


Aside from the issue of when to activate the binarysearch mode, there are also issues to consider in the navigation itself. I've implemented this intra-track navigation mode in a test build - essentially just replacing the NEXT / PREV TRACK functions altogether for the time being - and this is by way of reporting my findings.


Assume for a moment that the user has entered binarysearch. PREV / NEXT are used to do the search. The file is 10 minutes long, and the user is a the start and wants to get to the 6.5 minute mark. This is what the user does and how I handle it:

* The user presses NEXT. As this is the start of a search operation, I set the lower bound to the current position (the start of the track more or less), and the upper bound to the end of the track. I seek to the midpoint of the two bounds, at the 5 minute mark

* The user presses NEXT. As this is a continuation of a search operation, I set the lower bound to the previous start position (5 minutes) and skip to the midpoint again - 7.5 minutes

* The user presses PREV. Now I set the upper  bound to the current position (7.5), leave the lower bound as it is (5) and skip to the midpoint at 6.25

* The user presses NEXT. I set the lower bound to the current position (6.25), leave the upper bound as it is (7.5) and skip to the midpoint at 6.875

* The user presses PREV. I set the upper bound to the current position (6.875) leave the lower bound as it is (6.875) and skip to the midpoint at 6.5625


At this point the user is close enough - and you're tired of reading.


The point is that every time the user chooses a direction, I know which of the two bounds to adjust and by how much, and the jumps are smaller until they converge on the "right" place. It reads very clumsily, but it's actually very easy in practice (however...)


What happens when the process needs to be repeated - or the user skips in the wrong direction? These are equivalent "errors" - at this point the navigation is closed down to a very small window.


There are a few options:

1) The user flips out of and then back into binarysearch mode. This resets the "window". If the user does this at, say, 8 minutes into the track, they will binarysearch either the remaining time of 2 minutes or the elapsed time of 8 minutes depending on which direction they skip into first

2) The search itself has a timeout. This is the method I've implemented. If the user waits longer than 10 seconds after the last binarysearch skip in either direction, the search is reset and the initial search window depends on the current position and direction of initial search only.

3) Pause, FF, REW all reset the binarysearch window.


2 and 3 could be combined so that any of these conditions reset the window.


2 is closer to the way I'd imagine a user would expect it to work; they've skipped around to get the the right place. Once they've settled down and listened for a bit, they can skip around again and the previous skipping exercise has no bearing on the process.


ETA: In the end added this as an additional setting in the "Skip Length" menu under "Playback Setting".

This is persisted across boots in the same as a standard skip setting. If "Binary Skip" is chosen, the next track and previous track keys skip about within the current track as a binary search.

It seems very fast for large file, arguably faster than directly inputting the position that you want to skip to if such a thing could be done at the moment.