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::*;
use std::rc::Rc;
use std::cell::RefCell;
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
#[derive(Clone)]
pub struct Group{
pub key: AccountPK,
pub transactions: Rc<RefCell<Vec<Transaction>>>
}
impl Iterator for Group {
type Item = Transaction;
#[inline]
fn next(&mut self) -> Option<Self::Item> {
self.transactions.borrow_mut().pop()
}
}
impl Group {
pub fn new(key: AccountPK,transactions: Vec<Transaction>) -> Self {
Self{
key,
transactions:Rc::new(RefCell::new(transactions))
}
}
pub fn is_empty(&self) -> bool {
self.transactions.borrow().is_empty()
}
}
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(),
}
}
}
impl<'a> Iterator for PoolGroupIterator<'a> {
type Item = Group;
fn next(&mut self) -> Option<Self::Item> {
let Self {pool, sorted_groups} = self;
let next_group_key = pool.keys().next().cloned();
match next_group_key {
Some(key) => {
let mut group = pool.remove(&key.clone()).expect("Just checked existence");
group.sort_by_key(|a| std::cmp::Reverse(*a));
sorted_groups.push_front(Group::new(key.clone(), group));
Some(sorted_groups.front().expect("Just pushed").clone())
}
None => {
loop {
match sorted_groups.pop_front() {
None => break None, // All transactions were processed.
Some(sorted_group) => if sorted_group.is_empty() {
continue;
} else {
sorted_groups.push_back(sorted_group);
break Some(sorted_groups.back_mut().expect("Just pushed").clone());
}
}
}
}
}
}
}
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]);
for mut group in PoolGroupIterator::new(&mut pool) {
loop {
match group.next() {
Some(t) => if validate(t) {
println!("{}", t);
break;
}
None => {
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.