tuple Binaryheap

[xingzhicn]

I want to implement a tuple minimumheap, eg. vec![(1,5),(3,2),(2,3)], compare the size by second value.but report an error ,If you want to achieve what I should do？

 // custom-sort heap

Let mut heap = BinaryHeap::from_vec_cmp(vec![(1,5),(3,2),(2,3)], FnComparator(|a: (&i32,&i32), b:(&i32,&i32)| B.1.cmp(a.1)));

Assert_eq!(heap.pop(), Some((1,5)));

[sekineh]

Hi, What kind of error did you get?

Sent from my iPhone

On Sep 3, 2019, at 20:24, 张行之 notifications@github.com wrote:

I want to implement a tuple minimumheap, eg. vec![(1,5),(3,2),(2,3)], compare the size by second value.but report an error ,If you want to achieve what I should do？

// custom-sort heap

Let mut heap = BinaryHeap::from_vec_cmp(vec![(1,5),(3,2),(2,3)], FnComparator(|a: (&i32,&i32), b:(&i32,&i32)| B.1.cmp(a.1)));

Assert_eq!(heap.pop(), Some((1,5))); — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub, or mute the thread.

[sekineh]

You might want to change (&i32, &i32) to &(i32, i32).

[xingzhicn]

Thank you for your reply, I think it is compare::Compare does not support the comparison of tuples. my code:

// custom-sort heap
let mut heap = BinaryHeap::from_vec_cmp(vec![(1,5),(3,2),(2,3)], FnComparator(|a: (&i32,&i32), b:(&i32,&i32)| b.1.cmp(a.1)));
assert_eq!(heap.pop(), Some((1,5)));

error:

error[E0277]: the trait bound `binary_heap_plus::binary_heap::FnComparator<[closure@examples\test.rs:17:79: 17:123]>: compare::Compare<({integer}, {integer})>` is not satisfied
  --> examples\test.rs:17:16
   |
17 | let mut heap = BinaryHeap::from_vec_cmp(vec![(1,5),(3,2),(2,3)], FnComparator(|a: (&i32,&i32), b:(&i32,&i32)| b.1.cmp(a.1)));
   |                ^^^^^^^^^^^^^^^^^^^^^^^^ the trait `compare::Compare<({integer}, {integer})>` is not implemented for `binary_heap_plus::binary_heap::FnComparator<[closure@examples\test.rs:17:79: 17:123]>`
   |
   = help: the following implementations were found:
             <binary_heap_plus::binary_heap::FnComparator<F> as compare::Compare<T>>
   = note: required by `binary_heap_plus::binary_heap::BinaryHeap::<T, C>::from_vec_cmp`

error[E0277]: the trait bound `binary_heap_plus::binary_heap::FnComparator<[closure@examples\test.rs:17:79: 17:123]>: compare::Compare<({integer}, {integer})>` is not satisfied
  --> examples\test.rs:17:16
   |
17 | let mut heap = BinaryHeap::from_vec_cmp(vec![(1,5),(3,2),(2,3)], FnComparator(|a: (&i32,&i32), b:(&i32,&i32)| b.1.cmp(a.1)));
   |                ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ the trait `compare::Compare<({integer}, {integer})>` is not implemented for `binary_heap_plus::binary_heap::FnComparator<[closure@examples\test.rs:17:79: 17:123]>`
   |
   = help: the following implementations were found:
             <binary_heap_plus::binary_heap::FnComparator<F> as compare::Compare<T>>
   = note: required by `binary_heap_plus::binary_heap::BinaryHeap`

error[E0599]: no method named `pop` found for type `binary_heap_plus::binary_heap::BinaryHeap<({integer}, {integer}), binary_heap_plus::binary_heap::FnComparator<[closure@examples\test.rs:17:79: 17:123]>>` in the current scope
  --> examples\test.rs:18:17
   |
18 | assert_eq!(heap.pop(), Some((1,5)));
   |                 ^^^
   |
   = note: the method `pop` exists but the following trait bounds were not satisfied:
           `binary_heap_plus::binary_heap::FnComparator<[closure@examples\test.rs:17:79: 17:123]> : compare::Compare<({integer}, {integer})>`

error: aborting due to 3 previous errors

[sekineh]

For tuple compare function, you need to use &(T,T) instead of (&T, &T) for arguments.

I confirmed this will compile and run successfully:

use binary_heap_plus::*;

fn main() {
    // custom-sort heap
    let mut heap = BinaryHeap::from_vec_cmp(
        vec![(1,5),(3,2),(2,3)], 
        FnComparator(|a: &(i32,i32), b: &(i32,i32)| b.1.cmp(&a.1))
    );
    // assert_eq!(heap.pop(), Some((1,5)));
    assert_eq!(heap.pop(), Some((3,2))); // min value
}

You can also write like this in v0.2.0 or later:

    # FnComparator omitted
    let mut heap = BinaryHeap::from_vec_cmp(
        vec![(1,5),(3,2),(2,3)], 
        |a: &(i32,i32), b: &(i32,i32)| b.1.cmp(&a.1) // Just a closure here
    );

[xingzhicn]

Solve the problem perfectly！