Move containers utils to containers.hh and add filtered/transformed utils

16 files changed, 193 insertions, 72 deletions

diff --git a/src/buffer.cc b/src/buffer.cc
index 57a243e9..71cae3de 100644
--- a/src/buffer.cc
+++ b/src/buffer.cc
@@ -3,6 +3,7 @@
 #include "assert.hh"
 #include "buffer_manager.hh"
 #include "client.hh"
+#include "containers.hh"
 #include "context.hh"
 #include "file.hh"
 #include "interned_string.hh"
diff --git a/src/commands.cc b/src/commands.cc
index 80dd696e..2364d83f 100644
--- a/src/commands.cc
+++ b/src/commands.cc
@@ -7,6 +7,7 @@
 #include "client_manager.hh"
 #include "command_manager.hh"
 #include "completion.hh"
+#include "containers.hh"
 #include "context.hh"
 #include "debug.hh"
 #include "event_manager.hh"
diff --git a/src/containers.hh b/src/containers.hh
new file mode 100644
index 00000000..f4df5d45
--- /dev/null
+++ b/src/containers.hh
@@ -0,0 +1,172 @@
+#ifndef containers_hh_INCLUDED
+#define containers_hh_INCLUDED
+
+#include <algorithm>
+#include <utility>
+#include <iterator>
+
+namespace Kakoune
+{
+
+template<typename Container>
+struct ReversedContainer
+{
+    using iterator = decltype(std::declval<Container>().rbegin());
+    ReversedContainer(Container& container) : m_container(container) {}
+
+    iterator begin() { return m_container.rbegin(); }
+    iterator end()   { return m_container.rend(); }
+
+private:
+    Container& m_container;
+};
+
+template<typename Container>
+ReversedContainer<Container> reversed(Container&& container)
+{
+    return ReversedContainer<Container>(container);
+}
+
+template<typename Iterator, typename Filter>
+struct FilteredIterator : std::iterator<std::forward_iterator_tag,
+                                        typename Iterator::value_type>
+{
+    FilteredIterator(Filter filter, Iterator it, Iterator end)
+        : m_it(std::move(it)), m_end(std::move(end)), m_filter(std::move(filter))
+    {
+        do_filter();
+    }
+
+    auto operator*() -> decltype(*std::declval<Iterator>()) { return *m_it; }
+    FilteredIterator& operator++() { ++m_it; do_filter(); return *this; }
+    FilteredIterator operator++(int) { auto copy = *this; ++(*this); return copy; }
+
+    friend bool operator==(const FilteredIterator& lhs, const FilteredIterator& rhs)
+    {
+        return lhs.m_it == rhs.m_it;
+    }
+
+    friend bool operator!=(const FilteredIterator& lhs, const FilteredIterator& rhs)
+    {
+        return not (lhs == rhs);
+    }
+
+private:
+    void do_filter()
+    {
+        while (m_it != m_end and not m_filter(*m_it))
+            ++m_it;
+    }
+
+    Iterator m_it;
+    Iterator m_end;
+    Filter   m_filter;
+};
+
+template<typename Container, typename Filter>
+struct FilteredContainer
+{
+    using iterator = FilteredIterator<decltype(begin(std::declval<Container>())), Filter>;
+    FilteredContainer(Container& container, Filter filter)
+        : m_container(container), m_filter(std::move(filter)) {}
+
+    iterator begin() const { return iterator(m_filter, m_container.begin(), m_container.end()); }
+    iterator end()   const { return iterator(m_filter, m_container.end(), m_container.end()); }
+
+private:
+    Container& m_container;
+    Filter m_filter;
+};
+
+template<typename Container, typename Filter>
+FilteredContainer<Container, Filter> filtered(Container&& container, Filter filter)
+{
+    return FilteredContainer<Container, Filter>(container, std::move(filter));
+}
+
+template<typename Iterator, typename Transform>
+struct TransformedIterator : std::iterator<std::forward_iterator_tag,
+                                           typename std::remove_reference<decltype(std::declval<Transform>()(*std::declval<Iterator>()))>::type>
+{
+    TransformedIterator(Transform transform, Iterator it)
+        : m_it(std::move(it)), m_transform(std::move(transform)) {}
+
+    auto operator*() -> decltype(std::declval<Transform>()(*std::declval<Iterator>())) { return m_transform(*m_it); }
+    TransformedIterator& operator++() { ++m_it; return *this; }
+    TransformedIterator operator++(int) { auto copy = *this; ++m_it; return copy; }
+
+    friend bool operator==(const TransformedIterator& lhs, const TransformedIterator& rhs)
+    {
+        return lhs.m_it == rhs.m_it;
+    }
+
+    friend bool operator!=(const TransformedIterator& lhs, const TransformedIterator& rhs)
+    {
+        return not (lhs == rhs);
+    }
+
+private:
+    Iterator m_it;
+    Transform m_transform;
+};
+
+
+template<typename Container, typename Transform>
+struct TransformedContainer
+{
+    using iterator = TransformedIterator<decltype(begin(std::declval<Container>())), Transform>;
+    TransformedContainer(Container& container, Transform transform)
+        : m_container(container), m_transform(std::move(transform)) {}
+
+    iterator begin() const { return iterator(m_transform, m_container.begin()); }
+    iterator end()   const { return iterator(m_transform, m_container.end()); }
+
+private:
+    Container& m_container;
+    Transform m_transform;
+};
+
+template<typename Container, typename Transform>
+TransformedContainer<Container, Transform> transformed(Container&& container, Transform transform)
+{
+    return TransformedContainer<Container, Transform>(container, std::move(transform));
+}
+
+// Todo: move that into the following functions once we can remove the decltype
+//       return type.
+using std::begin;
+using std::end;
+
+template<typename Container, typename T>
+auto find(Container&& container, const T& value) -> decltype(begin(container))
+{
+    return std::find(begin(container), end(container), value);
+}
+
+template<typename Container, typename T>
+auto find_if(Container&& container, T op) -> decltype(begin(container))
+{
+    return std::find_if(begin(container), end(container), op);
+}
+
+template<typename Container, typename T>
+bool contains(Container&& container, const T& value)
+{
+    return find(container, value) != end(container);
+}
+
+template<typename Container, typename U>
+void unordered_erase(Container&& vec, U&& value)
+{
+    auto it = find(vec, std::forward<U>(value));
+    if (it != vec.end())
+    {
+        using std::swap;
+        swap(vec.back(), *it);
+        vec.pop_back();
+    }
+}
+
+}
+
+#endif // containers_hh_INCLUDED
diff --git a/src/event_manager.cc b/src/event_manager.cc
index 26a57eab..21cd6331 100644
--- a/src/event_manager.cc
+++ b/src/event_manager.cc
@@ -1,5 +1,7 @@
 #include "event_manager.hh"
 
+#include "containers.hh"
+
 #include <unistd.h>
 
 namespace Kakoune
diff --git a/src/face_registry.cc b/src/face_registry.cc
index 53e5867b..d99937c6 100644
--- a/src/face_registry.cc
+++ b/src/face_registry.cc
@@ -1,5 +1,6 @@
 #include "face_registry.hh"
 
+#include "containers.hh"
 #include "exception.hh"
 
 namespace Kakoune
@@ -7,8 +8,8 @@ namespace Kakoune
 
 static Face parse_face(StringView facedesc)
 {
-    auto bg_it = std::find(facedesc.begin(), facedesc.end(), ',');
-    auto attr_it = std::find(facedesc.begin(), facedesc.end(), '+');
+    auto bg_it = find(facedesc, ',');
+    auto attr_it = find(facedesc, '+');
     if (bg_it != facedesc.end() and attr_it < bg_it)
         throw runtime_error("invalid face description, expected <fg>[,<bg>][+<attr>]");
     Face res;
diff --git a/src/highlighter_group.cc b/src/highlighter_group.cc
index c796afbb..20058708 100644
--- a/src/highlighter_group.cc
+++ b/src/highlighter_group.cc
@@ -1,5 +1,7 @@
 #include "highlighter_group.hh"
 
+#include "containers.hh"
+
 namespace Kakoune
 {
 
diff --git a/src/id_map.hh b/src/id_map.hh
index 97d6f45e..a15903c1 100644
--- a/src/id_map.hh
+++ b/src/id_map.hh
@@ -1,9 +1,9 @@
 #ifndef id_map_hh_INCLUDED
 #define id_map_hh_INCLUDED
 
+#include "containers.hh"
 #include "completion.hh"
 #include "string.hh"
-#include "utils.hh"
 
 #include <vector>
 
diff --git a/src/keys.cc b/src/keys.cc
index a726a8c1..b10663ee 100644
--- a/src/keys.cc
+++ b/src/keys.cc
@@ -1,5 +1,8 @@
 #include "keys.hh"
 
+#include "containers.hh"
+#include "exception.hh"
+#include "string.hh"
 #include "utils.hh"
 #include "utf8_iterator.hh"
 
diff --git a/src/line_modification.hh b/src/line_modification.hh
index 3cd2d669..6f825c19 100644
--- a/src/line_modification.hh
+++ b/src/line_modification.hh
@@ -4,6 +4,8 @@
 #include "units.hh"
 #include "utils.hh"
 
+#include <vector>
+
 namespace Kakoune
 {
 
diff --git a/src/main.cc b/src/main.cc
index 885d7333..579eca35 100644
--- a/src/main.cc
+++ b/src/main.cc
@@ -5,6 +5,7 @@
 #include "client_manager.hh"
 #include "command_manager.hh"
 #include "commands.hh"
+#include "containers.hh"
 #include "context.hh"
 #include "debug.hh"
 #include "event_manager.hh"
diff --git a/src/ncurses_ui.cc b/src/ncurses_ui.cc
index b11f5a58..0a7dbf38 100644
--- a/src/ncurses_ui.cc
+++ b/src/ncurses_ui.cc
@@ -7,6 +7,7 @@
 #include "utf8_iterator.hh"
 
 #include <map>
+#include <algorithm>
 
 #define NCURSES_OPAQUE 0
 #define NCURSES_INTERNALS
diff --git a/src/normal.cc b/src/normal.cc
index e4b9c8d1..13f1fb7c 100644
--- a/src/normal.cc
+++ b/src/normal.cc
@@ -5,6 +5,7 @@
 #include "client_manager.hh"
 #include "command_manager.hh"
 #include "commands.hh"
+#include "containers.hh"
 #include "context.hh"
 #include "debug.hh"
 #include "face_registry.hh"
diff --git a/src/option_manager.hh b/src/option_manager.hh
index 439a0c53..c8fb1d5f 100644
--- a/src/option_manager.hh
+++ b/src/option_manager.hh
@@ -2,6 +2,7 @@
 #define option_manager_hh_INCLUDED
 
 #include "completion.hh"
+#include "containers.hh"
 #include "exception.hh"
 #include "flags.hh"
 #include "option_types.hh"
diff --git a/src/register_manager.cc b/src/register_manager.cc
index f3b6b06e..f9d36ae3 100644
--- a/src/register_manager.cc
+++ b/src/register_manager.cc
@@ -2,7 +2,7 @@
 
 #include "assert.hh"
 #include "id_map.hh"
-#include "utils.hh"
+#include "exception.hh"
 
 namespace Kakoune
 {
diff --git a/src/string.cc b/src/string.cc
index 152b90aa..6a1fda55 100644
--- a/src/string.cc
+++ b/src/string.cc
@@ -1,7 +1,7 @@
 #include "string.hh"
 
 #include "exception.hh"
-#include "utils.hh"
+#include "containers.hh"
 #include "utf8_iterator.hh"
 
 namespace Kakoune
diff --git a/src/utils.hh b/src/utils.hh
index c8e29f89..fbf39e10 100644
--- a/src/utils.hh
+++ b/src/utils.hh
@@ -2,11 +2,8 @@
 #define utils_hh_INCLUDED
 
 #include "assert.hh"
-#include "exception.hh"
 
-#include <algorithm>
 #include <memory>
-#include <vector>
 
 namespace Kakoune
 {
@@ -59,70 +56,6 @@ private:
 template<typename T>
 T* Singleton<T>::ms_instance = nullptr;
 
-// *** Containers helpers ***
-
-template<typename Container>
-struct ReversedContainer
-{
-    ReversedContainer(Container& container) : container(container) {}
-    Container& container;
-
-    decltype(container.rbegin()) begin() { return container.rbegin(); }
-    decltype(container.rend())   end()   { return container.rend(); }
-};
-
-template<typename Container>
-auto begin(ReversedContainer<Container>& c) -> decltype(c.begin())
-{
-    return c.begin();
-}
-
-template<typename Container>
-auto end(ReversedContainer<Container>& c) -> decltype(c.end())
-{
-    return c.end();
-}
-
-template<typename Container>
-ReversedContainer<Container> reversed(Container&& container)
-{
-    return ReversedContainer<Container>(container);
-}
-
-// Todo: move that into the following functions once we can remove the decltype
-//       return type.
-using std::begin;
-using std::end;
-
-template<typename Container, typename T>
-auto find(Container&& container, const T& value) -> decltype(begin(container))
-{
-    return std::find(begin(container), end(container), value);
-}
-
-template<typename Container, typename T>
-auto find_if(Container&& container, T op) -> decltype(begin(container))
-{
-    return std::find_if(begin(container), end(container), op);
-}
-
-template<typename Container, typename T>
-bool contains(Container&& container, const T& value)
-{
-    return find(container, value) != end(container);
-}
-
-template<typename T, typename U>
-void unordered_erase(std::vector<T>& vec, U&& value)
-{
-    auto it = find(vec, std::forward<U>(value));
-    if (it != vec.end())
-    {
-        std::swap(vec.back(), *it);
-        vec.pop_back();
-    }
-}
-
 template<typename Iterator, typename EndIterator, typename T>
 void skip_while(Iterator& it, const EndIterator& end, T condition)
 {