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