BinaryHeapに優先度を指定して追加したい

Rust初心者がいろいろやってみているところ、参考にはしないでもらいたい。

BinaryHeapを使用して、優先度に応じて取り出したいのだけど、どうやればよいのかわからなかったので、いろいろ調べてみた。

1. BinaryHeapに追加するにはOrdが実装されていないといけない。
2. その時々で優先度をつけるためには、優先順位を付与したオブジェクトでラップしてやればよい

ということで、こんな風になった。

use std::cmp::Ordering;
use std::cmp::Reverse;

struct Priority<T,P : Ord + Copy>(T, P);

impl<T,P : Ord + Copy> Priority<T,P> {
  fn  new(obj: T, priority : P) -> Priority<T,P> {
    Priority(obj, priority)
  }
  fn rev(obj: T, priority : P) -> Reverse<Priority<T,P>> {
    Reverse(Priority::new(obj, priority))
  }
}

impl<T,P : Ord + Copy> Eq for Priority<T,P> {}
impl<T,P : Ord + Copy> PartialEq for Priority<T,P> {
  fn eq(&self, other : &Priority<T,P>) -> bool {
    self.1.eq(&other.1)
  }
}
impl<T,P : Ord + Copy> PartialOrd for Priority<T,P> {
  fn partial_cmp(&self, other : &Priority<T,P>) -> Option<Ordering> {
    Some(self.1.cmp(&other.1))
  }  
}
impl<T,P : Ord + Copy> Ord for Priority<T,P> {
  fn cmp(&self, other : &Priority<T,P>) -> Ordering {
    self.1.cmp(&other.1)
  }
}

BinaryHeapはmax-heapなので、Priorityとした。
優先度が高い方が数値にしたとき数字が大きいイメージがあるから、優先度低い方から出すときは、std::cmp::Reverseを一緒に使う。

使い方は以下のようにPriority::new と Priority::revでラップしてBinaryHeapに追加する。

use std::collections::*;
fn main(){
  let mut heap = BinaryHeap::new();
  heap.push(Priority::new("A", 2));
  heap.push(Priority::new("B", 3));
  heap.push(Priority::new("C", 1));

  while let Some(Priority(s, pr)) = heap.pop() {
    // 優先度が高い方が先に出るので、BACの順
    // B 3
    // A 2
    // C 1
    println!("{} {}", s, pr);
  }

  let mut min_heap = BinaryHeap::new();
  min_heap.push(Priority::rev("A", 2));
  min_heap.push(Priority::rev("B", 3));
  min_heap.push(Priority::rev("C", 1));
  while let Some(Reverse(Priority(s, pr))) = min_heap .pop() {
    // 優先度が低い方が先に出るので、CABの順
    // C 1
    // A 2
    // B 3
    println!("{} {}", s, pr);
  }
}