1 /*
2  * Copyright (C) 2017 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 #ifndef MINIKIN_RANGE_H
18 #define MINIKIN_RANGE_H
19 
20 #include <algorithm>
21 #include <limits>
22 #include <utility>
23 
24 namespace minikin {
25 
26 // An undirected range.
27 class Range {
28 public:
29     static constexpr uint32_t NOWHERE = std::numeric_limits<uint32_t>::max();
30 
31     // start must be smaller than or equal to end otherwise the behavior is undefined.
Range(uint32_t start,uint32_t end)32     Range(uint32_t start, uint32_t end) : mStart(start), mEnd(end) {}
Range()33     Range() : Range(NOWHERE, NOWHERE) {}
34 
35     Range(const Range&) = default;
36     Range& operator=(const Range&) = default;
37 
invalidRange()38     static Range invalidRange() { return Range(NOWHERE, NOWHERE); }
isValid()39     inline bool isValid() const { return mStart != NOWHERE && mEnd != NOWHERE; }
40 
getStart()41     inline uint32_t getStart() const { return mStart; }       // inclusive
setStart(uint32_t start)42     inline void setStart(uint32_t start) { mStart = start; }  // inclusive
43 
getEnd()44     inline uint32_t getEnd() const { return mEnd; }   // exclusive
setEnd(uint32_t end)45     inline void setEnd(uint32_t end) { mEnd = end; }  // exclusive
46 
getLength()47     inline uint32_t getLength() const { return mEnd - mStart; }
48 
isEmpty()49     inline bool isEmpty() const { return mStart == mEnd; }
50 
toRangeOffset(uint32_t globalPos)51     inline uint32_t toRangeOffset(uint32_t globalPos) const { return globalPos - mStart; }
toGlobalOffset(uint32_t rangePos)52     inline uint32_t toGlobalOffset(uint32_t rangePos) const { return mStart + rangePos; }
53 
54     // The behavior is undefined if pos is out of range.
split(uint32_t pos)55     inline std::pair<Range, Range> split(uint32_t pos) const {
56         return std::make_pair(Range(mStart, pos), Range(pos, mEnd));
57     }
58 
contains(const Range & other)59     inline bool contains(const Range& other) const {
60         return mStart <= other.mStart && other.mEnd <= mEnd;
61     }
62 
63     // Returns true if the pos is in this range.
64     // For example,
65     //   const Range range(1, 2);  // 1 is inclusive, 2 is exclusive.
66     //   range.contains(0);  // false
67     //   range.contains(1);  // true
68     //   range.contains(2);  // false
contains(uint32_t pos)69     inline bool contains(uint32_t pos) const { return mStart <= pos && pos < mEnd; }
70 
71     // Returns true if left and right intersect.
intersects(const Range & left,const Range & right)72     inline static bool intersects(const Range& left, const Range& right) {
73         return left.isValid() && right.isValid() && left.mStart < right.mEnd &&
74                right.mStart < left.mEnd;
75     }
intersection(const Range & left,const Range & right)76     inline static Range intersection(const Range& left, const Range& right) {
77         return Range(std::max(left.mStart, right.mStart), std::min(left.mEnd, right.mEnd));
78     }
79 
80     // Returns merged range. This method assumes left and right are not invalid ranges and they have
81     // an intersection.
merge(const Range & left,const Range & right)82     static Range merge(const Range& left, const Range& right) {
83         return Range({std::min(left.mStart, right.mStart), std::max(left.mEnd, right.mEnd)});
84     }
85 
86     inline bool operator==(const Range& o) const { return mStart == o.mStart && mEnd == o.mEnd; }
87 
88     inline bool operator!=(const Range& o) const { return !(*this == o); }
89 
90     inline Range operator+(int32_t shift) const { return Range(mStart + shift, mEnd + shift); }
91 
92     inline Range operator-(int32_t shift) const { return Range(mStart - shift, mEnd - shift); }
93 
94 private:
95     // Helper class for "for (uint32_t i : range)" style for-loop.
96     class RangeIterator {
97     public:
RangeIterator(uint32_t pos)98         RangeIterator(uint32_t pos) : mPos(pos) {}
99 
100         inline bool operator!=(const RangeIterator& o) const { return o.mPos != mPos; }
101         inline uint32_t operator*() const { return mPos; }
102         inline RangeIterator& operator++() {
103             mPos++;
104             return *this;
105         }
106 
107     private:
108         uint32_t mPos;
109     };
110 
111 public:
begin()112     inline RangeIterator begin() const { return RangeIterator(mStart); }
end()113     inline RangeIterator end() const { return RangeIterator(mEnd); }
114 
115 private:
116     uint32_t mStart;
117     uint32_t mEnd;
118 };
119 
120 }  // namespace minikin
121 
122 #endif  // MINIKIN_RANGE_H
123