CppAD: A C++ Algorithmic Differentiation Package
20130918
|
00001 /* $Id$ */ 00002 # ifndef CPPAD_INDEX_SORT_INCLUDED 00003 # define CPPAD_INDEX_SORT_INCLUDED 00004 00005 /* -------------------------------------------------------------------------- 00006 CppAD: C++ Algorithmic Differentiation: Copyright (C) 2003-14 Bradley M. Bell 00007 00008 CppAD is distributed under multiple licenses. This distribution is under 00009 the terms of the 00010 Eclipse Public License Version 1.0. 00011 00012 A copy of this license is included in the COPYING file of this distribution. 00013 Please visit http://www.coin-or.org/CppAD/ for information on other licenses. 00014 -------------------------------------------------------------------------- */ 00015 00016 /* 00017 $begin index_sort$$ 00018 $spell 00019 cppad.hpp 00020 ind 00021 const 00022 $$ 00023 00024 $section Returns Indices that Sort a Vector$$ 00025 00026 $index index_sort$$ 00027 $index sort, index$$ 00028 00029 $head Syntax$$ 00030 $codei%# include <cppad/near_equal.hpp> 00031 index_sort(%keys%, %ind%)%$$ 00032 00033 $head keys$$ 00034 The argument $icode keys$$ has prototype 00035 $codei% 00036 const %VectorKey%& %keys% 00037 %$$ 00038 where $icode VectorKey$$ is 00039 a $cref SimpleVector$$ class with elements that support the $code <$$ 00040 operation. 00041 00042 $head ind$$ 00043 The argument $icode ind$$ has prototype 00044 $codei% 00045 const %VectorSize%& %ind% 00046 %$$ 00047 where $icode VectorSize$$ is 00048 a $cref SimpleVector$$ class with elements of type $code size_t$$. 00049 The routine $cref CheckSimpleVector$$ will generate an error message 00050 if this is not the case. 00051 The size of $icode ind$$ must be the same as the size of $icode keys$$ 00052 and the value of its input elements does not matter. 00053 $pre 00054 00055 $$ 00056 Upon return, $icode ind$$ is a permutation of the set of indices 00057 that yields increasing order for $icode keys$$. 00058 In other words, for all $icode%i% != %j%$$, 00059 $codei% 00060 %ind%[%i%] != %ind%[%j%] 00061 %$$ 00062 and for $icode%i% = 0 , %...% , %size%-2%$$, 00063 $codei% 00064 ( %keys%[ %ind%[%i%+1] ] < %keys%[ %ind%[%i%] ] ) == false 00065 %$$ 00066 00067 00068 $head Example$$ 00069 $children% 00070 example/index_sort.cpp 00071 %$$ 00072 The file $cref index_sort.cpp$$ contains an example 00073 and test of this routine. 00074 It return true if it succeeds and false otherwise. 00075 00076 $end 00077 */ 00078 # include <algorithm> 00079 # include <cppad/thread_alloc.hpp> 00080 # include <cppad/check_simple_vector.hpp> 00081 # include <cppad/local/define.hpp> 00082 00083 namespace CppAD { // BEGIN_CPPAD_NAMESPACE 00084 /*! 00085 \file index_sort.hpp 00086 File used to implement the CppAD index sort utility 00087 */ 00088 00089 /*! 00090 Helper class used by index_sort 00091 */ 00092 template <class Compare> 00093 class index_sort_element { 00094 private: 00095 /// key used to determine position of this element 00096 Compare key_; 00097 /// index vlaue corresponding to this key 00098 size_t index_; 00099 public: 00100 /// operator requried by std::sort 00101 bool operator<(const index_sort_element& other) const 00102 { return key_ < other.key_; } 00103 /// set the key for this element 00104 void set_key(const Compare& value) 00105 { key_ = value; } 00106 /// set the index for this element 00107 void set_index(const size_t& index) 00108 { index_ = index; } 00109 /// get the key for this element 00110 Compare get_key(void) const 00111 { return key_; } 00112 /// get the index for this element 00113 size_t get_index(void) const 00114 { return index_; } 00115 }; 00116 00117 /*! 00118 Compute the indices that sort a vector of keys 00119 00120 \tparam VectorKey 00121 Simple vector type that deterimene the sorting order by \c < operator 00122 on its elements. 00123 00124 \tparam VectorSize 00125 Simple vector type with elements of \c size_t 00126 that is used to return index values. 00127 00128 \param keys [in] 00129 values that determine the sorting order. 00130 00131 \param ind [out] 00132 must have the same size as \c keys. 00133 The input value of its elements does not matter. 00134 The output value of its elements satisfy 00135 \code 00136 ( keys[ ind[i] ] < keys[ ind[i+1] ] ) == false 00137 \endcode 00138 */ 00139 template <class VectorKey, class VectorSize> 00140 void index_sort(const VectorKey& keys, VectorSize& ind) 00141 { typedef typename VectorKey::value_type Compare; 00142 CheckSimpleVector<size_t, VectorSize>(); 00143 00144 typedef index_sort_element<Compare> element; 00145 00146 CPPAD_ASSERT_KNOWN( 00147 size_t(keys.size()) == size_t(ind.size()), 00148 "index_sort: vector sizes do not match" 00149 ); 00150 00151 size_t size_work = size_t(keys.size()); 00152 size_t size_out; 00153 element* work = 00154 thread_alloc::create_array<element>(size_work, size_out); 00155 00156 // copy initial order into work 00157 size_t i; 00158 for(i = 0; i < size_work; i++) 00159 { work[i].set_key( keys[i] ); 00160 work[i].set_index( i ); 00161 } 00162 00163 // sort the work array 00164 std::sort(work, work+size_work); 00165 00166 // copy the indices to the output vector 00167 for(i = 0; i < size_work; i++) 00168 ind[i] = work[i].get_index(); 00169 00170 // we are done with this work array 00171 thread_alloc::delete_array(work); 00172 00173 return; 00174 } 00175 00176 } // END_CPPAD_NAMESPACE 00177 00178 # endif