class Interval {
private:
- uint64_t Start;
- uint64_t End;
+ int64_t Start;
+ int64_t End;
public:
- Interval(uint64_t S, uint64_t E) : Start(S), End(E) {}
+ Interval(int64_t S, int64_t E) : Start(S), End(E) {}
- uint64_t getStart() const { return Start; }
- uint64_t getEnd() const { return End; }
+ int64_t getStart() const { return Start; }
+ int64_t getEnd() const { return End; }
};
template <typename T>
}
};
-template <typename ImutInfo> class ImutIntervalAVLFactory;
-
template <typename ImutInfo>
class ImutIntervalAVLFactory : public ImutAVLFactory<ImutInfo> {
typedef ImutAVLTree<ImutInfo> TreeTy;
typedef typename ImutInfo::data_type_ref data_type_ref;
public:
+ ImutIntervalAVLFactory(BumpPtrAllocator &Alloc)
+ : ImutAVLFactory<ImutInfo>(Alloc) {}
+
TreeTy *Add(TreeTy *T, value_type_ref V) {
T = Add_internal(V,T);
- MarkImmutable(T);
+ this->MarkImmutable(T);
return T;
}
if (!T)
return NULL;
- key_type_ref CurrentKey = ImutInfo::KeyOfValue(Value(T));
+ key_type_ref CurrentKey = ImutInfo::KeyOfValue(this->Value(T));
if (ImutInfo::isContainedIn(K, CurrentKey))
return T;
else if (ImutInfo::isLess(K, CurrentKey))
- return Find(Left(T), K);
+ return Find(this->Left(T), K);
else
- return Find(Right(T), K);
+ return Find(this->Right(T), K);
}
private:
TreeTy *Add_internal(value_type_ref V, TreeTy *T) {
key_type_ref K = ImutInfo::KeyOfValue(V);
T = RemoveAllOverlaps(T, K);
- if (isEmpty(T))
- return CreateNode(NULL, V, NULL);
+ if (this->isEmpty(T))
+ return this->CreateNode(NULL, V, NULL);
assert(!T->isMutable());
- key_type_ref KCurrent = ImutInfo::KeyOfValue(Value(T));
+ key_type_ref KCurrent = ImutInfo::KeyOfValue(this->Value(T));
if (ImutInfo::isLess(K, KCurrent))
- return Balance(Add_internal(V, Left(T)), Value(T), Right(T));
+ return this->Balance(Add_internal(V, this->Left(T)), this->Value(T),
+ this->Right(T));
else
- return Balance(Left(T), Value(T), Add_internal(V, Right(T)));
+ return this->Balance(this->Left(T), this->Value(T),
+ Add_internal(V, this->Right(T)));
}
// Remove all overlaps from T.
do {
Changed = false;
T = RemoveOverlap(T, K, Changed);
- MarkImmutable(T);
+ this->MarkImmutable(T);
} while (Changed);
return T;
TreeTy *RemoveOverlap(TreeTy *T, key_type_ref K, bool &Changed) {
if (!T)
return NULL;
- Interval CurrentK = ImutInfo::KeyOfValue(Value(T));
+ Interval CurrentK = ImutInfo::KeyOfValue(this->Value(T));
// If current key does not overlap the inserted key.
if (CurrentK.getStart() > K.getEnd())
- return Balance(RemoveOverlap(Left(T), K, Changed), Value(T), Right(T));
+ return this->Balance(RemoveOverlap(this->Left(T), K, Changed),
+ this->Value(T), this->Right(T));
else if (CurrentK.getEnd() < K.getStart())
- return Balance(Left(T), Value(T), RemoveOverlap(Right(T), K, Changed));
+ return this->Balance(this->Left(T), this->Value(T),
+ RemoveOverlap(this->Right(T), K, Changed));
// Current key overlaps with the inserted key.
// Remove the current key.
Changed = true;
- TreeTy *OldNode = T;
- T = Remove_internal(CurrentK, T);
+ data_type_ref OldData = ImutInfo::DataOfValue(this->Value(T));
+ T = this->Remove_internal(CurrentK, T);
// Add back the unoverlapped part of the current key.
if (CurrentK.getStart() < K.getStart()) {
if (CurrentK.getEnd() <= K.getEnd()) {
Interval NewK(CurrentK.getStart(), K.getStart()-1);
- return Add_internal(std::make_pair<key_type, data_type>(NewK,
- ImutInfo::DataOfValue(Value(OldNode))), T);
+ return Add_internal(std::make_pair(NewK, OldData), T);
} else {
Interval NewK1(CurrentK.getStart(), K.getStart()-1);
- T = Add_internal(std::make_pair<key_type, data_type>(NewK1,
- ImutInfo::DataOfValue(Value(OldNode))), T);
+ T = Add_internal(std::make_pair(NewK1, OldData), T);
Interval NewK2(K.getEnd()+1, CurrentK.getEnd());
- return Add_internal(std::make_pair<key_type, data_type>(NewK2,
- ImutInfo::DataOfValue(Value(OldNode))), T);
+ return Add_internal(std::make_pair(NewK2, OldData), T);
}
} else {
if (CurrentK.getEnd() > K.getEnd()) {
Interval NewK(K.getEnd()+1, CurrentK.getEnd());
- return Add_internal(std::make_pair<key_type, data_type>(NewK,
- ImutInfo::DataOfValue(Value(OldNode))), T);
- }
+ return Add_internal(std::make_pair(NewK, OldData), T);
+ } else
+ return T;
}
}
};
ImutIntervalAVLFactory<ImutIntervalInfo<ValT> > F;
public:
+ Factory(BumpPtrAllocator& Alloc) : F(Alloc) {}
+
ImmutableIntervalMap GetEmptyMap() {
return ImmutableIntervalMap(F.GetEmptyTree());
}
else
return 0;
}
-
};
private: