Struct TopSet 

pub struct TopSet<X, C>
where
    C: Fn(&X, &X) -> bool,
{ /* private fields */ }

A top N set of items.

This set contains no more than N items. When this limit is reached, the smallest (according to the specified comparison) is thrown.

Comparing two elements is done by a duel, resolved by a provided closure: if true is returned, the first item wins, if false the second.

By the way, using PartialOrd::gt will select the top elements and PartialOrd::lt will select the lowest.

Of course, any closure could be used but it should satisfy the transitivity. In other words, if a beats b and b beats c then a should beat c too. If it is not the case, the results are unpredictable.

Implementations

impl<X, C> TopSet<X, C>

where C: Fn(&X, &X) -> bool,

pub fn new(n: usize, beat: C) -> Self

Creates a new top set with a selecting closure.

The size corresponds to the maximum number of items allowed in the top set.

The function C is the challenge to decide if an element beats another one and so takes its place. It should corresponds to a total ordering.

If the first one beats the second one then true should be returned and if `false’ corresponds to the case when the second item beats the first one. This function should always returns the same result when dealing with the same items or results are unpredictable.

Example

Collecting the 5 greatest integers is performed by using a topset with n = 5 and beat = i32::gt.

let mut topset = TopSet::new(5, i32::gt);

Examples found in repository

examples/lowest_cost.rs (line 5)

pub fn main()
{
    let mut top = TopSet::<f32,_>::new(5, f32::lt);
    // top.extend(vec![81.5, 4.5, 4., 1., 45., 22., 11.]);
    //  top.extend(vec![81.5, 4.5, 4., 1., 45., 22., 11.]);
    vec![81.5, 4.5, 4., 1., 45., 22., 11.,93.].into_iter().for_each(|u| { dbg!(&top); dbg!(&u); dbg!(top.insert(u)); dbg!(&top); });
    vec![81.5, 4.5, 4., 1., 45., 22., 11.].into_iter().for_each(|u| { dbg!(&top); dbg!(&u); dbg!(top.insert(u));dbg!(&top); });
    assert_eq![ top.pop(), Some(4.5) ];
    assert_eq![ top.pop(), Some(4.) ];
    assert_eq![ top.pop(), Some(4.) ];
    assert_eq![ top.pop(), Some(1.) ];
    assert_eq![ top.pop(), Some(1.) ];
    assert_eq![ top.pop(), None ];
}

pub fn with_init<I: IntoIterator<Item = X>>(n: usize, beat: C, init: I) -> Self

Creates a new top set with a selecting closure and an initial set of items.

If the initial set contains more than n elements, only the n greatest ones (according to beat challenging function) are stored.

Example

let mut topset = TopSet::with_init(2, u32::gt, vec![7,5,6,9,4,2,3]);
assert_eq!( topset.pop(), Some(7));
assert_eq!( topset.pop(), Some(9));
assert_eq!( topset.pop(), None);

pub fn is_empty(&self) -> bool

Check if the top set is empty

Example

let mut topset = TopSet::new(2, u32::gt);
assert!( topset.is_empty() );
topset.extend( vec![7,5,6,9,4,2,3] );
assert!( ! topset.is_empty() );

pub fn len(&self) -> usize

Get the number of stored items.

It never exceeds the predefined capacity (the capacity does not grow by itself, only by calling Self::resize).

Example

let mut topset = TopSet::with_init(2, u32::gt, vec![7,5,6,9,4,2,3] );
assert_eq!( topset.len(), 2 );
topset.pop();
assert_eq!( topset.len(), 1 );

pub fn capacity(&self) -> usize

Get the capacity of this top set

The capacity limits the number of elements to keep. This capacity could only change by calling [resize].

Example

let mut topset = TopSet::new(4, u32::gt);
assert_eq!( topset.capacity(), 4 );
assert_eq!( topset.len(), 0 );

pub fn peek(&self) -> Option<&X>

Read access to the lowest item of the top set

Notice that it actually returned the lowest one and so all the others are better (or equal) this one.

To access to this lowest element and removing it, consider Self::pop.

Example

let mut topset = TopSet::with_init(2, u32::gt, vec![7,5,6,9,4,2,3] );
assert_eq!( topset.peek(), Some(&7) );
assert_eq!( topset.pop(), Some(7) );
assert_eq!( topset.peek(), Some(&9) );

pub fn is_candidate(&self, x: &X) -> bool

Checks if an item will be inserted or not

If it true is returned, it means that a call to Self::insert will actually insert the candidate. If false, then the insertion will be a non-op.

Note that in any case the insertion is not done. See Self::insert to perform the test and the insertion in one time.

Example

// this topset contains { 7, 9 }
let topset = TopSet::with_init(2, u32::gt, vec![7,5,6,9,4,2,3] );
assert!( topset.is_candidate(&10) );
assert!( topset.is_candidate(&8) );
assert!( ! topset.is_candidate(&7) );
assert!( ! topset.is_candidate(&6) );

pub fn iter(&self) -> impl Iterator<Item = &X>

Iterate over all the top selected items.

The iterator is not sorted. A sorted iteration could be obtained by iterative call to Self::pop or by using Self::into_iter_sorted.

To get a vector with all elements, instead of using this iterator, consider Self::into_vec.

Example

// this topset contains { 7, 9 }
let topset = TopSet::with_init(2, u32::gt, vec![7,5,6,9,4,2,3] );
let elts = topset.iter().cloned().collect::<Vec<_>>();

pub fn into_vec(self) -> Vec<X>

Gets all the top set elements in a vector.

This vector is not sorted. See Self::into_sorted_vec if a sorted result is expected.

Example

// this topset contains { 7, 9 }
let topset = TopSet::with_init(2, u32::gt, vec![7,5,6,9,4,2,3] );
let elts = topset.into_vec();

pub fn insert(&mut self, x: X) -> Option<X>

Insert a new item.

If the top set is not filled (i.e. its length is less than its capacity), the item is simply added and None is returned.

If there is no more room, then one item should be rejected:

• if the new item is better than some already stored ones, it is added and the removed item is returned
• if the new item is worse than all the stored ones, it is returned

Example

let mut topset = TopSet::new(2, u32::gt);
assert_eq!( topset.insert(7), None);
assert_eq!( topset.insert(8), None);
assert_eq!( topset.insert(9), Some(7));
assert_eq!( topset.insert(6), Some(6));

Examples found in repository

examples/lowest_cost.rs (line 8)

pub fn main()
{
    let mut top = TopSet::<f32,_>::new(5, f32::lt);
    // top.extend(vec![81.5, 4.5, 4., 1., 45., 22., 11.]);
    //  top.extend(vec![81.5, 4.5, 4., 1., 45., 22., 11.]);
    vec![81.5, 4.5, 4., 1., 45., 22., 11.,93.].into_iter().for_each(|u| { dbg!(&top); dbg!(&u); dbg!(top.insert(u)); dbg!(&top); });
    vec![81.5, 4.5, 4., 1., 45., 22., 11.].into_iter().for_each(|u| { dbg!(&top); dbg!(&u); dbg!(top.insert(u));dbg!(&top); });
    assert_eq![ top.pop(), Some(4.5) ];
    assert_eq![ top.pop(), Some(4.) ];
    assert_eq![ top.pop(), Some(4.) ];
    assert_eq![ top.pop(), Some(1.) ];
    assert_eq![ top.pop(), Some(1.) ];
    assert_eq![ top.pop(), None ];
}

pub fn into_iter_sorted(self) -> IntoIterSorted<X, C>

Converts this topset into a sorted iterator

Notice that the lowest item of the top set is the first one. The greatest item is the last one.

Example

// this topset contains { 7, 9 }
let topset = TopSet::with_init(2, u32::gt, vec![7,5,6,9,4,2,3] );
let mut iter = topset.into_iter_sorted();
assert_eq!( iter.next(), Some(7));
assert_eq!( iter.next(), Some(9));
assert_eq!( iter.next(), None);

pub fn into_sorted_vec(self) -> Vec<X>

where X: PartialEq,

Returns the topset in a sorted vector.

The first element of the vector is the lowest item of the top set and the last one is the greatest one.

Example

// this topset contains { 7, 9 }
let topset = TopSet::with_init(3, u32::gt, vec![1,2,7,4,7,5,6,9,4,2,3] );
assert_eq!( topset.into_sorted_vec(), vec![7,7,9]);

pub fn drain(&mut self) -> Drain<'_, X>

Clears the binary heap, returning an iterator over the removed elements in arbitrary order. If the iterator is dropped before being fully consumed, it drops the remaining elements in arbitrary order.

The returned iterator keeps a mutable borrow on the heap to optimize its implementation.

Example

let mut topset = TopSet::with_init(4, u32::gt, vec![7,5,6,9,4,2,3] );
let _ = topset.drain();
assert! (topset.is_empty());

pub fn resize(&mut self, n: usize)

Resize the top set

If the size decreases, then the lowest items are removed. If the size increases, nothing else happens but there is still more room for next insertions.

Example

let mut topset = TopSet::with_init(4, u32::gt, vec![7,5,6,9,4,2,3] );

// the topset contains { 7, 5, 6, 9 }
assert_eq! (topset.peek(), Some(&5));

topset.resize(2);
// the topset contains { 7, 9 }
assert_eq! (topset.peek(), Some(&7));

// try to add 1 but no more room left
assert_eq!( topset.insert(1), Some(1) );

topset.resize(3); // grows by one
assert_eq!( topset.insert(1), None ); // one room left
assert_eq!( topset.insert(2), Some(1) ); // but now, is full
// at this point, the topset contains { 7, 9, 2 }

pub fn pop(&mut self) -> Option<X>

Pop the lowest item of the top set

Remove and return the lowest item of the top set. After this call, there is one more room for a item.

This method is the only way to get the top elements in a sorted way (from the lowest to the best). Resize the top set

If the size decreases, then the lowest items are removed. If the size increases, nothing else happens but there is still more room for next insertions.

Example

let mut topset = TopSet::with_init(2, u32::gt, vec![7,5,6,9,4,2,3] );

assert_eq! (topset.pop(), Some(7));
assert_eq! (topset.pop(), Some(9));
assert_eq! (topset.pop(), None);

Examples found in repository

examples/lowest_cost.rs (line 10)

pub fn main()
{
    let mut top = TopSet::<f32,_>::new(5, f32::lt);
    // top.extend(vec![81.5, 4.5, 4., 1., 45., 22., 11.]);
    //  top.extend(vec![81.5, 4.5, 4., 1., 45., 22., 11.]);
    vec![81.5, 4.5, 4., 1., 45., 22., 11.,93.].into_iter().for_each(|u| { dbg!(&top); dbg!(&u); dbg!(top.insert(u)); dbg!(&top); });
    vec![81.5, 4.5, 4., 1., 45., 22., 11.].into_iter().for_each(|u| { dbg!(&top); dbg!(&u); dbg!(top.insert(u));dbg!(&top); });
    assert_eq![ top.pop(), Some(4.5) ];
    assert_eq![ top.pop(), Some(4.) ];
    assert_eq![ top.pop(), Some(4.) ];
    assert_eq![ top.pop(), Some(1.) ];
    assert_eq![ top.pop(), Some(1.) ];
    assert_eq![ top.pop(), None ];
}

pub fn clear(&mut self)

Removes all the elements in the top set

Example

let mut topset = TopSet::with_init(2, u32::gt, vec![7,5,6,9,4,2,3] );

assert_eq! (topset.len(), 2);
topset.clear();
assert_eq!( topset.len(), 0)

pub fn beat(&self, a: &X, b: &X) -> bool

Checks if an element beats the other.

It does not related to the current elements in the topset but refers only to the comparing function (the beat).

Example

let mut topset = TopSet::with_init(2, u32::gt, vec![7,5,6,9,4,2,3] );

assert! ( topset.beat(&4, &3));
assert! ( ! topset.beat(&4, &7));

Trait Implementations

impl<X: Clone, C> Clone for TopSet<X, C>

where C: Fn(&X, &X) -> bool + Clone,

fn clone(&self) -> TopSet<X, C>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<X, C> Debug for TopSet<X, C>

where X: Debug, C: Fn(&X, &X) -> bool,

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<X, C> Extend<X> for TopSet<X, C>

where C: Fn(&X, &X) -> bool,

fn extend<T: IntoIterator<Item = X>>(&mut self, iter: T)

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<X, C> From<TopSet<X, C>> for IntoIterSorted<X, C>

where C: Fn(&X, &X) -> bool,

fn from(topset: TopSet<X, C>) -> Self

Converts to this type from the input type.

impl<'a, X, C> IntoIterator for &'a TopSet<X, C>

where C: Fn(&X, &X) -> bool,

type Item = &'a X

The type of the elements being iterated over.

type IntoIter = <&'a Vec<X> as IntoIterator>::IntoIter

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<X, C> IntoIterator for TopSet<X, C>

where C: Fn(&X, &X) -> bool,

type Item = X

The type of the elements being iterated over.

type IntoIter = <Vec<X> as IntoIterator>::IntoIter

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.