hphp/util/algorithm.h

   1 /*
   2    +----------------------------------------------------------------------+
   3    | HipHop for PHP                                                       |
   4    +----------------------------------------------------------------------+
   5    | Copyright (c) 2010-present Facebook, Inc. (http://www.facebook.com)  |
   6    +----------------------------------------------------------------------+
   7    | This source file is subject to version 3.01 of the PHP license,      |
   8    | that is bundled with this package in the file LICENSE, and is        |
   9    | available through the world-wide-web at the following url:           |
  10    | http://www.php.net/license/3_01.txt                                  |
  11    | If you did not receive a copy of the PHP license and are unable to   |
  12    | obtain it through the world-wide-web, please send a note to          |
  13    | license@php.net so we can mail you a copy immediately.               |
  14    +----------------------------------------------------------------------+
  15 */
  16
  17 #ifndef incl_HPHP_UTIL_ALGORITHM_H_
  18 #define incl_HPHP_UTIL_ALGORITHM_H_
  19
  20 #include <algorithm>
  21 #include <iterator>
  22 #include <vector>
  23
  24 namespace HPHP {
  25
  26 ///////////////////////////////////////////////////////////////////////////////
  27 /*
  28  * Like <algorithm>, but jankier.
  29  */
  30
  31 ///////////////////////////////////////////////////////////////////////////////
  32
  33 /*
  34  * Sort the keys of a container by its values.
  35  */
  36 template<class T, class Compare>
  37 std::vector<size_t>
  38 sort_keys_by_value(const std::vector<T>& input, Compare compare) {
  39   auto result = std::vector<size_t>{};
  40   result.reserve(input.size());
  41   for (auto i = 0; i < input.size(); ++i) result.emplace_back(i);
  42
  43   std::sort(
  44     std::begin(result), std::end(result),
  45     [&] (size_t a, size_t b) { return compare(input[a], input[b]); }
  46   );
  47   return result;
  48 }
  49
  50 template<class Container, class Compare>
  51 std::vector<typename Container::key_type>
  52 sort_keys_by_value(const Container& input, Compare compare) {
  53   using key_type = typename Container::key_type;
  54
  55   auto result = std::vector<key_type>{};
  56   result.reserve(input.size());
  57   for (auto const& kv : input) result.emplace_back(kv.first);
  58
  59   std::sort(
  60     std::begin(result), std::end(result),
  61     [&] (const key_type& a, const key_type& b) {
  62       return compare(input.at(a), input.at(b));
  63     }
  64   );
  65   return result;
  66 }
  67
  68 ///////////////////////////////////////////////////////////////////////////////
  69
  70 }
  71
  72 #endif