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
* This program is free software; you can redistribute it and/or modify
5
* it under the terms of the GNU General Public License version 2 as
6
* published by the Free Software Foundation;
7
*
8
* This program is distributed in the hope that it will be useful,
9
* but WITHOUT ANY WARRANTY; without even the implied warranty of
10
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11
* GNU General Public License for more details.
12
*
13
* You should have received a copy of the GNU General Public License
14
* along with this program; if not, write to the Free Software
15
* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
16
*
17
* Author: Stefano Avallone <stavallo@unina.it>
18
*/
19
20
#ifndef SHUFFLE_H
21
#define SHUFFLE_H
22
23
/**
24
* \file
25
* \ingroup randomvariable
26
* Function to shuffle elements in a given range.
27
*/
28
29
#include "
random-variable-stream.h
"
30
31
#include <algorithm>
32
#include <iterator>
33
34
namespace
ns3
35
{
36
37
/**
38
* Shuffle the elements in the range <i>first</i> to <i>last</i>. Given that the implementation
39
* of std::shuffle is not dictated by the standard
40
* [CppReference](https://en.cppreference.com/w/cpp/algorithm/random_shuffle), it is not guaranteed
41
* that std::shuffle returns the same permutation of the given range using different compilers/OSes.
42
* Therefore, this function provides a specific implementation of the shuffling algorithm reported
43
* in "The Art of Computer Programming" of Donald Knuth and on
44
* [Wikipedia](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_modern_algorithm),
45
* which basically matches the implementation in libstdc++.
46
*
47
* The complexity of the implemented algorithm is linear with the distance between <i>first</i>
48
* and <i>last</i>. For containers that do not provide random access iterators (e.g., lists, sets)
49
* we can still achieve a linear complexity by copying the elements in a vector and shuffling the
50
* elements of the vector.
51
*
52
* \tparam RND_ACCESS_ITER \deduced the iterator type (must be a random access iterator)
53
* \param first an iterator pointing to the first element in the range to shuffle
54
* \param last an iterator pointing to past-the-last element in the range to shuffle
55
* \param rv pointer to a uniform random variable
56
*/
57
template
<
typename
RND_ACCESS_ITER>
58
void
59
Shuffle
(RND_ACCESS_ITER
first
, RND_ACCESS_ITER last,
Ptr<UniformRandomVariable>
rv)
60
{
61
if
(
auto
dist = std::distance(
first
, last); dist > 1)
62
{
63
for
(--last;
first
< last; ++
first
, --dist)
64
{
65
if
(
auto
i = rv->GetInteger(0, dist - 1); i != 0)
66
{
67
std::iter_swap(
first
, std::next(
first
, i));
68
}
69
}
70
}
71
}
72
73
}
// namespace ns3
74
75
#endif
/* SHUFFLE_H */
ns3::Ptr
Smart pointer class similar to boost::intrusive_ptr.
Definition:
ptr.h:77
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:59
random-variable-stream.h
ns3::RandomVariableStream declaration, and related classes.
src
core
model
shuffle.h
Generated on Tue May 28 2024 23:34:39 for ns-3 by
1.9.6