A Discrete-Event Network Simulator
API
Loading...
Searching...
No Matches
shuffle.h
Go to the documentation of this file.
1/*
2 * Copyright (c) 2024 Universita' degli Studi di Napoli Federico II
3 *
4 * SPDX-License-Identifier: GPL-2.0-only
5 *
6 * Author: Stefano Avallone <stavallo@unina.it>
7 */
8
9#ifndef SHUFFLE_H
10#define SHUFFLE_H
11
12/**
13 * \file
14 * \ingroup randomvariable
15 * Function to shuffle elements in a given range.
16 */
17
19
20#include <algorithm>
21#include <iterator>
22
23namespace ns3
24{
25
26/**
27 * Shuffle the elements in the range <i>first</i> to <i>last</i>. Given that the implementation
28 * of std::shuffle is not dictated by the standard
29 * [CppReference](https://en.cppreference.com/w/cpp/algorithm/random_shuffle), it is not guaranteed
30 * that std::shuffle returns the same permutation of the given range using different compilers/OSes.
31 * Therefore, this function provides a specific implementation of the shuffling algorithm reported
32 * in "The Art of Computer Programming" of Donald Knuth and on
33 * [Wikipedia](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_modern_algorithm),
34 * which basically matches the implementation in libstdc++.
35 *
36 * The complexity of the implemented algorithm is linear with the distance between <i>first</i>
37 * and <i>last</i>. For containers that do not provide random access iterators (e.g., lists, sets)
38 * we can still achieve a linear complexity by copying the elements in a vector and shuffling the
39 * elements of the vector.
40 *
41 * \tparam RND_ACCESS_ITER \deduced the iterator type (must be a random access iterator)
42 * \param first an iterator pointing to the first element in the range to shuffle
43 * \param last an iterator pointing to past-the-last element in the range to shuffle
44 * \param rv pointer to a uniform random variable
45 */
46template <typename RND_ACCESS_ITER>
47void
48Shuffle(RND_ACCESS_ITER first, RND_ACCESS_ITER last, Ptr<UniformRandomVariable> rv)
49{
50 if (auto dist = std::distance(first, last); dist > 1)
51 {
52 for (--last; first < last; ++first, --dist)
53 {
54 if (auto i = rv->GetInteger(0, dist - 1); i != 0)
55 {
56 std::iter_swap(first, std::next(first, i));
57 }
58 }
59 }
60}
61
62} // namespace ns3
63
64#endif /* SHUFFLE_H */
Smart pointer class similar to boost::intrusive_ptr.
Definition first.py:1
Every class exported by the ns3 library is enclosed in the ns3 namespace.
void Shuffle(RND_ACCESS_ITER first, RND_ACCESS_ITER last, Ptr< UniformRandomVariable > rv)
Shuffle the elements in the range first to last.
Definition shuffle.h:48
ns3::RandomVariableStream declaration, and related classes.