ActsExamples/Utilities/GroupBy.hpp

0001 // This file is part of the Acts project.
0002 //
0003 // Copyright (C) 2020 CERN for the benefit of the Acts project
0004 //
0005 // This Source Code Form is subject to the terms of the Mozilla Public
0006 // License, v. 2.0. If a copy of the MPL was not distributed with this
0007 // file, You can obtain one at http://mozilla.org/MPL/2.0/.
0008
0009 #pragma once
0010
0011 #include "ActsExamples/Utilities/Range.hpp"
0012
0013 #include <algorithm>
0014 #include <iterator>
0015 #include <utility>
0016
0017 namespace ActsExamples {
0018
0019 /// Proxy for iterating over groups of elements within a container.
0020 ///
0021 /// @note Each group will contain at least one element.
0022 ///
0023 /// Consecutive elements with the same key (as defined by the KeyGetter) are
0024 /// placed in one group. The proxy should always be used as part of a
0025 /// range-based for loop. In combination with structured bindings to reduce the
0026 /// boilerplate, the group iteration can be written as
0027 ///
0028 ///     for (auto&& [key, elements] : GroupBy<...>(...)) {
0029 ///         // do something with just the key
0030 ///         ...
0031 ///
0032 ///         // iterate over the group elements
0033 ///         for (const auto& element : elements) {
0034 ///             ...
0035 ///         }
0036 ///     }
0037 ///
0038 template <typename Iterator, typename KeyGetter>
0039 class GroupBy {
0040  public:
0041   /// The key type that identifies elements within a group.
0042   using Key = std::decay_t<decltype(KeyGetter()(*Iterator()))>;
0043   /// A Group is an iterator range with the associated key.
0044   using Group = std::pair<Key, Range<Iterator>>;
0045   /// Iterator type representing the end of the groups.
0046   ///
0047   /// The end iterator will not be dereferenced in C++17 range-based loops. It
0048   /// can thus be a simpler type without the overhead of the full group iterator
0049   /// below.
0050   using GroupEndIterator = Iterator;
0051   /// Iterator type representing a group of elements.
0052   class GroupIterator {
0053    public:
0054     using iterator_category = std::input_iterator_tag;
0055     using value_type = Group;
0056     using difference_type = std::ptrdiff_t;
0057     using pointer = Group*;
0058     using reference = Group&;
0059
0060     constexpr GroupIterator(const GroupBy& groupBy, Iterator groupBegin)
0061         : m_groupBy(groupBy),
0062           m_groupBegin(groupBegin),
0063           m_groupEnd(groupBy.findEndOfGroup(groupBegin)) {}
0064     /// Pre-increment operator to advance to the next group.
0065     constexpr GroupIterator& operator++() {
0066       // make the current end the new group beginning
0067       std::swap(m_groupBegin, m_groupEnd);
0068       // find the end of the next group starting from the new beginning
0069       m_groupEnd = m_groupBy.findEndOfGroup(m_groupBegin);
0070       return *this;
0071     }
0072     /// Post-increment operator to advance to the next group.
0073     constexpr GroupIterator operator++(int) {
0074       GroupIterator retval = *this;
0075       ++(*this);
0076       return retval;
0077     }
0078     /// Dereference operator that returns the pointed-to group of elements.
0079     constexpr Group operator*() const {
0080       const Key key = (m_groupBegin != m_groupEnd)
0081                           ? m_groupBy.m_keyGetter(*m_groupBegin)
0082                           : Key();
0083       return {key, makeRange(m_groupBegin, m_groupEnd)};
0084     }
0085
0086    private:
0087     const GroupBy& m_groupBy;
0088     Iterator m_groupBegin;
0089     Iterator m_groupEnd;
0090
0091     friend constexpr bool operator==(const GroupIterator& lhs,
0092                                      const GroupEndIterator& rhs) {
0093       return lhs.m_groupBegin == rhs;
0094     }
0095     friend constexpr bool operator!=(const GroupIterator& lhs,
0096                                      const GroupEndIterator& rhs) {
0097       return !(lhs == rhs);
0098     }
0099   };
0100
0101   /// Construct the group-by proxy for an iterator range.
0102   constexpr GroupBy(Iterator begin, Iterator end,
0103                     KeyGetter keyGetter = KeyGetter())
0104       : m_begin(begin), m_end(end), m_keyGetter(std::move(keyGetter)) {}
0105   constexpr GroupIterator begin() const {
0106     return GroupIterator(*this, m_begin);
0107   }
0108   constexpr GroupEndIterator end() const { return m_end; }
0109   constexpr bool empty() const { return m_begin == m_end; }
0110
0111  private:
0112   Iterator m_begin;
0113   Iterator m_end;
0114   KeyGetter m_keyGetter;
0115
0116   /// Find the end of the group that starts at the given position.
0117   ///
0118   /// This uses a linear search from the start position and thus has linear
0119   /// complexity in the group size. It does not assume any ordering of the
0120   /// underlying container and is a cache-friendly access pattern.
0121   constexpr Iterator findEndOfGroup(Iterator start) const {
0122     // check for end so we can safely dereference the start iterator.
0123     if (start == m_end) {
0124       return start;
0125     }
0126     // search the first element that does not share a key with the start.
0127     return std::find_if_not(std::next(start), m_end,
0128                             [this, start](const auto& x) {
0129                               return m_keyGetter(x) == m_keyGetter(*start);
0130                             });
0131   }
0132 };
0133
0134 /// Construct the group-by proxy for a container.
0135 template <typename Container, typename KeyGetter>
0136 auto makeGroupBy(const Container& container, KeyGetter keyGetter)
0137     -> GroupBy<decltype(std::begin(container)), KeyGetter> {
0138   return {std::begin(container), std::end(container), std::move(keyGetter)};
0139 }
0140
0141 }  // namespace ActsExamples