conflidb 0.1.0

const DATA_U64_SIZE: usize = 4;
const DATA_U8_SIZE: usize = 32;
const ONE_I128: i128 = 0x1_0000_0000_0000_0000;
const ONE_F64: f64 = ONE_I128 as f64;

use rand_core::{OsRng, RngCore};
use serde::{Deserialize, Serialize};
use sha2::Digest;
use sha2::Sha256;
use std::cmp::Ordering;
use std::fmt::Formatter;
use std::num::Wrapping;

/// CKey implements a consistent hask key.
/// Theory here: https://en.wikipedia.org/wiki/Consistent_hashing
///
/// # Examples
///
/// ```
/// use conflidb::CKey;
///
/// let k1 = CKey::new_rand();
/// let k2 = k1.next();
/// print!("k1:{:?} k2:{:?}\n", k1, k2);
/// ```
#[derive(Default, Clone, Copy, Serialize, Deserialize, PartialEq, Eq)]
pub struct CKey {
    data: [u64; DATA_U64_SIZE],
}

impl CKey {
    /// Make a digest from data and returns a new key from it.
    /// Typical usage is to create a a CKey from a string or an object content.
    ///
    /// # Examples
    /// ```
    /// use conflidb::CKey;
    ///
    /// let k = CKey::new_digest("/a/unique/path");
    /// assert_eq!("3b818742b0f27cfc10f4de1e5ba5594c975d580c412a31011ad58d36a2b17cdc", format!("{:?}",k));
    /// ```
    pub fn new_digest(data: impl AsRef<[u8]>) -> Self {
        let mut hasher = Sha256::default();
        hasher.update(data);
        let hash = hasher.finalize();
        bincode::deserialize(&hash).unwrap()
    }

    /// Generate a random key. This can be time consuming as it is using
    /// the OS random generation, which is better from a cryptographic
    /// point of view, but possibly slower than a standard prng.
    ///
    /// # Examples
    /// ```
    /// use conflidb::CKey;
    ///
    /// let k = CKey::new_rand();
    /// print!("k: {:?}", k);
    /// ```
    pub fn new_rand() -> Self {
        let mut hash = [0u8; DATA_U8_SIZE];
        OsRng.fill_bytes(&mut hash);
        bincode::deserialize(&hash).unwrap()
    }

    /// Generate a key with the value 0.
    ///
    /// # Examples
    /// ```
    /// use conflidb::CKey;
    ///
    /// let k = CKey::new_zero();
    /// assert_eq!("0000000000000000000000000000000000000000000000000000000000000000", format!("{:?}", k));
    /// ```
    pub fn new_zero() -> Self {
        Self::default()
    }

    /// Generate a key with the value 1, the smallest key possible just after zero.
    ///
    /// # Examples
    /// ```
    /// use conflidb::CKey;
    ///
    /// let k = CKey::new_unit();
    /// assert_eq!("0000000000000000000000000000000000000000000000000000000000000001", format!("{:?}", k));
    /// ```
    pub fn new_unit() -> Self {
        Self { data: [0, 0, 0, 1] }
    }

    /// Generate a key with the last, highest possible value.
    ///
    /// # Examples
    /// ```
    /// use conflidb::CKey;
    ///
    /// let k = CKey::new_last();
    /// assert_eq!("ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff", format!("{:?}", k));
    /// ```
    pub fn new_last() -> Self {
        Self {
            data: [
                0xffffffffffffffff,
                0xffffffffffffffff,
                0xffffffffffffffff,
                0xffffffffffffffff,
            ],
        }
    }

    /// Generate a key which is exactly in the middle of the ring.
    ///
    /// # Examples
    /// ```
    /// use conflidb::CKey;
    ///
    /// let k = CKey::new_half();
    /// assert_eq!("8000000000000000000000000000000000000000000000000000000000000000", format!("{:?}", k));
    /// ```
    pub fn new_half() -> Self {
        Self {
            data: [
                0x8000000000000000,
                0x0000000000000000,
                0x0000000000000000,
                0x0000000000000000,
            ],
        }
    }

    /// Returns true if self is inside lower and upper.
    /// Lower limit is excluded, upper is included.
    /// This is typically used in a ring to know if a given
    /// key is handled by a node. You would ask if key
    /// is inside previous node (lower) and this node (upper)
    /// and if true -> yes, this is the right node to handle it.
    ///
    /// # Examples
    /// ```
    /// use conflidb::CKey;
    ///
    /// let k1 = CKey::from(0.1);
    /// let k2 = CKey::from(0.3);
    /// let k3 = CKey::from(0.9);
    /// assert!(k2.inside(k1, k3));
    /// ```
    pub fn inside(self, lower: CKey, upper: CKey) -> bool {
        if lower == upper {
            // If lower and upper are equal, consider it matches all the ring,
            // so any value is inside the interval.
            return true;
        }
        // Upper limit is included within the interval. Lower is not.
        if self == lower {
            return false;
        }
        if self == upper {
            return true;
        }
        // Now compare member by member, since we made a diff initially,
        // self and upper are correctly ordered, according to lower.
        let lower_to_self = self - lower;
        let lower_to_upper = upper - lower;
        for i in 0..DATA_U64_SIZE {
            if lower_to_self.data[i] > lower_to_upper.data[i] {
                return false;
            }
            if lower_to_self.data[i] < lower_to_upper.data[i] {
                return true;
            }
        }
        // This should be unreachable code as to get here, we need to
        // have self == upper and this is a special case was tested before.
        true
    }

    /// Increment current key by one.
    ///
    /// # Examples
    /// ```
    /// use conflidb::CKey;
    ///
    /// let mut k = CKey::new_zero();
    /// k.incr();
    /// assert_eq!(CKey::new_unit(), k);
    /// ```
    pub fn incr(&mut self) {
        *self = self.next();
    }

    /// Decrement current key by one.
    ///
    /// # Examples
    /// ```
    /// use conflidb::CKey;
    ///
    /// let mut k = CKey::new_zero();
    /// k.decr();
    /// assert_eq!(CKey::new_last(), k);
    /// ```
    pub fn decr(&mut self) {
        *self = self.prev();
    }

    /// Return current key plus one.
    ///
    /// # Examples
    /// ```
    /// use conflidb::CKey;
    ///
    /// let k = CKey::new_zero();
    /// assert_eq!(CKey::new_unit(), k.next());
    /// ```
    pub fn next(self) -> CKey {
        self + Self::new_unit()
    }

    /// Return current key minus one.
    ///
    /// # Examples
    /// ```
    /// use conflidb::CKey;
    ///
    /// let k = CKey::new_zero();
    /// assert_eq!(CKey::new_last(), k.prev());
    /// ```
    pub fn prev(self) -> CKey {
        self - Self::new_unit()
    }

    /// Sort an array of keys, using a start reference.
    ///
    /// There is no way to sort keys in an absolute way,
    /// since they are virtually on a circle and wrapping,
    /// everything depends on where you start from.
    ///
    /// This is why there's a start parameter.
    ///
    /// # Examples
    /// ```
    /// use conflidb::CKey;
    ///
    /// let start = CKey::from(0.7);
    /// let k1 = CKey::from(0.2);
    /// let k2 = CKey::from(0.4);
    /// let k3 = CKey::from(0.3);
    /// let k4 = CKey::from(0.9);
    /// let mut sorted = vec![k1, k2, k3, k4];
    /// CKey::sort(&mut sorted, start);
    /// assert_eq!(4, sorted.len());
    /// assert_eq!("0.900000000", format!("{}", sorted[0]));
    /// assert_eq!("0.200000000", format!("{}", sorted[1]));
    /// assert_eq!("0.300000000", format!("{}", sorted[2]));
    /// assert_eq!("0.400000000", format!("{}", sorted[3]));
    /// ```
    pub fn sort(v: &mut Vec<CKey>, start: CKey) {
        v.sort_by(|a, b| {
            // So here, the logic is to consider that everything is
            // "normalized" so that the start is "key 0" and then we
            // look at the order *after* this starting point.
            //
            // In practice, self is lower than other if self is between
            // start and other.
            //
            // And self is greater than other if other is between start
            // and self.
            if *a == *b {
                Ordering::Equal
            } else if a.inside(start, *b) {
                // Other key is after us, considering the "zero" is start.
                Ordering::Less
            } else {
                Ordering::Greater
            }
        });
    }
}

impl From<f64> for CKey {
    /// Convert from an f64, considering the ring goes from 0 to 1.
    ///
    /// # Examples
    /// ```
    /// use conflidb::CKey;
    ///
    /// let k = CKey::from(0.5f64);
    /// assert_eq!("0.500000000", format!("{}", k));
    /// ```
    fn from(f: f64) -> CKey {
        let f_mod_1: f64 = if f < 0.0 {
            1.0 - ((-f).fract())
        } else {
            f.fract()
        };
        let v = (ONE_F64 * f_mod_1) as u64;
        CKey { data: [v, v, v, v] }
    }
}

impl From<u32> for CKey {
    /// Convert from a u32, considering the ring goes from 0 to 2^32.
    ///
    /// # Examples
    /// ```
    /// use conflidb::CKey;
    ///
    /// let k = CKey::from(1073741824u32);
    /// assert_eq!("0.250000000", format!("{}", k));
    /// ```
    fn from(u: u32) -> CKey {
        let v = (u as u64) << 32;
        CKey { data: [v, v, v, v] }
    }
}

impl From<u64> for CKey {
    /// Convert from a u64, considering the ring goes from 0 to 2^64.
    ///
    /// # Examples
    /// ```
    /// use conflidb::CKey;
    ///
    /// let k = CKey::from(1000000000000000000u64);
    /// assert_eq!("0.054210109", format!("{}", k));
    /// ```
    fn from(u: u64) -> CKey {
        CKey { data: [u, u, u, u] }
    }
}

impl From<CKey> for f64 {
    /// Convert to an f64, considering the ring goes from 0 to 1.
    ///
    /// # Examples
    /// ```
    /// use conflidb::CKey;
    /// use std::convert::TryFrom;
    ///
    /// let k = CKey::try_from("123456ffffffffffffffffffffffffffffffffffffffffffffffffffffffffff").unwrap();
    /// assert_eq!("0.071111143", format!("{:0.9}", f64::from(k)));
    /// ```
    fn from(k: CKey) -> f64 {
        (k.data[0] as f64) / ONE_F64
    }
}

impl From<CKey> for u32 {
    /// Convert to a u32, considering the ring goes from 0 to 2^32.
    ///
    /// # Examples
    /// ```
    /// use conflidb::CKey;
    /// use std::convert::TryFrom;
    ///
    /// let k = CKey::try_from("123456ffffffffffffffffffffffffffffffffffffffffffffffffffffffffff").unwrap();
    /// assert_eq!(305420031, u32::from(k));
    /// ```
    fn from(k: CKey) -> u32 {
        (k.data[0] >> 32) as u32
    }
}

impl From<CKey> for u64 {
    /// Convert to a u64, considering the ring goes from 0 to 2^64.
    ///
    /// # Examples
    /// ```
    /// use conflidb::CKey;
    /// use std::convert::TryFrom;
    ///
    /// let k = CKey::try_from("123456ffffffffffffffffffffffffffffffffffffffffffffffffffffffffff").unwrap();
    /// assert_eq!(1311769048983273471, u64::from(k));
    /// ```
    fn from(k: CKey) -> u64 {
        k.data[0]
    }
}

impl std::convert::TryFrom<&str> for CKey {
    type Error = hex::FromHexError;

    /// Try to convert from a &str.
    ///
    /// # Examples
    /// ```
    /// use conflidb::CKey;
    /// use std::convert::TryFrom;
    ///
    /// let k = CKey::try_from("12345678ffffffff01234567fffffffff00123456ffffffff0012345ffffffff").unwrap();
    /// assert_eq!("12345678ffffffff01234567fffffffff00123456ffffffff0012345ffffffff", format!("{:?}", k));
    /// ```
    fn try_from(value: &str) -> Result<CKey, Self::Error> {
        if value.len() != 64 {
            return Err(hex::FromHexError::InvalidStringLength);
        }
        Ok(CKey {
            data: [
                u64::from_str_radix(&value[0..16], 16).unwrap(),
                u64::from_str_radix(&value[16..32], 16).unwrap(),
                u64::from_str_radix(&value[32..48], 16).unwrap(),
                u64::from_str_radix(&value[48..64], 16).unwrap(),
            ],
        })
    }
}

impl std::convert::TryFrom<String> for CKey {
    type Error = hex::FromHexError;

    /// Try to convert from a String.
    ///
    /// # Examples
    /// ```
    /// use conflidb::CKey;
    /// use std::convert::TryFrom;
    ///
    /// let k = CKey::try_from(String::from("12345678ffffffff01234567fffffffff00123456ffffffff0012345ffffffff")).unwrap();
    /// assert_eq!("12345678ffffffff01234567fffffffff00123456ffffffff0012345ffffffff", format!("{:?}", k));
    /// ```
    fn try_from(value: String) -> Result<CKey, Self::Error> {
        Self::try_from(value.as_str())
    }
}

impl From<CKey> for String {
    /// Try to convert to a String.
    ///
    /// The representation it gives is the fmt::Display impl,
    /// which gives a short (not complete/unique) yet readable
    /// representation of the key, as a floating point from 0 to 1.
    ///
    /// # Examples
    /// ```
    /// use conflidb::CKey;
    ///
    /// let k = CKey::from(0.6 as f64);
    /// assert_eq!("0.600000000", String::from(k));
    /// ```
    fn from(k: CKey) -> String {
        format!("{}", k)
    }
}

impl std::ops::Add<CKey> for CKey {
    type Output = Self;

    /// Add another key.
    ///
    /// If the result is outside key space, will loop back,
    /// as in wrapping mode. So the result is always within key space.
    ///
    /// # Examples
    /// ```
    /// use conflidb::CKey;
    ///
    /// let k1 = CKey::from(0.6f64);
    /// let k2 = CKey::from(0.8f64);
    /// let k_sum = k1 + k2;
    /// assert_eq!("0.400000000", String::from(k_sum));
    /// ```
    fn add(self, other: CKey) -> CKey {
        let mut old_carry = 0;
        let mut ret: CKey = CKey::default();
        for i in 0..DATA_U64_SIZE {
            let j = DATA_U64_SIZE - i - 1;
            let (v, new_carry) = match self.data[j].checked_add(other.data[j]) {
                Some(v1) => match v1.checked_add(old_carry) {
                    Some(v2) => (v2, 0),
                    None => ((Wrapping(v1) + Wrapping(old_carry)).0, 1),
                },
                None => (
                    (Wrapping(self.data[j]) + Wrapping(other.data[j]) + Wrapping(old_carry)).0,
                    1,
                ),
            };
            ret.data[j] = v;
            old_carry = new_carry;
        }
        ret
    }
}

impl std::ops::Sub<CKey> for CKey {
    type Output = Self;

    /// Sub another key.
    ///
    /// If the result is outside key space, will loop back,
    /// as in wrapping mode. So the result is always within key space.
    ///
    /// # Examples
    /// ```
    /// use conflidb::CKey;
    ///
    /// let k1 = CKey::from(0.5f64);
    /// let k2 = CKey::from(0.9f64);
    /// let k_diff = k1 - k2;
    /// assert_eq!("0.600000000", String::from(k_diff));
    /// ```
    fn sub(self, other: CKey) -> CKey {
        let mut old_carry = 0;
        let mut ret: CKey = CKey::default();
        for i in 0..DATA_U64_SIZE {
            let j = DATA_U64_SIZE - i - 1;
            let (v, new_carry) = match self.data[j].checked_sub(other.data[j]) {
                Some(v1) => match v1.checked_sub(old_carry) {
                    Some(v2) => (v2, 0),
                    None => ((Wrapping(v1) - Wrapping(old_carry)).0, 1),
                },
                None => (
                    (Wrapping(self.data[j]) - Wrapping(other.data[j]) - Wrapping(old_carry)).0,
                    1,
                ),
            };
            ret.data[j] = v;
            old_carry = new_carry;
        }
        ret
    }
}

impl std::ops::Add<f64> for CKey {
    type Output = Self;

    /// Add an f64.
    ///
    /// The value is first converted to a key, considering key space
    /// goes from 0 to 1.
    ///
    /// # Examples
    /// ```
    /// use conflidb::CKey;
    ///
    /// let k = CKey::from(0.3f64);
    /// assert_eq!("0.700000000", String::from(k + 0.4f64));
    /// ```
    fn add(self, delta: f64) -> CKey {
        let other = CKey::from(delta);
        self + other
    }
}

impl std::ops::Sub<f64> for CKey {
    type Output = Self;

    /// Sub an f64.
    ///
    /// The value is first converted to a key, considering key space
    /// goes from 0 to 1.
    ///
    /// # Examples
    /// ```
    /// use conflidb::CKey;
    ///
    /// let k = CKey::from(0.3f64);
    /// assert_eq!("0.900000000", String::from(k - 0.4f64));
    /// ```
    fn sub(self, delta: f64) -> CKey {
        let other = CKey::from(delta);
        self - other
    }
}

impl std::ops::Add<u32> for CKey {
    type Output = Self;

    /// Add a u32.
    ///
    /// The value is first converted to a key, considering key space
    /// goes from 0 to 2^32.
    ///
    /// # Examples
    /// ```
    /// use conflidb::CKey;
    ///
    /// let k = CKey::from(0.1f64);
    /// assert_eq!("0.100232831", String::from(k + 1_000_000u32))
    /// ```
    fn add(self, delta: u32) -> CKey {
        let other = CKey::from(delta);
        self + other
    }
}

impl std::ops::Sub<u32> for CKey {
    type Output = Self;

    /// Sub a u32.
    ///
    /// The value is first converted to a key, considering key space
    /// goes from 0 to 2^32.
    ///
    /// # Examples
    /// ```
    /// use conflidb::CKey;
    ///
    /// let k = CKey::from(0.1f64);
    /// assert_eq!("0.099767169", String::from(k - 1_000_000u32))
    /// ```
    fn sub(self, delta: u32) -> CKey {
        let other = CKey::from(delta);
        self - other
    }
}

impl std::ops::Add<u64> for CKey {
    type Output = Self;

    /// Add a u64.
    ///
    /// The value is first converted to a key, considering key space
    /// goes from 0 to 2^64.
    ///
    /// # Examples
    /// ```
    /// use conflidb::CKey;
    ///
    /// let k = CKey::from(0.1f64);
    /// assert_eq!("0.100542101", String::from(k + 10_000_000_000_000_000u64))
    /// ```
    fn add(self, delta: u64) -> CKey {
        let other = CKey::from(delta);
        self + other
    }
}

impl std::ops::Sub<u64> for CKey {
    type Output = Self;

    /// Sub a u64.
    ///
    /// The value is first converted to a key, considering key space
    /// goes from 0 to 2^64.
    ///
    /// # Examples
    /// ```
    /// use conflidb::CKey;
    ///
    /// let k = CKey::from(0.1f64);
    /// assert_eq!("0.099457899", String::from(k - 10_000_000_000_000_000u64))
    /// ```
    fn sub(self, delta: u64) -> CKey {
        let other = CKey::from(delta);
        self - other
    }
}

impl std::fmt::Debug for CKey {
    /// Debug-print a key.
    ///
    /// The representation we use is an hex dump, the way you
    /// would write down the 2^256 integer corresponding to the key.
    ///
    /// # Examples
    /// ```
    /// use conflidb::CKey;
    /// use std::convert::TryFrom;
    ///
    /// let k = CKey::try_from("12345678ffffffff01234567fffffffff00123456ffffffff0012345ffffffff").unwrap();
    /// assert_eq!("12345678ffffffff01234567fffffffff00123456ffffffff0012345ffffffff", format!("{:?}", k));
    /// ```
    fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), std::fmt::Error> {
        write!(
            f,
            "{:016x}{:016x}{:016x}{:016x}",
            self.data[0], self.data[1], self.data[2], self.data[3]
        )
    }
}

impl std::fmt::Display for CKey {
    /// Pretty-print a key.
    ///
    /// The representation we use is a 9-digits decimal float number,
    /// 11 chars in total, including a leading "0.".
    ///
    /// The reason for this is -> 1 billion keys is enough to tell
    /// them apart, there *CAN* be collisions, but it should remain rare.
    /// To check for equality, use == operator, do not compare string reprs.
    ///
    /// At the same time, decimals between 0 and 1 are easier to reason
    /// about when debugging, much more than 64 chars hexa dumps.
    ///
    /// # Examples
    /// ```
    /// use conflidb::CKey;
    /// use std::convert::TryFrom;
    ///
    /// let k = CKey::try_from("12345678ffffffff01234567fffffffff00123456ffffffff0012345ffffffff").unwrap();
    /// assert_eq!("0.071111111", format!("{}", k));
    /// ```
    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
        write!(f, "{:0.9}", f64::from(*self))
    }
}

#[cfg(test)]
mod tests {
    use super::CKey;

    #[test]
    fn test_ckey_inside() {
        let k_zero = CKey::new_zero();
        let k_unit = CKey::new_unit();
        let k_half = CKey::new_half();
        let k_last = CKey::new_last();
        let k2 = CKey::from(0.2);
        let k3 = CKey::from(0.3);
        let k9 = CKey::from(0.9);

        assert!(k3.inside(k2, k9));
        assert!(!k2.inside(k3, k9));
        assert!(k2.inside(k9, k3));
        assert!(!k3.inside(k9, k2));
        assert!(k3.inside(k2, k2));
        assert!(k3.inside(k2, k3), "upper bound is included");
        assert!(!k2.inside(k2, k3), "lower bound is excluded");
        assert!(k_unit.inside(k_zero, k2));
        assert!(k_zero.inside(k9, k_zero));
        assert!(k_last.inside(k9, k_zero));
        assert!(k_zero.inside(k_last, k_zero));
        assert!(!k_last.inside(k_last, k_zero));
        assert!(k_half.inside(k3, k9));
    }

    #[test]
    fn test_ckey_next() {
        assert_eq!(
            "0000000000000000000000000000000000000000000000000000000000000001",
            format!("{:?}", CKey::new_zero().next())
        );
        assert_eq!(
            "0000000000000000000000000000000000000000000000000000000000000002",
            format!("{:?}", CKey::new_unit().next())
        );
        assert_eq!(
            "8000000000000000000000000000000000000000000000000000000000000001",
            format!("{:?}", CKey::new_half().next())
        );
        assert_eq!(
            "0000000000000000000000000000000000000000000000000000000000000000",
            format!("{:?}", CKey::new_last().next())
        );
    }

    #[test]
    fn test_ckey_prev() {
        assert_eq!(
            "ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff",
            format!("{:?}", CKey::new_zero().prev())
        );
        assert_eq!(
            "0000000000000000000000000000000000000000000000000000000000000000",
            format!("{:?}", CKey::new_unit().prev())
        );
        assert_eq!(
            "7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff",
            format!("{:?}", CKey::new_half().prev())
        );
        assert_eq!(
            "fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe",
            format!("{:?}", CKey::new_last().prev())
        );
    }

    #[test]
    fn test_fmt_display() {
        assert_eq!("0.000000000", format!("{}", CKey::new_zero()));
        assert_eq!("0.000000000", format!("{}", CKey::new_unit()));
        assert_eq!("0.500000000", format!("{}", CKey::new_half()));
        assert_eq!("1.000000000", format!("{}", CKey::new_last()));
    }

    #[test]
    fn test_ckey_add() {
        assert_eq!(
            "0.300000000",
            format!("{}", CKey::from(0.1) + CKey::from(0.2))
        );
        assert_eq!(
            "0.000000000",
            format!("{}", CKey::from(0.5) + CKey::from(0.5))
        );
        assert_eq!(
            "0.100000000",
            format!("{}", CKey::from(0.8) + CKey::from(0.3))
        );
        assert_eq!(
            "0.300000000",
            format!("{}", CKey::from(1.1) + CKey::from(0.2))
        );
        assert_eq!(
            "0.400000000",
            format!("{}", CKey::from(-0.1) + CKey::from(0.5))
        );
    }

    #[test]
    fn test_ckey_sub() {
        assert_eq!(
            "0.300000000",
            format!("{}", CKey::from(0.4) - CKey::from(0.1))
        );
        assert_eq!(
            "0.000000000",
            format!("{}", CKey::from(0.9) - CKey::from(0.9))
        );
        assert_eq!(
            "0.900000000",
            format!("{}", CKey::from(0.2) - CKey::from(0.3))
        );
        assert_eq!(
            "0.800000000",
            format!("{}", CKey::from(1.1) - CKey::from(1.3))
        );
        assert_eq!(
            "0.900000000",
            format!("{}", CKey::from(0.2) - CKey::from(-0.7))
        );
    }

    #[test]
    fn test_ckey_sort() {
        let k_zero = CKey::new_zero();
        let k_unit = CKey::new_unit();
        let k_half = CKey::new_half();
        let k_last = CKey::new_last();
        let k2 = CKey::from(0.2);
        let k3 = CKey::from(0.3);
        let k9 = CKey::from(0.9);

        let mut sorted = vec![k2, k9, k3, k_half, k_unit, k_last, k_unit, k_zero];
        CKey::sort(&mut sorted, k3);
        assert_eq!(8, sorted.len());
        assert_eq!(k_half, sorted[0]);
        assert_eq!(k9, sorted[1]);
        assert_eq!(k_last, sorted[2]);
        assert_eq!(k_zero, sorted[3]);
        assert_eq!(k_unit, sorted[4]);
        assert_eq!(k_unit, sorted[5]);
        assert_eq!(k2, sorted[6]);
        assert_eq!(k3, sorted[7]);
    }
}