Define simgrid::xbt::three_way_partition as a generic C++ function.

Replacement for the one in dynar.h.

diff --git a/include/xbt/algorithm.hpp b/include/xbt/algorithm.hpp
new file mode 100644 (file)
index 0000000..85cc181
--- /dev/null
+++ b/include/xbt/algorithm.hpp
@@ -0,0 +1,46 @@
+/* Copyright (c) 2015-2017. The SimGrid Team. All rights reserved.          */
+
+/* This program is free software; you can redistribute it and/or modify it
+ * under the terms of the license (GNU LGPL) which comes with this package. */
+
+#ifndef XBT_ALGORITHM_HPP
+#define XBT_ALGORITHM_HPP
+
+namespace simgrid {
+namespace xbt {
+
+/** @brief Sorts the elements of the sequence [first, last) according to their color assuming elements can have only
+ * three colors.  Since there are only three colors, it is linear and much faster than a classical sort.  See for
+ * example http://en.wikipedia.org/wiki/Dutch_national_flag_problem
+ *
+ * \param first forward iterators to the initial position of the sequence to partition.  \param last forward iterators
+ * to the final position of the sequence to partition.  \param color the color function that accepts an element in the
+ * range as argument, and returns a value of 0, 1, or 2.
+ *
+ * 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
+ * and elements with color 1 are in the middle.
+ */
+template <class ForwardIterator, class ColorFunction>
+void three_way_partition(ForwardIterator first, ForwardIterator last, ColorFunction color)
+{
+  ForwardIterator iter = first;
+  while (iter < last) {
+    int c = color(*iter);
+    if (c == 1) {
+      ++iter;
+    } else if (c == 0) {
+      if (iter != first)
+        std::swap(*iter, *first);
+      ++iter;
+      ++first;
+    } else { // c == 2
+      --last;
+      if (iter != last)
+        std::swap(*iter, *last);
+    }
+  }
+}
+}
+}
+
+#endif

diff --git a/tools/cmake/DefinePackages.cmake b/tools/cmake/DefinePackages.cmake
index d0e0137..7280d5d 100644 (file)
--- a/tools/cmake/DefinePackages.cmake
+++ b/tools/cmake/DefinePackages.cmake
@@ -699,31 +699,29 @@ set(headers_to_install
   include/smpi/smpi_extended_traces_fortran.h
   include/smpi/forward.hpp
   include/xbt.h
-  include/xbt/RngStream.h
+  include/xbt/algorithm.hpp
   include/xbt/asserts.h
   include/xbt/automaton.h
   include/xbt/automaton.hpp
+  include/xbt/backtrace.h
+  include/xbt/backtrace.hpp
   include/xbt/base.h
   include/xbt/config.h
   include/xbt/config.hpp
   include/xbt/cunit.h
   include/xbt/dict.h
-  include/xbt/string.hpp
-  include/xbt/signal.hpp
   include/xbt/dynar.h
   include/xbt/dynar.hpp
   include/xbt/ex.h
   include/xbt/ex.hpp
   include/xbt/exception.hpp
-  include/xbt/backtrace.h
-  include/xbt/backtrace.hpp
+  include/xbt/Extendable.hpp
   include/xbt/file.h
-  include/xbt/function_types.h
   include/xbt/functional.hpp
+  include/xbt/function_types.h
   include/xbt/future.hpp
   include/xbt/graph.h
   include/xbt/heap.h
-  include/xbt/Extendable.hpp
   include/xbt/log.h
   include/xbt/log.hpp
   include/xbt/mallocator.h
@@ -733,7 +731,10 @@ set(headers_to_install
   include/xbt/parmap.h
   include/xbt/range.hpp
   include/xbt/replay.hpp
+  include/xbt/RngStream.h
+  include/xbt/signal.hpp
   include/xbt/str.h
+  include/xbt/string.hpp
   include/xbt/swag.h
   include/xbt/synchro.h
   include/xbt/sysdep.h