I've got a monotone (strictly increasing) map that I will need to evaluate and invert (motivating problem is from implementing a CDF for an Empirical distribution)
Since it's monotone, ordinality is the same with both key and value and that means the sorting key can be something that is from both values. So I figured I can implement this with a BTreeSet
The benefit I expected was being able to range over the tree from either the key or value. However, I'm getting this error that requires I call something with RangeBounds<T> where T is the key / element for the BTreeSet, there's not a meaningful conversion from the RangeTo<KV<_,_>> which has one but not both key and value.
My questions are
- What are my options here?
- Why isn't
rangeinstead ofimpl RangeBounds<T: Ord<K> + Eq<K>>whereKis the type for thekeyinBTreeMap/BTreeSet?
use ordered_float::NotNan;
use rand::distributions::Distribution;
use std::collections::BTreeSet;
#[derive(PartialEq, Ord, Eq)]
struct MonotoneMap<K, V> {
key: K,
val: V,
}
impl<K, V> PartialOrd for MonotoneMap<K, V>
where
K: PartialOrd,
V: PartialOrd,
{
fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
let k_ord = self.key.partial_cmp(&other.key);
let v_ord = self.val.partial_cmp(&other.val);
if k_ord != v_ord {
panic!("Found violation of monotonicity comparing MonotoneMap")
} else {
k_ord
}
}
}
#[derive(PartialEq, PartialOrd, Ord, Eq)]
enum KV<K, V> {
K(K),
V(V),
}
impl<K, V> PartialEq<KV<K, V>> for MonotoneMap<K, V>
where
K: PartialEq,
V: PartialEq,
{
fn eq(&self, other: &KV<K, V>) -> bool {
match other {
KV::K(k) => self.key.eq(k),
KV::V(v) => self.val.eq(v),
}
}
}
impl<K, V> PartialOrd<KV<K, V>> for MonotoneMap<K, V>
where
K: PartialOrd,
V: PartialOrd,
{
fn partial_cmp(&self, other: &KV<K, V>) -> Option<std::cmp::Ordering> {
match other {
KV::K(k) => self.key.partial_cmp(k),
KV::V(v) => self.val.partial_cmp(v),
}
}
}
pub struct Empirical {
count: u64,
mode: Option<NotNan<f64>>,
mean_and_var: Option<(NotNan<f64>, NotNan<f64>)>,
data: BTreeSet<MonotoneMap<NotNan<f64>, NotNan<f64>>>,
}
impl Empirical {
fn new() -> Self {
Empirical {
count: 0,
mode: None,
mean_and_var: None,
data: BTreeSet::new(),
}
}
fn cdf(&self, x: f64) -> f64 {
if let Ok(not_nan_data) = NotNan::new(x) {
if let Some(last) = self.data.range(..=KV::K(not_nan_data)).next_back() {
return last.val.into_inner();
}
}
f64::NAN
}
fn inverse_cdf(&self, p: f64) -> f64 {
if !(0.0..=1.0).contains(&p) {
return f64::NAN;
}
if let Ok(not_nan_data) = NotNan::new(p) {
if let Some(last) = self.data.range(KV::V(p)..).next() {
return last.key.into_inner();
}
}
f64::NAN
}
}
impl Distribution<f64> for Empirical {
fn sample<R: rand::prelude::Rng + ?Sized>(&self, rng: &mut R) -> f64 {
let uniform = rand::distributions::uniform::Uniform::new(0.0, 1.0);
self.inverse_cdf(uniform.sample(rng))
}
}
Errors:
Compiling playground v0.0.1 (/playground)
error[E0277]: the trait bound `RangeToInclusive<KV<NotNan<f64>, _>>: RangeBounds<MonotoneMap<NotNan<f64>, NotNan<f64>>>` is not satisfied
--> src/lib.rs:62:49
|
62 | if let Some(last) = self.data.range(..=KV::K(not_nan_data)).next_back() {
| ----- ^^^^^^^^^^^^^^^^^^^^^^ the trait `RangeBounds<MonotoneMap<NotNan<f64>, NotNan<f64>>>` is not implemented for `RangeToInclusive<KV<NotNan<f64>, _>>`
| |
| required by a bound introduced by this call
|
= help: the following other types implement trait `RangeBounds<T>`:
RangeToInclusive<&T>
RangeToInclusive<T>
note: required by a bound in `BTreeSet::<T, A>::range`
--> /playground/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/alloc/src/collections/btree/set.rs:397:12
|
393 | pub fn range<K: ?Sized, R>(&self, range: R) -> Range<'_, T>
| ----- required by a bound in this associated function
...
397 | R: RangeBounds<K>,
| ^^^^^^^^^^^^^^ required by this bound in `BTreeSet::<T, A>::range`
error[E0277]: the trait bound `RangeFrom<KV<_, f64>>: RangeBounds<MonotoneMap<NotNan<f64>, NotNan<f64>>>` is not satisfied
--> src/lib.rs:74:49
|
74 | if let Some(last) = self.data.range(KV::V(p)..).next() {
| ----- ^^^^^^^^^^ the trait `RangeBounds<MonotoneMap<NotNan<f64>, NotNan<f64>>>` is not implemented for `RangeFrom<KV<_, f64>>`
| |
| required by a bound introduced by this call
|
= help: the following other types implement trait `RangeBounds<T>`:
RangeFrom<&T>
RangeFrom<T>
note: required by a bound in `BTreeSet::<T, A>::range`
--> /playground/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/alloc/src/collections/btree/set.rs:397:12
|
393 | pub fn range<K: ?Sized, R>(&self, range: R) -> Range<'_, T>
| ----- required by a bound in this associated function
...
397 | R: RangeBounds<K>,
| ^^^^^^^^^^^^^^ required by this bound in `BTreeSet::<T, A>::range`
For more information about this error, try `rustc --explain E0277`.
error: could not compile `playground` (lib) due to 2 previous errors
