1 // Copyright (c) 2018-2019, NVIDIA CORPORATION. All rights reserved. 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); 4 // you may not use this file except in compliance with the License. 5 // You may obtain a copy of the License at 6 // 7 // http://www.apache.org/licenses/LICENSE-2.0 8 // 9 // Unless required by applicable law or agreed to in writing, software 10 // distributed under the License is distributed on an "AS IS" BASIS, 11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 // See the License for the specific language governing permissions and 13 // limitations under the License. 14 15 #ifndef FORTRAN_COMMON_INTERVAL_H_ 16 #define FORTRAN_COMMON_INTERVAL_H_ 17 18 // Defines a generalized template class Interval<A> to represent 19 // the half-open interval [x .. x+n). 20 21 #include "idioms.h" 22 #include <cstddef> 23 #include <utility> 24 25 namespace Fortran::common { 26 27 template<typename A> class Interval { 28 public: 29 using type = A; Interval()30 constexpr Interval() {} 31 constexpr Interval(const A &s, std::size_t n = 1) : start_{s}, size_{n} {} 32 constexpr Interval(A &&s, std::size_t n = 1) 33 : start_{std::move(s)}, size_{n} {} 34 constexpr Interval(const Interval &) = default; 35 constexpr Interval(Interval &&) = default; 36 constexpr Interval &operator=(const Interval &) = default; 37 constexpr Interval &operator=(Interval &&) = default; 38 39 constexpr bool operator==(const Interval &that) const { 40 return start_ == that.start_ && size_ == that.size_; 41 } 42 constexpr bool operator!=(const Interval &that) const { 43 return !(*this == that); 44 } 45 start()46 constexpr const A &start() const { return start_; } size()47 constexpr std::size_t size() const { return size_; } empty()48 constexpr bool empty() const { return size_ == 0; } 49 Contains(const A & x)50 constexpr bool Contains(const A &x) const { 51 return start_ <= x && x < start_ + size_; 52 } Contains(const Interval & that)53 constexpr bool Contains(const Interval &that) const { 54 return Contains(that.start_) && Contains(that.start_ + (that.size_ - 1)); 55 } IsDisjointWith(const Interval & that)56 constexpr bool IsDisjointWith(const Interval &that) const { 57 return that.NextAfter() <= start_ || NextAfter() <= that.start_; 58 } ImmediatelyPrecedes(const Interval & that)59 constexpr bool ImmediatelyPrecedes(const Interval &that) const { 60 return NextAfter() == that.start_; 61 } Annex(const Interval & that)62 void Annex(const Interval &that) { 63 size_ = (that.start_ + that.size_) - start_; 64 } AnnexIfPredecessor(const Interval & that)65 bool AnnexIfPredecessor(const Interval &that) { 66 if (ImmediatelyPrecedes(that)) { 67 size_ += that.size_; 68 return true; 69 } 70 return false; 71 } ExtendToCover(const Interval & that)72 void ExtendToCover(const Interval &that) { 73 if (size_ == 0) { 74 *this = that; 75 } else if (that.size_ != 0) { 76 const auto end{std::max(NextAfter(), that.NextAfter())}; 77 start_ = std::min(start_, that.start_); 78 size_ = end - start_; 79 } 80 } 81 MemberOffset(const A & x)82 std::size_t MemberOffset(const A &x) const { 83 CHECK(Contains(x)); 84 return x - start_; 85 } OffsetMember(std::size_t n)86 A OffsetMember(std::size_t n) const { 87 CHECK(n < size_); 88 return start_ + n; 89 } 90 Last()91 constexpr A Last() const { return start_ + (size_ - 1); } NextAfter()92 constexpr A NextAfter() const { return start_ + size_; } Prefix(std::size_t n)93 constexpr Interval Prefix(std::size_t n) const { 94 return {start_, std::min(size_, n)}; 95 } Suffix(std::size_t n)96 Interval Suffix(std::size_t n) const { 97 CHECK(n <= size_); 98 return {start_ + n, size_ - n}; 99 } 100 Intersection(const Interval & that)101 constexpr Interval Intersection(const Interval &that) const { 102 if (that.NextAfter() <= start_) { 103 return {}; 104 } else if (that.start_ <= start_) { 105 auto skip{start_ - that.start_}; 106 return {start_, std::min(size_, that.size_ - skip)}; 107 } else if (NextAfter() <= that.start_) { 108 return {}; 109 } else { 110 auto skip{that.start_ - start_}; 111 return {that.start_, std::min(that.size_, size_ - skip)}; 112 } 113 } 114 115 private: 116 A start_; 117 std::size_t size_{0}; 118 }; 119 } 120 #endif // FORTRAN_COMMON_INTERVAL_H_ 121