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