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