use crate::segment::Bitfield;
mod selection;
#[cfg(test)]
mod tests;
mod types;
pub use types::{
PickedPiece, PieceInfo, PiecePickStrategy, PiecePickerConfig, PiecePriorityMode,
PieceSelectionStrategy,
};
pub const DEFAULT_ENDGAME_THRESHOLD: usize = 20;
pub struct PiecePicker {
num_pieces: u32,
strategy: PieceSelectionStrategy,
priority_mode: PiecePriorityMode,
frequencies: Vec<u32>,
rarest_order: Vec<u32>,
rarest_cursor: usize,
completed: Bitfield,
allowed: Bitfield,
in_progress: Bitfield,
priorities: Vec<u8>,
priority_pieces: Vec<u32>,
endgame_candidates: Vec<usize>,
completed_allowed_count: usize,
allowed_count: usize,
head_cursor: usize,
tail_cursor: usize,
endgame_threshold: usize,
rng_state: u64,
}
impl PiecePicker {
pub fn new(num_pieces: u32) -> Self {
let n = num_pieces as usize;
Self {
num_pieces,
strategy: PieceSelectionStrategy::RarestFirst,
priority_mode: PiecePriorityMode::RarestFirst,
frequencies: vec![0; n],
rarest_order: (0..num_pieces).collect(),
rarest_cursor: 0,
completed: Bitfield::new(n),
allowed: Bitfield::all_set(n),
in_progress: Bitfield::new(n),
priorities: vec![0; n],
priority_pieces: Vec::new(),
endgame_candidates: Vec::new(),
completed_allowed_count: 0,
allowed_count: n,
head_cursor: 0,
tail_cursor: n,
endgame_threshold: DEFAULT_ENDGAME_THRESHOLD,
rng_state: Self::seed(),
}
}
fn seed() -> u64 {
use std::hash::{BuildHasher, Hasher};
let s = std::collections::hash_map::RandomState::new()
.build_hasher()
.finish();
s | 1
}
fn next_rand(&mut self) -> u64 {
let mut x = self.rng_state;
x ^= x >> 12;
x ^= x << 25;
x ^= x >> 27;
self.rng_state = x;
x.wrapping_mul(0x2545_F491_4F6C_DD1D)
}
pub fn set_strategy(&mut self, strategy: PieceSelectionStrategy) {
self.strategy = strategy;
}
pub fn set_priority_mode(&mut self, mode: PiecePriorityMode) {
self.priority_mode = mode;
}
pub fn set_priority_pieces(&mut self, mut pieces: Vec<u32>) {
pieces.retain(|&piece| piece < self.num_pieces);
pieces.sort_unstable();
pieces.dedup();
for index in (1..pieces.len()).rev() {
let swap = (self.next_rand() % (index as u64 + 1)) as usize;
pieces.swap(index, swap);
}
self.priority_pieces = pieces;
}
pub fn priority_pieces(&self) -> &[u32] {
&self.priority_pieces
}
pub fn set_allowed_pieces(&mut self, pieces: &[u32]) {
self.allowed.clear_all();
for &piece in pieces {
self.allowed.set(piece as usize);
}
self.allowed_count = (0..self.num_pieces as usize)
.filter(|&i| self.allowed.test(i))
.count();
self.completed_allowed_count = (0..self.num_pieces as usize)
.filter(|&i| self.completed.test(i) && self.allowed.test(i))
.count();
self.head_cursor = 0;
self.tail_cursor = self.num_pieces as usize;
self.rarest_cursor = 0;
self.refresh_endgame_candidates();
}
pub fn is_allowed(&self, index: u32) -> bool {
self.allowed.test(index as usize)
}
pub fn allowed_count(&self) -> usize {
self.allowed_count
}
pub fn set_endgame_threshold(&mut self, threshold: usize) {
self.endgame_threshold = threshold;
self.refresh_endgame_candidates();
}
pub fn set_priority(&mut self, index: u32, priority: u8) {
let i = index as usize;
if i < self.num_pieces as usize {
self.priorities[i] = priority;
}
}
pub fn select(&mut self, bitfield: &[u8], nbits: usize) -> Option<u32> {
self.pick_internal(Some(bitfield), nbits, false)
}
pub fn pick_next(&mut self) -> Option<u32> {
let allow_in_progress = self.endgame_active();
let n = self.num_pieces as usize;
self.pick_internal(None, n, allow_in_progress)
}
pub fn pick_next_without_endgame(&mut self) -> Option<u32> {
let n = self.num_pieces as usize;
self.pick_internal(None, n, false)
}
pub fn endgame_active(&self) -> bool {
let remaining = self.remaining_count();
remaining > 0 && remaining <= self.endgame_threshold
}
fn refresh_endgame_candidates(&mut self) {
self.endgame_candidates.clear();
if !self.endgame_active() {
return;
}
for i in 0..self.num_pieces as usize {
if self.allowed.test(i) && !self.completed.test(i) {
self.endgame_candidates.push(i);
}
}
}
pub fn endgame_candidates(&self) -> &[usize] {
&self.endgame_candidates
}
pub fn set_frequencies_from_peers(&mut self, freqs: &[usize]) {
self.frequencies.fill(0);
let len = freqs.len().min(self.frequencies.len());
for (dst, src) in self.frequencies.iter_mut().zip(freqs.iter()).take(len) {
*dst = *src as u32;
}
self.rarest_order.sort_unstable_by_key(|&index| {
let index = index as usize;
(self.frequencies[index], index)
});
self.rarest_cursor = 0;
}
pub fn pieces_iter(&self) -> impl Iterator<Item = PieceInfo> + '_ {
let n = self.num_pieces as usize;
(0..n).map(move |i| PieceInfo {
index: i as u32,
frequency: self.frequencies[i],
is_completed: self.completed.test(i),
completed: self.completed.test(i),
in_progress: self.in_progress.test(i),
priority: self.priorities[i],
})
}
pub fn get_piece_info(&self, index: u32) -> Option<PieceInfo> {
let i = index as usize;
if i >= self.num_pieces as usize {
return None;
}
Some(PieceInfo {
index,
frequency: self.frequencies[i],
is_completed: self.completed.test(i),
completed: self.completed.test(i),
in_progress: self.in_progress.test(i),
priority: self.priorities[i],
})
}
pub fn priority_mode(&self) -> PiecePriorityMode {
self.priority_mode
}
pub fn remaining_count(&self) -> usize {
self.allowed_count()
.saturating_sub(self.completed_allowed_count)
}
pub fn mark_completed(&mut self, index: u32) {
let i = index as usize;
debug_assert!(
i < self.num_pieces as usize,
"mark_completed: index out of range"
);
if i >= self.num_pieces as usize {
return;
}
if !self.completed.test(i) {
self.completed.set(i);
if self.allowed.test(i) {
self.completed_allowed_count += 1;
}
}
self.in_progress.clear(i);
self.refresh_endgame_candidates();
}
pub fn mark_in_progress(&mut self, index: u32, in_progress: bool) {
let i = index as usize;
debug_assert!(
i < self.num_pieces as usize,
"mark_in_progress: index out of range"
);
if i >= self.num_pieces as usize {
return;
}
if in_progress {
self.in_progress.set(i);
} else {
self.in_progress.clear(i);
}
if !in_progress {
self.reopen(i);
}
}
pub fn is_in_progress(&self, index: u32) -> bool {
let i = index as usize;
i < self.num_pieces as usize && self.in_progress.test(i)
}
pub fn is_completed(&self, index: u32) -> bool {
let i = index as usize;
i < self.num_pieces as usize && self.completed.test(i)
}
pub fn export_bitfield(&self) -> Vec<u8> {
self.completed.as_bytes().to_vec()
}
pub fn is_complete(&self) -> bool {
self.completed_allowed_count == self.allowed_count()
}
}