Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Add WeightedIndexTree to rand_distr #1372

Merged
merged 20 commits into from
Feb 8, 2024
Merged

Add WeightedIndexTree to rand_distr #1372

Changes from 1 commit
Commits
Show all changes
20 commits
Select commit Hold shift + click to select a range
a7aa746
Add WeightedIndexTree to rand_distr
Jan 10, 2024
191a1fe
revert
Jan 10, 2024
3672f22
revert2
Jan 10, 2024
b20ac94
revert3
Jan 10, 2024
f90661e
d
Jan 10, 2024
8188aa9
a
Jan 10, 2024
42e2123
a
Jan 10, 2024
0eb69d4
a
Jan 10, 2024
b00c785
a
Jan 10, 2024
75c150f
a
Jan 10, 2024
30866d6
Make it safe against overflows
Jan 12, 2024
3b6229e
Checked adds and docs
Jan 12, 2024
45a03ac
a
Jan 12, 2024
bca832d
x
Jan 12, 2024
7a0e234
a
Jan 12, 2024
a23e842
Address comments
Feb 7, 2024
c8e5e35
more comments
Feb 7, 2024
689ac48
a
Feb 8, 2024
57158b7
c
Feb 8, 2024
e459645
a
Feb 8, 2024
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
Prev Previous commit
Next Next commit
a
  • Loading branch information
xmakro committed Feb 8, 2024
commit 689ac4875f83d6eb36f0452d63fdbd5a9d429697
31 changes: 13 additions & 18 deletions rand_distr/src/weighted_tree.rs
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -88,11 +88,15 @@ use serde::{Deserialize, Serialize};
serde(bound(deserialize = "W: Deserialize<'de>, W::Sampler: Deserialize<'de>"))
)]
#[derive(Clone, Default, Debug, PartialEq)]
pub struct WeightedTreeIndex<W: SampleUniform> {
pub struct WeightedTreeIndex<
W: Clone + PartialEq + PartialOrd + SampleUniform + SubAssign<W> + Weight,
> {
subtotals: Vec<W>,
}

impl<W: Clone + PartialEq + PartialOrd + SampleUniform + Weight> WeightedTreeIndex<W> {
impl<W: Clone + PartialEq + PartialOrd + SampleUniform + SubAssign<W> + Weight>
WeightedTreeIndex<W>
{
/// Creates a new [`WeightedTreeIndex`] from a slice of weights.
pub fn new<I>(weights: I) -> Result<Self, WeightedError>
where
Expand Down Expand Up @@ -138,28 +142,22 @@ impl<W: Clone + PartialEq + PartialOrd + SampleUniform + Weight> WeightedTreeInd
}

/// Gets the weight at an index.
pub fn get(&self, index: usize) -> W
where
W: for<'a> SubAssign<&'a W>,
{
pub fn get(&self, index: usize) -> W {
let left_index = 2 * index + 1;
let right_index = 2 * index + 2;
let mut w = self.subtotals[index].clone();
w -= &self.subtotal(left_index);
w -= &self.subtotal(right_index);
w -= self.subtotal(left_index);
w -= self.subtotal(right_index);
w
}

/// Removes the last weight and returns it, or [`None`] if it is empty.
pub fn pop(&mut self) -> Option<W>
where
W: for<'a> SubAssign<&'a W>,
{
pub fn pop(&mut self) -> Option<W> {
self.subtotals.pop().map(|weight| {
let mut index = self.len();
while index != 0 {
index = (index - 1) / 2;
self.subtotals[index] -= &weight;
self.subtotals[index] -= weight.clone();
}
weight
})
Expand All @@ -186,15 +184,12 @@ impl<W: Clone + PartialEq + PartialOrd + SampleUniform + Weight> WeightedTreeInd
}

/// Updates the weight at an index.
pub fn update(&mut self, mut index: usize, weight: W) -> Result<(), WeightedError>
where
W: for<'a> SubAssign<&'a W>,
{
pub fn update(&mut self, mut index: usize, weight: W) -> Result<(), WeightedError> {
if weight < W::ZERO {
return Err(WeightedError::InvalidWeight);
}
let mut difference = weight;
difference -= &self.get(index);
difference -= self.get(index);
if difference == W::ZERO {
return Ok(());
}
Expand Down
Loading