include/xbt/algorithm.hpp

   1 /* Copyright (c) 2015-2017. The SimGrid Team. All rights reserved.          */
   2
   3 /* This program is free software; you can redistribute it and/or modify it
   4  * under the terms of the license (GNU LGPL) which comes with this package. */
   5
   6 #ifndef XBT_ALGORITHM_HPP
   7 #define XBT_ALGORITHM_HPP
   8
   9 #include <utility>
  10
  11 namespace simgrid {
  12 namespace xbt {
  13
  14 /** @brief Comparator class for using with std::priority_queue or boost::heap.
  15  *
  16  * Compare two std::pair by their first element (of type double), and return true when the first is greater than the
  17  * second.  Useful to have priority queues with the smallest element on top.
  18  */
  19 template <class Pair> class HeapComparator {
  20 public:
  21   bool operator()(const Pair& a, const Pair& b) const { return a.first > b.first; }
  22 };
  23
  24 /** @brief Sorts the elements of the sequence [first, last) according to their color assuming elements can have only
  25  * three colors.  Since there are only three colors, it is linear and much faster than a classical sort.  See for
  26  * example http://en.wikipedia.org/wiki/Dutch_national_flag_problem
  27  *
  28  * \param first forward iterators to the initial position of the sequence to partition.
  29  * \param last forward iterators to the final position of the sequence to partition.
  30  * \param color the color function that accepts an element in the range as argument, and returns a value of 0, 1, or 2.
  31  *
  32  * At the end of the call, elements with color 0 are at the beginning of the range, elements with color 2 are at the end
  33  * and elements with color 1 are in the middle.
  34  */
  35 template <class ForwardIterator, class ColorFunction>
  36 void three_way_partition(ForwardIterator first, ForwardIterator last, ColorFunction color)
  37 {
  38   ForwardIterator iter = first;
  39   while (iter < last) {
  40     int c = color(*iter);
  41     if (c == 1) {
  42       ++iter;
  43     } else if (c == 0) {
  44       if (iter != first)
  45         std::swap(*iter, *first);
  46       ++iter;
  47       ++first;
  48     } else { // c == 2
  49       --last;
  50       if (iter != last)
  51         std::swap(*iter, *last);
  52     }
  53   }
  54 }
  55 }
  56 }
  57
  58 #endif