From dca341dbb54737e8cc14a41088e23d23f7eb385e Mon Sep 17 00:00:00 2001 From: JSDurand Date: Tue, 14 Mar 2023 23:11:09 +0800 Subject: Implement the correct solution Now the correct solution, as suggested by the professor, is implemented as the function `smi`. :D --- src/lib.rs | 27 ++++++++++++++++++--------- 1 file changed, 18 insertions(+), 9 deletions(-) (limited to 'src/lib.rs') diff --git a/src/lib.rs b/src/lib.rs index c474398..ff309d1 100644 --- a/src/lib.rs +++ b/src/lib.rs @@ -14,6 +14,10 @@ use rand::{ use std::collections::HashSet; +pub mod incremental; + +pub use incremental::smi; + /// Adjacency set representation type Graph = Vec>; @@ -275,19 +279,24 @@ mod tests { }; let mut count = 0; - let _sorted = sm(input.as_slice(), &mut count); - // println!( - // "sorted = {:?}", - // sorted - // .into_iter() - // .map(|x| *input.get(x).unwrap()) - // .collect::>() - // ); + let sorted = sm(input.as_slice(), &mut count); + + let sorted: Vec<_> = sorted.into_iter().map(|x| *input.get(x).unwrap()).collect(); + + let mut really_sorted = input; + + // floats are not totally ordered, so there is no default + // method to sort a vector of floats. + really_sorted.sort_unstable_by(|x, y| x.partial_cmp(y).unwrap()); + + assert_eq!(sorted, really_sorted); + + // println!("sorted = {:?}", sorted,); println!( "n = {n}, count = {count}, nlog(n) = {}", - n * ((n as f32).log2() as usize) + n * ((n as f32).log2().ceil() as usize) ); } } -- cgit v1.2.3-18-g5258