Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Code shared from the Rust Playground
use std::collections::*;
pub type AccountPK = u64;
pub type Transaction = u64;
pub type TxPool = HashMap<AccountPK, Vec<Transaction>>;
// Compiler will optimize this wrapper out.
// Using Rc+RefCell to workaround GATs https://users.rust-lang.org/t/unconstrained-lifetime-parameter-for-impl/27995/4
pub struct Group {
pub key: AccountPK,
pub transactions: Vec<Transaction>,
}
impl Group {
#[inline]
pub fn next(&mut self) -> Option<Transaction> {
self.transactions.pop()
}
}
pub struct PoolGroupIterator<'a> {
pool: &'a mut TxPool,
sorted_groups: LinkedList<Group>,
}
impl<'a> PoolGroupIterator<'a> {
pub fn new(pool: &'a mut TxPool) -> Self {
Self {
pool,
sorted_groups: Default::default(),
}
}
pub fn next(&mut self) -> Option<&mut Group> {
let Self {
pool,
sorted_groups,
} = self;
let next_group_key = pool.keys().next().cloned();
match next_group_key {
Some(key) => {
let mut transactions = pool.remove(&key.clone()).expect("Just checked existence");
transactions.sort_by_key(|a| std::cmp::Reverse(*a));
sorted_groups.push_front(Group {
key: key.clone(),
transactions,
});
Some(sorted_groups.front_mut().expect("Just pushed"))
}
None => {
loop {
match sorted_groups.pop_front() {
None => break None, // All transactions were processed.
Some(sorted_group) => {
if sorted_group.transactions.is_empty() {
continue;
} else {
sorted_groups.push_back(sorted_group);
break Some(sorted_groups.back_mut().expect("Just pushed"));
}
}
}
}
}
}
}
}
// impl<'a> Drop for PoolGroupIterator<'a> {
// fn drop(&mut self) {
// // let Self {pool, sorted_groups} = self;
// // while let Some(sorted_group) = sorted_groups.pop_front() {
// // let Group{key, transactions} = sorted_group;
// // pool.insert(key, Rc::try_unwrap(transactions).expect("Should be the last reference").replace(Vec::new()));
// // }
// }
// }
fn validate(tx: u64) -> bool {
tx % 2 == 1
}
pub fn main() {
let mut pool = HashMap::new();
pool.insert(1, vec![2, 1]);
pool.insert(0, vec![1]);
pool.insert(2, vec![3]);
let mut it = PoolGroupIterator::new(&mut pool);
while let Some(group) = it.next() {
while let Some(t) = group.next() {
if validate(t) {
println!("{}", t);
break;
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.