daily pastebin goal
89%
SHARE
TWEET

Untitled

a guest May 17th, 2018 87 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #![allow(unused_assignments, unused_variables, dead_code)]
  2. #![feature(fn_traits, unboxed_closures)]
  3.  
  4. use std::{
  5.     cmp::Ordering,
  6.     marker::PhantomData,
  7. };
  8.  
  9. struct BinaryHeap<T, C>
  10. where
  11.     C: FnMut(&T, &T) -> Ordering,
  12. {
  13.     data: Vec<T>,
  14.     cmp: C,
  15. }
  16.  
  17. struct Max<T: Ord>(PhantomData<fn(&T, &T) -> Ordering>);
  18.  
  19. impl<T: Ord> Max<T> {
  20.     pub fn new() -> Max<T> {
  21.         Max(PhantomData)
  22.     }
  23. }
  24.  
  25. impl<'a, 'b, T: Ord> FnOnce<(&'a T, &'b T)> for Max<T> {
  26.     type Output = Ordering;
  27.     extern "rust-call" fn call_once(self, args: (&'a T, &'b T)) -> Ordering {
  28.         T::cmp(args.0, args.1)
  29.     }
  30. }
  31.  
  32. impl<'a, 'b, T: Ord> FnMut<(&'a T, &'b T)> for Max<T> {
  33.     extern "rust-call" fn call_mut(&mut self, args: (&'a T, &'b T)) -> Ordering {
  34.         T::cmp(args.0, args.1)
  35.     }
  36. }
  37.  
  38. impl<'a, 'b, T: Ord> Fn<(&'a T, &'b T)> for Max<T> {
  39.     extern "rust-call" fn call(&self, args: (&'a T, &'b T)) -> Ordering {
  40.         T::cmp(args.0, args.1)
  41.     }
  42. }
  43.  
  44. struct Min<T: Ord>(PhantomData<fn(&T, &T) -> Ordering>);
  45.  
  46. impl<T: Ord> Min<T> {
  47.     pub fn new() -> Min<T> {
  48.         Min(PhantomData)
  49.     }
  50. }
  51.  
  52. impl<'a, 'b, T: Ord> FnOnce<(&'a T, &'b T)> for Min<T> {
  53.     type Output = Ordering;
  54.     extern "rust-call" fn call_once(self, args: (&'a T, &'b T)) -> Ordering {
  55.         T::cmp(args.1, args.0)
  56.     }
  57. }
  58.  
  59. impl<'a, 'b, T: Ord> FnMut<(&'a T, &'b T)> for Min<T> {
  60.     extern "rust-call" fn call_mut(&mut self, args: (&'a T, &'b T)) -> Ordering {
  61.         T::cmp(args.1, args.0)
  62.     }
  63. }
  64.  
  65. impl<'a, 'b, T: Ord> Fn<(&'a T, &'b T)> for Min<T> {
  66.     extern "rust-call" fn call(&self, args: (&'a T, &'b T)) -> Ordering {
  67.         T::cmp(args.1, args.0)
  68.     }
  69. }
  70.  
  71. impl<T> BinaryHeap<T, fn(&T, &T) -> Ordering> {
  72.     pub fn new() -> BinaryHeap<T, Max<T>>
  73.     where
  74.         T: Ord,
  75.     {
  76.         BinaryHeap {
  77.             data: Vec::new(),
  78.             cmp: Max(PhantomData),
  79.         }
  80.     }
  81.  
  82.     pub fn new_by<C>(cmp: C) -> BinaryHeap<T, C>
  83.     where
  84.         C: FnMut(&T, &T) -> Ordering,
  85.     {
  86.         BinaryHeap {
  87.             data: Vec::new(),
  88.             cmp,
  89.         }
  90.     }
  91.  
  92.     pub fn new_by_key<K, F>(mut f: F) -> BinaryHeap<T, impl FnMut(&T, &T) -> Ordering>
  93.     where
  94.         K: Ord,
  95.         F: FnMut(&T) -> K,
  96.     {
  97.         BinaryHeap {
  98.             data: Vec::new(),
  99.             cmp: move |x, y| K::cmp(&f(x), &f(y)),
  100.         }
  101.     }
  102.  
  103.     pub fn with_capacity(capacity: usize) -> BinaryHeap<T, Max<T>>
  104.     where
  105.         T: Ord,
  106.     {
  107.         BinaryHeap {
  108.             data: Vec::with_capacity(capacity),
  109.             cmp: Max(PhantomData),
  110.         }
  111.     }
  112.  
  113.     pub fn with_capacity_by<C>(capacity: usize, cmp: C) -> BinaryHeap<T, C>
  114.     where
  115.         C: FnMut(&T, &T) -> Ordering,
  116.     {
  117.         BinaryHeap {
  118.             data: Vec::with_capacity(capacity),
  119.             cmp,
  120.         }
  121.     }
  122.  
  123.     pub fn with_capacity_by_key<K, F>(capacity: usize, mut f: F) -> BinaryHeap<T, impl FnMut(&T, &T) -> Ordering>
  124.     where
  125.         K: Ord,
  126.         F: FnMut(&T) -> K,
  127.     {
  128.         BinaryHeap {
  129.             data: Vec::with_capacity(capacity),
  130.             cmp: move |x, y| K::cmp(&f(x), &f(y)),
  131.         }
  132.     }
  133.  
  134.     pub fn from(vec: Vec<T>) -> BinaryHeap<T, Max<T>>
  135.     where
  136.         T: Ord,
  137.     {
  138.         // TODO heapify data.
  139.         BinaryHeap {
  140.             data: vec,
  141.             cmp: Max(PhantomData),
  142.         }
  143.     }
  144.  
  145.     pub fn from_by<C>(vec: Vec<T>, cmp: C) -> BinaryHeap<T, C>
  146.     where
  147.         C: FnMut(&T, &T) -> Ordering,
  148.     {
  149.         // TODO heapify data.
  150.         BinaryHeap {
  151.             data: vec,
  152.             cmp,
  153.         }
  154.     }
  155.  
  156.     pub fn from_by_key<K, F>(vec: Vec<T>, mut f: F) -> BinaryHeap<T, impl FnMut(&T, &T) -> Ordering>
  157.     where
  158.         K: Ord,
  159.         F: FnMut(&T) -> K,
  160.     {
  161.         // TODO heapify data.
  162.         BinaryHeap {
  163.             data: vec,
  164.             cmp: move |x, y| K::cmp(&f(x), &f(y)),
  165.         }
  166.     }
  167. }
  168.  
  169. impl<T, F> BinaryHeap<T, F>
  170. where
  171.     F: FnMut(&T, &T) -> Ordering,
  172. {
  173.     pub fn change_compare(&mut self, cmp: F) {
  174.         // TODO heapify data.
  175.         self.cmp = cmp;
  176.     }
  177.  
  178.     pub fn peek(&self) -> Option<&T> {
  179.         if self.data.len() > 0 {
  180.             Some(&self.data[0])
  181.         } else {
  182.             None
  183.         }
  184.     }
  185. }
  186.  
  187. fn main() {
  188.     let heap = BinaryHeap::new();
  189.     let value: Option<&usize> = heap.peek();
  190.    
  191.     let heap = BinaryHeap::new_by(Min::new());
  192.     let value: Option<&usize> = heap.peek();
  193.    
  194.     let heap = BinaryHeap::new_by_key(|value| !0 - *value);
  195.     let value: Option<&usize> = heap.peek();
  196. }
RAW Paste Data
Top