topset/
lib.rs

1//! # Top N set
2//!
3//! This crate provides a _topset_ which selects a given number of greatest items.
4//! The criterium used to sort the items could be specified as a closure.
5//! It is based internally on a binary heap with a fixed size.
6//!
7//! The struct [`TopSet`] could be used directly or through the trait [`TopSetReducing`]
8//! which automatically extend the iterator trait.
9//!
10//! ```
11//! use topset::*;
12//!     let items = vec![4, 5, 8, 3, 2, 1, 4, 7, 9, 8];
13//!
14//!     // getting the four greatest integers (repeating allowed)
15//!     items.iter().cloned()
16//!             .topset(4, i32::gt)
17//!             .into_iter()
18//!             .for_each(|x| eprintln!("in the top 4: {}", x));
19//!
20//!     // getting the four smallest integers
21//!     // (we just need to reverse the comparison function)
22//!     items.topset(4, i32::lt)
23//!             .into_iter()
24//!             .for_each(|x| eprintln!("in the last 4: {}", x));
25//! ```
26//! will produce (possibly in an different order):
27//! ```text
28//! in the top 4: 7
29//! in the top 4: 8
30//! in the top 4: 9
31//! in the top 4: 8
32//! in the last 4: 4
33//! in the last 4: 2
34//! in the last 4: 3
35//! in the last 4: 1
36//! ```
37
38mod heap;
39pub mod iter;
40
41pub use iter::TopSetReducing;
42
43/// A top N set of items.
44///
45/// This set contains no more than N items.
46/// When this limit is reached, the smallest (according to
47/// the specified comparison) is thrown.
48///
49/// Comparing two elements is done by a duel, resolved by a provided closure:
50/// if `true` is returned, the first item wins, if `false` the second.
51///
52/// By the way, using [`PartialOrd::gt`]
53/// will select the top elements and [`PartialOrd::lt`]
54/// will select the lowest.
55///
56/// Of course, any closure could be used but it should satisfy the transitivity.
57/// In other words, if `a` beats `b` and `b` beats `c` then `a` should beat `c` too.
58/// If it is not the case, the results are unpredictable.
59///
60#[derive(Clone)]
61pub struct TopSet<X,C>
62    where C: Fn(&X,&X) -> bool
63{
64    heap: Vec<X>, // a heap with the greatest at the end
65    count: usize,
66    beat:  C
67}
68
69
70#[cfg(test)]
71#[test]
72fn dummy_tests_just_for_coverage() {
73    let top = TopSet::new(10, u32::gt);
74    let _ = (&top).into_iter();
75    let _ = top.clone().into_iter();
76    dbg!(&top);
77}
topset/lib.rs

topset/
lib.rs
