Make Utils::transform more generic

- Works for all container types now, defaulting to
  the same container type for input and output

- Enables specifying the result container type,
  e.g. QSet<X> x = Utils::transform<QSet>(list, function);

- Use our own inserter instead of std::back_inserter,
  to enable usage with QSet<>

Change-Id: I7256e51430bfc1409456c68b6ee270778b95e9d5
Reviewed-by: hjk <hjk121@nokiamail.com>

1 files changed, 134 insertions, 18 deletions

diff --git a/src/libs/utils/algorithm.h b/src/libs/utils/algorithm.h
index a3659983ec..5efaed2343 100644
--- a/src/libs/utils/algorithm.h
+++ b/src/libs/utils/algorithm.h
@@ -35,6 +35,7 @@
 
 #include <algorithm>
 #include <functional>
+#include <QStringList>
 
 namespace Utils
 {
@@ -140,41 +141,156 @@ auto equal(R (S::*function)() const, T value)
 // transform
 /////////////////
 
-// transform taking a member function pointer
-template<typename T, typename R, typename S>
+namespace {
+// needed for msvc 2010, that doesn't have a declval
+// can be removed once we stop supporting it
+template<typename T>
+T &&declval();
+
+/////////////////
+// helper code for transform to use back_inserter and thus push_back for everything
+// and insert for QSet<>
+//
+
+// QSetInsertIterator, straight from the standard for insert_iterator
+// just without the additional parameter to insert
+template <class Container>
+  class QSetInsertIterator :
+    public std::iterator<std::output_iterator_tag,void,void,void,void>
+{
+protected:
+  Container *container;
+
+public:
+  typedef Container container_type;
+  explicit QSetInsertIterator (Container &x)
+    : container(&x) {}
+  QSetInsertIterator<Container> &operator=(const typename Container::value_type &value)
+    { container->insert(value); return *this; }
+  QSetInsertIterator<Container> &operator= (typename Container::value_type &&value)
+    { container->insert(std::move(value)); return *this; }
+  QSetInsertIterator<Container >&operator*()
+    { return *this; }
+  QSetInsertIterator<Container> &operator++()
+    { return *this; }
+  QSetInsertIterator<Container> operator++(int)
+    { return *this; }
+};
+
+// inserter helper function, returns a std::back_inserter for most containers
+// and is overloaded for QSet<> to return a QSetInsertIterator
+template<typename C>
+inline std::back_insert_iterator<C>
+inserter(C &container)
+{
+    return std::back_inserter(container);
+}
+
+template<typename X>
+inline QSetInsertIterator<QSet<X>>
+inserter(QSet<X> &container)
+{
+    return QSetInsertIterator<QSet<X>>(container);
+}
+
+// helper: removes const, volatile and references from a type
+template<typename T>
+struct RemoveCvAndReference
+{
+    typedef typename std::remove_cv<typename std::remove_reference<T>::type>::type type;
+};
+
+template<typename F, typename T>
+struct ResultOfFunctionWithoutCvAndReference
+{
+    typedef typename RemoveCvAndReference<decltype(declval<F>()(declval<T>()))>::type type;
+};
+
+// actual implementation of transform
+template<template<typename> class C, // result container type
+         template<typename> class SC, // input container type
+         typename T, // element type of input container
+         typename F> // function type
 Q_REQUIRED_RESULT
-auto transform(const QList<T> &container, R (S::*p)() const)
-    -> QList<typename std::remove_cv<typename std::remove_reference<R>::type>::type>
+auto transform_impl(const SC<T> &container, F function)
+     -> C<typename ResultOfFunctionWithoutCvAndReference<F, T>::type>
 {
-    QList<typename std::remove_cv<typename std::remove_reference<R>::type>::type> result;
+    C<typename ResultOfFunctionWithoutCvAndReference<F, T>::type> result;
     result.reserve(container.size());
     std::transform(container.begin(), container.end(),
-                   std::back_inserter(result),
-                   std::mem_fn(p));
+                   inserter(result),
+                   function);
     return result;
 }
 
-namespace {
-// needed for msvc 2010, that doesn't have a declval
-// can be removed once we stop supporting it
-template<typename T>
-T &&declval();
 }
 
-// Note: add overloads for other container types as needed
-template<typename T, typename F>
+// transform taking a member function pointer
+template<template<typename> class C,
+        typename T,
+        typename R,
+        typename S>
 Q_REQUIRED_RESULT
-auto transform(const QList<T> &container, F function)
-     -> QList<typename std::remove_cv<typename std::remove_reference<decltype(function(declval<T>()))>::type>::type>
+auto transform(const C<T> &container, R (S::*p)() const)
+    -> C<typename RemoveCvAndReference<R>::type>
 {
-    QList<typename std::remove_cv<typename std::remove_reference<decltype(function(declval<T>()))>::type>::type> result;
+    C<typename RemoveCvAndReference<R>::type> result;
     result.reserve(container.size());
     std::transform(container.begin(), container.end(),
                    std::back_inserter(result),
-                   function);
+                   std::mem_fn(p));
     return result;
 }
 
+// same container type for input and output, e.g. transforming a QList<QString> into QList<int>
+template<template<typename> class C, // container
+         typename T, // element type
+         typename F> // function type
+Q_REQUIRED_RESULT
+auto transform(const C<T> &container, F function)
+     -> C<typename RemoveCvAndReference<decltype(declval<F>()(declval<T>()))>::type>
+{
+    return transform_impl<QList>(container, function);
+}
+
+// different container types for input and output, e.g. transforming a QList into a QSet
+template<template<typename> class C, // result container type
+         template<typename> class SC, // input container type
+         typename T, // element type of input container
+         typename F> // function type
+Q_REQUIRED_RESULT
+auto transform(const SC<T> &container, F function)
+     -> C<typename RemoveCvAndReference<decltype(declval<F>()(declval<T>()))>::type>
+{
+    return transform_impl(container, function);
+}
+
+
+//////////
+// transform for QStringList, because that isn't a specialization but a separate type
+// and g++ doesn't want to use the above templates for that
+// clang and msvc do find the base class QList<QString>
+//////////
+
+// QStringList -> QList<>
+template<typename F> // function type
+Q_REQUIRED_RESULT
+auto transform(const QStringList &container, F function)
+     -> QList<typename RemoveCvAndReference<decltype(declval<F>()(declval<QString>()))>::type>
+{
+    return transform_impl<QList>(QList<QString>(container), function);
+}
+
+// QStringList -> any container type
+template<template<typename> class C, // result container type
+         typename F> // function type
+Q_REQUIRED_RESULT
+auto transform(const QStringList &container, F function)
+     -> C<typename RemoveCvAndReference<decltype(declval<F>()(declval<QString>()))>::type>
+{
+    return transform_impl<C>(QList<QString>(container), function);
+}
+
 //////////////////
 // sort
 /////////////////