Skip to main content

rusttorch_data/
sampler.rs

1use std::{num::NonZeroUsize, ops::Range, vec::IntoIter};
2
3use rand::{
4    Rng, SeedableRng,
5    distributions::{Distribution, Open01, WeightedIndex},
6    seq::SliceRandom,
7};
8use rand_chacha::ChaCha12Rng;
9use rusttorch_core::{Result, RustTorchError};
10use serde::{Deserialize, Serialize, de::DeserializeOwned};
11
12/// Serialized cursor for [`SequentialSampler`].
13#[derive(Clone, Debug, Deserialize, Serialize)]
14pub struct SequentialSamplerState {
15    /// Configured index count.
16    pub length: u64,
17    /// Active epoch.
18    pub epoch: u64,
19    /// Next index position.
20    pub position: u64,
21}
22
23/// Replacement mode stored by [`RandomSamplerState`].
24#[derive(Clone, Copy, Debug, Deserialize, Eq, PartialEq, Serialize)]
25pub enum RandomReplacement {
26    /// Draw each generated index independently.
27    With,
28    /// Generate successive shuffled permutations.
29    Without,
30}
31
32/// Serialized configuration and cursor for [`RandomSampler`].
33#[derive(Clone, Debug, Deserialize, Serialize)]
34pub struct RandomSamplerState {
35    /// Configured index range length.
36    pub length: u64,
37    /// Number of generated occurrences.
38    pub num_samples: u64,
39    /// Replacement policy.
40    pub replacement: RandomReplacement,
41    /// Base seed.
42    pub seed: u64,
43    /// Active epoch.
44    pub epoch: u64,
45    /// Next occurrence position.
46    pub position: u64,
47}
48
49/// Serialized configuration and cursor for [`SubsetRandomSampler`].
50#[derive(Clone, Debug, Deserialize, Serialize)]
51pub struct SubsetRandomSamplerState {
52    /// Exact caller-supplied subset indices.
53    pub indices: Vec<u64>,
54    /// Base seed.
55    pub seed: u64,
56    /// Active epoch.
57    pub epoch: u64,
58    /// Next occurrence position.
59    pub position: u64,
60}
61
62/// Serialized configuration and cursor for [`WeightedRandomSampler`].
63#[derive(Clone, Debug, Deserialize, Serialize)]
64pub struct WeightedRandomSamplerState {
65    /// Exact IEEE-754 bit patterns of the configured weights.
66    pub weight_bits: Vec<u64>,
67    /// Number of generated occurrences.
68    pub num_samples: u64,
69    /// Replacement policy.
70    pub replacement: bool,
71    /// Base seed.
72    pub seed: u64,
73    /// Active epoch.
74    pub epoch: u64,
75    /// Next occurrence position.
76    pub position: u64,
77}
78
79/// Serialized configuration and cursor for [`DistributedSampler`].
80#[derive(Clone, Debug, Deserialize, Serialize)]
81pub struct DistributedSamplerState {
82    /// Global dataset length.
83    pub length: u64,
84    /// Replica count.
85    pub replicas: u64,
86    /// This sampler's rank.
87    pub rank: u64,
88    /// Whether the global indices are shuffled.
89    pub shuffle: bool,
90    /// Base seed.
91    pub seed: u64,
92    /// Whether the global tail is truncated.
93    pub drop_last: bool,
94    /// Active epoch.
95    pub epoch: u64,
96    /// Next rank-local occurrence position.
97    pub position: u64,
98}
99
100/// Serialized cursor for a compositional [`BatchSampler`].
101#[derive(Clone, Debug, Deserialize, Serialize)]
102pub struct BatchSamplerState<S> {
103    /// Inner sampler configuration and cursor.
104    pub sampler: S,
105    /// Configured batch size.
106    pub batch_size: u64,
107    /// Whether an incomplete final batch is omitted.
108    pub drop_last: bool,
109    /// Next visible batch number.
110    pub next_batch: u64,
111    /// Next logical sample occurrence.
112    pub next_logical_sample: u64,
113}
114
115#[doc(hidden)]
116#[derive(Clone, Copy, Debug, Eq, PartialEq)]
117pub struct DistributedConfiguration {
118    pub(crate) replicas: usize,
119    pub(crate) rank: usize,
120    pub(crate) shuffle: bool,
121    pub(crate) seed: u64,
122    pub(crate) drop_last: bool,
123}
124
125#[doc(hidden)]
126pub trait SamplerCheckpoint: Sampler {
127    type State: Clone + Serialize + DeserializeOwned;
128
129    fn kind(&self) -> &'static str;
130    /// Derives the stable sampler kind from owned checkpoint state only.
131    fn checkpoint_kind_from_state(state: &Self::State) -> String;
132    fn checkpoint_state(&self, position: u64) -> Result<Self::State>;
133    fn validate_checkpoint_state(
134        &self,
135        state: &Self::State,
136        epoch: u64,
137        position: u64,
138    ) -> Result<()>;
139    fn restore_checkpoint_iter_validated(&mut self, state: &Self::State) -> Self::Iter;
140
141    fn distributed_configuration(&self) -> Option<DistributedConfiguration> {
142        None
143    }
144
145    /// Derives distributed identity from owned checkpoint state only.
146    fn checkpoint_distributed_configuration_from_state(
147        state: &Self::State,
148    ) -> Result<Option<DistributedConfiguration>>;
149}
150
151#[doc(hidden)]
152pub trait BatchSourceCheckpoint: BatchSource {
153    type State: Clone + Serialize + DeserializeOwned;
154
155    fn kind(&self) -> String;
156    /// Derives the stable batch-source kind from owned checkpoint state only.
157    fn checkpoint_kind_from_state(state: &Self::State) -> String;
158    fn checkpoint_state(&self, next_batch: u64, next_logical_sample: u64) -> Result<Self::State>;
159    fn validate_checkpoint_state(
160        &self,
161        state: &Self::State,
162        epoch: u64,
163        next_batch: u64,
164        next_logical_sample: u64,
165    ) -> Result<()>;
166    fn restore_checkpoint_iter_validated(&mut self, state: &Self::State) -> Self::Iter;
167    fn distributed_configuration(&self) -> Option<DistributedConfiguration>;
168    /// Derives distributed identity from owned checkpoint state only.
169    fn checkpoint_distributed_configuration_from_state(
170        state: &Self::State,
171    ) -> Result<Option<DistributedConfiguration>>;
172}
173
174/// A reusable, epoch-aware source of finite sample indices.
175///
176/// Every call to [`Sampler::iter`] creates a fresh iterator. An exact length
177/// is optional and is never required for iteration.
178pub trait Sampler {
179    /// A fresh finite iterator over sample indices.
180    type Iter: Iterator<Item = usize>;
181
182    /// Creates an iterator for the current epoch.
183    fn iter(&self) -> Self::Iter;
184
185    /// Returns the exact number of indices when it is known.
186    fn exact_len(&self) -> Option<usize> {
187        None
188    }
189
190    /// Returns the current epoch.
191    fn epoch(&self) -> u64;
192
193    /// Selects the epoch used by future iterators.
194    fn set_epoch(&mut self, epoch: u64);
195}
196
197/// A reusable, epoch-aware source of finite index batches.
198///
199/// Every call to [`BatchSource::iter`] creates a fresh iterator. An exact
200/// number of batches is optional and is never required for iteration.
201pub trait BatchSource {
202    /// A fresh finite iterator over index batches.
203    type Iter: Iterator<Item = Vec<usize>>;
204
205    /// Creates an iterator for the current epoch.
206    fn iter(&self) -> Self::Iter;
207
208    /// Returns the exact number of batches when it is known.
209    fn exact_len(&self) -> Option<usize> {
210        None
211    }
212
213    /// Returns the current epoch.
214    fn epoch(&self) -> u64;
215
216    /// Selects the epoch used by future iterators.
217    fn set_epoch(&mut self, epoch: u64);
218}
219
220/// Adapts an epoch-aware iterator factory into a reusable [`Sampler`].
221pub struct FnSampler<F> {
222    exact_len: Option<usize>,
223    epoch: u64,
224    make_iter: F,
225}
226
227impl<F> FnSampler<F> {
228    /// Creates a sampler with an optional exact index count.
229    pub fn new(exact_len: Option<usize>, make_iter: F) -> Self {
230        Self {
231            exact_len,
232            epoch: 0,
233            make_iter,
234        }
235    }
236}
237
238impl<F, I> Sampler for FnSampler<F>
239where
240    F: Fn(u64) -> I,
241    I: Iterator<Item = usize>,
242{
243    type Iter = I;
244
245    fn iter(&self) -> Self::Iter {
246        (self.make_iter)(self.epoch)
247    }
248
249    fn exact_len(&self) -> Option<usize> {
250        self.exact_len
251    }
252
253    fn epoch(&self) -> u64 {
254        self.epoch
255    }
256
257    fn set_epoch(&mut self, epoch: u64) {
258        self.epoch = epoch;
259    }
260}
261
262/// Adapts an epoch-aware batch-iterator factory into a reusable [`BatchSource`].
263pub struct FnBatchSource<F> {
264    exact_len: Option<usize>,
265    epoch: u64,
266    make_iter: F,
267}
268
269impl<F> FnBatchSource<F> {
270    /// Creates a batch source with an optional exact batch count.
271    pub fn new(exact_len: Option<usize>, make_iter: F) -> Self {
272        Self {
273            exact_len,
274            epoch: 0,
275            make_iter,
276        }
277    }
278}
279
280impl<F, I> BatchSource for FnBatchSource<F>
281where
282    F: Fn(u64) -> I,
283    I: Iterator<Item = Vec<usize>>,
284{
285    type Iter = I;
286
287    fn iter(&self) -> Self::Iter {
288        (self.make_iter)(self.epoch)
289    }
290
291    fn exact_len(&self) -> Option<usize> {
292        self.exact_len
293    }
294
295    fn epoch(&self) -> u64 {
296        self.epoch
297    }
298
299    fn set_epoch(&mut self, epoch: u64) {
300        self.epoch = epoch;
301    }
302}
303
304/// Groups sampler indices into fixed-size batches.
305///
306/// The sampler remains directly iterable when `S` is an iterator. When `S`
307/// implements [`Sampler`], this type also implements [`BatchSource`] and
308/// creates fresh batches for every iteration.
309///
310/// ```
311/// use rusttorch_data::BatchSampler;
312///
313/// let batches = BatchSampler::new(0..5, 2, false)
314///     .expect("batch size is nonzero")
315///     .collect::<Vec<_>>();
316/// assert_eq!(batches, vec![vec![0, 1], vec![2, 3], vec![4]]);
317/// ```
318pub struct BatchSampler<S> {
319    sampler: S,
320    batch_size: usize,
321    drop_last: bool,
322}
323
324impl<S> BatchSampler<S> {
325    /// Creates a batch sampler.
326    ///
327    /// A short final batch is omitted when `drop_last` is `true`.
328    ///
329    /// # Errors
330    ///
331    /// Returns [`RustTorchError::InvalidConfiguration`] when `batch_size` is
332    /// zero or cannot describe an allocatable index batch.
333    pub fn new(sampler: S, batch_size: usize, drop_last: bool) -> Result<Self> {
334        let batch_size = validate_batch_size(batch_size)?;
335        Ok(Self::from_validated(sampler, batch_size, drop_last))
336    }
337
338    pub(crate) fn from_validated(sampler: S, batch_size: NonZeroUsize, drop_last: bool) -> Self {
339        Self {
340            sampler,
341            batch_size: batch_size.get(),
342            drop_last,
343        }
344    }
345}
346
347impl<S> BatchSampler<S>
348where
349    S: Iterator<Item = usize>,
350{
351    /// Returns the exact number of remaining batches when the sampler reports
352    /// an exact remaining length.
353    pub fn exact_len(&self) -> Option<usize> {
354        let (lower, upper) = self.sampler.size_hint();
355        (upper == Some(lower)).then(|| batch_count(lower, self.batch_size, self.drop_last))
356    }
357}
358
359impl<S> Iterator for BatchSampler<S>
360where
361    S: Iterator<Item = usize>,
362{
363    type Item = Vec<usize>;
364
365    fn next(&mut self) -> Option<Self::Item> {
366        let first = self.sampler.next()?;
367        let mut batch = try_vec(self.batch_size, "batch_size")
368            .expect("batch storage dimensions were validated during construction");
369        batch.push(first);
370        batch.extend(self.sampler.by_ref().take(self.batch_size - 1));
371        (!self.drop_last || batch.len() == self.batch_size).then_some(batch)
372    }
373
374    fn size_hint(&self) -> (usize, Option<usize>) {
375        let (lower, upper) = self.sampler.size_hint();
376        (
377            batch_count(lower, self.batch_size, self.drop_last),
378            upper.map(|length| batch_count(length, self.batch_size, self.drop_last)),
379        )
380    }
381}
382
383impl<S> BatchSource for BatchSampler<S>
384where
385    S: Sampler,
386{
387    type Iter = BatchSampler<S::Iter>;
388
389    fn iter(&self) -> Self::Iter {
390        BatchSampler::new(self.sampler.iter(), self.batch_size, self.drop_last)
391            .expect("batch storage dimensions were validated during construction")
392    }
393
394    fn exact_len(&self) -> Option<usize> {
395        self.sampler
396            .exact_len()
397            .map(|length| batch_count(length, self.batch_size, self.drop_last))
398    }
399
400    fn epoch(&self) -> u64 {
401        self.sampler.epoch()
402    }
403
404    fn set_epoch(&mut self, epoch: u64) {
405        self.sampler.set_epoch(epoch);
406    }
407}
408
409/// An allocation-free sampler that yields indices in ascending order.
410pub struct SequentialSampler {
411    length: usize,
412    epoch: u64,
413    indices: Range<usize>,
414}
415
416impl SequentialSampler {
417    /// Creates a sampler for indices `0..length`.
418    pub fn new(length: usize) -> Self {
419        Self {
420            length,
421            epoch: 0,
422            indices: 0..length,
423        }
424    }
425}
426
427impl Sampler for SequentialSampler {
428    type Iter = Range<usize>;
429
430    fn iter(&self) -> Self::Iter {
431        0..self.length
432    }
433
434    fn exact_len(&self) -> Option<usize> {
435        Some(self.length)
436    }
437
438    fn epoch(&self) -> u64 {
439        self.epoch
440    }
441
442    fn set_epoch(&mut self, epoch: u64) {
443        self.epoch = epoch;
444        self.indices = 0..self.length;
445    }
446}
447
448impl Iterator for SequentialSampler {
449    type Item = usize;
450
451    fn next(&mut self) -> Option<Self::Item> {
452        self.indices.next()
453    }
454}
455
456#[derive(Clone, Copy)]
457enum Replacement {
458    With,
459    Without,
460}
461
462/// A seeded sampler over a finite index range.
463///
464/// Shuffling uses sampler-local ChaCha12 state, so it does not alter
465/// LibTorch's global random state. Its sequence intentionally does not claim
466/// exact PyTorch Philox parity.
467pub struct RandomSampler {
468    length: usize,
469    num_samples: usize,
470    replacement: Replacement,
471    seed: u64,
472    epoch: u64,
473    indices: IntoIter<usize>,
474}
475
476impl RandomSampler {
477    /// Creates a reproducible shuffled permutation of `0..length`.
478    ///
479    /// # Errors
480    ///
481    /// Returns [`RustTorchError::InvalidConfiguration`] when `length` is zero
482    /// or storage for the permutation cannot be reserved.
483    pub fn new(length: usize, seed: u64) -> Result<Self> {
484        Self::without_replacement(length, length, seed)
485    }
486
487    /// Creates a sampler that draws `num_samples` indices with replacement.
488    ///
489    /// # Errors
490    ///
491    /// Returns [`RustTorchError::InvalidConfiguration`] when `length` or
492    /// `num_samples` is zero or requested sampler storage cannot be reserved.
493    pub fn with_replacement(length: usize, num_samples: usize, seed: u64) -> Result<Self> {
494        Self::build(length, num_samples, Replacement::With, seed)
495    }
496
497    /// Creates a sampler that draws shuffled indices without replacement.
498    ///
499    /// Counts larger than `length` concatenate independent complete
500    /// permutations and one final permutation prefix.
501    ///
502    /// # Errors
503    ///
504    /// Returns [`RustTorchError::InvalidConfiguration`] when `length` or
505    /// `num_samples` is zero or requested sampler storage cannot be reserved.
506    pub fn without_replacement(length: usize, num_samples: usize, seed: u64) -> Result<Self> {
507        Self::build(length, num_samples, Replacement::Without, seed)
508    }
509
510    fn build(
511        length: usize,
512        num_samples: usize,
513        replacement: Replacement,
514        seed: u64,
515    ) -> Result<Self> {
516        validate_positive(length, "length")?;
517        validate_positive(num_samples, "num_samples")?;
518        let indices = random_indices(length, num_samples, replacement, seed)?.into_iter();
519        Ok(Self {
520            length,
521            num_samples,
522            replacement,
523            seed,
524            epoch: 0,
525            indices,
526        })
527    }
528
529    fn indices_for_epoch(&self) -> Vec<usize> {
530        random_indices(
531            self.length,
532            self.num_samples,
533            self.replacement,
534            epoch_seed(self.seed, self.epoch),
535        )
536        .expect("sampler storage dimensions were validated during construction")
537    }
538}
539
540impl Sampler for RandomSampler {
541    type Iter = IntoIter<usize>;
542
543    fn iter(&self) -> Self::Iter {
544        self.indices_for_epoch().into_iter()
545    }
546
547    fn exact_len(&self) -> Option<usize> {
548        Some(self.num_samples)
549    }
550
551    fn epoch(&self) -> u64 {
552        self.epoch
553    }
554
555    fn set_epoch(&mut self, epoch: u64) {
556        self.epoch = epoch;
557        self.indices = self.indices_for_epoch().into_iter();
558    }
559}
560
561impl Iterator for RandomSampler {
562    type Item = usize;
563
564    fn next(&mut self) -> Option<Self::Item> {
565        self.indices.next()
566    }
567}
568
569/// A seeded sampler that shuffles a caller-provided subset of indices.
570pub struct SubsetRandomSampler {
571    source: Vec<usize>,
572    seed: u64,
573    epoch: u64,
574    indices: IntoIter<usize>,
575}
576
577impl SubsetRandomSampler {
578    /// Creates a sampler that yields each supplied index once.
579    ///
580    /// # Errors
581    ///
582    /// Returns [`RustTorchError::InvalidConfiguration`] when storage for a
583    /// shuffled copy of the supplied indices cannot be reserved.
584    pub fn new(indices: Vec<usize>, seed: u64) -> Result<Self> {
585        let shuffled = shuffled_copy(&indices, seed)?.into_iter();
586        Ok(Self {
587            source: indices,
588            seed,
589            epoch: 0,
590            indices: shuffled,
591        })
592    }
593
594    fn indices_for_epoch(&self) -> Vec<usize> {
595        shuffled_copy(&self.source, epoch_seed(self.seed, self.epoch))
596            .expect("sampler storage dimensions were validated during construction")
597    }
598}
599
600impl Sampler for SubsetRandomSampler {
601    type Iter = IntoIter<usize>;
602
603    fn iter(&self) -> Self::Iter {
604        self.indices_for_epoch().into_iter()
605    }
606
607    fn exact_len(&self) -> Option<usize> {
608        Some(self.source.len())
609    }
610
611    fn epoch(&self) -> u64 {
612        self.epoch
613    }
614
615    fn set_epoch(&mut self, epoch: u64) {
616        self.epoch = epoch;
617        self.indices = self.indices_for_epoch().into_iter();
618    }
619}
620
621impl Iterator for SubsetRandomSampler {
622    type Item = usize;
623
624    fn next(&mut self) -> Option<Self::Item> {
625        self.indices.next()
626    }
627}
628
629/// A seeded sampler that draws indices according to nonnegative weights.
630pub struct WeightedRandomSampler {
631    weights: Vec<f64>,
632    num_samples: usize,
633    replacement: bool,
634    seed: u64,
635    epoch: u64,
636    distribution: WeightedIndex<f64>,
637    indices: IntoIter<usize>,
638}
639
640impl WeightedRandomSampler {
641    /// Creates a weighted sampler.
642    ///
643    /// Without replacement, `num_samples` may be at most `weights.len()`.
644    /// Positive-weight entries are selected first; deterministically shuffled
645    /// zero-weight entries fill any remaining positions.
646    ///
647    /// # Errors
648    ///
649    /// Returns [`RustTorchError::InvalidConfiguration`] when weights are
650    /// empty, non-finite, negative, or have no positive finite total; when
651    /// `num_samples` is zero; when a without-replacement count exceeds the
652    /// number of weights; or when requested sampler storage cannot be
653    /// reserved.
654    pub fn new(
655        weights: Vec<f64>,
656        num_samples: usize,
657        replacement: bool,
658        seed: u64,
659    ) -> Result<Self> {
660        validate_weights(&weights)?;
661        validate_positive(num_samples, "num_samples")?;
662        if !replacement && num_samples > weights.len() {
663            return Err(invalid_configuration(
664                "num_samples",
665                "must not exceed the number of weights without replacement",
666            ));
667        }
668        let distribution = WeightedIndex::new(&weights).map_err(|error| {
669            invalid_configuration("weights", format!("cannot form a distribution: {error}"))
670        })?;
671        let indices =
672            weighted_indices(&weights, num_samples, replacement, seed, &distribution)?.into_iter();
673        Ok(Self {
674            weights,
675            num_samples,
676            replacement,
677            seed,
678            epoch: 0,
679            distribution,
680            indices,
681        })
682    }
683
684    fn indices_for_epoch(&self) -> Vec<usize> {
685        weighted_indices(
686            &self.weights,
687            self.num_samples,
688            self.replacement,
689            epoch_seed(self.seed, self.epoch),
690            &self.distribution,
691        )
692        .expect("sampler storage dimensions were validated during construction")
693    }
694}
695
696impl Sampler for WeightedRandomSampler {
697    type Iter = IntoIter<usize>;
698
699    fn iter(&self) -> Self::Iter {
700        self.indices_for_epoch().into_iter()
701    }
702
703    fn exact_len(&self) -> Option<usize> {
704        Some(self.num_samples)
705    }
706
707    fn epoch(&self) -> u64 {
708        self.epoch
709    }
710
711    fn set_epoch(&mut self, epoch: u64) {
712        self.epoch = epoch;
713        self.indices = self.indices_for_epoch().into_iter();
714    }
715}
716
717impl Iterator for WeightedRandomSampler {
718    type Item = usize;
719
720    fn next(&mut self) -> Option<Self::Item> {
721        self.indices.next()
722    }
723}
724
725/// Deterministically shards a finite index range across distributed ranks.
726///
727/// When `drop_last` is false, indices are cyclically padded so every rank has
728/// the same length. When it is true, the global sequence is truncated to a
729/// multiple of the replica count. Optional shuffling uses sampler-local
730/// ChaCha12 state and does not alter LibTorch's global random state.
731///
732/// ```
733/// use rusttorch_data::DistributedSampler;
734///
735/// let rank_one = DistributedSampler::new(5, 2, 1, false, 0, false)
736///     .expect("replica and rank are valid")
737///     .collect::<Vec<_>>();
738/// assert_eq!(rank_one, vec![1, 3, 0]);
739/// ```
740pub struct DistributedSampler {
741    length: usize,
742    replicas: usize,
743    rank: usize,
744    shuffle: bool,
745    seed: u64,
746    drop_last: bool,
747    epoch: u64,
748    num_samples: usize,
749    indices: IntoIter<usize>,
750}
751
752impl DistributedSampler {
753    /// Creates a rank-aware sampler over `0..length`.
754    ///
755    /// Empty datasets are accepted and yield no indices on every valid rank.
756    ///
757    /// # Errors
758    ///
759    /// Returns [`RustTorchError::InvalidConfiguration`] when `replicas` is
760    /// zero, `rank` is outside `0..replicas`, padding arithmetic overflows, or
761    /// requested sampler storage cannot be reserved.
762    pub fn new(
763        length: usize,
764        replicas: usize,
765        rank: usize,
766        shuffle: bool,
767        seed: u64,
768        drop_last: bool,
769    ) -> Result<Self> {
770        validate_positive(replicas, "replicas")?;
771        if rank >= replicas {
772            return Err(invalid_configuration(
773                "rank",
774                "must be less than the replica count",
775            ));
776        }
777        let num_samples = distributed_sample_count(length, replicas, drop_last)?;
778        let indices = distributed_indices(
779            length,
780            replicas,
781            rank,
782            shuffle,
783            seed,
784            drop_last,
785            num_samples,
786        )?
787        .into_iter();
788        Ok(Self {
789            length,
790            replicas,
791            rank,
792            shuffle,
793            seed,
794            drop_last,
795            epoch: 0,
796            num_samples,
797            indices,
798        })
799    }
800
801    /// Returns the number of indices assigned to this rank.
802    pub fn len(&self) -> usize {
803        self.num_samples
804    }
805
806    /// Returns `true` when this rank has no indices.
807    pub fn is_empty(&self) -> bool {
808        self.num_samples == 0
809    }
810
811    /// Returns the current epoch.
812    pub fn epoch(&self) -> u64 {
813        self.epoch
814    }
815
816    /// Returns the number of indices consumed by direct iteration.
817    pub fn position(&self) -> usize {
818        self.num_samples - self.indices.len()
819    }
820
821    /// Selects the epoch and resets direct iteration to its beginning.
822    pub fn set_epoch(&mut self, epoch: u64) {
823        self.epoch = epoch;
824        self.indices = self.indices_for_epoch().into_iter();
825    }
826
827    fn indices_for_epoch(&self) -> Vec<usize> {
828        distributed_indices(
829            self.length,
830            self.replicas,
831            self.rank,
832            self.shuffle,
833            epoch_seed(self.seed, self.epoch),
834            self.drop_last,
835            self.num_samples,
836        )
837        .expect("distributed sampler dimensions were validated during construction")
838    }
839}
840
841impl Sampler for DistributedSampler {
842    type Iter = IntoIter<usize>;
843
844    fn iter(&self) -> Self::Iter {
845        self.indices_for_epoch().into_iter()
846    }
847
848    fn exact_len(&self) -> Option<usize> {
849        Some(self.num_samples)
850    }
851
852    fn epoch(&self) -> u64 {
853        self.epoch()
854    }
855
856    fn set_epoch(&mut self, epoch: u64) {
857        self.set_epoch(epoch);
858    }
859}
860
861impl Iterator for DistributedSampler {
862    type Item = usize;
863
864    fn next(&mut self) -> Option<Self::Item> {
865        self.indices.next()
866    }
867
868    fn size_hint(&self) -> (usize, Option<usize>) {
869        self.indices.size_hint()
870    }
871}
872
873impl ExactSizeIterator for DistributedSampler {}
874
875impl SamplerCheckpoint for SequentialSampler {
876    type State = SequentialSamplerState;
877
878    fn kind(&self) -> &'static str {
879        "sequential"
880    }
881
882    fn checkpoint_kind_from_state(_state: &Self::State) -> String {
883        "sequential".to_owned()
884    }
885
886    fn checkpoint_state(&self, position: u64) -> Result<Self::State> {
887        let length = usize_to_u64(self.length, "sampler")?;
888        validate_position(position, length)?;
889        Ok(SequentialSamplerState {
890            length,
891            epoch: self.epoch,
892            position,
893        })
894    }
895
896    fn validate_checkpoint_state(
897        &self,
898        state: &Self::State,
899        epoch: u64,
900        position: u64,
901    ) -> Result<()> {
902        require_equal(
903            "sampler",
904            state.length,
905            usize_to_u64(self.length, "sampler")?,
906        )?;
907        validate_epoch_position(state.epoch, state.position, epoch, position)?;
908        validate_position(state.position, state.length)
909    }
910
911    fn restore_checkpoint_iter_validated(&mut self, state: &Self::State) -> Self::Iter {
912        self.set_epoch(state.epoch);
913        let position = usize::try_from(state.position)
914            .expect("validated sequential sampler position fits usize");
915        position..self.length
916    }
917
918    fn checkpoint_distributed_configuration_from_state(
919        _state: &Self::State,
920    ) -> Result<Option<DistributedConfiguration>> {
921        Ok(None)
922    }
923}
924
925impl SamplerCheckpoint for RandomSampler {
926    type State = RandomSamplerState;
927
928    fn kind(&self) -> &'static str {
929        match self.replacement {
930            Replacement::With => "random_replacement",
931            Replacement::Without => "random",
932        }
933    }
934
935    fn checkpoint_kind_from_state(state: &Self::State) -> String {
936        match state.replacement {
937            RandomReplacement::With => "random_replacement",
938            RandomReplacement::Without => "random",
939        }
940        .to_owned()
941    }
942
943    fn checkpoint_state(&self, position: u64) -> Result<Self::State> {
944        let num_samples = usize_to_u64(self.num_samples, "sampler")?;
945        validate_position(position, num_samples)?;
946        Ok(RandomSamplerState {
947            length: usize_to_u64(self.length, "sampler")?,
948            num_samples,
949            replacement: match self.replacement {
950                Replacement::With => RandomReplacement::With,
951                Replacement::Without => RandomReplacement::Without,
952            },
953            seed: self.seed,
954            epoch: self.epoch,
955            position,
956        })
957    }
958
959    fn validate_checkpoint_state(
960        &self,
961        state: &Self::State,
962        epoch: u64,
963        position: u64,
964    ) -> Result<()> {
965        require_equal(
966            "sampler",
967            state.length,
968            usize_to_u64(self.length, "sampler")?,
969        )?;
970        require_equal(
971            "sampler",
972            state.num_samples,
973            usize_to_u64(self.num_samples, "sampler")?,
974        )?;
975        let replacement = match self.replacement {
976            Replacement::With => RandomReplacement::With,
977            Replacement::Without => RandomReplacement::Without,
978        };
979        require_equal("sampler", state.replacement, replacement)?;
980        require_equal("sampler", state.seed, self.seed)?;
981        validate_epoch_position(state.epoch, state.position, epoch, position)?;
982        validate_position(state.position, state.num_samples)
983    }
984
985    fn restore_checkpoint_iter_validated(&mut self, state: &Self::State) -> Self::Iter {
986        self.set_epoch(state.epoch);
987        let mut iterator = self.iter();
988        advance(&mut iterator, state.position)
989            .expect("validated random sampler cursor is regenerable");
990        iterator
991    }
992
993    fn checkpoint_distributed_configuration_from_state(
994        _state: &Self::State,
995    ) -> Result<Option<DistributedConfiguration>> {
996        Ok(None)
997    }
998}
999
1000impl SamplerCheckpoint for SubsetRandomSampler {
1001    type State = SubsetRandomSamplerState;
1002
1003    fn kind(&self) -> &'static str {
1004        "subset_random"
1005    }
1006
1007    fn checkpoint_kind_from_state(_state: &Self::State) -> String {
1008        "subset_random".to_owned()
1009    }
1010
1011    fn checkpoint_state(&self, position: u64) -> Result<Self::State> {
1012        let length = usize_to_u64(self.source.len(), "sampler")?;
1013        validate_position(position, length)?;
1014        Ok(SubsetRandomSamplerState {
1015            indices: self
1016                .source
1017                .iter()
1018                .copied()
1019                .map(|index| usize_to_u64(index, "sampler"))
1020                .collect::<Result<Vec<_>>>()?,
1021            seed: self.seed,
1022            epoch: self.epoch,
1023            position,
1024        })
1025    }
1026
1027    fn validate_checkpoint_state(
1028        &self,
1029        state: &Self::State,
1030        epoch: u64,
1031        position: u64,
1032    ) -> Result<()> {
1033        let expected = self
1034            .source
1035            .iter()
1036            .copied()
1037            .map(|index| usize_to_u64(index, "sampler"))
1038            .collect::<Result<Vec<_>>>()?;
1039        require_equal("sampler", &state.indices, &expected)?;
1040        require_equal("sampler", state.seed, self.seed)?;
1041        validate_epoch_position(state.epoch, state.position, epoch, position)?;
1042        validate_position(
1043            state.position,
1044            usize_to_u64(state.indices.len(), "sampler")?,
1045        )
1046    }
1047
1048    fn restore_checkpoint_iter_validated(&mut self, state: &Self::State) -> Self::Iter {
1049        self.set_epoch(state.epoch);
1050        let mut iterator = self.iter();
1051        advance(&mut iterator, state.position)
1052            .expect("validated subset sampler cursor is regenerable");
1053        iterator
1054    }
1055
1056    fn checkpoint_distributed_configuration_from_state(
1057        _state: &Self::State,
1058    ) -> Result<Option<DistributedConfiguration>> {
1059        Ok(None)
1060    }
1061}
1062
1063impl SamplerCheckpoint for WeightedRandomSampler {
1064    type State = WeightedRandomSamplerState;
1065
1066    fn kind(&self) -> &'static str {
1067        if self.replacement {
1068            "weighted_random_replacement"
1069        } else {
1070            "weighted_random"
1071        }
1072    }
1073
1074    fn checkpoint_kind_from_state(state: &Self::State) -> String {
1075        if state.replacement {
1076            "weighted_random_replacement"
1077        } else {
1078            "weighted_random"
1079        }
1080        .to_owned()
1081    }
1082
1083    fn checkpoint_state(&self, position: u64) -> Result<Self::State> {
1084        let num_samples = usize_to_u64(self.num_samples, "sampler")?;
1085        validate_position(position, num_samples)?;
1086        Ok(WeightedRandomSamplerState {
1087            weight_bits: self.weights.iter().map(|weight| weight.to_bits()).collect(),
1088            num_samples,
1089            replacement: self.replacement,
1090            seed: self.seed,
1091            epoch: self.epoch,
1092            position,
1093        })
1094    }
1095
1096    fn validate_checkpoint_state(
1097        &self,
1098        state: &Self::State,
1099        epoch: u64,
1100        position: u64,
1101    ) -> Result<()> {
1102        let expected = self
1103            .weights
1104            .iter()
1105            .map(|weight| weight.to_bits())
1106            .collect::<Vec<_>>();
1107        require_equal("sampler", &state.weight_bits, &expected)?;
1108        require_equal(
1109            "sampler",
1110            state.num_samples,
1111            usize_to_u64(self.num_samples, "sampler")?,
1112        )?;
1113        require_equal("sampler", state.replacement, self.replacement)?;
1114        require_equal("sampler", state.seed, self.seed)?;
1115        validate_epoch_position(state.epoch, state.position, epoch, position)?;
1116        validate_position(state.position, state.num_samples)
1117    }
1118
1119    fn restore_checkpoint_iter_validated(&mut self, state: &Self::State) -> Self::Iter {
1120        self.set_epoch(state.epoch);
1121        let mut iterator = self.iter();
1122        advance(&mut iterator, state.position)
1123            .expect("validated weighted sampler cursor is regenerable");
1124        iterator
1125    }
1126
1127    fn checkpoint_distributed_configuration_from_state(
1128        _state: &Self::State,
1129    ) -> Result<Option<DistributedConfiguration>> {
1130        Ok(None)
1131    }
1132}
1133
1134impl SamplerCheckpoint for DistributedSampler {
1135    type State = DistributedSamplerState;
1136
1137    fn kind(&self) -> &'static str {
1138        "distributed"
1139    }
1140
1141    fn checkpoint_kind_from_state(_state: &Self::State) -> String {
1142        "distributed".to_owned()
1143    }
1144
1145    fn checkpoint_state(&self, position: u64) -> Result<Self::State> {
1146        let num_samples = usize_to_u64(self.num_samples, "sampler")?;
1147        validate_position(position, num_samples)?;
1148        Ok(DistributedSamplerState {
1149            length: usize_to_u64(self.length, "sampler")?,
1150            replicas: usize_to_u64(self.replicas, "sampler")?,
1151            rank: usize_to_u64(self.rank, "sampler")?,
1152            shuffle: self.shuffle,
1153            seed: self.seed,
1154            drop_last: self.drop_last,
1155            epoch: self.epoch,
1156            position,
1157        })
1158    }
1159
1160    fn validate_checkpoint_state(
1161        &self,
1162        state: &Self::State,
1163        epoch: u64,
1164        position: u64,
1165    ) -> Result<()> {
1166        require_equal(
1167            "sampler",
1168            state.length,
1169            usize_to_u64(self.length, "sampler")?,
1170        )?;
1171        require_equal(
1172            "sampler",
1173            state.replicas,
1174            usize_to_u64(self.replicas, "sampler")?,
1175        )?;
1176        require_equal("sampler", state.rank, usize_to_u64(self.rank, "sampler")?)?;
1177        require_equal("sampler", state.shuffle, self.shuffle)?;
1178        require_equal("sampler", state.seed, self.seed)?;
1179        require_equal("sampler", state.drop_last, self.drop_last)?;
1180        validate_epoch_position(state.epoch, state.position, epoch, position)?;
1181        validate_position(state.position, usize_to_u64(self.num_samples, "sampler")?)
1182    }
1183
1184    fn restore_checkpoint_iter_validated(&mut self, state: &Self::State) -> Self::Iter {
1185        self.set_epoch(state.epoch);
1186        let mut iterator = self.iter();
1187        advance(&mut iterator, state.position)
1188            .expect("validated distributed sampler cursor is regenerable");
1189        iterator
1190    }
1191
1192    fn distributed_configuration(&self) -> Option<DistributedConfiguration> {
1193        Some(DistributedConfiguration {
1194            replicas: self.replicas,
1195            rank: self.rank,
1196            shuffle: self.shuffle,
1197            seed: self.seed,
1198            drop_last: self.drop_last,
1199        })
1200    }
1201
1202    fn checkpoint_distributed_configuration_from_state(
1203        state: &Self::State,
1204    ) -> Result<Option<DistributedConfiguration>> {
1205        Ok(Some(DistributedConfiguration {
1206            replicas: u64_to_usize(state.replicas, "sampler")?,
1207            rank: u64_to_usize(state.rank, "sampler")?,
1208            shuffle: state.shuffle,
1209            seed: state.seed,
1210            drop_last: state.drop_last,
1211        }))
1212    }
1213}
1214
1215impl<S> BatchSourceCheckpoint for BatchSampler<S>
1216where
1217    S: SamplerCheckpoint,
1218{
1219    type State = BatchSamplerState<S::State>;
1220
1221    fn kind(&self) -> String {
1222        format!("batch_sampler/{}", self.sampler.kind())
1223    }
1224
1225    fn checkpoint_kind_from_state(state: &Self::State) -> String {
1226        format!(
1227            "batch_sampler/{}",
1228            S::checkpoint_kind_from_state(&state.sampler)
1229        )
1230    }
1231
1232    fn checkpoint_state(&self, next_batch: u64, next_logical_sample: u64) -> Result<Self::State> {
1233        validate_batch_boundary(
1234            self.sampler.exact_len(),
1235            self.batch_size,
1236            self.drop_last,
1237            next_batch,
1238            next_logical_sample,
1239        )?;
1240        Ok(BatchSamplerState {
1241            sampler: self.sampler.checkpoint_state(next_logical_sample)?,
1242            batch_size: usize_to_u64(self.batch_size, "batch_sampler")?,
1243            drop_last: self.drop_last,
1244            next_batch,
1245            next_logical_sample,
1246        })
1247    }
1248
1249    fn validate_checkpoint_state(
1250        &self,
1251        state: &Self::State,
1252        epoch: u64,
1253        next_batch: u64,
1254        next_logical_sample: u64,
1255    ) -> Result<()> {
1256        require_equal(
1257            "batch_sampler",
1258            state.batch_size,
1259            usize_to_u64(self.batch_size, "batch_sampler")?,
1260        )?;
1261        require_equal("batch_sampler", state.drop_last, self.drop_last)?;
1262        require_equal("checkpoint", state.next_batch, next_batch)?;
1263        require_equal("checkpoint", state.next_logical_sample, next_logical_sample)?;
1264        validate_batch_boundary(
1265            self.sampler.exact_len(),
1266            self.batch_size,
1267            self.drop_last,
1268            state.next_batch,
1269            state.next_logical_sample,
1270        )?;
1271        self.sampler
1272            .validate_checkpoint_state(&state.sampler, epoch, state.next_logical_sample)
1273    }
1274
1275    fn restore_checkpoint_iter_validated(&mut self, state: &Self::State) -> Self::Iter {
1276        let iterator = self
1277            .sampler
1278            .restore_checkpoint_iter_validated(&state.sampler);
1279        BatchSampler::from_validated(
1280            iterator,
1281            NonZeroUsize::new(self.batch_size)
1282                .expect("batch sampler construction validated a nonzero size"),
1283            self.drop_last,
1284        )
1285    }
1286
1287    fn distributed_configuration(&self) -> Option<DistributedConfiguration> {
1288        self.sampler.distributed_configuration()
1289    }
1290
1291    fn checkpoint_distributed_configuration_from_state(
1292        state: &Self::State,
1293    ) -> Result<Option<DistributedConfiguration>> {
1294        S::checkpoint_distributed_configuration_from_state(&state.sampler)
1295    }
1296}
1297
1298fn validate_epoch_position(
1299    state_epoch: u64,
1300    state_position: u64,
1301    epoch: u64,
1302    position: u64,
1303) -> Result<()> {
1304    require_equal("checkpoint", state_epoch, epoch)?;
1305    require_equal("checkpoint", state_position, position)
1306}
1307
1308fn validate_position(position: u64, length: u64) -> Result<()> {
1309    if position > length {
1310        return Err(invalid_configuration(
1311            "checkpoint",
1312            format!("sampler position {position} exceeds length {length}"),
1313        ));
1314    }
1315    let _ = u64_to_usize(position, "checkpoint")?;
1316    Ok(())
1317}
1318
1319fn validate_batch_boundary(
1320    exact_len: Option<usize>,
1321    batch_size: usize,
1322    drop_last: bool,
1323    next_batch: u64,
1324    next_logical_sample: u64,
1325) -> Result<()> {
1326    let batch_size = usize_to_u64(batch_size, "batch_sampler")?;
1327    let complete_boundary = next_logical_sample
1328        .checked_div(batch_size)
1329        .ok_or_else(|| invalid_configuration("batch_sampler", "batch size is zero"))?;
1330    let is_aligned = next_logical_sample.is_multiple_of(batch_size);
1331    let final_short = exact_len
1332        .map(|length| usize_to_u64(length, "batch_sampler"))
1333        .transpose()?
1334        .is_some_and(|length| {
1335            !drop_last
1336                && next_logical_sample == length
1337                && next_batch == complete_boundary + u64::from(!is_aligned)
1338        });
1339    if (!is_aligned || next_batch != complete_boundary) && !final_short {
1340        return Err(invalid_configuration(
1341            "checkpoint",
1342            "batch and logical sample cursors are not on a visible batch boundary",
1343        ));
1344    }
1345    Ok(())
1346}
1347
1348fn advance<I>(iterator: &mut I, position: u64) -> Result<()>
1349where
1350    I: Iterator,
1351{
1352    let position = u64_to_usize(position, "checkpoint")?;
1353    for _ in 0..position {
1354        if iterator.next().is_none() {
1355            return Err(invalid_configuration(
1356                "checkpoint",
1357                "sampler cursor exceeds the regenerated sequence",
1358            ));
1359        }
1360    }
1361    Ok(())
1362}
1363
1364fn usize_to_u64(value: usize, field: &'static str) -> Result<u64> {
1365    u64::try_from(value)
1366        .map_err(|_| invalid_configuration(field, "value does not fit the checkpoint schema"))
1367}
1368
1369fn u64_to_usize(value: u64, field: &'static str) -> Result<usize> {
1370    usize::try_from(value)
1371        .map_err(|_| invalid_configuration(field, "checkpoint value does not fit this platform"))
1372}
1373
1374fn require_equal<T>(field: &'static str, actual: T, expected: T) -> Result<()>
1375where
1376    T: PartialEq,
1377{
1378    if actual != expected {
1379        return Err(invalid_configuration(
1380            field,
1381            "checkpoint configuration does not match the loader",
1382        ));
1383    }
1384    Ok(())
1385}
1386
1387fn validate_positive(value: usize, field: &'static str) -> Result<()> {
1388    if value == 0 {
1389        return Err(invalid_configuration(field, "must be greater than zero"));
1390    }
1391    Ok(())
1392}
1393
1394pub(crate) fn validate_batch_size(batch_size: usize) -> Result<NonZeroUsize> {
1395    validate_positive(batch_size, "batch_size")?;
1396    let _ = try_vec::<usize>(batch_size, "batch_size")?;
1397    NonZeroUsize::new(batch_size)
1398        .ok_or_else(|| invalid_configuration("batch_size", "must be greater than zero"))
1399}
1400
1401fn validate_weights(weights: &[f64]) -> Result<()> {
1402    if weights.is_empty() {
1403        return Err(invalid_configuration("weights", "must not be empty"));
1404    }
1405    if weights.iter().any(|weight| !weight.is_finite()) {
1406        return Err(invalid_configuration("weights", "must be finite"));
1407    }
1408    if weights.iter().any(|&weight| weight < 0.0) {
1409        return Err(invalid_configuration("weights", "must be nonnegative"));
1410    }
1411    let total = weights.iter().sum::<f64>();
1412    if !total.is_finite() || total <= 0.0 {
1413        return Err(invalid_configuration(
1414            "weights",
1415            "must have a positive finite total",
1416        ));
1417    }
1418    Ok(())
1419}
1420
1421fn invalid_configuration(field: &'static str, reason: impl Into<String>) -> RustTorchError {
1422    RustTorchError::InvalidConfiguration {
1423        field,
1424        reason: reason.into(),
1425    }
1426}
1427
1428fn epoch_seed(seed: u64, epoch: u64) -> u64 {
1429    seed.wrapping_add(epoch)
1430}
1431
1432fn batch_count(length: usize, batch_size: usize, drop_last: bool) -> usize {
1433    let complete = length / batch_size;
1434    complete + usize::from(!drop_last && !length.is_multiple_of(batch_size))
1435}
1436
1437fn distributed_sample_count(length: usize, replicas: usize, drop_last: bool) -> Result<usize> {
1438    if drop_last {
1439        return Ok(length / replicas);
1440    }
1441    let complete = length / replicas;
1442    complete
1443        .checked_add(usize::from(!length.is_multiple_of(replicas)))
1444        .ok_or_else(|| invalid_configuration("length", "padded rank length overflows usize"))
1445}
1446
1447#[allow(clippy::too_many_arguments)]
1448fn distributed_indices(
1449    length: usize,
1450    replicas: usize,
1451    rank: usize,
1452    shuffle: bool,
1453    seed: u64,
1454    drop_last: bool,
1455    num_samples: usize,
1456) -> Result<Vec<usize>> {
1457    let total_size = num_samples
1458        .checked_mul(replicas)
1459        .ok_or_else(|| invalid_configuration("length", "padded global length overflows usize"))?;
1460    let materialized_length = if shuffle || !drop_last {
1461        length
1462    } else {
1463        total_size
1464    };
1465    let mut indices = try_vec(total_size.max(materialized_length), "length")?;
1466    indices.extend(0..materialized_length);
1467    if shuffle {
1468        indices.shuffle(&mut ChaCha12Rng::seed_from_u64(seed));
1469    }
1470    if drop_last {
1471        indices.truncate(total_size);
1472    } else if length != 0 {
1473        for position in length..total_size {
1474            indices.push(indices[(position - length) % length]);
1475        }
1476    }
1477
1478    let mut rank_indices = try_vec(num_samples, "length")?;
1479    rank_indices.extend(indices.into_iter().skip(rank).step_by(replicas));
1480    Ok(rank_indices)
1481}
1482
1483fn random_indices(
1484    length: usize,
1485    num_samples: usize,
1486    replacement: Replacement,
1487    seed: u64,
1488) -> Result<Vec<usize>> {
1489    let mut rng = ChaCha12Rng::seed_from_u64(seed);
1490    match replacement {
1491        Replacement::With => {
1492            let mut output = try_vec(num_samples, "num_samples")?;
1493            output.extend((0..num_samples).map(|_| rng.gen_range(0..length)));
1494            Ok(output)
1495        }
1496        Replacement::Without => {
1497            let mut permutation = try_vec(length, "length")?;
1498            permutation.extend(0..length);
1499            let mut output = try_vec(num_samples, "num_samples")?;
1500            while output.len() < num_samples {
1501                permutation.shuffle(&mut rng);
1502                let remaining = num_samples - output.len();
1503                output.extend(permutation.iter().copied().take(remaining));
1504            }
1505            Ok(output)
1506        }
1507    }
1508}
1509
1510fn try_vec<T>(capacity: usize, field: &'static str) -> Result<Vec<T>> {
1511    let mut values = Vec::new();
1512    values.try_reserve_exact(capacity).map_err(|error| {
1513        invalid_configuration(field, format!("cannot reserve requested storage: {error}"))
1514    })?;
1515    Ok(values)
1516}
1517
1518fn shuffled_copy(indices: &[usize], seed: u64) -> Result<Vec<usize>> {
1519    let mut shuffled = try_vec(indices.len(), "indices")?;
1520    shuffled.extend_from_slice(indices);
1521    shuffled.shuffle(&mut ChaCha12Rng::seed_from_u64(seed));
1522    Ok(shuffled)
1523}
1524
1525fn weighted_indices(
1526    weights: &[f64],
1527    num_samples: usize,
1528    replacement: bool,
1529    seed: u64,
1530    distribution: &WeightedIndex<f64>,
1531) -> Result<Vec<usize>> {
1532    let mut rng = ChaCha12Rng::seed_from_u64(seed);
1533    if replacement {
1534        let mut output = try_vec(num_samples, "num_samples")?;
1535        output.extend((0..num_samples).map(|_| distribution.sample(&mut rng)));
1536        return Ok(output);
1537    }
1538
1539    let mut positive = try_vec(weights.len(), "weights")?;
1540    positive.extend(
1541        weights
1542            .iter()
1543            .enumerate()
1544            .filter(|(_, weight)| **weight > 0.0)
1545            .map(|(index, &weight)| {
1546                let draw: f64 = rng.sample(Open01);
1547                (index, weight.ln() - (-draw.ln()).ln())
1548            }),
1549    );
1550    positive.sort_unstable_by(|(left_index, left_key), (right_index, right_key)| {
1551        right_key
1552            .total_cmp(left_key)
1553            .then_with(|| left_index.cmp(right_index))
1554    });
1555
1556    let mut output = try_vec(num_samples, "num_samples")?;
1557    output.extend(
1558        positive
1559            .into_iter()
1560            .take(num_samples)
1561            .map(|(index, _)| index),
1562    );
1563    if output.len() < num_samples {
1564        let mut zero_weight_indices = try_vec(weights.len(), "weights")?;
1565        zero_weight_indices.extend(
1566            weights
1567                .iter()
1568                .enumerate()
1569                .filter_map(|(index, &weight)| (weight == 0.0).then_some(index)),
1570        );
1571        zero_weight_indices.shuffle(&mut rng);
1572        output.extend(
1573            zero_weight_indices
1574                .into_iter()
1575                .take(num_samples - output.len()),
1576        );
1577    }
1578    Ok(output)
1579}