From c5fb22694e95f12c24b8d8af76999be7aea3fcec Mon Sep 17 00:00:00 2001 From: 魏曹先生 <1992414357@qq.com> Date: Mon, 12 Jan 2026 04:28:28 +0800 Subject: Reorganize crate structure and move documentation files --- crates/utils/data_struct/Cargo.toml | 10 -- crates/utils/data_struct/src/bi_map.rs | 239 ------------------------------ crates/utils/data_struct/src/data_sort.rs | 232 ----------------------------- crates/utils/data_struct/src/lib.rs | 2 - 4 files changed, 483 deletions(-) delete mode 100644 crates/utils/data_struct/Cargo.toml delete mode 100644 crates/utils/data_struct/src/bi_map.rs delete mode 100644 crates/utils/data_struct/src/data_sort.rs delete mode 100644 crates/utils/data_struct/src/lib.rs (limited to 'crates/utils/data_struct') diff --git a/crates/utils/data_struct/Cargo.toml b/crates/utils/data_struct/Cargo.toml deleted file mode 100644 index e8caa6e..0000000 --- a/crates/utils/data_struct/Cargo.toml +++ /dev/null @@ -1,10 +0,0 @@ -[package] -name = "data_struct" -edition = "2024" -version.workspace = true - -[features] - -[dependencies] -serde = { version = "1.0.228", features = ["derive"] } -ahash = "0.8.12" diff --git a/crates/utils/data_struct/src/bi_map.rs b/crates/utils/data_struct/src/bi_map.rs deleted file mode 100644 index c21a9c8..0000000 --- a/crates/utils/data_struct/src/bi_map.rs +++ /dev/null @@ -1,239 +0,0 @@ -use ahash::AHasher; -use serde::{Deserialize, Serialize}; -use std::collections::HashMap; -use std::hash::{BuildHasherDefault, Hash}; - -type FastHashMap = HashMap>; - -#[derive(Debug, Clone, Serialize, Deserialize)] -pub struct BiMap -where - A: Eq + Hash + Clone, - B: Eq + Hash + Clone, -{ - #[serde(flatten)] - a_to_b: FastHashMap, - #[serde(skip)] - b_to_a: FastHashMap, -} - -pub struct Entry<'a, A, B> -where - A: Eq + Hash + Clone, - B: Eq + Hash + Clone, -{ - bimap: &'a mut BiMap, - key: A, - value: Option, -} - -impl BiMap -where - A: Eq + Hash + Clone, - B: Eq + Hash + Clone, -{ - pub fn new() -> Self { - Self { - a_to_b: FastHashMap::default(), - b_to_a: FastHashMap::default(), - } - } - - pub fn entry(&mut self, a: A) -> Entry<'_, A, B> { - let value = self.a_to_b.get(&a).cloned(); - Entry { - bimap: self, - key: a, - value, - } - } - - #[inline(always)] - pub fn insert(&mut self, a: A, b: B) { - if let Some(old_b) = self.a_to_b.insert(a.clone(), b.clone()) { - self.b_to_a.remove(&old_b); - } - if let Some(old_a) = self.b_to_a.insert(b.clone(), a.clone()) { - self.a_to_b.remove(&old_a); - } - } - - #[inline(always)] - pub fn get_by_a(&self, key: &A) -> Option<&B> { - self.a_to_b.get(key) - } - - #[inline(always)] - pub fn get_by_b(&self, key: &B) -> Option<&A> { - self.b_to_a.get(key) - } - - pub fn remove_by_a(&mut self, key: &A) -> Option<(A, B)> { - if let Some(b) = self.get_by_a(key).cloned() { - let a = self.get_by_b(&b).cloned().unwrap(); - self.a_to_b.remove(key); - self.b_to_a.remove(&b); - Some((a, b)) - } else { - None - } - } - - pub fn remove_by_b(&mut self, key: &B) -> Option<(A, B)> { - if let Some(a) = self.get_by_b(key).cloned() { - let b = self.get_by_a(&a).cloned().unwrap(); - self.b_to_a.remove(key); - self.a_to_b.remove(&a); - Some((a, b)) - } else { - None - } - } - - pub fn reserve(&mut self, additional: usize) { - self.a_to_b.reserve(additional); - self.b_to_a.reserve(additional); - } - - pub fn len(&self) -> usize { - self.a_to_b.len() - } - - pub fn is_empty(&self) -> bool { - self.a_to_b.is_empty() - } - - pub fn clear(&mut self) { - self.a_to_b.clear(); - self.b_to_a.clear(); - } - - pub fn contains_a(&self, key: &A) -> bool { - self.a_to_b.contains_key(key) - } - - pub fn contains_b(&self, key: &B) -> bool { - self.b_to_a.contains_key(key) - } - - pub fn keys_a(&self) -> impl Iterator { - self.a_to_b.keys() - } - - pub fn keys_b(&self) -> impl Iterator { - self.b_to_a.keys() - } - - pub fn iter_a_to_b(&self) -> impl Iterator { - self.a_to_b.iter() - } - - pub fn iter_b_to_a(&self) -> impl Iterator { - self.b_to_a.iter() - } -} - -impl<'a, A, B> Entry<'a, A, B> -where - A: Eq + Hash + Clone, - B: Eq + Hash + Clone, -{ - pub fn and_modify(mut self, f: F) -> Self - where - F: FnOnce(&mut B), - { - if let Some(ref mut value) = self.value { - f(value); - } - self - } - - pub fn or_insert(self, default: B) -> Result<&'a mut B, &'static str> { - self.or_insert_with(|| default) - } - - pub fn or_insert_with(mut self, default: F) -> Result<&'a mut B, &'static str> - where - F: FnOnce() -> B, - { - if self.value.is_none() { - self.value = Some(default()); - } - - let value = self.value.as_ref().ok_or("Value is None")?.clone(); - self.bimap.insert(self.key.clone(), value); - - self.bimap - .a_to_b - .get_mut(&self.key) - .ok_or("Key not found in a_to_b map") - } -} - -impl Default for BiMap -where - A: Eq + Hash + Clone, - B: Eq + Hash + Clone, -{ - fn default() -> Self { - Self::new() - } -} - -#[cfg(test)] -mod tests { - use super::*; - - #[test] - fn test_bimap_basic_operations() { - let mut bimap = BiMap::new(); - bimap.insert("key1", "value1"); - - assert_eq!(bimap.get_by_a(&"key1"), Some(&"value1")); - assert_eq!(bimap.get_by_b(&"value1"), Some(&"key1")); - assert!(bimap.contains_a(&"key1")); - assert!(bimap.contains_b(&"value1")); - } - - #[test] - fn test_bimap_remove() { - let mut bimap = BiMap::new(); - bimap.insert(1, "one"); - - assert_eq!(bimap.remove_by_a(&1), Some((1, "one"))); - assert!(bimap.is_empty()); - } - - #[test] - fn test_bimap_entry() { - let mut bimap = BiMap::new(); - bimap.entry("key1").or_insert("value1").unwrap(); - - assert_eq!(bimap.get_by_a(&"key1"), Some(&"value1")); - } - - #[test] - fn test_bimap_iterators() { - let mut bimap = BiMap::new(); - bimap.insert(1, "one"); - bimap.insert(2, "two"); - - let a_keys: Vec<_> = bimap.keys_a().collect(); - assert!(a_keys.contains(&&1) && a_keys.contains(&&2)); - - let b_keys: Vec<_> = bimap.keys_b().collect(); - assert!(b_keys.contains(&&"one") && b_keys.contains(&&"two")); - } - - #[test] - fn test_bimap_duplicate_insert() { - let mut bimap = BiMap::new(); - bimap.insert(1, "one"); - bimap.insert(1, "new_one"); - bimap.insert(2, "one"); - - assert_eq!(bimap.get_by_a(&1), Some(&"new_one")); - assert_eq!(bimap.get_by_b(&"one"), Some(&2)); - assert_eq!(bimap.get_by_a(&2), Some(&"one")); - } -} diff --git a/crates/utils/data_struct/src/data_sort.rs b/crates/utils/data_struct/src/data_sort.rs deleted file mode 100644 index 2c7a452..0000000 --- a/crates/utils/data_struct/src/data_sort.rs +++ /dev/null @@ -1,232 +0,0 @@ -/// Quick sort a slice with a custom comparison function -/// -/// # Arguments -/// * `arr` - The mutable slice to be sorted -/// * `inverse` - Sort direction: true for descending, false for ascending -/// * `compare` - Comparison function that returns -1, 0, or 1 indicating the relative order of two elements -pub fn quick_sort_with_cmp(arr: &mut [T], inverse: bool, compare: F) -where - F: Fn(&T, &T) -> i32, -{ - quick_sort_with_cmp_helper(arr, inverse, &compare); -} - -/// Quick sort for types that implement the PartialOrd trait -/// -/// # Arguments -/// * `arr` - The mutable slice to be sorted -/// * `inverse` - Sort direction: true for descending, false for ascending -pub fn quick_sort(arr: &mut [T], inverse: bool) { - quick_sort_with_cmp(arr, inverse, |a, b| { - if a < b { - -1 - } else if a > b { - 1 - } else { - 0 - } - }); -} - -fn quick_sort_with_cmp_helper(arr: &mut [T], inverse: bool, compare: &F) -where - F: Fn(&T, &T) -> i32, -{ - if arr.len() <= 1 { - return; - } - - let pivot_index = partition_with_cmp(arr, inverse, compare); - let (left, right) = arr.split_at_mut(pivot_index); - - quick_sort_with_cmp_helper(left, inverse, compare); - quick_sort_with_cmp_helper(&mut right[1..], inverse, compare); -} - -fn partition_with_cmp(arr: &mut [T], inverse: bool, compare: &F) -> usize -where - F: Fn(&T, &T) -> i32, -{ - let len = arr.len(); - let pivot_index = len / 2; - - arr.swap(pivot_index, len - 1); - - let mut i = 0; - for j in 0..len - 1 { - let cmp_result = compare(&arr[j], &arr[len - 1]); - let should_swap = if inverse { - cmp_result > 0 - } else { - cmp_result < 0 - }; - - if should_swap { - arr.swap(i, j); - i += 1; - } - } - - arr.swap(i, len - 1); - i -} - -#[cfg(test)] -pub mod sort_test { - use crate::data_sort::{quick_sort, quick_sort_with_cmp}; - - #[test] - fn test_quick_sort_ascending() { - let mut arr = [3, 1, 4, 1, 5, 9, 2, 6]; - quick_sort(&mut arr, false); - assert_eq!(arr, [1, 1, 2, 3, 4, 5, 6, 9]); - } - - #[test] - fn test_quick_sort_descending() { - let mut arr = [3, 1, 4, 1, 5, 9, 2, 6]; - quick_sort(&mut arr, true); - assert_eq!(arr, [9, 6, 5, 4, 3, 2, 1, 1]); - } - - #[test] - fn test_quick_sort_single() { - let mut arr = [42]; - quick_sort(&mut arr, false); - assert_eq!(arr, [42]); - } - - #[test] - fn test_quick_sort_already_sorted() { - let mut arr = [1, 2, 3, 4, 5]; - quick_sort(&mut arr, false); - assert_eq!(arr, [1, 2, 3, 4, 5]); - } - - #[test] - fn test_quick_sort_with_cmp_by_count() { - #[derive(Debug, PartialEq)] - struct WordCount { - word: String, - count: usize, - } - - let mut words = vec![ - WordCount { - word: "apple".to_string(), - count: 3, - }, - WordCount { - word: "banana".to_string(), - count: 1, - }, - WordCount { - word: "cherry".to_string(), - count: 5, - }, - WordCount { - word: "date".to_string(), - count: 2, - }, - ]; - - quick_sort_with_cmp(&mut words, false, |a, b| { - if a.count < b.count { - -1 - } else if a.count > b.count { - 1 - } else { - 0 - } - }); - - assert_eq!( - words, - vec![ - WordCount { - word: "banana".to_string(), - count: 1 - }, - WordCount { - word: "date".to_string(), - count: 2 - }, - WordCount { - word: "apple".to_string(), - count: 3 - }, - WordCount { - word: "cherry".to_string(), - count: 5 - }, - ] - ); - - quick_sort_with_cmp(&mut words, true, |a, b| { - if a.count < b.count { - -1 - } else if a.count > b.count { - 1 - } else { - 0 - } - }); - - assert_eq!( - words, - vec![ - WordCount { - word: "cherry".to_string(), - count: 5 - }, - WordCount { - word: "apple".to_string(), - count: 3 - }, - WordCount { - word: "date".to_string(), - count: 2 - }, - WordCount { - word: "banana".to_string(), - count: 1 - }, - ] - ); - } - - #[test] - fn test_quick_sort_with_cmp_by_first_letter() { - let mut words = vec!["zebra", "apple", "banana", "cherry", "date"]; - - quick_sort_with_cmp(&mut words, false, |a, b| { - let a_first = a.chars().next().unwrap(); - let b_first = b.chars().next().unwrap(); - - if a_first < b_first { - -1 - } else if a_first > b_first { - 1 - } else { - 0 - } - }); - - assert_eq!(words, vec!["apple", "banana", "cherry", "date", "zebra"]); - - quick_sort_with_cmp(&mut words, true, |a, b| { - let a_first = a.chars().next().unwrap(); - let b_first = b.chars().next().unwrap(); - - if a_first < b_first { - -1 - } else if a_first > b_first { - 1 - } else { - 0 - } - }); - - assert_eq!(words, vec!["zebra", "date", "cherry", "banana", "apple"]); - } -} diff --git a/crates/utils/data_struct/src/lib.rs b/crates/utils/data_struct/src/lib.rs deleted file mode 100644 index 47cc03c..0000000 --- a/crates/utils/data_struct/src/lib.rs +++ /dev/null @@ -1,2 +0,0 @@ -pub mod bi_map; -pub mod data_sort; -- cgit