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
81
82
83
84
85
86
87
88
89
90
91
|
// SPDX-License-Identifier: EPL-2.0 OR GPL-2.0-or-later
// SPDX-FileCopyrightText: Bradley M. Bell <bradbell@seanet.com>
// SPDX-FileContributor: 2003-24 Bradley M. Bell
// ----------------------------------------------------------------------------
/*
{xrst_begin index_sort.cpp}
Index Sort: Example and Test
############################
{xrst_literal
// BEGIN C++
// END C++
}
{xrst_end index_sort.cpp}
*/
// BEGIN C++
# include <cppad/utility/index_sort.hpp>
# include <cppad/utility/vector.hpp>
# include <valarray>
# include <vector>
namespace{
// class that uses < to compare a pair of size_t values
class Key {
public:
size_t first_;
size_t second_;
//
Key(void)
{ }
//
Key(size_t first, size_t second)
: first_(first), second_(second)
{ }
//
bool operator<(const Key& other) const
{ if( first_ == other.first_ )
return second_ < other.second_;
return first_ < other.first_;
}
};
template <class KeyVector, class SizeVector>
bool vector_case(void)
{ bool ok = true;
size_t i, j;
size_t first[] = { 4, 4, 3, 3, 2, 2, 1, 1};
size_t second[] = { 0, 1, 0, 1, 0, 1, 0, 1};
size_t size = sizeof(first) / sizeof(first[0]);
KeyVector keys(size);
for(i = 0; i < size; i++)
keys[i] = Key(first[i], second[i]);
SizeVector ind(size);
CppAD::index_sort(keys, ind);
// check that all the indices are different
for(i = 0; i < size; i++)
{ for(j = 0; j < size; j++)
ok &= (i == j) || (ind[i] != ind[j]);
}
// check for increasing order
for(i = 0; i < size-1; i++)
{ if( first[ ind[i] ] == first[ ind[i+1] ] )
ok &= second[ ind[i] ] <= second[ ind[i+1] ];
else
ok &= first[ ind[i] ] < first[ ind[i+1] ];
}
return ok;
}
}
bool index_sort(void)
{ bool ok = true;
// some example simple vector template classes
ok &= vector_case< std::vector<Key>, std::valarray<size_t> >();
ok &= vector_case< std::valarray<Key>, CppAD::vector<size_t> >();
ok &= vector_case< CppAD::vector<Key>, std::vector<size_t> >();
return ok;
}
// END C++
|
