Krolyxon
Commit c498905

Branches

Tags

Refs →

remagesrcstatequeue.rs

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