CppAD: A C++ Algorithmic Differentiation Package  20130918
index_sort.hpp
Go to the documentation of this file.
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
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines