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 <ostream>
23 #include <utility>
24 
25 namespace minikin {
26 
27 // An undirected range.
28 class Range {
29 public:
30     static constexpr uint32_t NOWHERE = std::numeric_limits<uint32_t>::max();
31 
32     // start must be smaller than or equal to end otherwise the behavior is undefined.
Range(uint32_t start,uint32_t end)33     Range(uint32_t start, uint32_t end) : mStart(start), mEnd(end) {}
Range()34     Range() : Range(NOWHERE, NOWHERE) {}
35 
36     Range(const Range&) = default;
37     Range& operator=(const Range&) = default;
38 
invalidRange()39     static Range invalidRange() { return Range(NOWHERE, NOWHERE); }
isValid()40     inline bool isValid() const { return mStart != NOWHERE && mEnd != NOWHERE; }
41 
getStart()42     inline uint32_t getStart() const { return mStart; }       // inclusive
setStart(uint32_t start)43     inline void setStart(uint32_t start) { mStart = start; }  // inclusive
44 
getEnd()45     inline uint32_t getEnd() const { return mEnd; }   // exclusive
setEnd(uint32_t end)46     inline void setEnd(uint32_t end) { mEnd = end; }  // exclusive
47 
getLength()48     inline uint32_t getLength() const { return mEnd - mStart; }
49 
isEmpty()50     inline bool isEmpty() const { return mStart == mEnd; }
51 
toRangeOffset(uint32_t globalPos)52     inline uint32_t toRangeOffset(uint32_t globalPos) const { return globalPos - mStart; }
toGlobalOffset(uint32_t rangePos)53     inline uint32_t toGlobalOffset(uint32_t rangePos) const { return mStart + rangePos; }
54 
55     // The behavior is undefined if pos is out of range.
split(uint32_t pos)56     inline std::pair<Range, Range> split(uint32_t pos) const {
57         return std::make_pair(Range(mStart, pos), Range(pos, mEnd));
58     }
59 
contains(const Range & other)60     inline bool contains(const Range& other) const {
61         return mStart <= other.mStart && other.mEnd <= mEnd;
62     }
63 
64     // Returns true if the pos is in this range.
65     // For example,
66     //   const Range range(1, 2);  // 1 is inclusive, 2 is exclusive.
67     //   range.contains(0);  // false
68     //   range.contains(1);  // true
69     //   range.contains(2);  // false
contains(uint32_t pos)70     inline bool contains(uint32_t pos) const { return mStart <= pos && pos < mEnd; }
71 
72     // Returns true if left and right intersect.
intersects(const Range & left,const Range & right)73     inline static bool intersects(const Range& left, const Range& right) {
74         return left.isValid() && right.isValid() && left.mStart < right.mEnd &&
75                right.mStart < left.mEnd;
76     }
intersection(const Range & left,const Range & right)77     inline static Range intersection(const Range& left, const Range& right) {
78         return Range(std::max(left.mStart, right.mStart), std::min(left.mEnd, right.mEnd));
79     }
80 
81     // Returns merged range. This method assumes left and right are not invalid ranges and they have
82     // an intersection.
merge(const Range & left,const Range & right)83     static Range merge(const Range& left, const Range& right) {
84         return Range({std::min(left.mStart, right.mStart), std::max(left.mEnd, right.mEnd)});
85     }
86 
87     inline bool operator==(const Range& o) const { return mStart == o.mStart && mEnd == o.mEnd; }
88 
89     inline bool operator!=(const Range& o) const { return !(*this == o); }
90 
91     inline Range operator+(int32_t shift) const { return Range(mStart + shift, mEnd + shift); }
92 
93     inline Range operator-(int32_t shift) const { return Range(mStart - shift, mEnd - shift); }
94 
95 private:
96     // Helper class for "for (uint32_t i : range)" style for-loop.
97     class RangeIterator {
98     public:
RangeIterator(uint32_t pos)99         RangeIterator(uint32_t pos) : mPos(pos) {}
100 
101         inline bool operator!=(const RangeIterator& o) const { return o.mPos != mPos; }
102         inline uint32_t operator*() const { return mPos; }
103         inline RangeIterator& operator++() {
104             mPos++;
105             return *this;
106         }
107 
108     private:
109         uint32_t mPos;
110     };
111 
112 public:
begin()113     inline RangeIterator begin() const { return RangeIterator(mStart); }
end()114     inline RangeIterator end() const { return RangeIterator(mEnd); }
115 
116 private:
117     uint32_t mStart;
118     uint32_t mEnd;
119 };
120 
121 // For gtest output
122 inline std::ostream& operator<<(std::ostream& os, const Range& r) {
123     return os << "(" << r.getStart() << ", " << r.getEnd() << ")";
124 }
125 
126 }  // namespace minikin
127 
128 #endif  // MINIKIN_RANGE_H
129