use std::cmp::Ordering;
use std::collections::HashMap;
use std::path::Path;
pub struct WalkOrder<'a> {
root: &'a Path,
listings: HashMap<String, Option<HashMap<String, usize>>>,
}
impl<'a> WalkOrder<'a> {
pub fn new(root: &'a Path) -> Self {
Self {
root,
listings: HashMap::new(),
}
}
fn position(&mut self, dir: &str, name: &str) -> Option<usize> {
let root = self.root;
let listing = self.listings.entry(dir.to_string()).or_insert_with(|| {
let path = if dir.is_empty() {
root.to_path_buf()
} else {
root.join(dir)
};
let entries = std::fs::read_dir(path).ok()?;
Some(
entries
.filter_map(|e| e.ok())
.enumerate()
.map(|(i, e)| (e.file_name().to_string_lossy().into_owned(), i))
.collect(),
)
});
listing.as_ref()?.get(name).copied()
}
pub fn cmp(&mut self, a: &str, b: &str) -> Option<Ordering> {
let mut dir = String::new();
let (mut ai, mut bi) = (a.split('/'), b.split('/'));
loop {
match (ai.next(), bi.next()) {
(Some(x), Some(y)) if x == y => {
if !dir.is_empty() {
dir.push('/');
}
dir.push_str(x);
}
(Some(x), Some(y)) => {
let px = self.position(&dir, x)?;
let py = self.position(&dir, y)?;
return Some(px.cmp(&py));
}
(None, Some(_)) => return Some(Ordering::Less),
(Some(_), None) => return Some(Ordering::Greater),
(None, None) => return Some(Ordering::Equal),
}
}
}
pub fn insert_position<S: AsRef<str>>(&mut self, ordered: &[S], path: &str) -> Option<usize> {
let (mut lo, mut hi) = (0, ordered.len());
while lo < hi {
let mid = lo + (hi - lo) / 2;
match self.cmp(ordered[mid].as_ref(), path)? {
Ordering::Less => lo = mid + 1,
Ordering::Greater => hi = mid,
Ordering::Equal => return Some(mid),
}
}
Some(lo)
}
}
#[cfg(test)]
mod tests {
use super::*;
use std::fs;
fn walked(root: &Path) -> Vec<String> {
ignore::WalkBuilder::new(root)
.hidden(false)
.build()
.filter_map(|e| e.ok())
.filter(|e| e.file_type().is_some_and(|t| t.is_file()))
.map(|e| {
e.path()
.strip_prefix(root)
.unwrap()
.to_string_lossy()
.replace('\\', "/")
})
.collect()
}
fn tree() -> tempfile::TempDir {
let temp = tempfile::TempDir::new().unwrap();
let mut state = 7u64;
let mut next = || {
state = state
.wrapping_mul(6364136223846793005)
.wrapping_add(1442695040888963407);
(state >> 33) as usize
};
let dirs = ["", "a", "a/b", "a/b/c", "d", "d/e", "zz", "m/n/o/p"];
for i in 0..300 {
let dir = dirs[next() % dirs.len()];
let name = format!("f{}_{}.rs", next() % 1000, i);
let path = temp.path().join(dir).join(name);
fs::create_dir_all(path.parent().unwrap()).unwrap();
fs::write(path, "x").unwrap();
}
temp
}
#[test]
fn sorting_by_the_comparator_gives_the_walk_order() {
let temp = tree();
let root = temp.path();
let expected = walked(root);
let mut shuffled = expected.clone();
shuffled.sort(); shuffled.reverse();
let mut order = WalkOrder::new(root);
shuffled.sort_by(|a, b| order.cmp(a, b).unwrap());
assert_eq!(shuffled, expected);
}
#[test]
fn inserting_each_file_finds_its_walk_position() {
let temp = tree();
let root = temp.path();
let expected = walked(root);
let mut order = WalkOrder::new(root);
for (k, path) in expected.iter().enumerate().step_by(7) {
let mut rest = expected.clone();
rest.remove(k);
assert_eq!(order.insert_position(&rest, path), Some(k), "{path}");
}
}
#[test]
fn a_missing_entry_cannot_be_compared() {
let temp = tree();
let mut order = WalkOrder::new(temp.path());
assert_eq!(order.cmp("a/none.rs", "a/other.rs"), None);
assert_eq!(order.cmp("a/x", "a/x"), Some(Ordering::Equal));
}
}