1 //===-- include/flang/Common/interval.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_INTERVAL_H_ 10 #define FORTRAN_COMMON_INTERVAL_H_ 11 12 // Defines a generalized template class Interval<A> to represent 13 // the half-open interval [x .. x+n). 14 15 #include "idioms.h" 16 #include <algorithm> 17 #include <cstddef> 18 #include <utility> 19 20 namespace Fortran::common { 21 22 template <typename A> class Interval { 23 public: 24 using type = A; Interval()25 constexpr Interval() {} 26 constexpr Interval(const A &s, std::size_t n = 1) : start_{s}, size_{n} {} 27 constexpr Interval(A &&s, std::size_t n = 1) 28 : start_{std::move(s)}, size_{n} {} 29 constexpr Interval(const Interval &) = default; 30 constexpr Interval(Interval &&) = default; 31 constexpr Interval &operator=(const Interval &) = default; 32 constexpr Interval &operator=(Interval &&) = default; 33 34 constexpr bool operator<(const Interval &that) const { 35 return start_ < that.start_ || 36 (start_ == that.start_ && size_ < that.size_); 37 } 38 constexpr bool operator<=(const Interval &that) const { 39 return start_ < that.start_ || 40 (start_ == that.start_ && size_ <= that.size_); 41 } 42 constexpr bool operator==(const Interval &that) const { 43 return start_ == that.start_ && size_ == that.size_; 44 } 45 constexpr bool operator!=(const Interval &that) const { 46 return !(*this == that); 47 } 48 constexpr bool operator>=(const Interval &that) const { 49 return !(*this < that); 50 } 51 constexpr bool operator>(const Interval &that) const { 52 return !(*this <= that); 53 } 54 start()55 constexpr const A &start() const { return start_; } size()56 constexpr std::size_t size() const { return size_; } empty()57 constexpr bool empty() const { return size_ == 0; } 58 Contains(const A & x)59 constexpr bool Contains(const A &x) const { 60 return start_ <= x && x < start_ + size_; 61 } Contains(const Interval & that)62 constexpr bool Contains(const Interval &that) const { 63 return Contains(that.start_) && Contains(that.start_ + (that.size_ - 1)); 64 } IsDisjointWith(const Interval & that)65 constexpr bool IsDisjointWith(const Interval &that) const { 66 return that.NextAfter() <= start_ || NextAfter() <= that.start_; 67 } ImmediatelyPrecedes(const Interval & that)68 constexpr bool ImmediatelyPrecedes(const Interval &that) const { 69 return NextAfter() == that.start_; 70 } Annex(const Interval & that)71 void Annex(const Interval &that) { 72 size_ = (that.start_ + that.size_) - start_; 73 } AnnexIfPredecessor(const Interval & that)74 bool AnnexIfPredecessor(const Interval &that) { 75 if (ImmediatelyPrecedes(that)) { 76 size_ += that.size_; 77 return true; 78 } 79 return false; 80 } ExtendToCover(const Interval & that)81 void ExtendToCover(const Interval &that) { 82 if (size_ == 0) { 83 *this = that; 84 } else if (that.size_ != 0) { 85 const auto end{std::max(NextAfter(), that.NextAfter())}; 86 start_ = std::min(start_, that.start_); 87 size_ = end - start_; 88 } 89 } 90 MemberOffset(const A & x)91 std::size_t MemberOffset(const A &x) const { 92 CHECK(Contains(x)); 93 return x - start_; 94 } OffsetMember(std::size_t n)95 A OffsetMember(std::size_t n) const { 96 CHECK(n < size_); 97 return start_ + n; 98 } 99 Last()100 constexpr A Last() const { return start_ + (size_ - 1); } NextAfter()101 constexpr A NextAfter() const { return start_ + size_; } Prefix(std::size_t n)102 constexpr Interval Prefix(std::size_t n) const { 103 return {start_, std::min(size_, n)}; 104 } Suffix(std::size_t n)105 Interval Suffix(std::size_t n) const { 106 CHECK(n <= size_); 107 return {start_ + n, size_ - n}; 108 } 109 Intersection(const Interval & that)110 constexpr Interval Intersection(const Interval &that) const { 111 if (that.NextAfter() <= start_) { 112 return {}; 113 } else if (that.start_ <= start_) { 114 auto skip{start_ - that.start_}; 115 return {start_, std::min(size_, that.size_ - skip)}; 116 } else if (NextAfter() <= that.start_) { 117 return {}; 118 } else { 119 auto skip{that.start_ - start_}; 120 return {that.start_, std::min(that.size_, size_ - skip)}; 121 } 122 } 123 124 private: 125 A start_; 126 std::size_t size_{0}; 127 }; 128 } // namespace Fortran::common 129 #endif // FORTRAN_COMMON_INTERVAL_H_ 130