2 +----------------------------------------------------------------------+
4 +----------------------------------------------------------------------+
5 | Copyright (c) 2010-present Facebook, Inc. (http://www.facebook.com) |
6 +----------------------------------------------------------------------+
7 | This source file is subject to version 3.01 of the PHP license, |
8 | that is bundled with this package in the file LICENSE, and is |
9 | available through the world-wide-web at the following url: |
10 | http://www.php.net/license/3_01.txt |
11 | If you did not receive a copy of the PHP license and are unable to |
12 | obtain it through the world-wide-web, please send a note to |
13 | license@php.net so we can mail you a copy immediately. |
14 +----------------------------------------------------------------------+
17 #include "hphp/util/interval-set.h"
19 #include "hphp/util/assertions.h"
20 #include "hphp/util/compilation-flags.h"
26 IntervalSet
IntervalSet::operator ~() const {
29 for (auto const& i
: intervals
) {
30 if (i
.start
> start
) {
31 ret
.intervals
.push_back({start
, i
.start
- 1});
32 if (i
.end
== POS_INF
) return ret
.checkInvariants();
36 ret
.intervals
.push_back({start
, POS_INF
});
37 return ret
.checkInvariants();
39 IntervalSet
& IntervalSet::operator |=(const IntervalSet
& o
) {
43 IntervalSet
& IntervalSet::operator &=(const IntervalSet
& o
) {
47 IntervalSet
& IntervalSet::operator -=(const IntervalSet
& o
) {
51 IntervalSet
IntervalSet::operator |(const IntervalSet
& o
) const {
53 size_t j0
= 0, j1
= 0;
54 while (j0
< intervals
.size() || j1
< o
.intervals
.size()) {
56 if (j0
== intervals
.size()) return o
.intervals
[j1
++];
57 if (j1
== o
.intervals
.size()) return intervals
[j0
++];
58 if (intervals
[j0
].start
< o
.intervals
[j1
].start
) return intervals
[j0
++];
59 return o
.intervals
[j1
++];
61 if (!ret
.intervals
.size()) {
62 ret
.intervals
.emplace_back(i
);
65 auto& last
= ret
.intervals
.back();
66 if (last
.end
== POS_INF
) return ret
.checkInvariants();
67 if (last
.end
+ 1 >= i
.start
) {
68 if (i
.end
> last
.end
) last
.end
= i
.end
;
70 ret
.intervals
.emplace_back(i
);
73 return ret
.checkInvariants();
75 IntervalSet
IntervalSet::operator &(const IntervalSet
& o
) const {
77 size_t j0
= 0, j1
= 0;
78 while (j0
< intervals
.size() && j1
< o
.intervals
.size()) {
79 auto const& i0
= intervals
[j0
];
80 auto const& i1
= o
.intervals
[j1
];
81 if (i0
.end
< i1
.start
) {
83 } else if (i1
.end
< i0
.start
) {
86 ret
.intervals
.push_back({
87 std::max(i0
.start
, i1
.start
),
88 std::min(i0
.end
, i1
.end
)
90 if (i0
.end
< i1
.end
) j0
++;
94 return ret
.checkInvariants();
96 IntervalSet
IntervalSet::operator -(const IntervalSet
& o
) const {
100 bool IntervalSet::operator ==(const IntervalSet
& o
) const {
101 return intervals
== o
.intervals
;
103 bool IntervalSet::operator !=(const IntervalSet
& o
) const {
104 return !(*this == o
);
107 IntervalSet
IntervalSet::None() { return IntervalSet
{}; }
108 IntervalSet
IntervalSet::All() {
109 return Inclusive(NEG_INF
, POS_INF
);
111 IntervalSet
IntervalSet::Point(value_type v
) {
113 ret
.intervals
.push_back({v
, v
});
114 return ret
.checkInvariants();
116 IntervalSet
IntervalSet::Inclusive(value_type start
, value_type end
) {
118 ret
.intervals
.push_back({start
, end
});
119 return ret
.checkInvariants();
121 IntervalSet
IntervalSet::Range(value_type start
, value_type end
) {
122 assertx(start
!= NEG_INF
);
123 assert_flog(start
<= end
, "start: {}, end: {}", start
, end
);
124 if (start
== end
) return None();
126 ret
.intervals
.push_back({start
, end
- 1});
127 return ret
.checkInvariants();
129 IntervalSet
IntervalSet::Below(value_type end
) {
130 assertx(end
!= NEG_INF
);
132 ret
.intervals
.push_back({NEG_INF
, end
- 1});
133 return ret
.checkInvariants();
135 IntervalSet
IntervalSet::Above(value_type start
) {
137 ret
.intervals
.push_back({start
, POS_INF
});
138 return ret
.checkInvariants();
141 std::string
IntervalSet::toString() const {
143 std::ostringstream os
;
145 for (auto const& i
: intervals
) {
147 if (i
.start
== NEG_INF
) os
<< "(-INF";
148 else os
<< "[" << i
.start
;
150 if (i
.end
== POS_INF
) os
<< "+INF";
151 else os
<< i
.end
+ 1;
159 IntervalSet
& IntervalSet::checkInvariants() {
160 if constexpr (!debug
) return *this;
161 SCOPE_ASSERT_DETAIL("IntervalSet") {
164 for (size_t j
= 0; j
< intervals
.size(); j
++) {
165 always_assert(intervals
[j
].start
<= intervals
[j
].end
);
166 always_assert(IMPLIES(j
, intervals
[j
- 1].end
< POS_INF
));
167 always_assert(IMPLIES(j
, intervals
[j
- 1].end
+ 1 < intervals
[j
].start
));
171 const IntervalSet
& IntervalSet::checkInvariants() const {
172 return const_cast<IntervalSet
*>(this)->checkInvariants();