CppAD: A C++ Algorithmic Differentiation Package
20130102
|
00001 /* $Id$ */ 00002 # ifndef CPPAD_INDEX_SORT_INCLUDED 00003 # define CPPAD_INDEX_SORT_INCLUDED 00004 00005 /* -------------------------------------------------------------------------- 00006 CppAD: C++ Algorithmic Differentiation: Copyright (C) 2003-12 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 CPPAD_BEGIN_NAMESPACE 00084 /*! 00085 \defgroup index_sort_hpp index_sort.hpp 00086 \{ 00087 \file index_sort.hpp 00088 File used to implement the CppAD index sort utility 00089 */ 00090 00091 /*! 00092 Helper class used by index_sort 00093 */ 00094 template <class Compare> 00095 class index_sort_element { 00096 private: 00097 /// key used to determine position of this element 00098 Compare key_; 00099 /// index vlaue corresponding to this key 00100 size_t index_; 00101 public: 00102 /// operator requried by std::sort 00103 bool operator<(const index_sort_element& other) const 00104 { return key_ < other.key_; } 00105 /// set the key for this element 00106 void set_key(const Compare& value) 00107 { key_ = value; } 00108 /// set the index for this element 00109 void set_index(const size_t& index) 00110 { index_ = index; } 00111 /// get the key for this element 00112 Compare get_key(void) const 00113 { return key_; } 00114 /// get the index for this element 00115 size_t get_index(void) const 00116 { return index_; } 00117 }; 00118 00119 /*! 00120 Compute the indices that sort a vector of keys 00121 00122 \tparam VectorKey 00123 Simple vector type that deterimene the sorting order by \c < operator 00124 on its elements. 00125 00126 \tparam VectorSize 00127 Simple vector type with elements of \c size_t 00128 that is used to return index values. 00129 00130 \param keys [in] 00131 values that determine the sorting order. 00132 00133 \param ind [out] 00134 must have the same size as \c keys. 00135 The input value of its elements does not matter. 00136 The output value of its elements satisfy 00137 \code 00138 ( keys[ ind[i] ] < keys[ ind[i+1] ] ) == false 00139 \endcode 00140 */ 00141 template <class VectorKey, class VectorSize> 00142 void index_sort(const VectorKey& keys, VectorSize& ind) 00143 { typedef typename VectorKey::value_type Compare; 00144 CheckSimpleVector<size_t, VectorSize>(); 00145 00146 typedef index_sort_element<Compare> element; 00147 00148 CPPAD_ASSERT_KNOWN( 00149 size_t(keys.size()) == size_t(ind.size()), 00150 "index_sort: vector sizes do not match" 00151 ); 00152 00153 size_t size_work = size_t(keys.size()); 00154 size_t size_out; 00155 element* work = 00156 thread_alloc::create_array<element>(size_work, size_out); 00157 00158 // copy initial order into work 00159 size_t i; 00160 for(i = 0; i < size_work; i++) 00161 { work[i].set_key( keys[i] ); 00162 work[i].set_index( i ); 00163 } 00164 00165 // sort the work array 00166 std::sort(work, work+size_work); 00167 00168 // copy the indices to the output vector 00169 for(i = 0; i < size_work; i++) 00170 ind[i] = work[i].get_index(); 00171 00172 // we are done with this work array 00173 thread_alloc::delete_array(work); 00174 00175 return; 00176 } 00177 00178 /*! \} */ 00179 CPPAD_END_NAMESPACE 00180 00181 # endif