CppAD: A C++ Algorithmic Differentiation Package  20130102
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-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
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines