A Discrete-Event Network Simulator
Home
Tutorials ▼
English
Documentation ▼
Installation
Manual
Models
Contributing
Wiki
Development ▼
API Docs
Issue Tracker
Merge Requests
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
18
#include "
random-variable-stream.h
"
19
20
#include <algorithm>
21
#include <iterator>
22
23
namespace
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
*/
46
template
<
typename
RND_ACCESS_ITER>
47
void
48
Shuffle
(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 */
ns3::Ptr
Smart pointer class similar to boost::intrusive_ptr.
Definition
mpi-test-fixtures.h:37
first
Definition
first.py:1
ns3
Every class exported by the ns3 library is enclosed in the ns3 namespace.
ns3::Shuffle
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
random-variable-stream.h
ns3::RandomVariableStream declaration, and related classes.
src
core
model
shuffle.h
Generated on Fri Nov 8 2024 13:58:59 for ns-3 by
1.11.0