1 /* --------------------------------------------------------------------------
2 CppAD: C++ Algorithmic Differentiation: Copyright (C) 2003-20 Bradley M. Bell
3
4 CppAD is distributed under the terms of the
5 Eclipse Public License Version 2.0.
6
7 This Source Code may also be made available under the following
8 Secondary License when the conditions for such availability set forth
9 in the Eclipse Public License, Version 2.0 are satisfied:
10 GNU General Public License, Version 2.0 or later.
11 ---------------------------------------------------------------------------- */
12
13 /*
14 $begin index_sort.cpp$$
15
16 $section Index Sort: Example and Test$$
17
18
19 $srcthisfile%0%// BEGIN C++%// END C++%1%$$
20
21 $end
22 */
23 // BEGIN C++
24 # include <cppad/utility/index_sort.hpp>
25 # include <cppad/utility/vector.hpp>
26 # include <valarray>
27 # include <vector>
28
29
30 namespace{
31 // class that uses < to compare a pair of size_t values
32 class Key {
33 public:
34 size_t first_;
35 size_t second_;
36 //
Key(void)37 Key(void)
38 { }
39 //
Key(size_t first,size_t second)40 Key(size_t first, size_t second)
41 : first_(first), second_(second)
42 { }
43 //
operator <(const Key & other) const44 bool operator<(const Key& other) const
45 { if( first_ == other.first_ )
46 return second_ < other.second_;
47 return first_ < other.first_;
48 }
49 };
50
51 template <class KeyVector, class SizeVector>
vector_case(void)52 bool vector_case(void)
53 { bool ok = true;
54 size_t i, j;
55 size_t first[] = { 4, 4, 3, 3, 2, 2, 1, 1};
56 size_t second[] = { 0, 1, 0, 1, 0, 1, 0, 1};
57 size_t size = sizeof(first) / sizeof(first[0]);
58
59 KeyVector keys(size);
60 for(i = 0; i < size; i++)
61 keys[i] = Key(first[i], second[i]);
62
63 SizeVector ind(size);
64 CppAD::index_sort(keys, ind);
65
66 // check that all the indices are different
67 for(i = 0; i < size; i++)
68 { for(j = 0; j < size; j++)
69 ok &= (i == j) | (ind[i] != ind[j]);
70 }
71
72 // check for increasing order
73 for(i = 0; i < size-1; i++)
74 { if( first[ ind[i] ] == first[ ind[i+1] ] )
75 ok &= second[ ind[i] ] <= second[ ind[i+1] ];
76 else
77 ok &= first[ ind[i] ] < first[ ind[i+1] ];
78 }
79
80 return ok;
81 }
82 }
83
index_sort(void)84 bool index_sort(void)
85 { bool ok = true;
86
87 // some example simple vector template classes
88 ok &= vector_case< std::vector<Key>, std::valarray<size_t> >();
89 ok &= vector_case< std::valarray<Key>, CppAD::vector<size_t> >();
90 ok &= vector_case< CppAD::vector<Key>, std::vector<size_t> >();
91
92 return ok;
93 }
94
95 // END C++
96