ceph/src/common/weighted_shuffle.h

   1 // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
   2 // vim: ts=8 sw=2 smarttab
   3
   4 #pragma once
   5
   6 #include <algorithm>
   7 #include <iterator>
   8 #include <random>
   9
  10 template <class RandomIt, class DistIt, class URBG>
  11 void weighted_shuffle(RandomIt first, RandomIt last,
  12                       DistIt weight_first, DistIt weight_last,
  13                       URBG &&g)
  14 {
  15   if (first == last) {
  16     return;
  17   } else {
  18     std::discrete_distribution d{weight_first, weight_last};
  19     if (auto n = d(g); n > 0) {
  20       std::iter_swap(first, std::next(first, n));
  21       std::iter_swap(weight_first, std::next(weight_first, n));
  22     }
  23     weighted_shuffle(++first, last, ++weight_first, weight_last, std::move(g));
  24   }
  25 }