weighted_list/weighted_list.rs
1use std::{
2 fmt,
3 iter,
4 ops::*,
5};
6
7use bon::bon;
8use itertools::Itertools;
9use num_traits as nums;
10use rand::{
11 prelude::*,
12 seq::SliceRandom,
13};
14
15use crate::root::*;
16use crate::WeightedItem;
17
18
19/// A shorthand for [`WeightedList`].
20pub type WList<V,W> = WeightedList<V,W>;
21
22
23/// A homogeneous list of weighted items with values of type `V` and weights of numerical type `W`.
24///
25/// Near-identical to `Vec<T>`, but stores `WeightedItem<V,W>` objects instead. You can think of it like a `Vec<WeightedItem<V,W>>`.
26///
27/// # Usage
28///
29/// ```
30/// # use weighted_list::*;
31/// let wl: WeightedList<String, u32> = wlist![
32/// (2, "sup".to_string()),
33/// (3, "nova".to_string()),
34/// (5, "shard".to_string()),
35/// ];
36///
37/// for item in &wl {
38/// println!("{item}");
39/// }
40///
41/// if let Some(result) = wl.select_random_value(&mut rand::rng()) {
42/// println!("{result}");
43/// }
44/// ```
45///
46/// # Indexing
47///
48/// `WeightedList` uses *weighted* indexing; this is the key difference between it and a `Vec`. It's most easily explained with an example:
49///
50/// ```should_panic
51/// # use weighted_list::*;
52/// let wl = wlist![(1, "qi"), (2, "sup"), (5, "shard")];
53///
54/// let _ = wl[0]; // => WeightedItem { weight: 1, value: "qi" }
55/// let _ = wl[1]; // => WeightedItem { weight: 2, value: "sup" }
56/// let _ = wl[2]; // => WeightedItem { weight: 2, value: "sup" }
57/// let _ = wl[3]; // => WeightedItem { weight: 5, value: "shard" }
58/// let _ = wl[4]; // => WeightedItem { weight: 5, value: "shard" }
59/// let _ = wl[5]; // => WeightedItem { weight: 5, value: "shard" }
60/// let _ = wl[6]; // => WeightedItem { weight: 5, value: "shard" }
61/// let _ = wl[7]; // => WeightedItem { weight: 5, value: "shard" }
62/// let _ = wl[8]; // => panic - out of bounds!
63/// ```
64///
65/// In essence, each value is "copied" a number of times equal to its weight – this is what enables the weighted randomisation. But because the values are stored in [`WeightedItem`] objects, instead of actually being copied, larger weight values can be used without fear of performance impacts.
66///
67/// # Tips
68///
69/// - Most methods return `&Self` or `&mut Self`, allowing you to chain methods. Here's a contrived example:
70///
71/// ```
72/// # use weighted_list::*;
73/// let mut list = wlist![(2, "sup")];
74///
75/// list.push_value("sup")
76/// .merge_duplicates()
77/// .prune()
78/// .len();
79/// ```
80#[derive(Clone, Hash, PartialEq, Eq, Default, Debug)]
81pub struct WeightedList<V,
82 W: Weight>
83{
84 data: Vec<WeightedItem<V,W>>
85}
86
87// == CONSTRUCTORS == //
88impl<V, W: Weight> WeightedList<V,W>
89{
90 /// Construct an empty list.
91 pub fn new() -> Self
92 {
93 Self { data: Vec::new() }
94 }
95
96 /// Construct an empty list with the specified capacity.
97 pub fn with_capacity(capacity: usize) -> Self
98 {
99 Self { data: Vec::with_capacity(capacity) }
100 }
101
102 /// Construct a [`WeightedList`] from an iterable of `(weight, value)` pairs.
103 pub fn init<I>(pairs: I) -> Self
104 where I: IntoIterator<Item = (W, V)>
105 {
106 Self {
107 data:
108 pairs.into_iter()
109 .map(
110 |(weight, value)| WeightedItem::new(weight, value)
111 )
112 .collect::<Vec<_>>()
113 }
114 }
115
116 /// Construct a [`WeightedList`] from an iterable of `value`s, merging duplicate values into single [`WeightedItem`]s.
117 ///
118 /// Note that this has $O(n^2)$ time complexity.
119 pub fn from_expanded<I>(values: I) -> Self
120 where
121 I: IntoIterator<Item = V>,
122 V: PartialEq,
123 {
124 let mut out = WeightedList::new();
125
126 for value in values {
127 if let Some(existing) = out.iter_mut().find(|item| item.value == value) {
128 existing.weight += W::one();
129 }
130 else {
131 out.push_value(value);
132 }
133 }
134
135 out
136 }
137}
138
139/// Construct a [`WeightedList`] from the provided `(weight, value)` pairs.
140///
141/// # Usage
142///
143/// ```
144/// # use weighted_list::*;
145/// let wl = wlist![
146/// (2, "sup"),
147/// (3, "nova"),
148/// (5, "shard"),
149/// ];
150///
151/// let empty: WeightedList<(), usize> = wlist![];
152/// ```
153#[macro_export]
154macro_rules! wlist {
155 ($( $item:expr ),* $(,)?) =>
156 {
157 WeightedList::init([
158 $( $item, )*
159 ])
160 };
161}
162
163// == ACCESSORS == //
164impl<V, W: Weight> WeightedList<V,W>
165{
166 /// Get an iterator over the weights of each item in the list.
167 ///
168 /// # Usage
169 ///
170 /// ```
171 /// # use weighted_list::*;
172 /// let wl = wlist![(2, "sup"), (3, "nova")];
173 ///
174 /// for weight in wl.weights() {
175 /// println!("{weight}"); // => 2, 3
176 /// }
177 ///
178 /// assert_eq!( wl.weights().collect::<Vec<u32>>(), vec![2, 3] );
179 /// ```
180 pub fn weights(&self) -> impl Iterator<Item = W>
181 {
182 self.data.iter().map(|item| item.weight)
183 }
184
185 /// Get an iterator over the values of each item in the list.
186 ///
187 /// # Usage
188 ///
189 /// ```
190 /// # use weighted_list::*;
191 /// let wl = wlist![(2, "sup"), (3, "nova")];
192 ///
193 /// for value in wl.values() {
194 /// println!("{value}"); // => &"sup", &"nova"
195 /// }
196 ///
197 /// assert_eq!( wl.values().collect::<Vec<&&str>>(), vec![&"sup", &"nova"] );
198 /// ```
199 pub fn values(&self) -> impl Iterator<Item = &V>
200 {
201 self.data.iter().map(|item| &item.value)
202 }
203
204 /// Get a reference to the `Vec<>` of items in the list.
205 ///
206 /// # Usage
207 ///
208 /// ```
209 /// # use weighted_list::*;
210 /// let wl = wlist![(2, "sup"), (3, "nova")];
211 ///
212 /// for item in wl.items() {
213 /// println!("({}, {})", item.weight, item.value); // => (2, "sup"), (3, "nova")
214 /// }
215 /// ```
216 pub fn items(&self) -> &Vec<WeightedItem<V,W>>
217 {
218 &self.data
219 }
220
221 /// Get an iterator over (weight, value) tuples representing each item in the list.
222 ///
223 /// # Usage
224 ///
225 /// ```
226 /// # use weighted_list::*;
227 /// let wl = wlist![(2, "sup"), (3, "nova")];
228 ///
229 /// for (weight, value) in wl.raw() {
230 /// println!("({weight}, {value})"); // => (2, "sup"), (3, "nova")
231 /// }
232 ///
233 /// assert_eq!( wl.raw().collect::<Vec<_>>(), vec![(2, &"sup"), (3, &"nova")] );
234 /// ```
235 ///
236 /// # Notes
237 ///
238 /// This satisfies the axiom:
239 ///
240 /// ```
241 /// # use weighted_list::*;
242 /// let wl = wlist![(2, "sup"), (3, "nova")];
243 /// let rl = WeightedList::init(wl.raw());
244 ///
245 /// for (left, right) in std::iter::zip(wl.clone(), rl.clone()) {
246 /// assert_eq!(left.weight, right.weight);
247 /// assert_eq!(left.value, *right.value);
248 /// }
249 /// ```
250 pub fn raw(&self) -> impl Iterator<Item = (W,&V)>
251 {
252 self.data.iter().map(|item| (item.weight, &item.value))
253 }
254}
255
256impl<V, W: Weight + nums::PrimInt> WeightedList<V,W>
257{
258 /// Get an iterator over each value in the list, repeated a number of times equal to its weight.
259 ///
260 /// # Usage
261 ///
262 /// ```
263 /// # use weighted_list::*;
264 /// let wl = wlist![(2, "sup"), (3, "nova")];
265 ///
266 /// let mut test = vec![];
267 /// for value in wl.expanded() {
268 /// test.push(*value);
269 /// }
270 ///
271 /// assert_eq!( test, vec!["sup", "sup", "nova", "nova", "nova"] );
272 /// ```
273 pub fn expanded(&self) -> impl Iterator<Item = &V>
274 {
275 self.data
276 .iter()
277 .flat_map(|item| iter::repeat_n(
278 &item.value,
279 nums::cast::<W, usize>(item.weight).unwrap_or(0)
280 ))
281 }
282}
283
284// == PROPERTIES == //
285impl<V, W: Weight> WeightedList<V,W>
286{
287 /// Sum the weights of all items in the list.
288 ///
289 /// # Notes
290 ///
291 /// - This is not the number of items in the list – use [`.total_values()`](Self::total_values) for that.
292 /// - `self.len() == 0` does not imply the list is empty – items may have zero or negative weights! To check if the list is empty, use [`.is_empty()`](Self::is_empty) instead.
293 pub fn len(&self) -> W
294 {
295 self.data.iter().map(|item| item.weight).sum()
296 }
297
298 pub fn capacity(&self) -> usize
299 {
300 self.data.capacity()
301 }
302
303 /// How many items/values are in the list?
304 ///
305 /// Note that this is not equivalent to [`self.len()`](Self::len), which is the total weights of all items in the list.
306 ///
307 /// # Usage
308 ///
309 /// ```
310 /// # use weighted_list::*;
311 /// let wl = wlist![(2, "sup"), (3, "nova")];
312 ///
313 /// assert_eq!( wl.total_values(), 2 );
314 /// assert_eq!( wl.len(), 5 );
315 /// ```
316 pub fn total_values(&self) -> usize
317 {
318 self.data.len()
319 }
320
321 /// Does the list contain no items?
322 ///
323 /// Note that this returns `false` if the list contains items with weights of `0`.
324 ///
325 /// # Usage
326 ///
327 /// ```
328 /// # use weighted_list::*;
329 /// let empty: WeightedList<(), usize> = wlist![];
330 /// assert_eq!( empty.is_empty(), true );
331 ///
332 /// assert_eq!( wlist![(0, "qi")].is_empty(), false );
333 /// ```
334 pub fn is_empty(&self) -> bool
335 {
336 self.data.is_empty()
337 }
338
339 /// Do all items have a weight of `0`?
340 ///
341 /// # Usage
342 ///
343 /// ```
344 /// # use weighted_list::*;
345 /// assert_eq!( wlist![(0, "qi")].is_zero(), true );
346 /// assert_eq!( wlist![(1, "qi")].is_zero(), false );
347 /// assert_eq!( wlist![(0, "qi"), (0, "xi")].is_zero(), true );
348 /// assert_eq!( wlist![(0, "qi"), (1, "vi")].is_zero(), false );
349 ///
350 /// let empty: WeightedList<(), usize> = wlist![];
351 /// assert_eq!( empty.is_zero(), false );
352 /// ```
353 ///
354 /// # Notes
355 /// - Returns `false` if `.is_empty()` is `true`.
356 pub fn is_zero(&self) -> bool
357 {
358 !self.is_empty()
359 && self.data.iter().all(|item| item.weight == W::zero())
360 }
361
362 /// Do any items have a negative weight?
363 ///
364 /// # Usage
365 ///
366 /// ```
367 /// # use weighted_list::*;
368 /// assert_eq!( wlist![(0, "qi"), ( 2, "sup") ].has_negative_weights(), false );
369 /// assert_eq!( wlist![(0, "qi"), (-1, "aleph")].has_negative_weights(), true );
370 /// ```
371 pub fn has_negative_weights(&self) -> bool
372 {
373 !self.is_empty()
374 && self.data.iter().any(|item| item.weight < W::zero())
375 }
376}
377
378// == CONVERSIONS == //
379impl<V, W: Weight> From<WeightedList<V,W>> for Vec<WeightedItem<V,W>> {
380 fn from(list: WeightedList<V,W>) -> Self {
381 list.data
382 }
383}
384
385impl<V, W: Weight> FromIterator<WeightedItem<V,W>> for WeightedList<V,W>
386{
387 fn from_iter<I>(items: I) -> Self
388 where I: IntoIterator<Item = WeightedItem<V,W>>
389 {
390 // TODO benchmark
391 // Self {
392 // data: items.into_iter().collect::<Vec<WeightedItem<V,W>>>()
393 // }
394
395 let mut data = vec![];
396
397 for item in items {
398 data.push(item);
399 }
400
401 Self { data }
402 }
403}
404
405impl<V, W: Weight> FromIterator<(W,V)> for WeightedList<V,W> {
406 fn from_iter<I>(pairs: I) -> Self
407 where I: IntoIterator<Item = (W,V)>
408 {
409 Self::init(pairs)
410 }
411}
412
413impl<V, W: Weight> From<Vec<WeightedItem<V,W>>> for WeightedList<V,W> {
414 fn from(vec: Vec<WeightedItem<V,W>>) -> Self {
415 Self { data: vec }
416 }
417}
418impl<V, W: Weight> From<Vec<(W,V)>> for WeightedList<V,W> {
419 fn from(vec: Vec<(W,V)>) -> Self {
420 Self::init(vec.into_iter())
421 }
422}
423
424impl<V, W: Weight, const N: usize> From<[(W,V); N]> for WeightedList<V,W> {
425 fn from(pairs: [(W,V); N]) -> Self {
426 Self::init(pairs)
427 }
428}
429
430impl<V, W: Weight> AsRef<Vec<WeightedItem<V,W>>> for WeightedList<V,W> {
431 fn as_ref(&self) -> &Vec<WeightedItem<V,W>> {
432 &self.data
433 }
434}
435
436impl<V, W: Weight> Deref for WeightedList<V,W> {
437 type Target = [WeightedItem<V,W>];
438
439 fn deref(&self) -> &Self::Target {
440 self.data.deref()
441 }
442}
443
444impl<V, W: Weight> DerefMut for WeightedList<V,W> {
445 fn deref_mut(&mut self) -> &mut Self::Target {
446 self.data.deref_mut()
447 }
448}
449
450// == TRAITS == //
451impl<V: fmt::Display, W: Weight + fmt::Display> fmt::Display for WeightedList<V,W>
452{
453 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result
454 {
455 write!(f,
456 "WeightedList[{}]",
457 self.data.iter().map(|item| item.to_string()).join(", ")
458 )
459 }
460}
461
462impl<V, W: Weight> Extend<WeightedItem<V,W>> for WeightedList<V,W>
463{
464 fn extend<T>(&mut self, iter: T)
465 where T: IntoIterator<Item = WeightedItem<V,W>>
466 {
467 for item in iter {
468 self.push_item(item);
469 }
470 }
471}
472
473// == INDEXING == //
474impl<V, W: Weight> Index<W> for WeightedList<V,W>
475{
476 type Output = WeightedItem<V,W>;
477
478 fn index(&self, weighted_index: W) -> &Self::Output
479 {
480 let mut t = W::zero();
481
482 for item in &self.data {
483 t += item.weight;
484
485 if t > weighted_index {
486 return item;
487 }
488 };
489
490 panic!("index out of bounds: the len is {} but the index is {weighted_index}", self.len());
491 }
492}
493
494impl<V, W: Weight> IndexMut<W> for WeightedList<V,W>
495{
496 fn index_mut(&mut self, weighted_index: W) -> &mut Self::Output
497 {
498 let idx = self._unweight_index_(weighted_index);
499 &mut self.data[idx]
500 }
501}
502
503// == ITERATION == //
504impl<V, W: Weight> IntoIterator for WeightedList<V,W>
505{
506 type Item = WeightedItem<V,W>;
507 type IntoIter = <Vec<Self::Item> as IntoIterator>::IntoIter;
508
509 /// ```compile_fail
510 /// # use weighted_list::*;
511 /// let list = wlist![]
512 /// for _ in list {}
513 /// list; // compile error
514 /// ```
515 fn into_iter(self) -> Self::IntoIter {
516 self.data.into_iter()
517 }
518}
519
520impl<'l, V, W: Weight> IntoIterator for &'l WeightedList<V,W>
521{
522 type Item = &'l WeightedItem<V,W>;
523 type IntoIter = std::slice::Iter<'l, WeightedItem<V,W>>;
524
525 fn into_iter(self) -> Self::IntoIter {
526 self.data.iter()
527 }
528}
529
530impl<'l, V, W: Weight> IntoIterator for &'l mut WeightedList<V,W>
531{
532 type Item = &'l mut WeightedItem<V,W>;
533 type IntoIter = std::slice::IterMut<'l, WeightedItem<V,W>>;
534
535 fn into_iter(self) -> Self::IntoIter {
536 self.data.iter_mut()
537 }
538}
539
540// == LIST QUERYING == //
541impl<V: Clone, W: Weight> WeightedList<V,W>
542{
543 /// Return a clone of the list with items sorted in ascending order of weights.
544 ///
545 /// Orderings of items with equivalent weights is (currently) undefined behaviour.
546 pub fn sorted(&self) -> Self
547 where V: Eq, W: Ord
548 {
549 let mut out = self.clone();
550 out.sort();
551 out
552 }
553
554 /// Return a clone of the list with items reversed.
555 pub fn reversed(&self) -> Self
556 {
557 let mut out = self.clone();
558 out.reverse();
559 out
560 }
561}
562
563// == LIST MUTATION == //
564impl<V, W: Weight> WeightedList<V,W>
565{
566 pub fn reserve(&mut self, additional: usize) -> &mut Self
567 {
568 self.data.reserve(additional);
569 self
570 }
571
572 /// Append an item to the end of the list.
573 ///
574 /// # Usage
575 ///
576 /// ```
577 /// # use weighted_list::*;
578 /// let mut wl = wlist![(2, "sup"), (3, "nova"), (5, "shard")];
579 ///
580 /// assert_eq!(
581 /// *wl.push_item(wl[0].clone()),
582 /// wlist![(2, "sup"), (3, "nova"), (5, "shard"), (2, "sup")],
583 /// )
584 /// ```
585 pub fn push_item(&mut self, item: WeightedItem<V,W>) -> &mut Self
586 {
587 self.data.push(item);
588 self
589 }
590
591 /// Append a new item with `value` and `weight` to the end of the list.
592 ///
593 /// # Usage
594 ///
595 /// ```
596 /// # use weighted_list::*;
597 /// let mut wl = wlist![(2, "sup"), (3, "nova"), (5, "shard")];
598 ///
599 /// assert_eq!(
600 /// *wl.push_new_item(7, "cortex"),
601 /// wlist![(2, "sup"), (3, "nova"), (5, "shard"), (7, "cortex")],
602 /// )
603 /// ```
604 pub fn push_new_item(&mut self, weight: W, value: V) -> &mut Self
605 {
606 self.push_item(WeightedItem { weight, value })
607 }
608
609 /// Append a new item with `value` and a weight of `1` to the end of the list.
610 ///
611 /// # Usage
612 ///
613 /// ```
614 /// # use weighted_list::*;
615 /// let mut wl = wlist![(2, "sup"), (3, "nova"), (5, "shard")];
616 ///
617 /// assert_eq!(
618 /// *wl.push_value("elysion"),
619 /// wlist![(2, "sup"), (3, "nova"), (5, "shard"), (1, "elysion")],
620 /// )
621 /// ```
622 pub fn push_value(&mut self, value: V) -> &mut Self
623 {
624 self.push_item(WeightedItem::unit(value))
625 }
626
627 /// Insert an item into the list at `weighted_index`. If `weighted_index >= len`, the item is appended to the end (the function does *not* panic).
628 pub fn insert_item(&mut self,
629 weighted_index: W,
630 item: WeightedItem<V,W>
631 ) -> &mut Self
632 {
633 self.data.insert(self._unweight_index_nopanic_(weighted_index), item);
634 self
635 }
636
637 /// Insert a new item with `value` and `weight` into the list at `weighted_index`. If `weighted_index >= len`, the item is appended to the end (the function does *not* panic).
638 pub fn insert_new_item(&mut self,
639 weighted_index: W,
640 (weight, value): (W, V)
641 ) -> &mut Self
642 {
643 self.insert_item(weighted_index, WeightedItem::new(weight, value))
644 }
645
646 /// Insert an item with `value` and a weight of `1` into the list at `weighted_index`. If `weighted_index >= len`, the item is appended to the end (the function does *not* panic).
647 pub fn insert_value(&mut self,
648 weighted_index: W,
649 value: V,
650 ) -> &mut Self
651 {
652 self.insert_item(weighted_index, WeightedItem::unit(value))
653 }
654
655 /// Move all items in `other` into `self`, leaving `other` empty.
656 pub fn append(&mut self, other: &mut WeightedList<V,W>) -> &mut Self
657 {
658 self.data.append(&mut other.data);
659 self
660 }
661
662 /// Reverse the order of items in the list (in-place).
663 pub fn reverse(&mut self) -> &mut Self
664 {
665 self.data.reverse();
666 self
667 }
668
669 /// Swap the items at weighted indices `left` and `right`.
670 ///
671 /// # Panics
672 ///
673 /// Panics if `left` or `right` are out of bounds.
674 pub fn swap(&mut self, left: W, right: W) -> &mut Self
675 {
676 let l = self._unweight_index_(left);
677 let r = self._unweight_index_(right);
678 self.data.swap(l, r);
679 self
680 }
681
682 /// Removes the last item from the list and returns it, or `None` if the list is empty.
683 pub fn pop(&mut self) -> Option<WeightedItem<V,W>>
684 {
685 self.data.pop()
686 }
687
688 pub fn pop_if(&mut self,
689 predicate: impl FnOnce(&mut WeightedItem<V,W>) -> bool
690 ) -> Option<WeightedItem<V,W>>
691 {
692 self.data.pop_if(predicate)
693 }
694
695 /// Remove the entire item at `weighted_index` and return it.
696 ///
697 /// # Panics
698 ///
699 /// Panics if `weighted_index` is out of bounds.
700 pub fn remove_at(&mut self, weighted_index: W) -> WeightedItem<V,W>
701 {
702 self.data.remove(self._unweight_index_(weighted_index))
703 }
704
705 pub fn truncate(&mut self, len: W) -> &mut Self
706 {
707 if len == W::zero() {
708 return self.clear();
709 }
710
711 let mut t = W::zero();
712 let mut n = 0;
713
714 for (i, each) in self.iter_mut().enumerate() {
715 t += each.weight;
716
717 if t >= len {
718 if t > len {
719 each.weight += len - t;
720 }
721
722 n = i + 1;
723 break;
724 }
725 }
726
727 self.data.truncate(n);
728
729 self
730 }
731
732 /// Retain only items that fulfil `predicate``.
733 pub fn retain<F>(&mut self, predicate: F) -> &mut Self
734 where F: FnMut(&WeightedItem<V,W>) -> bool
735 {
736 self.data.retain(predicate);
737 self
738 }
739
740 /// Retain only items that fulfil `predicate``, passing a mutable reference to the predicate.
741 pub fn retain_mut<F>(&mut self, predicate: F) -> &mut Self
742 where F: FnMut(&mut WeightedItem<V,W>) -> bool
743 {
744 self.data.retain_mut(predicate);
745 self
746 }
747
748 /// Clear the list, removing all items (in-place).
749 ///
750 /// If you'd like to set the weights of all items to `0`, you can use [`.zero_all_weights()`](Self::zero_all_weights).
751 pub fn clear(&mut self) -> &mut Self
752 {
753 self.data.clear();
754 self
755 }
756}
757
758// == SPECIALISED QUERYING == //
759impl<V, W: Weight> WeightedList<V,W>
760{
761 /// Does any item in the list have a value equal to `value`?
762 pub fn contains_value(&self, value: &V) -> bool
763 where V: PartialEq
764 {
765 self.data.iter().any(|item| item.value == *value)
766 }
767
768 /// Does any item in the list have a weight equal to `weight`?
769 pub fn contains_weight(&self, weight: W) -> bool
770 {
771 self.data.iter().any(|item| item.weight == weight)
772 }
773}
774
775// == SPECIALISED MUTATION == //
776impl<V, W: Weight> WeightedList<V,W>
777{
778 /// Remove all items with non-positive weight.
779 pub fn prune(&mut self) -> &mut Self
780 {
781 self.data.retain(|item| item.weight > W::zero());
782 self
783 }
784
785 /// Return a clone of the list with all items having a non-positive weight removed.
786 ///
787 /// Out-of-place version of [`.prune()`](Self::prune).
788 pub fn pruned(&self) -> Self
789 where V: Clone
790 {
791 let mut out = self.clone();
792 out.prune();
793 out
794 }
795
796 /// Find the first occurrence (from the left) of an item with `value`, and remove the entire item.
797 ///
798 /// # Usage
799 ///
800 /// ```
801 /// # use weighted_list::*;
802 /// let mut wl = wlist![(2, "sup"), (3, "nova"), (5, "shard")];
803 ///
804 /// assert_eq!(
805 /// *wl.remove_value_first(&"nova"),
806 /// wlist![(2, "sup"), (5, "shard")],
807 /// )
808 /// ```
809 pub fn remove_value_first(&mut self, value: &V) -> &mut Self
810 where V: PartialEq
811 {
812 self.remove_first_where(|item| item.value == *value)
813 }
814
815 /// Find the last occurrence (from the right) of an item with `value`, and remove the entire item.
816 ///
817 /// # Usage
818 ///
819 /// ```
820 /// # use weighted_list::*;
821 /// let mut wl = wlist![(0, "qi"), (1, "qi"), (2, "sup")];
822 ///
823 /// assert_eq!(
824 /// *wl.remove_value_last(&"qi"),
825 /// wlist![(0, "qi"), (2, "sup")],
826 /// )
827 /// ```
828 pub fn remove_value_last(&mut self, value: &V) -> &mut Self
829 where V: PartialEq
830 {
831 self.remove_last_where(|item| item.value == *value)
832 }
833
834 /// Find the first occurrence (from the left) of an item that fulfils `predicate`, and remove the entire item.
835 ///
836 /// # Usage
837 ///
838 /// ```
839 /// # use weighted_list::*;
840 /// let mut wl = wlist![(2, "sup"), (3, "nova"), (5, "shard")];
841 ///
842 /// assert_eq!(
843 /// *wl.remove_first_where(|item| item.weight > 2),
844 /// wlist![(2, "sup"), (5, "shard")],
845 /// )
846 /// ```
847 pub fn remove_first_where<F>(&mut self, predicate: F) -> &mut Self
848 where F: FnMut(&WeightedItem<V,W>) -> bool
849 {
850 if let Some(idx) = self.iter().position(predicate) {
851 self.data.remove(idx);
852 }
853
854 self
855 }
856
857 /// Find the last occurrence (from the right) of an item that fulfils `predicate`, and remove the entire item.
858 ///
859 /// # Usage
860 ///
861 /// ```
862 /// # use weighted_list::*;
863 /// let mut wl = wlist![(2, "sup"), (3, "nova"), (5, "shard")];
864 ///
865 /// assert_eq!(
866 /// *wl.remove_last_where(|item| item.weight > 2),
867 /// wlist![(2, "sup"), (3, "nova")],
868 /// );
869 /// ```
870 pub fn remove_last_where<F>(&mut self, predicate: F) -> &mut Self
871 where F: FnMut(&WeightedItem<V,W>) -> bool
872 {
873 if let Some(idx) = self.iter().rposition(predicate) {
874 self.data.remove(idx);
875 }
876
877 self
878 }
879
880 /// Set the weight of all items to `0`.
881 ///
882 /// # Usage
883 ///
884 /// ```
885 /// # use weighted_list::*;
886 /// let mut wl = wlist![(2, "sup"), (3, "nova"), (5, "shard")];
887 ///
888 /// assert_eq!(
889 /// *wl.zero_all_weights(),
890 /// wlist![(0, "sup"), (0, "nova"), (0, "shard")],
891 /// )
892 /// ```
893 pub fn zero_all_weights(&mut self) -> &mut Self
894 {
895 for item in &mut self.data {
896 item.weight = W::zero();
897 }
898
899 self
900 }
901
902 /// Set the weight of all items to `weight`.
903 ///
904 /// # Usage
905 ///
906 /// ```
907 /// # use weighted_list::*;
908 /// let mut wl = wlist![(2, "sup"), (3, "nova"), (5, "shard")];
909 ///
910 /// assert_eq!(
911 /// *wl.set_all_weights(1),
912 /// wlist![(1, "sup"), (1, "nova"), (1, "shard")],
913 /// )
914 /// ```
915 pub fn set_all_weights(&mut self, weight: W) -> &mut Self
916 {
917 for item in &mut self.data {
918 item.weight = weight;
919 }
920
921 self
922 }
923
924 /// Return a clone of the list with all item weights normalised such that they sum to `1.0`.
925 ///
926 /// # Usage
927 ///
928 /// ```
929 /// # use weighted_list::*;
930 /// let mut wl = wlist![(2, "sup"), (3, "nova"), (5, "shard")];
931 ///
932 /// assert_eq!(
933 /// wl.normalised().ok(),
934 /// Some(wlist![(0.2, "sup"), (0.3, "nova"), (0.5, "shard")])
935 /// );
936 /// ```
937 pub fn normalised(&mut self) -> Result<WeightedList<V, f64>, &str>
938 where V: Clone
939 {
940 let total;
941
942 if let Some(t) = nums::cast::<W, f64>(self.len()) {
943 total = t;
944 } else {
945 return Err("Error casting total weights to `f64`");
946 };
947
948 let items =
949 self.data
950 .iter()
951 .map(|item| {
952 let weight = nums::cast::<W, f64>(item.weight)?;
953 Some(WeightedItem {
954 weight: weight / total,
955 value: item.value.clone()
956 })
957 })
958 .collect::<Option<Vec<WeightedItem<V, f64>>>>()
959 ;
960
961 match items {
962 Some(data) => Ok(WeightedList { data }),
963 None => Err("Error casting weights to `f64`")
964 }
965 }
966}
967
968impl<V: PartialEq, W: Weight> WeightedList<V,W>
969{
970 /// Merge an item into the list. If an item with the same value already exists, add the weight of the new item to the existing item. Otherwise, append the new item to the list.
971 ///
972 /// # Tips
973 ///
974 /// - Use this method when you already have an existing [`WeightedItem`] instance. If you're going to construct a new [`WeightedItem`], [`.merge_new_item()`](Self::merge_new_item) is probably more convenient.
975 ///
976 /// # Usage
977 ///
978 /// ```
979 /// # use weighted_list::*;
980 /// let mut wl = wlist![(1, "sup")];
981 ///
982 /// let item = WeightedItem::new(2, "sup");
983 /// wl.merge_item(item);
984 /// assert!(wl == wlist![(3, "sup")]);
985 /// // "sup" merged with existing instance
986 ///
987 /// let item = WeightedItem::unit("elysion");
988 /// wl.merge_item(item);
989 /// assert!(wl == wlist![(3, "sup"), (1, "elysion")]);
990 /// // "elysion" appended to end
991 /// ```
992 pub fn merge_item(&mut self, item: WeightedItem<V,W>) -> &mut Self
993 {
994 if let Some(existing) = self.data.iter_mut().find(|each| each.value == item.value) {
995 existing.weight += item.weight;
996 }
997 else {
998 self.data.push(item);
999 }
1000
1001 self
1002 }
1003
1004 /// Merge a new item with `value` and `weight` into the list.
1005 ///
1006 /// See [`.merge_item()`](Self::merge_item) for details.
1007 pub fn merge_new_item(&mut self, weight: W, value: V) -> &mut Self
1008 {
1009 self.merge_item(WeightedItem { weight, value })
1010 }
1011
1012 /// Merge a new item with `value` and a weight of `1` into the list.
1013 ///
1014 /// See [`.merge_item()`](Self::merge_item) for details.
1015 pub fn merge_value(&mut self, value: V) -> &mut Self
1016 {
1017 self.merge_item(WeightedItem::unit(value))
1018 }
1019
1020 /// Merge the items of `other` into `self`, leaving `other` empty.
1021 ///
1022 /// See [`.merge_item()`](Self::merge_item) for details.
1023 pub fn merge_with(&mut self, other: WeightedList<V,W>) -> &mut Self
1024 {
1025 for item in other {
1026 self.merge_item(item);
1027 }
1028
1029 self
1030 }
1031
1032 /// Merge any items in the list with duplicate values by combining their weights with the first instance.
1033 ///
1034 /// # Usage
1035 ///
1036 /// ```
1037 /// # use weighted_list::*;
1038 /// let mut wl = wlist![
1039 /// (1, "sup"),
1040 /// (2, ""),
1041 /// (20, "sup")
1042 /// ];
1043 ///
1044 /// assert_eq!(
1045 /// *wl.merge_duplicates(),
1046 /// wlist![
1047 /// (21, "sup"),
1048 /// (2, ""),
1049 /// ]
1050 /// );
1051 /// ```
1052 pub fn merge_duplicates(&mut self) -> &mut Self
1053 {
1054 let orig = std::mem::replace(self, WeightedList::new());
1055 self.merge_with(orig);
1056 self
1057 }
1058}
1059
1060impl<V: Clone, W: Weight> WeightedList<V,W>
1061{
1062 /// Decrement the weight of the item at `weighted_index` by `1`. If its weight becomes non-positive as a result, remove the entire item. Returns a clone of the item with its updated weight.
1063 ///
1064 /// # Usage
1065 ///
1066 /// ```
1067 /// # use weighted_list::*;
1068 /// let mut wl = wlist![(2, "sup"), (3, "nova"), (5, "shard")];
1069 ///
1070 /// wl.take_one_at(2);
1071 /// assert_eq!( wl, wlist![(2, "sup"), (2, "nova"), (5, "shard")] );
1072 ///
1073 /// wl.take_one_at(2);
1074 /// assert_eq!( wl, wlist![(2, "sup"), (1, "nova"), (5, "shard")] );
1075 ///
1076 /// wl.take_one_at(2);
1077 /// assert_eq!( wl, wlist![(2, "sup"), (5, "shard")] );
1078 /// ```
1079 pub fn take_one_at(&mut self, weighted_index: W) -> WeightedItem<V,W>
1080 {
1081 self.take_by_at(W::one(), weighted_index)
1082 }
1083
1084 /// Decrement the weight of the item at `weighted_index` by `decrement`. If its weight becomes non-positive as a result, remove the entire item. Returns a clone of the item with its updated weight.
1085 ///
1086 /// # Panics
1087 ///
1088 /// Panics if `weighted_index` is out of bounds.
1089 ///
1090 /// # Usage
1091 ///
1092 /// ```
1093 /// # use weighted_list::*;
1094 /// let mut wl = wlist![(2, "sup"), (3, "nova"), (5, "shard")];
1095 ///
1096 /// wl.take_by_at(2, 2);
1097 /// assert_eq!( wl, wlist![(2, "sup"), (1, "nova"), (5, "shard")] );
1098 ///
1099 /// wl.take_by_at(2, 2);
1100 /// assert_eq!( wl, wlist![(2, "sup"), (5, "shard")]);
1101 /// ```
1102 pub fn take_by_at(&mut self, decrement: W, weighted_index: W) -> WeightedItem<V,W>
1103 {
1104 let idx = self._unweight_index_(weighted_index);
1105 let target = &mut self.data[idx];
1106
1107 target.weight -= decrement;
1108
1109 if target.weight <= W::zero() {
1110 self.data.remove(idx)
1111 }
1112 else {
1113 target.clone()
1114 }
1115 }
1116
1117 /// Remove the entire item at `weighted_index`.
1118 ///
1119 /// # Usage
1120 ///
1121 /// ```
1122 /// # use weighted_list::*;
1123 /// let mut wl = wlist![(2, "sup"), (3, "nova"), (5, "shard")];
1124 ///
1125 /// wl.take_entire_at(3);
1126 /// assert_eq!( wl, wlist![(2, "sup"), (5, "shard")] );
1127 /// ```
1128 pub fn take_entire_at(&mut self, weighted_index: W) -> WeightedItem<V,W>
1129 {
1130 self.remove_at(weighted_index)
1131 }
1132}
1133
1134// == RANDOMISATION == //
1135impl<V, W: Weight> WeightedList<V,W>
1136{
1137 fn _get_random_weighted_index_up_to_<RNG>(&self, rng: &mut RNG, upper: W) -> Option<W>
1138 where RNG: Rng + ?Sized
1139 {
1140 let len: f64 = nums::cast::<W, f64>(upper)?;
1141 let scalar: f64 = rng.random();
1142
1143 let idx = (len * scalar).floor();
1144 let out = nums::cast::<f64, W>(idx)?;
1145
1146 Some(out)
1147 }
1148
1149 fn _get_random_weighted_index_<RNG>(&self, rng: &mut RNG) -> Option<W>
1150 where RNG: Rng + ?Sized
1151 {
1152 self._get_random_weighted_index_up_to_(rng, self.len())
1153 }
1154
1155 /// Select a random item from the list and return its value, using weighted randomisation.
1156 ///
1157 /// # Usage
1158 ///
1159 /// ```
1160 /// # use weighted_list::*;
1161 /// let wl = wlist![(2, "sup"), (3, "nova"), (5, "shard")];
1162 ///
1163 /// wl.select_random_value(&mut rand::rng());
1164 /// // could give:
1165 /// // - Some("sup" ) with 20% probability
1166 /// // - Some("nova" ) with 30% probability
1167 /// // - Some("shard") with 50% probability
1168 /// ```
1169 pub fn select_random_value<RNG>(&self, rng: &mut RNG) -> Option<&V>
1170 where RNG: Rng + ?Sized
1171 {
1172 let out = &self.select_random_item(rng)?.value;
1173 Some(out)
1174 }
1175
1176 /// Select a random item from the list, using weighted randomisation.
1177 ///
1178 /// # Usage
1179 ///
1180 /// ```
1181 /// # use weighted_list::*;
1182 /// let wl = wlist![(2, "sup"), (3, "nova"), (5, "shard")];
1183 ///
1184 /// wl.select_random_item(&mut rand::rng());
1185 /// // could give:
1186 /// // - Some(WeightedItem { 2, "sup" }) with 20% probability
1187 /// // - Some(WeightedItem { 3, "nova" }) with 30% probability
1188 /// // - Some(WeightedItem { 5, "shard" }) with 50% probability
1189 /// ```
1190 pub fn select_random_item<RNG>(&self, rng: &mut RNG) -> Option<&WeightedItem<V,W>>
1191 where RNG: Rng + ?Sized
1192 {
1193 if self.data.is_empty() { return None }
1194
1195 let idx = self._get_random_weighted_index_(rng)?;
1196 let out = &self[idx];
1197
1198 Some(out)
1199 }
1200}
1201
1202impl<V: Clone, W: Weight> WeightedList<V,W>
1203{
1204 /// Select a random item from the list using weighted randomisation, and decrement its weight by `1`.
1205 ///
1206 /// # Usage
1207 ///
1208 /// ```
1209 /// # use weighted_list::*;
1210 /// let mut wl = wlist![(2, "sup"), (3, "nova"), (5, "shard")];
1211 ///
1212 /// wl.take_one_random(&mut rand::rng());
1213 /// // could give:
1214 /// // - Some(WeightedItem { 1, "sup" }) with 20% probability
1215 /// // - Some(WeightedItem { 2, "nova" }) with 30% probability
1216 /// // - Some(WeightedItem { 4, "shard" }) with 50% probability
1217 /// ```
1218 pub fn take_one_random<RNG>(&mut self, rng: &mut RNG) -> Option<WeightedItem<V,W>>
1219 where RNG: Rng + ?Sized
1220 {
1221 self.take_by_random(rng, W::one())
1222 }
1223
1224 /// Select a random item from the list using weighted randomisation, and decrement its weight by `decrement`.
1225 ///
1226 /// # Usage
1227 ///
1228 /// ```
1229 /// # use weighted_list::*;
1230 /// let mut wl = wlist![(2, "sup"), (3, "nova"), (5, "shard")];
1231 ///
1232 /// wl.take_by_random(&mut rand::rng(), 2);
1233 /// // could give:
1234 /// // - Some(WeightedItem { 0, "sup" }) with 20% probability
1235 /// // - Some(WeightedItem { 1, "nova" }) with 30% probability
1236 /// // - Some(WeightedItem { 3, "shard" }) with 50% probability
1237 /// ```
1238 pub fn take_by_random<RNG>(&mut self, rng: &mut RNG, decrement: W) -> Option<WeightedItem<V,W>>
1239 where RNG: Rng + ?Sized
1240 {
1241 if self.data.is_empty() { return None }
1242
1243 let idx = self._get_random_weighted_index_(rng)?;
1244 let out = self.take_by_at(decrement, idx);
1245
1246 Some(out)
1247 }
1248
1249 /// Select and remove a random item from the list, using weighted randomisation.
1250 ///
1251 /// # Usage
1252 ///
1253 /// ```
1254 /// # use weighted_list::*;
1255 /// let mut wl = wlist![(2, "sup"), (3, "nova"), (5, "shard")];
1256 ///
1257 /// wl.take_entire_random(&mut rand::rng());
1258 /// // could give:
1259 /// // - Some(WeightedItem { 2, "sup" }) with 20% probability
1260 /// // - Some(WeightedItem { 3, "nova" }) with 30% probability
1261 /// // - Some(WeightedItem { 5, "shard" }) with 50% probability
1262 ///
1263 /// assert!( wl.total_values() == 2 );
1264 /// ```
1265 pub fn take_entire_random<RNG>(&mut self, rng: &mut RNG) -> Option<WeightedItem<V,W>>
1266 where RNG: Rng + ?Sized
1267 {
1268 if self.data.is_empty() { return None }
1269
1270 let idx = self._get_random_weighted_index_(rng)?;
1271 let out = self.take_entire_at(idx);
1272
1273 Some(out)
1274 }
1275}
1276
1277#[bon]
1278impl<V: Clone + Eq, W: Weight> WeightedList<V,W>
1279{
1280 /// Select `count` values using weighted randomisation.
1281 ///
1282 /// Call this method using `bon` builder syntax (see § Usage below).
1283 ///
1284 /// # Options
1285 ///
1286 /// ```compile_fail
1287 /// rng: RNG,
1288 /// count: usize,
1289 /// replace: bool = true,
1290 /// decrement: W = 1,
1291 /// unique: bool = false,
1292 /// ```
1293 ///
1294 /// - `count`: How many values to select.
1295 /// - `replace` (optional): If `true`, items do not have their weight decremented after selection, and infinite values can be selected. If `false`, items have their weight decremented after selection.
1296 /// - This means at most `self.len()` values will be returned.
1297 /// - `decrement` (optional): How much to decrement weights by if `replace` is `false`.
1298 /// - `unique` (optional): If `true`, only distinct values will be returned.
1299 /// - `replace` becomes irrelevant in this case.
1300 /// - This uses `Eq` equality comparison.
1301 /// - This means at most [`self.total_values()`](Self::total_values) values will be returned.
1302 ///
1303 /// # Usage
1304 ///
1305 /// This method uses the bon builder syntax:
1306 ///
1307 /// ```
1308 /// # use weighted_list::*;
1309 /// let mut pool = wlist![
1310 /// (2, "sup".to_string()),
1311 /// (3, "nova".to_string()),
1312 /// (5, "shard".to_string()),
1313 /// ];
1314 ///
1315 /// let mut rng = rand::rng();
1316 ///
1317 /// // with replacement
1318 /// let selected =
1319 /// pool.select_random_values()
1320 /// .rng(&mut rng)
1321 /// .count(3)
1322 /// .call();
1323 ///
1324 /// assert!(selected.len() == 3);
1325 ///
1326 /// // without replacement
1327 /// let selected =
1328 /// pool.select_random_values()
1329 /// .rng(&mut rng)
1330 /// .count(10)
1331 /// .replace(false)
1332 /// .decrement(2)
1333 /// .call();
1334 ///
1335 /// assert!(selected.len() == 6);
1336 ///
1337 /// // unique only
1338 /// let selected =
1339 /// pool.select_random_values()
1340 /// .rng(&mut rng)
1341 /// .count(100)
1342 /// .unique(true)
1343 /// .call();
1344 ///
1345 /// assert!(selected.len() == 3);
1346 /// ```
1347 ///
1348 /// # Notes
1349 ///
1350 /// - It is not guaranteed that the results will have exactly `count` values.
1351 /// - If `count` exceeds the maximum possible number of values that can be returned, excess iterations will be skipped.
1352 /// - If selection for an iteration fails, that value is excluded from the output list.
1353 /// - This method reserves a `Vec<>` with capacity `count` initially, so be careful of passing in extremely large `count`s.
1354 #[builder]
1355 pub fn select_random_values<RNG>(&self,
1356 rng: &mut RNG,
1357 count: usize,
1358 replace: Option<bool>,
1359 decrement: Option<W>,
1360 unique: Option<bool>,
1361 ) -> Vec<V>
1362 where RNG: Rng + ?Sized
1363 {
1364 let replace = replace.unwrap_or(true);
1365 let decrement = decrement.unwrap_or(W::one());
1366 let unique = unique.unwrap_or(false);
1367
1368 let mut pool = self.clone();
1369 let mut n = 0;
1370 let mut out = Vec::with_capacity(count);
1371
1372 loop
1373 {
1374 n += 1;
1375 if n > count || self.data.is_empty() { break }
1376
1377 if let Some(item) = {
1378 if unique { pool.take_entire_random(rng) }
1379 else if replace { pool.take_by_random(rng, W::zero()) }
1380 else { pool.take_by_random(rng, decrement) }
1381 } {
1382 out.push(item.value.clone());
1383 }
1384 }
1385
1386 out
1387 }
1388
1389 /// Take `count` values using weighted randomisation.
1390 #[builder]
1391 pub fn take_random_values<RNG>(&mut self,
1392 rng: &mut RNG,
1393 count: usize,
1394 take_entire: Option<bool>,
1395 decrement: Option<W>,
1396 ) -> Vec<V>
1397 where RNG: Rng + ?Sized
1398 {
1399 let take_entire = take_entire.unwrap_or(true);
1400 let decrement = decrement.unwrap_or(W::one());
1401
1402 let mut n = 0;
1403 let mut out = Vec::with_capacity(count as usize);
1404
1405 loop
1406 {
1407 n += 1;
1408 if n > count || self.data.is_empty() { break }
1409
1410 if let Some(item) = {
1411 if take_entire { self.take_entire_random(rng) }
1412 else { self.take_by_random(rng, decrement) }
1413 } {
1414 out.push(item.value.clone());
1415 }
1416 }
1417
1418 out
1419 }
1420}
1421
1422#[bon]
1423impl<V: Clone + Eq + std::hash::Hash, W: Weight> WeightedList<V,W>
1424{
1425 /// Variant of `._unweighted_index_()` for mutating random selection with unique outputs.
1426 fn _unweight_index_skipping_(&self,
1427 weighted_index: W,
1428 seen: &std::collections::HashSet<V>,
1429 ) -> Option<usize>
1430 {
1431 let mut t = W::zero();
1432
1433 for (i, item) in self.data.iter().enumerate() {
1434 if seen.contains(&item.value) {
1435 continue
1436 }
1437
1438 t += item.weight;
1439
1440 if t > weighted_index {
1441 return Some(i);
1442 }
1443 }
1444
1445 None
1446 }
1447
1448 /// Take `count` unique values using weighted randomisation.
1449 ///
1450 /// This method is separate to `.take_random_values` due to having more restrictive trait bounds on `V` and using a different algorithm with heavier performance.
1451 #[builder]
1452 pub fn take_random_values_unique<RNG>(&mut self,
1453 rng: &mut RNG,
1454 count: usize,
1455 decrement: Option<W>,
1456 ) -> Vec<V>
1457 where RNG: Rng + ?Sized,
1458 {
1459 let decrement = decrement.unwrap_or(W::one());
1460
1461 let mut n = 0;
1462 let mut l = self.len();
1463
1464 let mut seen = std::collections::HashSet::<V>::new();
1465
1466 let mut out = Vec::with_capacity(
1467 if count > 16 {
1468 count.min(self.total_values())
1469 } else {
1470 count
1471 }
1472 );
1473
1474 loop {
1475 n += 1;
1476 if n > count || self.data.is_empty() { break }
1477
1478 if let Some(value) = (|| {
1479 let weighted_index = self._get_random_weighted_index_up_to_(rng, l)?;
1480 let idx = self._unweight_index_skipping_(weighted_index, &seen)?;
1481
1482 let target = &mut self.data[idx];
1483 let value = target.value.clone();
1484
1485 target.weight -= decrement;
1486
1487 if target.weight <= W::zero() {
1488 self.data.remove(idx);
1489 }
1490
1491 Some(value)
1492 })()
1493 {
1494 seen.insert(value.clone());
1495 out.push(value);
1496
1497 /* Yeah, the double traversal is horrific, but I can’t see any other way... we’ve got to discount *all* duplicates of the value we pick */
1498 l = self.data.iter()
1499 .filter_map(
1500 |item| {
1501 if !seen.contains(&item.value) { Some(item.weight) }
1502 else { None }
1503 }
1504 )
1505 .sum::<W>();
1506 }
1507 }
1508
1509 out
1510 }
1511}
1512
1513impl<V: Clone, W: Weight + Clone> WeightedList<V,W>
1514{
1515 /// Shuffle the order of items in the list (in-place).
1516 pub fn shuffle_items<RNG>(&mut self, rng: &mut RNG) -> &mut Self
1517 where RNG: Rng + ?Sized
1518 {
1519 self.data.shuffle(rng);
1520 self
1521 }
1522
1523 /// Return a clone with the order of items shuffled.
1524 ///
1525 /// Out-of-place version of [`.shuffle_items()`](Self::shuffle_items).
1526 pub fn shuffled_items<RNG>(&self, rng: &mut RNG) -> Self
1527 where RNG: Rng + ?Sized
1528 {
1529 let mut out = self.clone();
1530 out.shuffle_items(rng);
1531
1532 out
1533 }
1534
1535 /// Shuffle the pairings of (weight, value) for items in the list (in-place).
1536 ///
1537 /// Values remain in the same order, while weights are re-assigned.
1538 ///
1539 /// # Usage
1540 ///
1541 /// ```
1542 /// # use weighted_list::*;
1543 /// let mut wl = wlist![(2, "sup"), (3, "nova"), (5, "shard")];
1544 ///
1545 /// wl.shuffle_weights(&mut rand::rng());
1546 ///
1547 /// println!("{wl}");
1548 /// // could give:
1549 /// // WeightedList[{3, sup}, {5, nova}, {2, shard}]
1550 ///
1551 /// println!("{wl}");
1552 /// // could now give:
1553 /// // WeightedList[{2, sup}, {5, nova}, {3, shard}]
1554 /// ```
1555 pub fn shuffle_weights<RNG>(&mut self, rng: &mut RNG) -> &mut Self
1556 where RNG: Rng + ?Sized
1557 {
1558 let mut weights: Vec<W> = self.weights().collect();
1559 weights.shuffle(rng);
1560
1561 for item in &mut self.data {
1562 /* guaranteed to be Some */
1563 item.weight = weights.pop().unwrap();
1564 }
1565
1566 self
1567 }
1568
1569 /// Return a clone of the list with (weight, value) pairings shuffled.
1570 ///
1571 /// Out-of-place version of [`.shuffle_weights()`](Self::shuffle_weights).
1572 pub fn shuffled_weights<RNG>(&self, rng: &mut RNG) -> Self
1573 where RNG: Rng + ?Sized
1574 {
1575 let mut out = self.clone();
1576 out.shuffle_weights(rng);
1577
1578 out
1579 }
1580}
1581
1582// == INTERNAL == //
1583impl<V, W: Weight> WeightedList<V,W>
1584{
1585 /// Convert a `weighted_index` to its unweighted equivalent in the underlying `Vec<>`. Does not panic on overflow and instead returns `Vec::len()`.
1586 fn _unweight_index_nopanic_(&self, weighted_index: W) -> usize
1587 {
1588 let mut t = W::zero();
1589 let mut i = 0;
1590
1591 for item in &self.data {
1592 t += item.weight;
1593
1594 if t > weighted_index {
1595 return i;
1596 }
1597
1598 i += 1;
1599 }
1600
1601 i
1602 }
1603
1604 /// Convert a `weighted_index` to its unweighted equivalent in the underlying `Vec<>`. Panics on overflow.
1605 fn _unweight_index_(&self, weighted_index: W) -> usize
1606 {
1607 let mut t = W::zero();
1608
1609 for (i, item) in self.data.iter().enumerate() {
1610 t += item.weight;
1611
1612 if t > weighted_index {
1613 return i;
1614 }
1615 }
1616
1617 panic!(
1618 "index out of bounds: the len is {} but the index is {}",
1619 self.len(), weighted_index
1620 );
1621 }
1622}
1623
1624
1625#[cfg(test)] mod tests
1626{
1627 use super::*;
1628
1629 fn el() -> WeightedList<String, i32>
1630 {
1631 wlist![]
1632 }
1633
1634 fn wl() -> WeightedList<String, i32>
1635 {
1636 wlist![
1637 (2, "sup".to_string()),
1638 (3, "nova".to_string()),
1639 (5, "shard".to_string()),
1640 ]
1641 }
1642
1643 #[test] fn _unweight_index_()
1644 {
1645 let list = wl();
1646 assert_eq!( list._unweight_index_(0), 0 );
1647 assert_eq!( list._unweight_index_(1), 0 );
1648 assert_eq!( list._unweight_index_(2), 1 );
1649 assert_eq!( list._unweight_index_(3), 1 );
1650 assert_eq!( list._unweight_index_(4), 1 );
1651 assert_eq!( list._unweight_index_(5), 2 );
1652 assert_eq!( list._unweight_index_(6), 2 );
1653 assert_eq!( list._unweight_index_(7), 2 );
1654 assert_eq!( list._unweight_index_(8), 2 );
1655 assert_eq!( list._unweight_index_(9), 2 );
1656 }
1657
1658 #[test] #[should_panic] fn _unweight_index_empty_()
1659 {
1660 el()._unweight_index_(0);
1661 }
1662
1663 #[test] #[should_panic] fn _unweight_index_out_of_bounds_()
1664 {
1665 wl()._unweight_index_(10);
1666 }
1667
1668 #[test] fn _unweight_index_nopanic_()
1669 {
1670 let list = wl();
1671 assert_eq!( list._unweight_index_nopanic_(10), 3 );
1672 assert_eq!( list._unweight_index_nopanic_(11), 3 );
1673 assert_eq!( list._unweight_index_nopanic_(12), 3 );
1674 }
1675
1676 #[test] fn _unweight_index_skipping_()
1677 {
1678 let list = wl();
1679
1680 let seen = std::collections::HashSet::from(["sup".to_string()]);
1681 assert_eq!( list._unweight_index_skipping_(0, &seen), Some(1) );
1682 assert_eq!( list._unweight_index_skipping_(1, &seen), Some(1) );
1683 assert_eq!( list._unweight_index_skipping_(2, &seen), Some(1) );
1684 assert_eq!( list._unweight_index_skipping_(3, &seen), Some(2) );
1685 assert_eq!( list._unweight_index_skipping_(4, &seen), Some(2) );
1686 assert_eq!( list._unweight_index_skipping_(5, &seen), Some(2) );
1687 assert_eq!( list._unweight_index_skipping_(6, &seen), Some(2) );
1688 assert_eq!( list._unweight_index_skipping_(7, &seen), Some(2) );
1689
1690 let seen = std::collections::HashSet::from(["nova".to_string()]);
1691 assert_eq!( list._unweight_index_skipping_(0, &seen), Some(0) );
1692 assert_eq!( list._unweight_index_skipping_(1, &seen), Some(0) );
1693 assert_eq!( list._unweight_index_skipping_(2, &seen), Some(2) );
1694 assert_eq!( list._unweight_index_skipping_(3, &seen), Some(2) );
1695 assert_eq!( list._unweight_index_skipping_(4, &seen), Some(2) );
1696 assert_eq!( list._unweight_index_skipping_(5, &seen), Some(2) );
1697 assert_eq!( list._unweight_index_skipping_(6, &seen), Some(2) );
1698 }
1699}