-
Notifications
You must be signed in to change notification settings - Fork 299
/
SortedPermutation.h
80 lines (65 loc) · 3.21 KB
/
SortedPermutation.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
/******************************************************************************
* SOFA, Simulation Open-Framework Architecture *
* (c) 2006 INRIA, USTL, UJF, CNRS, MGH *
* *
* This program is free software; you can redistribute it and/or modify it *
* under the terms of the GNU Lesser General Public License as published by *
* the Free Software Foundation; either version 2.1 of the License, or (at *
* your option) any later version. *
* *
* This program is distributed in the hope that it will be useful, but WITHOUT *
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or *
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License *
* for more details. *
* *
* You should have received a copy of the GNU Lesser General Public License *
* along with this program. If not, see <http://www.gnu.org/licenses/>. *
*******************************************************************************
* Authors: The SOFA Team and external contributors (see Authors.txt) *
* *
* Contact information: contact@sofa-framework.org *
******************************************************************************/
#ifndef SOFA_HELPER_SortedPermutation_H
#define SOFA_HELPER_SortedPermutation_H
/** Utility to compute the sorted permutation of a container. See example at the end of the file
Francois Faure, April 2012
*/
#include <sofa/type/vector.h>
#include <iostream>
#include <algorithm>
namespace sofa::helper
{
/** Comparison operator used to compute sorted permutations of a container.
The comparison operator of two indices compares the corresponding entries of the container.
The container must allow random access.
*/
template<class Container>
struct CompareIndirect
{
const Container& values;
CompareIndirect( const Container& v ):values(v) {}
bool operator () (unsigned i, unsigned j) const { return values[i] < values[j]; }
};
/// Return a sorted permutation of the container, i.e. a list of indices corresponding to increasing entries.
template<class Container>
type::vector<unsigned> sortedPermutation( const Container& values )
{
type::vector<unsigned> permutation;
permutation.resize(values.size());
for(unsigned i=0; i<permutation.size(); i++)
permutation[i] = i;
CompareIndirect<Container> cmp(values);
std::sort( permutation.begin(), permutation.end(), cmp );
return permutation;
}
////Example:
/// type::vector<double> values;
/// values.push_back(24);
/// values.push_back(55);
/// values.push_back(22);
/// values.push_back(1);
/// vector<unsigned> permutation = sortedPermutation(values);
/// //The following prints: 3 2 0 1
/// std::cout << permutation << "\n";
} // namespace sofa::helper
#endif