SHARE
TWEET

Untitled

a guest May 22nd, 2019 66 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. use std::cmp::Ordering;
  2.  
  3. fn merge_sort<T: PartialOrd + Copy>(data: &mut [T]) {
  4.     fn merge<T: PartialOrd + Copy>(left: &mut [T], right: &mut [T], util: &mut [Option<T>]) {
  5.         let mut left_index = 0usize;
  6.         let mut right_index = 0usize;
  7.         let left_len = left.len();
  8.         let right_len = right.len();
  9.    
  10.         for item in util {
  11.             if (left_index < left_len) &&
  12.             (right_index >= right_len || left[left_index] <= right[right_index]) {
  13.                 *item = Some(left[left_index]);
  14.                 left_index += 1;
  15.             } else {
  16.                 *item = Some(right[right_index]);
  17.                 right_index += 1;
  18.             }
  19.         }
  20.     }
  21.  
  22.     fn tick<T: PartialOrd + Copy>(data: &mut [T], util: &mut [Option<T>]) {
  23.         if data.len() < 2 {
  24.             return
  25.         }
  26.        
  27.         let middle = data.len() / 2;
  28.    
  29.         let (data_left, data_right) = data.split_at_mut(middle);
  30.         let (util_left, util_right) = util.split_at_mut(middle);
  31.        
  32.         tick(data_left, util_left);
  33.         tick(data_right, util_right);
  34.        
  35.         merge(data_left, data_right, util);
  36.        
  37.         let util_iter = util.iter().filter_map(|item| *item);
  38.        
  39.         for (index, item) in util_iter.enumerate() {
  40.             data[index] = item;
  41.         }
  42.     }
  43.    
  44.     let len = data.len();
  45.    
  46.     if len < 2 {
  47.         return
  48.     }
  49.    
  50.     let mut util: Vec<Option<T>> = vec![None; len];
  51.    
  52.     tick(data, util.as_mut_slice());
  53. }
  54.  
  55. fn main() {
  56.     fn show_numbers_example(data: &mut [u32]) {
  57.         merge_sort(data);
  58.        
  59.         println!("{:?}", data);
  60.     }
  61.    
  62.     show_numbers_example(&mut [38, 27, 43, 3, 9, 82, 10]);
  63.     show_numbers_example(&mut [2, 1]);
  64.     show_numbers_example(&mut [3, 4, 5]);
  65.    
  66.    
  67.     fn show_users_example(data: &mut [User]) {
  68.         merge_sort(data);
  69.        
  70.         println!("{:?}", data);
  71.     }
  72.    
  73.     show_users_example(&mut [
  74.         User::new(0, "Boris", 21),
  75.         User::new(1, "Sarah", 32),
  76.         User::new(2, "Rose", 12),
  77.         User::new(3, "John", 23)
  78.     ]);
  79. }
  80.  
  81. #[derive(Clone, Copy, Debug)]
  82. struct User {
  83.     id: u32,
  84.     name: &'static str,
  85.     age: u32
  86. }
  87.  
  88. impl User {
  89.     fn new(id: u32, name: &'static str, age: u32) -> Self {
  90.         Self {
  91.             id,
  92.             name,
  93.             age
  94.         }
  95.     }
  96. }
  97.  
  98. impl PartialEq for User {
  99.     fn eq(&self, other: &Self) -> bool {
  100.         self.age == other.age
  101.     }
  102. }
  103.  
  104. impl PartialOrd for User {
  105.     fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
  106.         Some(self.age.cmp(&other.age))
  107.     }
  108. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top