#ifndef LLVM_ADT_INTERVALMAP_H
#define LLVM_ADT_INTERVALMAP_H
-#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/PointerIntPair.h"
+#include "llvm/ADT/SmallVector.h"
#include "llvm/Support/Allocator.h"
#include "llvm/Support/RecyclingAllocator.h"
#include <iterator>
// A Path is used by iterators to represent a position in a B+-tree, and the
// path to get there from the root.
//
-// The Path class also constains the tree navigation code that doesn't have to
+// The Path class also contains the tree navigation code that doesn't have to
// be templatized.
//
//===----------------------------------------------------------------------===//
public:
typedef typename Sizer::Allocator Allocator;
+ typedef KeyT KeyType;
+ typedef ValT ValueType;
typedef Traits KeyTraits;
private:
/// const_iterator - Create an iterator that isn't pointing anywhere.
const_iterator() : map(0) {}
+ /// setMap - Change the map iterated over. This call must be followed by a
+ /// call to goToBegin(), goToEnd(), or find()
+ void setMap(const IntervalMap &m) { map = const_cast<IntervalMap*>(&m); }
+
/// valid - Return true if the current position is valid, false for end().
bool valid() const { return path.valid(); }
+ /// atBegin - Return true if the current position is the first map entry.
+ bool atBegin() const { return path.atBegin(); }
+
/// start - Return the beginning of the current interval.
const KeyT &start() const { return unsafeStart(); }
/// The search is started from the current position, and no earlier positions
/// can be found. This is much faster than find() for small moves.
void advanceTo(KeyT x) {
+ if (!valid())
+ return;
if (branched())
treeAdvanceTo(x);
else
CurSize[Nodes] = CurSize[NewNode];
Node[Nodes] = Node[NewNode];
CurSize[NewNode] = 0;
- Node[NewNode] = this->map->newNode<NodeT>();
+ Node[NewNode] = this->map->template newNode<NodeT>();
++Nodes;
}
///
template <typename MapA, typename MapB>
class IntervalMapOverlaps {
+ typedef typename MapA::KeyType KeyType;
typedef typename MapA::KeyTraits Traits;
typename MapA::const_iterator posA;
typename MapB::const_iterator posB;
/// either meets end.
/// Don't move the iterators if they are already overlapping.
void advance() {
+ if (!valid())
+ return;
+
+ if (Traits::stopLess(posA.stop(), posB.start())) {
+ // A ends before B begins. Catch up.
+ posA.advanceTo(posB.start());
+ if (!posA.valid() || !Traits::stopLess(posB.stop(), posA.start()))
+ return;
+ } else if (Traits::stopLess(posB.stop(), posA.start())) {
+ // B ends before A begins. Catch up.
+ posB.advanceTo(posA.start());
+ if (!posB.valid() || !Traits::stopLess(posA.stop(), posB.start()))
+ return;
+ } else
+ // Already overlapping.
+ return;
+
for (;;) {
// Make a.end > b.start.
posA.advanceTo(posB.start());
/// IntervalMapOverlaps - Create an iterator for the overlaps of a and b.
IntervalMapOverlaps(const MapA &a, const MapB &b)
: posA(b.empty() ? a.end() : a.find(b.start())),
- posB(posA.valid() ? b.find(posA.start()) : b.end()) {
- if (valid())
- advance();
- }
+ posB(posA.valid() ? b.find(posA.start()) : b.end()) { advance(); }
/// valid - Return true if iterator is at an overlap.
bool valid() const {
/// b - access the right hand side in the overlap.
const typename MapB::const_iterator &b() const { return posB; }
+ /// start - Beginning of the overlapping interval.
+ KeyType start() const {
+ KeyType ak = a().start();
+ KeyType bk = b().start();
+ return Traits::startLess(ak, bk) ? bk : ak;
+ }
+
+ /// stop - End of the overlapping interval.
+ KeyType stop() const {
+ KeyType ak = a().stop();
+ KeyType bk = b().stop();
+ return Traits::startLess(ak, bk) ? ak : bk;
+ }
+
/// skipA - Move to the next overlap that doesn't involve a().
void skipA() {
++posA;
- if (!posA.valid() || !Traits::stopLess(posB.stop(), posA.start()))
- return;
- // Second half-loop of advance().
- posB.advanceTo(posA.start());
- if (!posB.valid() || !Traits::stopLess(posA.stop(), posB.start()))
- return ;
advance();
}
/// skipB - Move to the next overlap that doesn't involve b().
void skipB() {
++posB;
- if (!posB.valid() || !Traits::stopLess(posA.stop(), posB.start()))
- return;
advance();
}
skipA();
return *this;
}
-};
+ /// advanceTo - Move to the first overlapping interval with
+ /// stopLess(x, stop()).
+ void advanceTo(KeyType x) {
+ if (!valid())
+ return;
+ // Make sure advanceTo sees monotonic keys.
+ if (Traits::stopLess(posA.stop(), x))
+ posA.advanceTo(x);
+ if (Traits::stopLess(posB.stop(), x))
+ posB.advanceTo(x);
+ advance();
+ }
+};
} // namespace llvm