creature_feature 0.2.0

use crate::feature_from::FeatureFrom;
use crate::gap_gram::GapPair;
use fxhash::FxHasher64;
use nohash_hasher::IsEnabled;
#[cfg(feature = "serde1")]
use serde::{Deserialize, Serialize};
use std::cmp::Reverse;
use std::hash::{Hash, Hasher};
use std::iter::FromIterator;

///[`HashedAs<U>`] can encode any feature that's hashable. Here, `U` can be `u8`, `u16`, `u32` or `u64`. Hash collisions are usually not a big problem for most uses (especially with `HashedAs<u64>`)
///`HashedAs` can really speed things up where you need to do a lot of equality comparisons and your feature is longer that `U`. It can also provide more balanced nodes in a BTree. Currently uses `FxHash`.
/// # Example: Succinctly implementing MinHash
/// ```
///use creature_feature::ftzrs::bigram;
///use creature_feature::traits::*;
///use creature_feature::HashedAs;
///use std::cmp::Reverse;
///use std::collections::BinaryHeap;
///
/// // jaccard similarity is very fast on two sorted vecs, left as an exercise
///fn min_hash(s: &str, n: usize) -> Vec<HashedAs<u64>> {
///
///    let heap: BinaryHeap<Reverse<HashedAs<u64>>> = bigram().featurize(s);
///
///    heap.into_sorted_vec() // ascending in `Reverse`, i.e. largest hash first
///        .into_iter()
///        .rev()             // smallest hashes first
///        .map(|r| r.0)
///        .take(n)
///        .collect()
///}
///let signature = min_hash("the quick brown fox", 4);
///assert_eq!(signature.len(), 4);
/// ```
#[derive(Hash, Copy, Clone, PartialEq, Ord, PartialOrd, Eq, Debug)]
#[cfg_attr(feature = "serde1", derive(Serialize, Deserialize))]
pub struct HashedAs<T>(pub(crate) T);

type TheHasher = FxHasher64;

macro_rules! impl_hashed {
    ($u_type:ty) => {
        impl<A: Hash> FromIterator<A> for HashedAs<$u_type> {
            fn from_iter<T>(iter: T) -> Self
            where
                T: IntoIterator<Item = A>,
            {
                let mut h = TheHasher::default();
                for t in iter.into_iter() {
                    t.hash(&mut h);
                }
                HashedAs(h.finish() as $u_type)
            }
        }
        impl<T: Hash> FeatureFrom<T> for HashedAs<$u_type> {
            fn from(token_group: T) -> Self {
                let mut h = TheHasher::default();
                token_group.hash(&mut h);
                HashedAs(h.finish() as $u_type)
            }
        }
        impl<T: Hash, V: Hash> From<GapPair<T, V>> for HashedAs<$u_type> {
            fn from(x: GapPair<T, V>) -> Self {
                let mut h = TheHasher::default();
                x.0.hash(&mut h);
                [x.2, 4567].hash(&mut h);
                x.1.hash(&mut h);
                HashedAs(h.finish() as $u_type)
            }
        }
        impl From<HashedAs<$u_type>> for $u_type {
            fn from(x: HashedAs<$u_type>) -> $u_type {
                x.0
            }
        }
        impl IsEnabled for HashedAs<$u_type> {}
    };
}

impl<A, B> FeatureFrom<A> for Reverse<HashedAs<B>>
where
    HashedAs<B>: FeatureFrom<A>,
{
    fn from(token_group: A) -> Self {
        Reverse(FeatureFrom::from(token_group))
    }
}
impl_hashed!(u8);
impl_hashed!(u16);
impl_hashed!(u32);
impl_hashed!(u64);

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

    /// Regression: `From<GapPair<T, V>>` used to hash the first component twice
    /// and never hash the second, so pairs differing only in the second
    /// component collided.
    #[test]
    fn gap_pair_hash_uses_both_components() {
        let a: HashedAs<u64> = From::from(GapPair("ab", "cd", 1));
        let b: HashedAs<u64> = From::from(GapPair("ab", "zz", 1));
        assert_ne!(a, b);
        // and it must still be deterministic
        let a2: HashedAs<u64> = From::from(GapPair("ab", "cd", 1));
        assert_eq!(a, a2);
    }
}