Krolyxon
Commit e3295f9

Branches

Tags

Refs →

remagesrcstatequeue.rs

502 lines · 15.1 KB · Rust

Raw Blame History Download
1//! The file list: current index, ordering and navigation.
2
3use std::cmp::Ordering;
4use std::collections::HashSet;
5use std::path::{Path, PathBuf};
6
7#[derive(
8 Clone,
9 Copy,
10 Debug,
11 Default,
12 PartialEq,
13 Eq,
14 clap::ValueEnum,
15 serde::Deserialize,
16 serde::Serialize,
17)]
18#[serde(rename_all = "lowercase")]
19pub enum SortKey {
20 #[default]
21 Natural,
22 Name,
23 Mtime,
24 Size,
25 Random,
26}
27
28#[derive(Debug, Default)]
29pub struct Queue {
30 files: Vec<PathBuf>,
31 index: usize,
32 /// Marked files, by path so reordering keeps them.
33 marks: HashSet<PathBuf>,
34 /// Bumped on every change to the marks, so watchers can spot one.
35 marks_version: u64,
36}
37
38impl Queue {
39 /// Build a queue positioned on `start` if present, else on `start_index` (clamped).
40 pub fn new(files: Vec<PathBuf>, start: Option<&Path>, start_index: usize) -> Self {
41 let index = start
42 .and_then(|s| files.iter().position(|f| f == s))
43 .unwrap_or(start_index);
44 let mut q = Self {
45 files,
46 index: 0,
47 marks: HashSet::new(),
48 marks_version: 0,
49 };
50 q.index = q.clamp(index);
51 q
52 }
53
54 pub fn len(&self) -> usize {
55 self.files.len()
56 }
57
58 pub fn is_empty(&self) -> bool {
59 self.files.is_empty()
60 }
61
62 pub fn index(&self) -> usize {
63 self.index
64 }
65
66 pub fn current(&self) -> Option<&Path> {
67 self.files.get(self.index).map(PathBuf::as_path)
68 }
69
70 pub fn get(&self, i: usize) -> Option<&Path> {
71 self.files.get(i).map(PathBuf::as_path)
72 }
73
74 /// Jump to `i` (clamped). Returns whether the current file changed.
75 pub fn goto(&mut self, i: usize) -> bool {
76 let i = self.clamp(i);
77 let changed = i != self.index;
78 self.index = i;
79 changed
80 }
81
82 /// Move by `delta`, wrapping around the ends when `wrap` is set.
83 pub fn step(&mut self, delta: isize, wrap: bool) -> bool {
84 if self.files.is_empty() {
85 return false;
86 }
87 let len = self.files.len() as isize;
88 let target = self.index as isize + delta;
89 let i = if wrap {
90 target.rem_euclid(len)
91 } else {
92 target.clamp(0, len - 1)
93 };
94 self.goto(i as usize)
95 }
96
97 /// Remove `path`; the current position moves to the following file.
98 pub fn remove(&mut self, path: &Path) -> bool {
99 let Some(i) = self.files.iter().position(|f| f == path) else {
100 return false;
101 };
102 let removed = self.files.remove(i);
103 if self.marks.remove(&removed) {
104 self.marks_version += 1;
105 }
106 if i < self.index {
107 self.index -= 1;
108 }
109 self.index = self.clamp(self.index);
110 true
111 }
112
113 /// Insert paths in natural order, keeping the current file selected.
114 pub fn insert_sorted(&mut self, paths: impl IntoIterator<Item = PathBuf>) {
115 let current = self.current().map(Path::to_path_buf);
116 for p in paths {
117 if self.files.contains(&p) {
118 continue;
119 }
120 let at = self
121 .files
122 .partition_point(|f| natural_cmp_path(f, &p) != Ordering::Greater);
123 self.files.insert(at, p);
124 }
125 if let Some(cur) = current
126 && let Some(i) = self.files.iter().position(|f| *f == cur)
127 {
128 self.index = i;
129 }
130 }
131
132 /// Up to `n` neighbours on each side of the current file, nearest first.
133 pub fn neighbours(&self, n: usize, wrap: bool) -> Vec<usize> {
134 let len = self.files.len();
135 let mut out = Vec::with_capacity(n * 2);
136 for k in 1..=n {
137 for delta in [k as isize, -(k as isize)] {
138 let raw = self.index as isize + delta;
139 let i = if wrap {
140 raw.rem_euclid(len as isize) as usize
141 } else if (0..len as isize).contains(&raw) {
142 raw as usize
143 } else {
144 continue;
145 };
146 if i != self.index && !out.contains(&i) {
147 out.push(i);
148 }
149 }
150 }
151 out
152 }
153
154 pub fn files(&self) -> &[PathBuf] {
155 &self.files
156 }
157
158 /// Reverse the order, keeping the current file selected.
159 pub fn reverse(&mut self) {
160 self.files.reverse();
161 self.index = self.clamp(self.files.len().saturating_sub(1) - self.index);
162 }
163
164 /// Adopt a new order of the same files (a finished re-sort), keeping the current file.
165 /// Files removed meanwhile stay removed; files added meanwhile go at the end.
166 pub fn reorder(&mut self, order: Vec<PathBuf>) {
167 let current = self.current().map(Path::to_path_buf);
168 let have: HashSet<&PathBuf> = self.files.iter().collect();
169 let mut files: Vec<PathBuf> = order.into_iter().filter(|f| have.contains(f)).collect();
170 let placed: HashSet<&PathBuf> = files.iter().collect();
171 let missing: Vec<PathBuf> = self
172 .files
173 .iter()
174 .filter(|f| !placed.contains(f))
175 .cloned()
176 .collect();
177 files.extend(missing);
178 self.files = files;
179 if let Some(cur) = current
180 && let Some(i) = self.files.iter().position(|f| *f == cur)
181 {
182 self.index = i;
183 }
184 }
185
186 pub fn is_marked(&self, i: usize) -> bool {
187 self.files.get(i).is_some_and(|f| self.marks.contains(f))
188 }
189
190 pub fn marked_count(&self) -> usize {
191 self.marks.len()
192 }
193
194 pub fn marks_version(&self) -> u64 {
195 self.marks_version
196 }
197
198 /// Mark or unmark file `i`. Returns whether anything changed.
199 pub fn set_mark(&mut self, i: usize, on: bool) -> bool {
200 let Some(f) = self.files.get(i) else {
201 return false;
202 };
203 let changed = if on {
204 self.marks.insert(f.clone())
205 } else {
206 self.marks.remove(f)
207 };
208 self.marks_version += changed as u64;
209 changed
210 }
211
212 pub fn mark_all(&mut self) {
213 self.marks = self.files.iter().cloned().collect();
214 self.marks_version += 1;
215 }
216
217 pub fn unmark_all(&mut self) {
218 self.marks.clear();
219 self.marks_version += 1;
220 }
221
222 pub fn invert_marks(&mut self) {
223 self.marks_version += 1;
224 self.marks = self
225 .files
226 .iter()
227 .filter(|f| !self.marks.contains(*f))
228 .cloned()
229 .collect();
230 }
231
232 /// Marked files in queue order.
233 pub fn marked(&self) -> Vec<&Path> {
234 self.files
235 .iter()
236 .filter(|f| self.marks.contains(*f))
237 .map(PathBuf::as_path)
238 .collect()
239 }
240
241 /// The `n`th marked file after (`forward`) or before the current one.
242 pub fn find_mark(&self, forward: bool, n: usize, wrap: bool) -> Option<usize> {
243 let len = self.files.len();
244 if self.marks.is_empty() || len == 0 {
245 return None;
246 }
247 let mut found = None;
248 let mut left = n.max(1);
249 for k in 1..len {
250 let i = if forward {
251 let i = self.index + k;
252 if i >= len && !wrap {
253 break;
254 }
255 i % len
256 } else {
257 if k > self.index && !wrap {
258 break;
259 }
260 (self.index + len - k) % len
261 };
262 if self.is_marked(i) {
263 found = Some(i);
264 left -= 1;
265 if left == 0 {
266 break;
267 }
268 }
269 }
270 found
271 }
272
273 fn clamp(&self, i: usize) -> usize {
274 i.min(self.files.len().saturating_sub(1))
275 }
276}
277
278/// Sort `files` in place. `meta` supplies (mtime seconds, size) for the stat-based keys.
279pub fn sort_files(
280 files: &mut [PathBuf],
281 key: SortKey,
282 reverse: bool,
283 meta: impl Fn(&Path) -> (i64, u64),
284 seed: u64,
285) {
286 match key {
287 SortKey::Natural => files.sort_by(|a, b| natural_cmp_path(a, b)),
288 SortKey::Name => files.sort(),
289 SortKey::Mtime => {
290 files.sort_by_cached_key(|p| meta(p).0);
291 }
292 SortKey::Size => {
293 files.sort_by_cached_key(|p| meta(p).1);
294 }
295 SortKey::Random => shuffle(files, seed),
296 }
297 if reverse {
298 files.reverse();
299 }
300}
301
302fn shuffle<T>(items: &mut [T], seed: u64) {
303 // xorshift64*: plenty for shuffling a file list.
304 let mut s = seed | 1;
305 for i in (1..items.len()).rev() {
306 s ^= s >> 12;
307 s ^= s << 25;
308 s ^= s >> 27;
309 let r = s.wrapping_mul(0x2545_F491_4F6C_DD1D);
310 items.swap(i, (r % (i as u64 + 1)) as usize);
311 }
312}
313
314pub fn natural_cmp_path(a: &Path, b: &Path) -> Ordering {
315 natural_cmp(&a.to_string_lossy(), &b.to_string_lossy())
316}
317
318/// Compare strings with digit runs ordered numerically and letters case-insensitively,
319/// so `img2` sorts before `img10` and `B` sits next to `b`.
320pub fn natural_cmp(a: &str, b: &str) -> Ordering {
321 let (mut x, mut y) = (a.chars().peekable(), b.chars().peekable());
322 loop {
323 match (x.peek().copied(), y.peek().copied()) {
324 (None, None) => return a.cmp(b),
325 (None, Some(_)) => return Ordering::Less,
326 (Some(_), None) => return Ordering::Greater,
327 (Some(c), Some(d)) if c.is_ascii_digit() && d.is_ascii_digit() => {
328 let take = |it: &mut std::iter::Peekable<std::str::Chars>| {
329 let mut s = String::new();
330 while let Some(&c) = it.peek().filter(|c| c.is_ascii_digit()) {
331 s.push(c);
332 it.next();
333 }
334 s
335 };
336 let (m, n) = (take(&mut x), take(&mut y));
337 let (mt, nt) = (m.trim_start_matches('0'), n.trim_start_matches('0'));
338 let ord = mt.len().cmp(&nt.len()).then_with(|| mt.cmp(nt));
339 if ord != Ordering::Equal {
340 return ord;
341 }
342 }
343 (Some(c), Some(d)) => {
344 let ord = c.to_lowercase().cmp(d.to_lowercase());
345 if ord != Ordering::Equal {
346 return ord;
347 }
348 x.next();
349 y.next();
350 }
351 }
352 }
353}
354
355#[cfg(test)]
356mod tests {
357 use super::*;
358
359 fn paths(names: &[&str]) -> Vec<PathBuf> {
360 names.iter().map(PathBuf::from).collect()
361 }
362
363 #[test]
364 fn natural_order() {
365 let mut v = vec![
366 "img10.png",
367 "img2.png",
368 "Img1.png",
369 "img02.png",
370 "a.png",
371 "img1b.png",
372 ];
373 v.sort_by(|a, b| natural_cmp(a, b));
374 assert_eq!(
375 v,
376 [
377 "a.png",
378 "Img1.png",
379 "img1b.png",
380 "img02.png",
381 "img2.png",
382 "img10.png"
383 ]
384 );
385 }
386
387 #[test]
388 fn step_wraps_or_clamps() {
389 let mut q = Queue::new(paths(&["a", "b", "c"]), None, 0);
390 assert!(q.step(-1, true));
391 assert_eq!(q.index(), 2);
392 assert!(!q.step(1, false));
393 assert!(q.step(-5, false));
394 assert_eq!(q.index(), 0);
395 }
396
397 #[test]
398 fn starts_on_named_file() {
399 let q = Queue::new(paths(&["a", "b", "c"]), Some(Path::new("b")), 0);
400 assert_eq!(q.current(), Some(Path::new("b")));
401 let q = Queue::new(paths(&["a", "b"]), None, 9);
402 assert_eq!(q.index(), 1);
403 }
404
405 #[test]
406 fn remove_keeps_position() {
407 let mut q = Queue::new(paths(&["a", "b", "c"]), Some(Path::new("b")), 0);
408 q.remove(Path::new("a"));
409 assert_eq!(q.current(), Some(Path::new("b")));
410 q.remove(Path::new("b"));
411 assert_eq!(q.current(), Some(Path::new("c")));
412 q.remove(Path::new("c"));
413 assert!(q.current().is_none());
414 }
415
416 #[test]
417 fn insert_sorted_keeps_current() {
418 let mut q = Queue::new(paths(&["img1", "img3"]), Some(Path::new("img3")), 0);
419 q.insert_sorted(paths(&["img2", "img10", "img1"]));
420 assert_eq!(q.len(), 4);
421 assert_eq!(q.get(1), Some(Path::new("img2")));
422 assert_eq!(q.get(3), Some(Path::new("img10")));
423 assert_eq!(q.current(), Some(Path::new("img3")));
424 }
425
426 #[test]
427 fn neighbours_nearest_first() {
428 let q = Queue::new(paths(&["a", "b", "c", "d", "e"]), None, 0);
429 assert_eq!(q.neighbours(2, false), vec![1, 2]);
430 assert_eq!(q.neighbours(2, true), vec![1, 4, 2, 3]);
431 let q = Queue::new(paths(&["a", "b"]), None, 0);
432 assert_eq!(q.neighbours(2, true), vec![1]);
433 }
434
435 #[test]
436 fn reverse_and_reorder_keep_current() {
437 let mut q = Queue::new(paths(&["a", "b", "c", "d"]), Some(Path::new("b")), 0);
438 q.reverse();
439 assert_eq!(q.files(), paths(&["d", "c", "b", "a"]));
440 assert_eq!(q.current(), Some(Path::new("b")));
441 q.remove(Path::new("d"));
442 q.reorder(paths(&["a", "b", "d", "c"]));
443 assert_eq!(q.files(), paths(&["a", "b", "c"]));
444 assert_eq!(q.current(), Some(Path::new("b")));
445 q.reorder(paths(&["c"]));
446 assert_eq!(q.files(), paths(&["c", "a", "b"]));
447 assert_eq!(q.current(), Some(Path::new("b")));
448 let mut empty = Queue::default();
449 empty.reverse();
450 assert!(empty.is_empty());
451 }
452
453 #[test]
454 fn marks_follow_files() {
455 let mut q = Queue::new(paths(&["a", "b", "c", "d"]), None, 0);
456 assert!(q.set_mark(1, true));
457 assert!(q.set_mark(3, true));
458 let v = q.marks_version();
459 assert!(!q.set_mark(3, true));
460 assert_eq!(q.marks_version(), v);
461 assert_eq!(q.marked_count(), 2);
462 q.reverse();
463 assert!(q.is_marked(0) && q.is_marked(2));
464 assert_eq!(q.marked(), [Path::new("d"), Path::new("b")]);
465 q.invert_marks();
466 assert_eq!(q.marked(), [Path::new("c"), Path::new("a")]);
467 q.remove(Path::new("c"));
468 assert_eq!(q.marked_count(), 1);
469 q.mark_all();
470 assert_eq!(q.marked_count(), 3);
471 q.unmark_all();
472 assert_eq!(q.marked_count(), 0);
473 }
474
475 #[test]
476 fn finding_marks() {
477 let mut q = Queue::new(paths(&["a", "b", "c", "d", "e"]), None, 2);
478 assert_eq!(q.find_mark(true, 1, true), None);
479 q.set_mark(0, true);
480 q.set_mark(4, true);
481 assert_eq!(q.find_mark(true, 1, true), Some(4));
482 assert_eq!(q.find_mark(true, 2, true), Some(0));
483 assert_eq!(q.find_mark(false, 1, true), Some(0));
484 assert_eq!(q.find_mark(false, 2, false), Some(0));
485 q.goto(4);
486 assert_eq!(q.find_mark(true, 1, false), None);
487 assert_eq!(q.find_mark(true, 1, true), Some(0));
488 // The current file alone is not a next mark.
489 q.unmark_all();
490 q.set_mark(4, true);
491 assert_eq!(q.find_mark(true, 1, true), None);
492 }
493
494 #[test]
495 fn random_sort_is_a_permutation() {
496 let mut v = paths(&["a", "b", "c", "d", "e"]);
497 sort_files(&mut v, SortKey::Random, false, |_| (0, 0), 42);
498 let mut s = v.clone();
499 s.sort();
500 assert_eq!(s, paths(&["a", "b", "c", "d", "e"]));
501 }
502}