82 lines
1.7 KiB
Rust
82 lines
1.7 KiB
Rust
use std::cmp::Ordering;
|
|
|
|
fn merge2<T: Ord + Copy, F: Fn(T)>(c1: &[T], c2: &[T], action: F) {
|
|
let mut i1 = 0;
|
|
let mut i2 = 0;
|
|
|
|
while i1 < c1.len() && i2 < c2.len() {
|
|
if c1[i1] <= c2[i2] {
|
|
action(c1[i1]);
|
|
i1 += 1;
|
|
} else {
|
|
action(c2[i2]);
|
|
i2 += 1;
|
|
}
|
|
}
|
|
|
|
while i1 < c1.len() {
|
|
action(c1[i1]);
|
|
i1 += 1;
|
|
}
|
|
|
|
while i2 < c2.len() {
|
|
action(c2[i2]);
|
|
i2 += 1;
|
|
}
|
|
}
|
|
|
|
fn merge_n<T: Ord + Copy, F: Fn(T)>(action: F, all: &[&[T]]) {
|
|
let mut vit: Vec<(usize, usize)> = all.iter().map(|c| (0, c.len())).collect();
|
|
|
|
loop {
|
|
let mut done = true;
|
|
let mut least: Option<usize> = None;
|
|
|
|
for (i, &(start, end)) in vit.iter().enumerate() {
|
|
if start < end {
|
|
if least.is_none() {
|
|
least = Some(i);
|
|
} else {
|
|
if let Some(l) = least {
|
|
if all[i][start].cmp(&all[l][vit[l].0]) == Ordering::Less {
|
|
least = Some(i);
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
if let Some(l) = least {
|
|
if vit[l].0 < vit[l].1 {
|
|
done = false;
|
|
action(all[l][vit[l].0]);
|
|
vit[l].0 += 1;
|
|
}
|
|
}
|
|
|
|
if done {
|
|
break;
|
|
}
|
|
}
|
|
}
|
|
|
|
|
|
fn display(num: i32) {
|
|
print!("{} ", num);
|
|
}
|
|
|
|
fn main() {
|
|
let v1 = vec![0, 3, 6];
|
|
let v2 = vec![1, 4, 7];
|
|
let v3 = vec![2, 5, 8];
|
|
|
|
merge2(&v2, &v1, display);
|
|
println!();
|
|
|
|
merge_n(display, &[&v1]);
|
|
println!();
|
|
|
|
merge_n(display, &[&v3, &v2, &v1]);
|
|
println!();
|
|
}
|