1 //===--------- interval_map.h - A sorted interval map -----------*- C++ -*-===//
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
11 //===----------------------------------------------------------------------===//
64     // Early out if the key is clearly outside the range.  in find()
65     if (empty() || K < begin()->first.first ||  in find()
66         K >= std::prev(end())->first.second)  in find()
69     auto I = Impl.upper_bound(K);  in find()
72     if (K < I->first.second)  in find()
78     return const_cast<IntervalMapBase<KeyT, ValT> *>(this)->find(K);  in find()
82     auto I = find(K);
85     return I->second;
89   // range in the map. Removal is allowed to split the range.
94     auto J = Impl.upper_bound(KS);  in erase()
96     // Check previous range. Bail out if range to remove is entirely after  in erase()
98     auto I = std::prev(J);  in erase()
99     if (KS >= I->first.second)  in erase()
102     // Assert that range is wholly contained.  in erase()
103     assert(KE <= I->first.second);  in erase()
105     auto Tmp = std::move(*I);  in erase()
108     // Split-right -- introduce right-split range.  in erase()
115     // Split-left -- introduce left-split range.  in erase()
132   // Coalescing insert. Requires that ValTs be equality-comparable.
134     auto J = this->Impl.upper_bound(KS);  in insert()
136     // Coalesce-right if possible. Either way, J points at our insertion  in insert()
138     if (J != this->end() && KE == J->first.first && J->second == V) {  in insert()
139       KE = J->first.second;  in insert()
140       auto Tmp = J++;  in insert()
141       this->Impl.erase(Tmp);  in insert()
144     // Coalesce-left if possible.  in insert()
145     if (J != this->begin()) {  in insert()
146       auto I = std::prev(J);  in insert()
147       if (I->first.second == KS && I->second == V) {  in insert()
148         KS = I->first.first;  in insert()
149         this->Impl.erase(I);  in insert()
152     this->Impl.insert(J, std::make_pair(std::make_pair(KS, KE), std::move(V)));  in insert()
160   // Non-coalescing insert. Does not require ValT to be equality-comparable.
162     this->Impl.insert(std::make_pair(std::make_pair(KS, KE), std::move(V)));  in insert()