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 #pragma once
  18
  19 #include <algorithm>
  20 #include <iterator>
  21 #include <vector>
  22
  23 namespace HPHP {
  24
  25 ///////////////////////////////////////////////////////////////////////////////
  26 /*
  27  * Like <algorithm>, but jankier.
  28  */
  29
  30 ///////////////////////////////////////////////////////////////////////////////
  31
  32 /*
  33  * Sort the keys of a container by its values.
  34  */
  35 template<class T, class Compare>
  36 std::vector<size_t>
  37 sort_keys_by_value(const std::vector<T>& input, Compare compare) {
  38   auto result = std::vector<size_t>{};
  39   result.reserve(input.size());
  40   for (auto i = 0; i < input.size(); ++i) result.emplace_back(i);
  41
  42   std::sort(
  43     std::begin(result), std::end(result),
  44     [&] (size_t a, size_t b) { return compare(input[a], input[b]); }
  45   );
  46   return result;
  47 }
  48
  49 template<class Container, class Compare>
  50 std::vector<typename Container::key_type>
  51 sort_keys_by_value(const Container& input, Compare compare) {
  52   using key_type = typename Container::key_type;
  53
  54   auto result = std::vector<key_type>{};
  55   result.reserve(input.size());
  56   for (auto const& kv : input) result.emplace_back(kv.first);
  57
  58   std::sort(
  59     std::begin(result), std::end(result),
  60     [&] (const key_type& a, const key_type& b) {
  61       return compare(input.at(a), input.at(b));
  62     }
  63   );
  64   return result;
  65 }
  66
  67 ///////////////////////////////////////////////////////////////////////////////
  68
  69 }
  70