1 //===-- include/flang/Common/static-multimap-view.h -------------*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 
9 #ifndef FORTRAN_COMMON_STATIC_MULTIMAP_VIEW_H_
10 #define FORTRAN_COMMON_STATIC_MULTIMAP_VIEW_H_
11 #include <algorithm>
12 #include <utility>
13 
14 /// StaticMultimapView is a constexpr friendly multimap implementation over
15 /// sorted constexpr arrays. As the View name suggests, it does not duplicate
16 /// the sorted array but only brings range and search concepts over it. It
17 /// mainly erases the array size from the type and ensures the array is sorted
18 /// at compile time. When C++20 brings std::span and constexpr std::is_sorted,
19 /// this can most likely be replaced by those.
20 
21 namespace Fortran::common {
22 
23 template <typename V> class StaticMultimapView {
24 public:
25   using Key = typename V::Key;
26   using const_iterator = const V *;
27 
begin()28   constexpr const_iterator begin() const { return begin_; }
end()29   constexpr const_iterator end() const { return end_; }
30   // Be sure to static_assert(map.Verify(), "must be sorted"); for
31   // every instance constexpr created. Sadly this cannot be done in
32   // the ctor since there is no way to know whether the ctor is actually
33   // called at compile time or not.
34   template <std::size_t N>
StaticMultimapView(const V (& array)[N])35   constexpr StaticMultimapView(const V (&array)[N])
36       : begin_{&array[0]}, end_{&array[0] + N} {}
37 
38   // std::equal_range will be constexpr in C++20 only, so far there is actually
39   // no need for equal_range to be constexpr anyway.
equal_range(const Key & key)40   std::pair<const_iterator, const_iterator> equal_range(const Key &key) const {
41     return std::equal_range(begin_, end_, key);
42   }
43 
44   // Check that the array is sorted. This used to assert at compile time that
45   // the array is indeed sorted. When C++20 is required for flang,
46   // std::is_sorted can be used here since it will be constexpr.
Verify()47   constexpr bool Verify() const {
48     const V *lastSeen{begin_};
49     bool isSorted{true};
50     for (const auto *x{begin_}; x != end_; ++x) {
51       isSorted &= lastSeen->key <= x->key;
52       lastSeen = x;
53     }
54     return isSorted;
55   }
56 
57 private:
58   const_iterator begin_{nullptr};
59   const_iterator end_{nullptr};
60 };
61 } // namespace Fortran::common
62 #endif // FORTRAN_COMMON_STATIC_MULTIMAP_VIEW_H_
63