1 //===- llvm/ADT/IntervalMap.h - A sorted interval map -----------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements a coalescing interval map for small objects.
12 // KeyT objects are mapped to ValT objects. Intervals of keys that map to the
13 // same value are represented in a compressed form.
15 // Iterators provide ordered access to the compressed intervals rather than the
16 // individual keys, and insert and erase operations use key intervals as well.
18 // Like SmallVector, IntervalMap will store the first N intervals in the map
19 // object itself without any allocations. When space is exhausted it switches to
20 // a B+-tree representation with very small overhead for small key and value
23 // A Traits class specifies how keys are compared. It also allows IntervalMap to
24 // work with both closed and half-open intervals.
26 // Keys and values are not stored next to each other in a std::pair, so we don't
27 // provide such a value_type. Dereferencing iterators only returns the mapped
28 // value. The interval bounds are accessible through the start() and stop()
31 // IntervalMap is optimized for small key and value objects, 4 or 8 bytes each
32 // is the optimal size. For large objects use std::map instead.
34 //===----------------------------------------------------------------------===//
38 // template <typename KeyT, typename ValT, unsigned N, typename Traits>
39 // class IntervalMap {
41 // typedef KeyT key_type;
42 // typedef ValT mapped_type;
43 // typedef RecyclingAllocator<...> Allocator;
45 // class const_iterator;
47 // explicit IntervalMap(Allocator&);
50 // bool empty() const;
51 // KeyT start() const;
53 // ValT lookup(KeyT x, Value NotFound = Value()) const;
55 // const_iterator begin() const;
56 // const_iterator end() const;
59 // const_iterator find(KeyT x) const;
60 // iterator find(KeyT x);
62 // void insert(KeyT a, KeyT b, ValT y);
66 // template <typename KeyT, typename ValT, unsigned N, typename Traits>
67 // class IntervalMap::const_iterator :
68 // public std::iterator<std::bidirectional_iterator_tag, ValT> {
70 // bool operator==(const const_iterator &) const;
71 // bool operator!=(const const_iterator &) const;
72 // bool valid() const;
74 // const KeyT &start() const;
75 // const KeyT &stop() const;
76 // const ValT &value() const;
77 // const ValT &operator*() const;
78 // const ValT *operator->() const;
80 // const_iterator &operator++();
81 // const_iterator &operator++(int);
82 // const_iterator &operator--();
83 // const_iterator &operator--(int);
87 // void advanceTo(KeyT x);
90 // template <typename KeyT, typename ValT, unsigned N, typename Traits>
91 // class IntervalMap::iterator : public const_iterator {
93 // void insert(KeyT a, KeyT b, Value y);
97 //===----------------------------------------------------------------------===//
99 #ifndef LLVM_ADT_INTERVALMAP_H
100 #define LLVM_ADT_INTERVALMAP_H
102 #include "llvm/ADT/PointerIntPair.h"
103 #include "llvm/ADT/SmallVector.h"
104 #include "llvm/Support/Allocator.h"
105 #include "llvm/Support/RecyclingAllocator.h"
111 //===----------------------------------------------------------------------===//
112 //--- Key traits ---//
113 //===----------------------------------------------------------------------===//
115 // The IntervalMap works with closed or half-open intervals.
116 // Adjacent intervals that map to the same value are coalesced.
118 // The IntervalMapInfo traits class is used to determine if a key is contained
119 // in an interval, and if two intervals are adjacent so they can be coalesced.
120 // The provided implementation works for closed integer intervals, other keys
121 // probably need a specialized version.
123 // The point x is contained in [a;b] when !startLess(x, a) && !stopLess(b, x).
125 // It is assumed that (a;b] half-open intervals are not used, only [a;b) is
126 // allowed. This is so that stopLess(a, b) can be used to determine if two
127 // intervals overlap.
129 //===----------------------------------------------------------------------===//
131 template <typename T
>
132 struct IntervalMapInfo
{
134 /// startLess - Return true if x is not in [a;b].
135 /// This is x < a both for closed intervals and for [a;b) half-open intervals.
136 static inline bool startLess(const T
&x
, const T
&a
) {
140 /// stopLess - Return true if x is not in [a;b].
141 /// This is b < x for a closed interval, b <= x for [a;b) half-open intervals.
142 static inline bool stopLess(const T
&b
, const T
&x
) {
146 /// adjacent - Return true when the intervals [x;a] and [b;y] can coalesce.
147 /// This is a+1 == b for closed intervals, a == b for half-open intervals.
148 static inline bool adjacent(const T
&a
, const T
&b
) {
154 template <typename T
>
155 struct IntervalMapHalfOpenInfo
{
157 /// startLess - Return true if x is not in [a;b).
158 static inline bool startLess(const T
&x
, const T
&a
) {
162 /// stopLess - Return true if x is not in [a;b).
163 static inline bool stopLess(const T
&b
, const T
&x
) {
167 /// adjacent - Return true when the intervals [x;a) and [b;y) can coalesce.
168 static inline bool adjacent(const T
&a
, const T
&b
) {
174 /// IntervalMapImpl - Namespace used for IntervalMap implementation details.
175 /// It should be considered private to the implementation.
176 namespace IntervalMapImpl
{
178 // Forward declarations.
179 template <typename
, typename
, unsigned, typename
> class LeafNode
;
180 template <typename
, typename
, unsigned, typename
> class BranchNode
;
182 typedef std::pair
<unsigned,unsigned> IdxPair
;
185 //===----------------------------------------------------------------------===//
186 //--- IntervalMapImpl::NodeBase ---//
187 //===----------------------------------------------------------------------===//
189 // Both leaf and branch nodes store vectors of pairs.
190 // Leaves store ((KeyT, KeyT), ValT) pairs, branches use (NodeRef, KeyT).
192 // Keys and values are stored in separate arrays to avoid padding caused by
193 // different object alignments. This also helps improve locality of reference
194 // when searching the keys.
196 // The nodes don't know how many elements they contain - that information is
197 // stored elsewhere. Omitting the size field prevents padding and allows a node
198 // to fill the allocated cache lines completely.
200 // These are typical key and value sizes, the node branching factor (N), and
201 // wasted space when nodes are sized to fit in three cache lines (192 bytes):
203 // T1 T2 N Waste Used by
204 // 4 4 24 0 Branch<4> (32-bit pointers)
205 // 8 4 16 0 Leaf<4,4>, Branch<4>
206 // 8 8 12 0 Leaf<4,8>, Branch<8>
207 // 16 4 9 12 Leaf<8,4>
208 // 16 8 8 0 Leaf<8,8>
210 //===----------------------------------------------------------------------===//
212 template <typename T1
, typename T2
, unsigned N
>
215 enum { Capacity
= N
};
220 /// copy - Copy elements from another node.
221 /// @param Other Node elements are copied from.
222 /// @param i Beginning of the source range in other.
223 /// @param j Beginning of the destination range in this.
224 /// @param Count Number of elements to copy.
225 template <unsigned M
>
226 void copy(const NodeBase
<T1
, T2
, M
> &Other
, unsigned i
,
227 unsigned j
, unsigned Count
) {
228 assert(i
+ Count
<= M
&& "Invalid source range");
229 assert(j
+ Count
<= N
&& "Invalid dest range");
230 for (unsigned e
= i
+ Count
; i
!= e
; ++i
, ++j
) {
231 first
[j
] = Other
.first
[i
];
232 second
[j
] = Other
.second
[i
];
236 /// moveLeft - Move elements to the left.
237 /// @param i Beginning of the source range.
238 /// @param j Beginning of the destination range.
239 /// @param Count Number of elements to copy.
240 void moveLeft(unsigned i
, unsigned j
, unsigned Count
) {
241 assert(j
<= i
&& "Use moveRight shift elements right");
242 copy(*this, i
, j
, Count
);
245 /// moveRight - Move elements to the right.
246 /// @param i Beginning of the source range.
247 /// @param j Beginning of the destination range.
248 /// @param Count Number of elements to copy.
249 void moveRight(unsigned i
, unsigned j
, unsigned Count
) {
250 assert(i
<= j
&& "Use moveLeft shift elements left");
251 assert(j
+ Count
<= N
&& "Invalid range");
253 first
[j
+ Count
] = first
[i
+ Count
];
254 second
[j
+ Count
] = second
[i
+ Count
];
258 /// erase - Erase elements [i;j).
259 /// @param i Beginning of the range to erase.
260 /// @param j End of the range. (Exclusive).
261 /// @param Size Number of elements in node.
262 void erase(unsigned i
, unsigned j
, unsigned Size
) {
263 moveLeft(j
, i
, Size
- j
);
266 /// erase - Erase element at i.
267 /// @param i Index of element to erase.
268 /// @param Size Number of elements in node.
269 void erase(unsigned i
, unsigned Size
) {
273 /// shift - Shift elements [i;size) 1 position to the right.
274 /// @param i Beginning of the range to move.
275 /// @param Size Number of elements in node.
276 void shift(unsigned i
, unsigned Size
) {
277 moveRight(i
, i
+ 1, Size
- i
);
280 /// transferToLeftSib - Transfer elements to a left sibling node.
281 /// @param Size Number of elements in this.
282 /// @param Sib Left sibling node.
283 /// @param SSize Number of elements in sib.
284 /// @param Count Number of elements to transfer.
285 void transferToLeftSib(unsigned Size
, NodeBase
&Sib
, unsigned SSize
,
287 Sib
.copy(*this, 0, SSize
, Count
);
288 erase(0, Count
, Size
);
291 /// transferToRightSib - Transfer elements to a right sibling node.
292 /// @param Size Number of elements in this.
293 /// @param Sib Right sibling node.
294 /// @param SSize Number of elements in sib.
295 /// @param Count Number of elements to transfer.
296 void transferToRightSib(unsigned Size
, NodeBase
&Sib
, unsigned SSize
,
298 Sib
.moveRight(0, Count
, SSize
);
299 Sib
.copy(*this, Size
-Count
, 0, Count
);
302 /// adjustFromLeftSib - Adjust the number if elements in this node by moving
303 /// elements to or from a left sibling node.
304 /// @param Size Number of elements in this.
305 /// @param Sib Right sibling node.
306 /// @param SSize Number of elements in sib.
307 /// @param Add The number of elements to add to this node, possibly < 0.
308 /// @return Number of elements added to this node, possibly negative.
309 int adjustFromLeftSib(unsigned Size
, NodeBase
&Sib
, unsigned SSize
, int Add
) {
311 // We want to grow, copy from sib.
312 unsigned Count
= std::min(std::min(unsigned(Add
), SSize
), N
- Size
);
313 Sib
.transferToRightSib(SSize
, *this, Size
, Count
);
316 // We want to shrink, copy to sib.
317 unsigned Count
= std::min(std::min(unsigned(-Add
), Size
), N
- SSize
);
318 transferToLeftSib(Size
, Sib
, SSize
, Count
);
324 /// IntervalMapImpl::adjustSiblingSizes - Move elements between sibling nodes.
325 /// @param Node Array of pointers to sibling nodes.
326 /// @param Nodes Number of nodes.
327 /// @param CurSize Array of current node sizes, will be overwritten.
328 /// @param NewSize Array of desired node sizes.
329 template <typename NodeT
>
330 void adjustSiblingSizes(NodeT
*Node
[], unsigned Nodes
,
331 unsigned CurSize
[], const unsigned NewSize
[]) {
332 // Move elements right.
333 for (int n
= Nodes
- 1; n
; --n
) {
334 if (CurSize
[n
] == NewSize
[n
])
336 for (int m
= n
- 1; m
!= -1; --m
) {
337 int d
= Node
[n
]->adjustFromLeftSib(CurSize
[n
], *Node
[m
], CurSize
[m
],
338 NewSize
[n
] - CurSize
[n
]);
341 // Keep going if the current node was exhausted.
342 if (CurSize
[n
] >= NewSize
[n
])
350 // Move elements left.
351 for (unsigned n
= 0; n
!= Nodes
- 1; ++n
) {
352 if (CurSize
[n
] == NewSize
[n
])
354 for (unsigned m
= n
+ 1; m
!= Nodes
; ++m
) {
355 int d
= Node
[m
]->adjustFromLeftSib(CurSize
[m
], *Node
[n
], CurSize
[n
],
356 CurSize
[n
] - NewSize
[n
]);
359 // Keep going if the current node was exhausted.
360 if (CurSize
[n
] >= NewSize
[n
])
366 for (unsigned n
= 0; n
!= Nodes
; n
++)
367 assert(CurSize
[n
] == NewSize
[n
] && "Insufficient element shuffle");
371 /// IntervalMapImpl::distribute - Compute a new distribution of node elements
372 /// after an overflow or underflow. Reserve space for a new element at Position,
373 /// and compute the node that will hold Position after redistributing node
376 /// It is required that
378 /// Elements == sum(CurSize), and
379 /// Elements + Grow <= Nodes * Capacity.
381 /// NewSize[] will be filled in such that:
383 /// sum(NewSize) == Elements, and
384 /// NewSize[i] <= Capacity.
386 /// The returned index is the node where Position will go, so:
388 /// sum(NewSize[0..idx-1]) <= Position
389 /// sum(NewSize[0..idx]) >= Position
391 /// The last equality, sum(NewSize[0..idx]) == Position, can only happen when
392 /// Grow is set and NewSize[idx] == Capacity-1. The index points to the node
393 /// before the one holding the Position'th element where there is room for an
396 /// @param Nodes The number of nodes.
397 /// @param Elements Total elements in all nodes.
398 /// @param Capacity The capacity of each node.
399 /// @param CurSize Array[Nodes] of current node sizes, or NULL.
400 /// @param NewSize Array[Nodes] to receive the new node sizes.
401 /// @param Position Insert position.
402 /// @param Grow Reserve space for a new element at Position.
403 /// @return (node, offset) for Position.
404 IdxPair
distribute(unsigned Nodes
, unsigned Elements
, unsigned Capacity
,
405 const unsigned *CurSize
, unsigned NewSize
[],
406 unsigned Position
, bool Grow
);
409 //===----------------------------------------------------------------------===//
410 //--- IntervalMapImpl::NodeSizer ---//
411 //===----------------------------------------------------------------------===//
413 // Compute node sizes from key and value types.
415 // The branching factors are chosen to make nodes fit in three cache lines.
416 // This may not be possible if keys or values are very large. Such large objects
417 // are handled correctly, but a std::map would probably give better performance.
419 //===----------------------------------------------------------------------===//
422 // Cache line size. Most architectures have 32 or 64 byte cache lines.
423 // We use 64 bytes here because it provides good branching factors.
425 CacheLineBytes
= 1 << Log2CacheLine
,
426 DesiredNodeBytes
= 3 * CacheLineBytes
429 template <typename KeyT
, typename ValT
>
432 // Compute the leaf node branching factor that makes a node fit in three
433 // cache lines. The branching factor must be at least 3, or some B+-tree
434 // balancing algorithms won't work.
435 // LeafSize can't be larger than CacheLineBytes. This is required by the
436 // PointerIntPair used by NodeRef.
437 DesiredLeafSize
= DesiredNodeBytes
/
438 static_cast<unsigned>(2*sizeof(KeyT
)+sizeof(ValT
)),
440 LeafSize
= DesiredLeafSize
> MinLeafSize
? DesiredLeafSize
: MinLeafSize
443 typedef NodeBase
<std::pair
<KeyT
, KeyT
>, ValT
, LeafSize
> LeafBase
;
446 // Now that we have the leaf branching factor, compute the actual allocation
447 // unit size by rounding up to a whole number of cache lines.
448 AllocBytes
= (sizeof(LeafBase
) + CacheLineBytes
-1) & ~(CacheLineBytes
-1),
450 // Determine the branching factor for branch nodes.
451 BranchSize
= AllocBytes
/
452 static_cast<unsigned>(sizeof(KeyT
) + sizeof(void*))
455 /// Allocator - The recycling allocator used for both branch and leaf nodes.
456 /// This typedef is very likely to be identical for all IntervalMaps with
457 /// reasonably sized entries, so the same allocator can be shared among
458 /// different kinds of maps.
459 typedef RecyclingAllocator
<BumpPtrAllocator
, char,
460 AllocBytes
, CacheLineBytes
> Allocator
;
465 //===----------------------------------------------------------------------===//
466 //--- IntervalMapImpl::NodeRef ---//
467 //===----------------------------------------------------------------------===//
469 // B+-tree nodes can be leaves or branches, so we need a polymorphic node
470 // pointer that can point to both kinds.
472 // All nodes are cache line aligned and the low 6 bits of a node pointer are
473 // always 0. These bits are used to store the number of elements in the
474 // referenced node. Besides saving space, placing node sizes in the parents
475 // allow tree balancing algorithms to run without faulting cache lines for nodes
476 // that may not need to be modified.
478 // A NodeRef doesn't know whether it references a leaf node or a branch node.
479 // It is the responsibility of the caller to use the correct types.
481 // Nodes are never supposed to be empty, and it is invalid to store a node size
482 // of 0 in a NodeRef. The valid range of sizes is 1-64.
484 //===----------------------------------------------------------------------===//
487 struct CacheAlignedPointerTraits
{
488 static inline void *getAsVoidPointer(void *P
) { return P
; }
489 static inline void *getFromVoidPointer(void *P
) { return P
; }
490 enum { NumLowBitsAvailable
= Log2CacheLine
};
492 PointerIntPair
<void*, Log2CacheLine
, unsigned, CacheAlignedPointerTraits
> pip
;
495 /// NodeRef - Create a null ref.
498 /// operator bool - Detect a null ref.
499 LLVM_EXPLICIT
operator bool() const { return pip
.getOpaqueValue(); }
501 /// NodeRef - Create a reference to the node p with n elements.
502 template <typename NodeT
>
503 NodeRef(NodeT
*p
, unsigned n
) : pip(p
, n
- 1) {
504 assert(n
<= NodeT::Capacity
&& "Size too big for node");
507 /// size - Return the number of elements in the referenced node.
508 unsigned size() const { return pip
.getInt() + 1; }
510 /// setSize - Update the node size.
511 void setSize(unsigned n
) { pip
.setInt(n
- 1); }
513 /// subtree - Access the i'th subtree reference in a branch node.
514 /// This depends on branch nodes storing the NodeRef array as their first
516 NodeRef
&subtree(unsigned i
) const {
517 return reinterpret_cast<NodeRef
*>(pip
.getPointer())[i
];
520 /// get - Dereference as a NodeT reference.
521 template <typename NodeT
>
523 return *reinterpret_cast<NodeT
*>(pip
.getPointer());
526 bool operator==(const NodeRef
&RHS
) const {
529 assert(pip
.getPointer() != RHS
.pip
.getPointer() && "Inconsistent NodeRefs");
533 bool operator!=(const NodeRef
&RHS
) const {
534 return !operator==(RHS
);
538 //===----------------------------------------------------------------------===//
539 //--- IntervalMapImpl::LeafNode ---//
540 //===----------------------------------------------------------------------===//
542 // Leaf nodes store up to N disjoint intervals with corresponding values.
544 // The intervals are kept sorted and fully coalesced so there are no adjacent
545 // intervals mapping to the same value.
547 // These constraints are always satisfied:
549 // - Traits::stopLess(start(i), stop(i)) - Non-empty, sane intervals.
551 // - Traits::stopLess(stop(i), start(i + 1) - Sorted.
553 // - value(i) != value(i + 1) || !Traits::adjacent(stop(i), start(i + 1))
554 // - Fully coalesced.
556 //===----------------------------------------------------------------------===//
558 template <typename KeyT
, typename ValT
, unsigned N
, typename Traits
>
559 class LeafNode
: public NodeBase
<std::pair
<KeyT
, KeyT
>, ValT
, N
> {
561 const KeyT
&start(unsigned i
) const { return this->first
[i
].first
; }
562 const KeyT
&stop(unsigned i
) const { return this->first
[i
].second
; }
563 const ValT
&value(unsigned i
) const { return this->second
[i
]; }
565 KeyT
&start(unsigned i
) { return this->first
[i
].first
; }
566 KeyT
&stop(unsigned i
) { return this->first
[i
].second
; }
567 ValT
&value(unsigned i
) { return this->second
[i
]; }
569 /// findFrom - Find the first interval after i that may contain x.
570 /// @param i Starting index for the search.
571 /// @param Size Number of elements in node.
572 /// @param x Key to search for.
573 /// @return First index with !stopLess(key[i].stop, x), or size.
574 /// This is the first interval that can possibly contain x.
575 unsigned findFrom(unsigned i
, unsigned Size
, KeyT x
) const {
576 assert(i
<= Size
&& Size
<= N
&& "Bad indices");
577 assert((i
== 0 || Traits::stopLess(stop(i
- 1), x
)) &&
578 "Index is past the needed point");
579 while (i
!= Size
&& Traits::stopLess(stop(i
), x
)) ++i
;
583 /// safeFind - Find an interval that is known to exist. This is the same as
584 /// findFrom except is it assumed that x is at least within range of the last
586 /// @param i Starting index for the search.
587 /// @param x Key to search for.
588 /// @return First index with !stopLess(key[i].stop, x), never size.
589 /// This is the first interval that can possibly contain x.
590 unsigned safeFind(unsigned i
, KeyT x
) const {
591 assert(i
< N
&& "Bad index");
592 assert((i
== 0 || Traits::stopLess(stop(i
- 1), x
)) &&
593 "Index is past the needed point");
594 while (Traits::stopLess(stop(i
), x
)) ++i
;
595 assert(i
< N
&& "Unsafe intervals");
599 /// safeLookup - Lookup mapped value for a safe key.
600 /// It is assumed that x is within range of the last entry.
601 /// @param x Key to search for.
602 /// @param NotFound Value to return if x is not in any interval.
603 /// @return The mapped value at x or NotFound.
604 ValT
safeLookup(KeyT x
, ValT NotFound
) const {
605 unsigned i
= safeFind(0, x
);
606 return Traits::startLess(x
, start(i
)) ? NotFound
: value(i
);
609 unsigned insertFrom(unsigned &Pos
, unsigned Size
, KeyT a
, KeyT b
, ValT y
);
612 /// insertFrom - Add mapping of [a;b] to y if possible, coalescing as much as
613 /// possible. This may cause the node to grow by 1, or it may cause the node
614 /// to shrink because of coalescing.
615 /// @param Pos Starting index = insertFrom(0, size, a)
616 /// @param Size Number of elements in node.
617 /// @param a Interval start.
618 /// @param b Interval stop.
619 /// @param y Value be mapped.
620 /// @return (insert position, new size), or (i, Capacity+1) on overflow.
621 template <typename KeyT
, typename ValT
, unsigned N
, typename Traits
>
622 unsigned LeafNode
<KeyT
, ValT
, N
, Traits
>::
623 insertFrom(unsigned &Pos
, unsigned Size
, KeyT a
, KeyT b
, ValT y
) {
625 assert(i
<= Size
&& Size
<= N
&& "Invalid index");
626 assert(!Traits::stopLess(b
, a
) && "Invalid interval");
628 // Verify the findFrom invariant.
629 assert((i
== 0 || Traits::stopLess(stop(i
- 1), a
)));
630 assert((i
== Size
|| !Traits::stopLess(stop(i
), a
)));
631 assert((i
== Size
|| Traits::stopLess(b
, start(i
))) && "Overlapping insert");
633 // Coalesce with previous interval.
634 if (i
&& value(i
- 1) == y
&& Traits::adjacent(stop(i
- 1), a
)) {
636 // Also coalesce with next interval?
637 if (i
!= Size
&& value(i
) == y
&& Traits::adjacent(b
, start(i
))) {
638 stop(i
- 1) = stop(i
);
639 this->erase(i
, Size
);
650 // Add new interval at end.
658 // Try to coalesce with following interval.
659 if (value(i
) == y
&& Traits::adjacent(b
, start(i
))) {
664 // We must insert before i. Detect overflow.
669 this->shift(i
, Size
);
677 //===----------------------------------------------------------------------===//
678 //--- IntervalMapImpl::BranchNode ---//
679 //===----------------------------------------------------------------------===//
681 // A branch node stores references to 1--N subtrees all of the same height.
683 // The key array in a branch node holds the rightmost stop key of each subtree.
684 // It is redundant to store the last stop key since it can be found in the
685 // parent node, but doing so makes tree balancing a lot simpler.
687 // It is unusual for a branch node to only have one subtree, but it can happen
688 // in the root node if it is smaller than the normal nodes.
690 // When all of the leaf nodes from all the subtrees are concatenated, they must
691 // satisfy the same constraints as a single leaf node. They must be sorted,
692 // sane, and fully coalesced.
694 //===----------------------------------------------------------------------===//
696 template <typename KeyT
, typename ValT
, unsigned N
, typename Traits
>
697 class BranchNode
: public NodeBase
<NodeRef
, KeyT
, N
> {
699 const KeyT
&stop(unsigned i
) const { return this->second
[i
]; }
700 const NodeRef
&subtree(unsigned i
) const { return this->first
[i
]; }
702 KeyT
&stop(unsigned i
) { return this->second
[i
]; }
703 NodeRef
&subtree(unsigned i
) { return this->first
[i
]; }
705 /// findFrom - Find the first subtree after i that may contain x.
706 /// @param i Starting index for the search.
707 /// @param Size Number of elements in node.
708 /// @param x Key to search for.
709 /// @return First index with !stopLess(key[i], x), or size.
710 /// This is the first subtree that can possibly contain x.
711 unsigned findFrom(unsigned i
, unsigned Size
, KeyT x
) const {
712 assert(i
<= Size
&& Size
<= N
&& "Bad indices");
713 assert((i
== 0 || Traits::stopLess(stop(i
- 1), x
)) &&
714 "Index to findFrom is past the needed point");
715 while (i
!= Size
&& Traits::stopLess(stop(i
), x
)) ++i
;
719 /// safeFind - Find a subtree that is known to exist. This is the same as
720 /// findFrom except is it assumed that x is in range.
721 /// @param i Starting index for the search.
722 /// @param x Key to search for.
723 /// @return First index with !stopLess(key[i], x), never size.
724 /// This is the first subtree that can possibly contain x.
725 unsigned safeFind(unsigned i
, KeyT x
) const {
726 assert(i
< N
&& "Bad index");
727 assert((i
== 0 || Traits::stopLess(stop(i
- 1), x
)) &&
728 "Index is past the needed point");
729 while (Traits::stopLess(stop(i
), x
)) ++i
;
730 assert(i
< N
&& "Unsafe intervals");
734 /// safeLookup - Get the subtree containing x, Assuming that x is in range.
735 /// @param x Key to search for.
736 /// @return Subtree containing x
737 NodeRef
safeLookup(KeyT x
) const {
738 return subtree(safeFind(0, x
));
741 /// insert - Insert a new (subtree, stop) pair.
742 /// @param i Insert position, following entries will be shifted.
743 /// @param Size Number of elements in node.
744 /// @param Node Subtree to insert.
745 /// @param Stop Last key in subtree.
746 void insert(unsigned i
, unsigned Size
, NodeRef Node
, KeyT Stop
) {
747 assert(Size
< N
&& "branch node overflow");
748 assert(i
<= Size
&& "Bad insert position");
749 this->shift(i
, Size
);
755 //===----------------------------------------------------------------------===//
756 //--- IntervalMapImpl::Path ---//
757 //===----------------------------------------------------------------------===//
759 // A Path is used by iterators to represent a position in a B+-tree, and the
760 // path to get there from the root.
762 // The Path class also contains the tree navigation code that doesn't have to
765 //===----------------------------------------------------------------------===//
768 /// Entry - Each step in the path is a node pointer and an offset into that
775 Entry(void *Node
, unsigned Size
, unsigned Offset
)
776 : node(Node
), size(Size
), offset(Offset
) {}
778 Entry(NodeRef Node
, unsigned Offset
)
779 : node(&Node
.subtree(0)), size(Node
.size()), offset(Offset
) {}
781 NodeRef
&subtree(unsigned i
) const {
782 return reinterpret_cast<NodeRef
*>(node
)[i
];
786 /// path - The path entries, path[0] is the root node, path.back() is a leaf.
787 SmallVector
<Entry
, 4> path
;
791 template <typename NodeT
> NodeT
&node(unsigned Level
) const {
792 return *reinterpret_cast<NodeT
*>(path
[Level
].node
);
794 unsigned size(unsigned Level
) const { return path
[Level
].size
; }
795 unsigned offset(unsigned Level
) const { return path
[Level
].offset
; }
796 unsigned &offset(unsigned Level
) { return path
[Level
].offset
; }
799 template <typename NodeT
> NodeT
&leaf() const {
800 return *reinterpret_cast<NodeT
*>(path
.back().node
);
802 unsigned leafSize() const { return path
.back().size
; }
803 unsigned leafOffset() const { return path
.back().offset
; }
804 unsigned &leafOffset() { return path
.back().offset
; }
806 /// valid - Return true if path is at a valid node, not at end().
808 return !path
.empty() && path
.front().offset
< path
.front().size
;
811 /// height - Return the height of the tree corresponding to this path.
812 /// This matches map->height in a full path.
813 unsigned height() const { return path
.size() - 1; }
815 /// subtree - Get the subtree referenced from Level. When the path is
816 /// consistent, node(Level + 1) == subtree(Level).
817 /// @param Level 0..height-1. The leaves have no subtrees.
818 NodeRef
&subtree(unsigned Level
) const {
819 return path
[Level
].subtree(path
[Level
].offset
);
822 /// reset - Reset cached information about node(Level) from subtree(Level -1).
823 /// @param Level 1..height. THe node to update after parent node changed.
824 void reset(unsigned Level
) {
825 path
[Level
] = Entry(subtree(Level
- 1), offset(Level
));
828 /// push - Add entry to path.
829 /// @param Node Node to add, should be subtree(path.size()-1).
830 /// @param Offset Offset into Node.
831 void push(NodeRef Node
, unsigned Offset
) {
832 path
.push_back(Entry(Node
, Offset
));
835 /// pop - Remove the last path entry.
840 /// setSize - Set the size of a node both in the path and in the tree.
841 /// @param Level 0..height. Note that setting the root size won't change
843 /// @param Size New node size.
844 void setSize(unsigned Level
, unsigned Size
) {
845 path
[Level
].size
= Size
;
847 subtree(Level
- 1).setSize(Size
);
850 /// setRoot - Clear the path and set a new root node.
851 /// @param Node New root node.
852 /// @param Size New root size.
853 /// @param Offset Offset into root node.
854 void setRoot(void *Node
, unsigned Size
, unsigned Offset
) {
856 path
.push_back(Entry(Node
, Size
, Offset
));
859 /// replaceRoot - Replace the current root node with two new entries after the
860 /// tree height has increased.
861 /// @param Root The new root node.
862 /// @param Size Number of entries in the new root.
863 /// @param Offsets Offsets into the root and first branch nodes.
864 void replaceRoot(void *Root
, unsigned Size
, IdxPair Offsets
);
866 /// getLeftSibling - Get the left sibling node at Level, or a null NodeRef.
867 /// @param Level Get the sibling to node(Level).
868 /// @return Left sibling, or NodeRef().
869 NodeRef
getLeftSibling(unsigned Level
) const;
871 /// moveLeft - Move path to the left sibling at Level. Leave nodes below Level
873 /// @param Level Move node(Level).
874 void moveLeft(unsigned Level
);
876 /// fillLeft - Grow path to Height by taking leftmost branches.
877 /// @param Height The target height.
878 void fillLeft(unsigned Height
) {
879 while (height() < Height
)
880 push(subtree(height()), 0);
883 /// getLeftSibling - Get the left sibling node at Level, or a null NodeRef.
884 /// @param Level Get the sinbling to node(Level).
885 /// @return Left sibling, or NodeRef().
886 NodeRef
getRightSibling(unsigned Level
) const;
888 /// moveRight - Move path to the left sibling at Level. Leave nodes below
890 /// @param Level Move node(Level).
891 void moveRight(unsigned Level
);
893 /// atBegin - Return true if path is at begin().
894 bool atBegin() const {
895 for (unsigned i
= 0, e
= path
.size(); i
!= e
; ++i
)
896 if (path
[i
].offset
!= 0)
901 /// atLastEntry - Return true if the path is at the last entry of the node at
903 /// @param Level Node to examine.
904 bool atLastEntry(unsigned Level
) const {
905 return path
[Level
].offset
== path
[Level
].size
- 1;
908 /// legalizeForInsert - Prepare the path for an insertion at Level. When the
909 /// path is at end(), node(Level) may not be a legal node. legalizeForInsert
910 /// ensures that node(Level) is real by moving back to the last node at Level,
911 /// and setting offset(Level) to size(Level) if required.
912 /// @param Level The level where an insertion is about to take place.
913 void legalizeForInsert(unsigned Level
) {
917 ++path
[Level
].offset
;
921 } // namespace IntervalMapImpl
924 //===----------------------------------------------------------------------===//
925 //--- IntervalMap ----//
926 //===----------------------------------------------------------------------===//
928 template <typename KeyT
, typename ValT
,
929 unsigned N
= IntervalMapImpl::NodeSizer
<KeyT
, ValT
>::LeafSize
,
930 typename Traits
= IntervalMapInfo
<KeyT
> >
932 typedef IntervalMapImpl::NodeSizer
<KeyT
, ValT
> Sizer
;
933 typedef IntervalMapImpl::LeafNode
<KeyT
, ValT
, Sizer::LeafSize
, Traits
> Leaf
;
934 typedef IntervalMapImpl::BranchNode
<KeyT
, ValT
, Sizer::BranchSize
, Traits
>
936 typedef IntervalMapImpl::LeafNode
<KeyT
, ValT
, N
, Traits
> RootLeaf
;
937 typedef IntervalMapImpl::IdxPair IdxPair
;
939 // The RootLeaf capacity is given as a template parameter. We must compute the
940 // corresponding RootBranch capacity.
942 DesiredRootBranchCap
= (sizeof(RootLeaf
) - sizeof(KeyT
)) /
943 (sizeof(KeyT
) + sizeof(IntervalMapImpl::NodeRef
)),
944 RootBranchCap
= DesiredRootBranchCap
? DesiredRootBranchCap
: 1
947 typedef IntervalMapImpl::BranchNode
<KeyT
, ValT
, RootBranchCap
, Traits
>
950 // When branched, we store a global start key as well as the branch node.
951 struct RootBranchData
{
957 RootDataSize
= sizeof(RootBranchData
) > sizeof(RootLeaf
) ?
958 sizeof(RootBranchData
) : sizeof(RootLeaf
)
962 typedef typename
Sizer::Allocator Allocator
;
963 typedef KeyT KeyType
;
964 typedef ValT ValueType
;
965 typedef Traits KeyTraits
;
968 // The root data is either a RootLeaf or a RootBranchData instance.
969 // We can't put them in a union since C++03 doesn't allow non-trivial
970 // constructors in unions.
971 // Instead, we use a char array with pointer alignment. The alignment is
972 // ensured by the allocator member in the class, but still verified in the
973 // constructor. We don't support keys or values that are more aligned than a
975 char data
[RootDataSize
];
978 // 0: Leaves in root.
979 // 1: Root points to leaf.
980 // 2: root->branch->leaf ...
983 // Number of entries in the root node.
986 // Allocator used for creating external nodes.
987 Allocator
&allocator
;
989 /// dataAs - Represent data as a node type without breaking aliasing rules.
990 template <typename T
>
1000 const RootLeaf
&rootLeaf() const {
1001 assert(!branched() && "Cannot acces leaf data in branched root");
1002 return dataAs
<RootLeaf
>();
1004 RootLeaf
&rootLeaf() {
1005 assert(!branched() && "Cannot acces leaf data in branched root");
1006 return dataAs
<RootLeaf
>();
1008 RootBranchData
&rootBranchData() const {
1009 assert(branched() && "Cannot access branch data in non-branched root");
1010 return dataAs
<RootBranchData
>();
1012 RootBranchData
&rootBranchData() {
1013 assert(branched() && "Cannot access branch data in non-branched root");
1014 return dataAs
<RootBranchData
>();
1016 const RootBranch
&rootBranch() const { return rootBranchData().node
; }
1017 RootBranch
&rootBranch() { return rootBranchData().node
; }
1018 KeyT
rootBranchStart() const { return rootBranchData().start
; }
1019 KeyT
&rootBranchStart() { return rootBranchData().start
; }
1021 template <typename NodeT
> NodeT
*newNode() {
1022 return new(allocator
.template Allocate
<NodeT
>()) NodeT();
1025 template <typename NodeT
> void deleteNode(NodeT
*P
) {
1027 allocator
.Deallocate(P
);
1030 IdxPair
branchRoot(unsigned Position
);
1031 IdxPair
splitRoot(unsigned Position
);
1033 void switchRootToBranch() {
1034 rootLeaf().~RootLeaf();
1036 new (&rootBranchData()) RootBranchData();
1039 void switchRootToLeaf() {
1040 rootBranchData().~RootBranchData();
1042 new(&rootLeaf()) RootLeaf();
1045 bool branched() const { return height
> 0; }
1047 ValT
treeSafeLookup(KeyT x
, ValT NotFound
) const;
1048 void visitNodes(void (IntervalMap::*f
)(IntervalMapImpl::NodeRef
,
1050 void deleteNode(IntervalMapImpl::NodeRef Node
, unsigned Level
);
1053 explicit IntervalMap(Allocator
&a
) : height(0), rootSize(0), allocator(a
) {
1054 assert((uintptr_t(data
) & (alignOf
<RootLeaf
>() - 1)) == 0 &&
1055 "Insufficient alignment");
1056 new(&rootLeaf()) RootLeaf();
1061 rootLeaf().~RootLeaf();
1064 /// empty - Return true when no intervals are mapped.
1065 bool empty() const {
1066 return rootSize
== 0;
1069 /// start - Return the smallest mapped key in a non-empty map.
1070 KeyT
start() const {
1071 assert(!empty() && "Empty IntervalMap has no start");
1072 return !branched() ? rootLeaf().start(0) : rootBranchStart();
1075 /// stop - Return the largest mapped key in a non-empty map.
1077 assert(!empty() && "Empty IntervalMap has no stop");
1078 return !branched() ? rootLeaf().stop(rootSize
- 1) :
1079 rootBranch().stop(rootSize
- 1);
1082 /// lookup - Return the mapped value at x or NotFound.
1083 ValT
lookup(KeyT x
, ValT NotFound
= ValT()) const {
1084 if (empty() || Traits::startLess(x
, start()) || Traits::stopLess(stop(), x
))
1086 return branched() ? treeSafeLookup(x
, NotFound
) :
1087 rootLeaf().safeLookup(x
, NotFound
);
1090 /// insert - Add a mapping of [a;b] to y, coalesce with adjacent intervals.
1091 /// It is assumed that no key in the interval is mapped to another value, but
1092 /// overlapping intervals already mapped to y will be coalesced.
1093 void insert(KeyT a
, KeyT b
, ValT y
) {
1094 if (branched() || rootSize
== RootLeaf::Capacity
)
1095 return find(a
).insert(a
, b
, y
);
1097 // Easy insert into root leaf.
1098 unsigned p
= rootLeaf().findFrom(0, rootSize
, a
);
1099 rootSize
= rootLeaf().insertFrom(p
, rootSize
, a
, b
, y
);
1102 /// clear - Remove all entries.
1105 class const_iterator
;
1107 friend class const_iterator
;
1108 friend class iterator
;
1110 const_iterator
begin() const {
1111 const_iterator
I(*this);
1122 const_iterator
end() const {
1123 const_iterator
I(*this);
1134 /// find - Return an iterator pointing to the first interval ending at or
1135 /// after x, or end().
1136 const_iterator
find(KeyT x
) const {
1137 const_iterator
I(*this);
1142 iterator
find(KeyT x
) {
1149 /// treeSafeLookup - Return the mapped value at x or NotFound, assuming a
1151 template <typename KeyT
, typename ValT
, unsigned N
, typename Traits
>
1152 ValT IntervalMap
<KeyT
, ValT
, N
, Traits
>::
1153 treeSafeLookup(KeyT x
, ValT NotFound
) const {
1154 assert(branched() && "treeLookup assumes a branched root");
1156 IntervalMapImpl::NodeRef NR
= rootBranch().safeLookup(x
);
1157 for (unsigned h
= height
-1; h
; --h
)
1158 NR
= NR
.get
<Branch
>().safeLookup(x
);
1159 return NR
.get
<Leaf
>().safeLookup(x
, NotFound
);
1163 // branchRoot - Switch from a leaf root to a branched root.
1164 // Return the new (root offset, node offset) corresponding to Position.
1165 template <typename KeyT
, typename ValT
, unsigned N
, typename Traits
>
1166 IntervalMapImpl::IdxPair IntervalMap
<KeyT
, ValT
, N
, Traits
>::
1167 branchRoot(unsigned Position
) {
1168 using namespace IntervalMapImpl
;
1169 // How many external leaf nodes to hold RootLeaf+1?
1170 const unsigned Nodes
= RootLeaf::Capacity
/ Leaf::Capacity
+ 1;
1172 // Compute element distribution among new nodes.
1173 unsigned size
[Nodes
];
1174 IdxPair
NewOffset(0, Position
);
1176 // Is is very common for the root node to be smaller than external nodes.
1180 NewOffset
= distribute(Nodes
, rootSize
, Leaf::Capacity
, nullptr, size
,
1183 // Allocate new nodes.
1185 NodeRef node
[Nodes
];
1186 for (unsigned n
= 0; n
!= Nodes
; ++n
) {
1187 Leaf
*L
= newNode
<Leaf
>();
1188 L
->copy(rootLeaf(), pos
, 0, size
[n
]);
1189 node
[n
] = NodeRef(L
, size
[n
]);
1193 // Destroy the old leaf node, construct branch node instead.
1194 switchRootToBranch();
1195 for (unsigned n
= 0; n
!= Nodes
; ++n
) {
1196 rootBranch().stop(n
) = node
[n
].template get
<Leaf
>().stop(size
[n
]-1);
1197 rootBranch().subtree(n
) = node
[n
];
1199 rootBranchStart() = node
[0].template get
<Leaf
>().start(0);
1204 // splitRoot - Split the current BranchRoot into multiple Branch nodes.
1205 // Return the new (root offset, node offset) corresponding to Position.
1206 template <typename KeyT
, typename ValT
, unsigned N
, typename Traits
>
1207 IntervalMapImpl::IdxPair IntervalMap
<KeyT
, ValT
, N
, Traits
>::
1208 splitRoot(unsigned Position
) {
1209 using namespace IntervalMapImpl
;
1210 // How many external leaf nodes to hold RootBranch+1?
1211 const unsigned Nodes
= RootBranch::Capacity
/ Branch::Capacity
+ 1;
1213 // Compute element distribution among new nodes.
1214 unsigned Size
[Nodes
];
1215 IdxPair
NewOffset(0, Position
);
1217 // Is is very common for the root node to be smaller than external nodes.
1221 NewOffset
= distribute(Nodes
, rootSize
, Leaf::Capacity
, nullptr, Size
,
1224 // Allocate new nodes.
1226 NodeRef Node
[Nodes
];
1227 for (unsigned n
= 0; n
!= Nodes
; ++n
) {
1228 Branch
*B
= newNode
<Branch
>();
1229 B
->copy(rootBranch(), Pos
, 0, Size
[n
]);
1230 Node
[n
] = NodeRef(B
, Size
[n
]);
1234 for (unsigned n
= 0; n
!= Nodes
; ++n
) {
1235 rootBranch().stop(n
) = Node
[n
].template get
<Branch
>().stop(Size
[n
]-1);
1236 rootBranch().subtree(n
) = Node
[n
];
1243 /// visitNodes - Visit each external node.
1244 template <typename KeyT
, typename ValT
, unsigned N
, typename Traits
>
1245 void IntervalMap
<KeyT
, ValT
, N
, Traits
>::
1246 visitNodes(void (IntervalMap::*f
)(IntervalMapImpl::NodeRef
, unsigned Height
)) {
1249 SmallVector
<IntervalMapImpl::NodeRef
, 4> Refs
, NextRefs
;
1251 // Collect level 0 nodes from the root.
1252 for (unsigned i
= 0; i
!= rootSize
; ++i
)
1253 Refs
.push_back(rootBranch().subtree(i
));
1255 // Visit all branch nodes.
1256 for (unsigned h
= height
- 1; h
; --h
) {
1257 for (unsigned i
= 0, e
= Refs
.size(); i
!= e
; ++i
) {
1258 for (unsigned j
= 0, s
= Refs
[i
].size(); j
!= s
; ++j
)
1259 NextRefs
.push_back(Refs
[i
].subtree(j
));
1260 (this->*f
)(Refs
[i
], h
);
1263 Refs
.swap(NextRefs
);
1266 // Visit all leaf nodes.
1267 for (unsigned i
= 0, e
= Refs
.size(); i
!= e
; ++i
)
1268 (this->*f
)(Refs
[i
], 0);
1271 template <typename KeyT
, typename ValT
, unsigned N
, typename Traits
>
1272 void IntervalMap
<KeyT
, ValT
, N
, Traits
>::
1273 deleteNode(IntervalMapImpl::NodeRef Node
, unsigned Level
) {
1275 deleteNode(&Node
.get
<Branch
>());
1277 deleteNode(&Node
.get
<Leaf
>());
1280 template <typename KeyT
, typename ValT
, unsigned N
, typename Traits
>
1281 void IntervalMap
<KeyT
, ValT
, N
, Traits
>::
1284 visitNodes(&IntervalMap::deleteNode
);
1290 //===----------------------------------------------------------------------===//
1291 //--- IntervalMap::const_iterator ----//
1292 //===----------------------------------------------------------------------===//
1294 template <typename KeyT
, typename ValT
, unsigned N
, typename Traits
>
1295 class IntervalMap
<KeyT
, ValT
, N
, Traits
>::const_iterator
:
1296 public std::iterator
<std::bidirectional_iterator_tag
, ValT
> {
1298 friend class IntervalMap
;
1300 // The map referred to.
1303 // We store a full path from the root to the current position.
1304 // The path may be partially filled, but never between iterator calls.
1305 IntervalMapImpl::Path path
;
1307 explicit const_iterator(const IntervalMap
&map
) :
1308 map(const_cast<IntervalMap
*>(&map
)) {}
1310 bool branched() const {
1311 assert(map
&& "Invalid iterator");
1312 return map
->branched();
1315 void setRoot(unsigned Offset
) {
1317 path
.setRoot(&map
->rootBranch(), map
->rootSize
, Offset
);
1319 path
.setRoot(&map
->rootLeaf(), map
->rootSize
, Offset
);
1322 void pathFillFind(KeyT x
);
1323 void treeFind(KeyT x
);
1324 void treeAdvanceTo(KeyT x
);
1326 /// unsafeStart - Writable access to start() for iterator.
1327 KeyT
&unsafeStart() const {
1328 assert(valid() && "Cannot access invalid iterator");
1329 return branched() ? path
.leaf
<Leaf
>().start(path
.leafOffset()) :
1330 path
.leaf
<RootLeaf
>().start(path
.leafOffset());
1333 /// unsafeStop - Writable access to stop() for iterator.
1334 KeyT
&unsafeStop() const {
1335 assert(valid() && "Cannot access invalid iterator");
1336 return branched() ? path
.leaf
<Leaf
>().stop(path
.leafOffset()) :
1337 path
.leaf
<RootLeaf
>().stop(path
.leafOffset());
1340 /// unsafeValue - Writable access to value() for iterator.
1341 ValT
&unsafeValue() const {
1342 assert(valid() && "Cannot access invalid iterator");
1343 return branched() ? path
.leaf
<Leaf
>().value(path
.leafOffset()) :
1344 path
.leaf
<RootLeaf
>().value(path
.leafOffset());
1348 /// const_iterator - Create an iterator that isn't pointing anywhere.
1349 const_iterator() : map(nullptr) {}
1351 /// setMap - Change the map iterated over. This call must be followed by a
1352 /// call to goToBegin(), goToEnd(), or find()
1353 void setMap(const IntervalMap
&m
) { map
= const_cast<IntervalMap
*>(&m
); }
1355 /// valid - Return true if the current position is valid, false for end().
1356 bool valid() const { return path
.valid(); }
1358 /// atBegin - Return true if the current position is the first map entry.
1359 bool atBegin() const { return path
.atBegin(); }
1361 /// start - Return the beginning of the current interval.
1362 const KeyT
&start() const { return unsafeStart(); }
1364 /// stop - Return the end of the current interval.
1365 const KeyT
&stop() const { return unsafeStop(); }
1367 /// value - Return the mapped value at the current interval.
1368 const ValT
&value() const { return unsafeValue(); }
1370 const ValT
&operator*() const { return value(); }
1372 bool operator==(const const_iterator
&RHS
) const {
1373 assert(map
== RHS
.map
&& "Cannot compare iterators from different maps");
1375 return !RHS
.valid();
1376 if (path
.leafOffset() != RHS
.path
.leafOffset())
1378 return &path
.template leaf
<Leaf
>() == &RHS
.path
.template leaf
<Leaf
>();
1381 bool operator!=(const const_iterator
&RHS
) const {
1382 return !operator==(RHS
);
1385 /// goToBegin - Move to the first interval in map.
1389 path
.fillLeft(map
->height
);
1392 /// goToEnd - Move beyond the last interval in map.
1394 setRoot(map
->rootSize
);
1397 /// preincrement - move to the next interval.
1398 const_iterator
&operator++() {
1399 assert(valid() && "Cannot increment end()");
1400 if (++path
.leafOffset() == path
.leafSize() && branched())
1401 path
.moveRight(map
->height
);
1405 /// postincrement - Dont do that!
1406 const_iterator
operator++(int) {
1407 const_iterator tmp
= *this;
1412 /// predecrement - move to the previous interval.
1413 const_iterator
&operator--() {
1414 if (path
.leafOffset() && (valid() || !branched()))
1415 --path
.leafOffset();
1417 path
.moveLeft(map
->height
);
1421 /// postdecrement - Dont do that!
1422 const_iterator
operator--(int) {
1423 const_iterator tmp
= *this;
1428 /// find - Move to the first interval with stop >= x, or end().
1429 /// This is a full search from the root, the current position is ignored.
1434 setRoot(map
->rootLeaf().findFrom(0, map
->rootSize
, x
));
1437 /// advanceTo - Move to the first interval with stop >= x, or end().
1438 /// The search is started from the current position, and no earlier positions
1439 /// can be found. This is much faster than find() for small moves.
1440 void advanceTo(KeyT x
) {
1447 map
->rootLeaf().findFrom(path
.leafOffset(), map
->rootSize
, x
);
1452 /// pathFillFind - Complete path by searching for x.
1453 /// @param x Key to search for.
1454 template <typename KeyT
, typename ValT
, unsigned N
, typename Traits
>
1455 void IntervalMap
<KeyT
, ValT
, N
, Traits
>::
1456 const_iterator::pathFillFind(KeyT x
) {
1457 IntervalMapImpl::NodeRef NR
= path
.subtree(path
.height());
1458 for (unsigned i
= map
->height
- path
.height() - 1; i
; --i
) {
1459 unsigned p
= NR
.get
<Branch
>().safeFind(0, x
);
1463 path
.push(NR
, NR
.get
<Leaf
>().safeFind(0, x
));
1466 /// treeFind - Find in a branched tree.
1467 /// @param x Key to search for.
1468 template <typename KeyT
, typename ValT
, unsigned N
, typename Traits
>
1469 void IntervalMap
<KeyT
, ValT
, N
, Traits
>::
1470 const_iterator::treeFind(KeyT x
) {
1471 setRoot(map
->rootBranch().findFrom(0, map
->rootSize
, x
));
1476 /// treeAdvanceTo - Find position after the current one.
1477 /// @param x Key to search for.
1478 template <typename KeyT
, typename ValT
, unsigned N
, typename Traits
>
1479 void IntervalMap
<KeyT
, ValT
, N
, Traits
>::
1480 const_iterator::treeAdvanceTo(KeyT x
) {
1481 // Can we stay on the same leaf node?
1482 if (!Traits::stopLess(path
.leaf
<Leaf
>().stop(path
.leafSize() - 1), x
)) {
1483 path
.leafOffset() = path
.leaf
<Leaf
>().safeFind(path
.leafOffset(), x
);
1487 // Drop the current leaf.
1490 // Search towards the root for a usable subtree.
1491 if (path
.height()) {
1492 for (unsigned l
= path
.height() - 1; l
; --l
) {
1493 if (!Traits::stopLess(path
.node
<Branch
>(l
).stop(path
.offset(l
)), x
)) {
1494 // The branch node at l+1 is usable
1495 path
.offset(l
+ 1) =
1496 path
.node
<Branch
>(l
+ 1).safeFind(path
.offset(l
+ 1), x
);
1497 return pathFillFind(x
);
1501 // Is the level-1 Branch usable?
1502 if (!Traits::stopLess(map
->rootBranch().stop(path
.offset(0)), x
)) {
1503 path
.offset(1) = path
.node
<Branch
>(1).safeFind(path
.offset(1), x
);
1504 return pathFillFind(x
);
1508 // We reached the root.
1509 setRoot(map
->rootBranch().findFrom(path
.offset(0), map
->rootSize
, x
));
1514 //===----------------------------------------------------------------------===//
1515 //--- IntervalMap::iterator ----//
1516 //===----------------------------------------------------------------------===//
1518 template <typename KeyT
, typename ValT
, unsigned N
, typename Traits
>
1519 class IntervalMap
<KeyT
, ValT
, N
, Traits
>::iterator
: public const_iterator
{
1520 friend class IntervalMap
;
1521 typedef IntervalMapImpl::IdxPair IdxPair
;
1523 explicit iterator(IntervalMap
&map
) : const_iterator(map
) {}
1525 void setNodeStop(unsigned Level
, KeyT Stop
);
1526 bool insertNode(unsigned Level
, IntervalMapImpl::NodeRef Node
, KeyT Stop
);
1527 template <typename NodeT
> bool overflow(unsigned Level
);
1528 void treeInsert(KeyT a
, KeyT b
, ValT y
);
1529 void eraseNode(unsigned Level
);
1530 void treeErase(bool UpdateRoot
= true);
1531 bool canCoalesceLeft(KeyT Start
, ValT x
);
1532 bool canCoalesceRight(KeyT Stop
, ValT x
);
1535 /// iterator - Create null iterator.
1538 /// setStart - Move the start of the current interval.
1539 /// This may cause coalescing with the previous interval.
1540 /// @param a New start key, must not overlap the previous interval.
1541 void setStart(KeyT a
);
1543 /// setStop - Move the end of the current interval.
1544 /// This may cause coalescing with the following interval.
1545 /// @param b New stop key, must not overlap the following interval.
1546 void setStop(KeyT b
);
1548 /// setValue - Change the mapped value of the current interval.
1549 /// This may cause coalescing with the previous and following intervals.
1550 /// @param x New value.
1551 void setValue(ValT x
);
1553 /// setStartUnchecked - Move the start of the current interval without
1554 /// checking for coalescing or overlaps.
1555 /// This should only be used when it is known that coalescing is not required.
1556 /// @param a New start key.
1557 void setStartUnchecked(KeyT a
) { this->unsafeStart() = a
; }
1559 /// setStopUnchecked - Move the end of the current interval without checking
1560 /// for coalescing or overlaps.
1561 /// This should only be used when it is known that coalescing is not required.
1562 /// @param b New stop key.
1563 void setStopUnchecked(KeyT b
) {
1564 this->unsafeStop() = b
;
1565 // Update keys in branch nodes as well.
1566 if (this->path
.atLastEntry(this->path
.height()))
1567 setNodeStop(this->path
.height(), b
);
1570 /// setValueUnchecked - Change the mapped value of the current interval
1571 /// without checking for coalescing.
1572 /// @param x New value.
1573 void setValueUnchecked(ValT x
) { this->unsafeValue() = x
; }
1575 /// insert - Insert mapping [a;b] -> y before the current position.
1576 void insert(KeyT a
, KeyT b
, ValT y
);
1578 /// erase - Erase the current interval.
1581 iterator
&operator++() {
1582 const_iterator::operator++();
1586 iterator
operator++(int) {
1587 iterator tmp
= *this;
1592 iterator
&operator--() {
1593 const_iterator::operator--();
1597 iterator
operator--(int) {
1598 iterator tmp
= *this;
1605 /// canCoalesceLeft - Can the current interval coalesce to the left after
1606 /// changing start or value?
1607 /// @param Start New start of current interval.
1608 /// @param Value New value for current interval.
1609 /// @return True when updating the current interval would enable coalescing.
1610 template <typename KeyT
, typename ValT
, unsigned N
, typename Traits
>
1611 bool IntervalMap
<KeyT
, ValT
, N
, Traits
>::
1612 iterator::canCoalesceLeft(KeyT Start
, ValT Value
) {
1613 using namespace IntervalMapImpl
;
1614 Path
&P
= this->path
;
1615 if (!this->branched()) {
1616 unsigned i
= P
.leafOffset();
1617 RootLeaf
&Node
= P
.leaf
<RootLeaf
>();
1618 return i
&& Node
.value(i
-1) == Value
&&
1619 Traits::adjacent(Node
.stop(i
-1), Start
);
1622 if (unsigned i
= P
.leafOffset()) {
1623 Leaf
&Node
= P
.leaf
<Leaf
>();
1624 return Node
.value(i
-1) == Value
&& Traits::adjacent(Node
.stop(i
-1), Start
);
1625 } else if (NodeRef NR
= P
.getLeftSibling(P
.height())) {
1626 unsigned i
= NR
.size() - 1;
1627 Leaf
&Node
= NR
.get
<Leaf
>();
1628 return Node
.value(i
) == Value
&& Traits::adjacent(Node
.stop(i
), Start
);
1633 /// canCoalesceRight - Can the current interval coalesce to the right after
1634 /// changing stop or value?
1635 /// @param Stop New stop of current interval.
1636 /// @param Value New value for current interval.
1637 /// @return True when updating the current interval would enable coalescing.
1638 template <typename KeyT
, typename ValT
, unsigned N
, typename Traits
>
1639 bool IntervalMap
<KeyT
, ValT
, N
, Traits
>::
1640 iterator::canCoalesceRight(KeyT Stop
, ValT Value
) {
1641 using namespace IntervalMapImpl
;
1642 Path
&P
= this->path
;
1643 unsigned i
= P
.leafOffset() + 1;
1644 if (!this->branched()) {
1645 if (i
>= P
.leafSize())
1647 RootLeaf
&Node
= P
.leaf
<RootLeaf
>();
1648 return Node
.value(i
) == Value
&& Traits::adjacent(Stop
, Node
.start(i
));
1651 if (i
< P
.leafSize()) {
1652 Leaf
&Node
= P
.leaf
<Leaf
>();
1653 return Node
.value(i
) == Value
&& Traits::adjacent(Stop
, Node
.start(i
));
1654 } else if (NodeRef NR
= P
.getRightSibling(P
.height())) {
1655 Leaf
&Node
= NR
.get
<Leaf
>();
1656 return Node
.value(0) == Value
&& Traits::adjacent(Stop
, Node
.start(0));
1661 /// setNodeStop - Update the stop key of the current node at level and above.
1662 template <typename KeyT
, typename ValT
, unsigned N
, typename Traits
>
1663 void IntervalMap
<KeyT
, ValT
, N
, Traits
>::
1664 iterator::setNodeStop(unsigned Level
, KeyT Stop
) {
1665 // There are no references to the root node, so nothing to update.
1668 IntervalMapImpl::Path
&P
= this->path
;
1669 // Update nodes pointing to the current node.
1671 P
.node
<Branch
>(Level
).stop(P
.offset(Level
)) = Stop
;
1672 if (!P
.atLastEntry(Level
))
1675 // Update root separately since it has a different layout.
1676 P
.node
<RootBranch
>(Level
).stop(P
.offset(Level
)) = Stop
;
1679 template <typename KeyT
, typename ValT
, unsigned N
, typename Traits
>
1680 void IntervalMap
<KeyT
, ValT
, N
, Traits
>::
1681 iterator::setStart(KeyT a
) {
1682 assert(Traits::stopLess(a
, this->stop()) && "Cannot move start beyond stop");
1683 KeyT
&CurStart
= this->unsafeStart();
1684 if (!Traits::startLess(a
, CurStart
) || !canCoalesceLeft(a
, this->value())) {
1688 // Coalesce with the interval to the left.
1692 setStartUnchecked(a
);
1695 template <typename KeyT
, typename ValT
, unsigned N
, typename Traits
>
1696 void IntervalMap
<KeyT
, ValT
, N
, Traits
>::
1697 iterator::setStop(KeyT b
) {
1698 assert(Traits::stopLess(this->start(), b
) && "Cannot move stop beyond start");
1699 if (Traits::startLess(b
, this->stop()) ||
1700 !canCoalesceRight(b
, this->value())) {
1701 setStopUnchecked(b
);
1704 // Coalesce with interval to the right.
1705 KeyT a
= this->start();
1707 setStartUnchecked(a
);
1710 template <typename KeyT
, typename ValT
, unsigned N
, typename Traits
>
1711 void IntervalMap
<KeyT
, ValT
, N
, Traits
>::
1712 iterator::setValue(ValT x
) {
1713 setValueUnchecked(x
);
1714 if (canCoalesceRight(this->stop(), x
)) {
1715 KeyT a
= this->start();
1717 setStartUnchecked(a
);
1719 if (canCoalesceLeft(this->start(), x
)) {
1721 KeyT a
= this->start();
1723 setStartUnchecked(a
);
1727 /// insertNode - insert a node before the current path at level.
1728 /// Leave the current path pointing at the new node.
1729 /// @param Level path index of the node to be inserted.
1730 /// @param Node The node to be inserted.
1731 /// @param Stop The last index in the new node.
1732 /// @return True if the tree height was increased.
1733 template <typename KeyT
, typename ValT
, unsigned N
, typename Traits
>
1734 bool IntervalMap
<KeyT
, ValT
, N
, Traits
>::
1735 iterator::insertNode(unsigned Level
, IntervalMapImpl::NodeRef Node
, KeyT Stop
) {
1736 assert(Level
&& "Cannot insert next to the root");
1737 bool SplitRoot
= false;
1738 IntervalMap
&IM
= *this->map
;
1739 IntervalMapImpl::Path
&P
= this->path
;
1742 // Insert into the root branch node.
1743 if (IM
.rootSize
< RootBranch::Capacity
) {
1744 IM
.rootBranch().insert(P
.offset(0), IM
.rootSize
, Node
, Stop
);
1745 P
.setSize(0, ++IM
.rootSize
);
1750 // We need to split the root while keeping our position.
1752 IdxPair Offset
= IM
.splitRoot(P
.offset(0));
1753 P
.replaceRoot(&IM
.rootBranch(), IM
.rootSize
, Offset
);
1755 // Fall through to insert at the new higher level.
1759 // When inserting before end(), make sure we have a valid path.
1760 P
.legalizeForInsert(--Level
);
1762 // Insert into the branch node at Level-1.
1763 if (P
.size(Level
) == Branch::Capacity
) {
1764 // Branch node is full, handle handle the overflow.
1765 assert(!SplitRoot
&& "Cannot overflow after splitting the root");
1766 SplitRoot
= overflow
<Branch
>(Level
);
1769 P
.node
<Branch
>(Level
).insert(P
.offset(Level
), P
.size(Level
), Node
, Stop
);
1770 P
.setSize(Level
, P
.size(Level
) + 1);
1771 if (P
.atLastEntry(Level
))
1772 setNodeStop(Level
, Stop
);
1778 template <typename KeyT
, typename ValT
, unsigned N
, typename Traits
>
1779 void IntervalMap
<KeyT
, ValT
, N
, Traits
>::
1780 iterator::insert(KeyT a
, KeyT b
, ValT y
) {
1781 if (this->branched())
1782 return treeInsert(a
, b
, y
);
1783 IntervalMap
&IM
= *this->map
;
1784 IntervalMapImpl::Path
&P
= this->path
;
1786 // Try simple root leaf insert.
1787 unsigned Size
= IM
.rootLeaf().insertFrom(P
.leafOffset(), IM
.rootSize
, a
, b
, y
);
1789 // Was the root node insert successful?
1790 if (Size
<= RootLeaf::Capacity
) {
1791 P
.setSize(0, IM
.rootSize
= Size
);
1795 // Root leaf node is full, we must branch.
1796 IdxPair Offset
= IM
.branchRoot(P
.leafOffset());
1797 P
.replaceRoot(&IM
.rootBranch(), IM
.rootSize
, Offset
);
1799 // Now it fits in the new leaf.
1800 treeInsert(a
, b
, y
);
1804 template <typename KeyT
, typename ValT
, unsigned N
, typename Traits
>
1805 void IntervalMap
<KeyT
, ValT
, N
, Traits
>::
1806 iterator::treeInsert(KeyT a
, KeyT b
, ValT y
) {
1807 using namespace IntervalMapImpl
;
1808 Path
&P
= this->path
;
1811 P
.legalizeForInsert(this->map
->height
);
1813 // Check if this insertion will extend the node to the left.
1814 if (P
.leafOffset() == 0 && Traits::startLess(a
, P
.leaf
<Leaf
>().start(0))) {
1815 // Node is growing to the left, will it affect a left sibling node?
1816 if (NodeRef Sib
= P
.getLeftSibling(P
.height())) {
1817 Leaf
&SibLeaf
= Sib
.get
<Leaf
>();
1818 unsigned SibOfs
= Sib
.size() - 1;
1819 if (SibLeaf
.value(SibOfs
) == y
&&
1820 Traits::adjacent(SibLeaf
.stop(SibOfs
), a
)) {
1821 // This insertion will coalesce with the last entry in SibLeaf. We can
1822 // handle it in two ways:
1823 // 1. Extend SibLeaf.stop to b and be done, or
1824 // 2. Extend a to SibLeaf, erase the SibLeaf entry and continue.
1825 // We prefer 1., but need 2 when coalescing to the right as well.
1826 Leaf
&CurLeaf
= P
.leaf
<Leaf
>();
1827 P
.moveLeft(P
.height());
1828 if (Traits::stopLess(b
, CurLeaf
.start(0)) &&
1829 (y
!= CurLeaf
.value(0) || !Traits::adjacent(b
, CurLeaf
.start(0)))) {
1830 // Easy, just extend SibLeaf and we're done.
1831 setNodeStop(P
.height(), SibLeaf
.stop(SibOfs
) = b
);
1834 // We have both left and right coalescing. Erase the old SibLeaf entry
1835 // and continue inserting the larger interval.
1836 a
= SibLeaf
.start(SibOfs
);
1837 treeErase(/* UpdateRoot= */false);
1841 // No left sibling means we are at begin(). Update cached bound.
1842 this->map
->rootBranchStart() = a
;
1846 // When we are inserting at the end of a leaf node, we must update stops.
1847 unsigned Size
= P
.leafSize();
1848 bool Grow
= P
.leafOffset() == Size
;
1849 Size
= P
.leaf
<Leaf
>().insertFrom(P
.leafOffset(), Size
, a
, b
, y
);
1851 // Leaf insertion unsuccessful? Overflow and try again.
1852 if (Size
> Leaf::Capacity
) {
1853 overflow
<Leaf
>(P
.height());
1854 Grow
= P
.leafOffset() == P
.leafSize();
1855 Size
= P
.leaf
<Leaf
>().insertFrom(P
.leafOffset(), P
.leafSize(), a
, b
, y
);
1856 assert(Size
<= Leaf::Capacity
&& "overflow() didn't make room");
1859 // Inserted, update offset and leaf size.
1860 P
.setSize(P
.height(), Size
);
1862 // Insert was the last node entry, update stops.
1864 setNodeStop(P
.height(), b
);
1867 /// erase - erase the current interval and move to the next position.
1868 template <typename KeyT
, typename ValT
, unsigned N
, typename Traits
>
1869 void IntervalMap
<KeyT
, ValT
, N
, Traits
>::
1871 IntervalMap
&IM
= *this->map
;
1872 IntervalMapImpl::Path
&P
= this->path
;
1873 assert(P
.valid() && "Cannot erase end()");
1874 if (this->branched())
1876 IM
.rootLeaf().erase(P
.leafOffset(), IM
.rootSize
);
1877 P
.setSize(0, --IM
.rootSize
);
1880 /// treeErase - erase() for a branched tree.
1881 template <typename KeyT
, typename ValT
, unsigned N
, typename Traits
>
1882 void IntervalMap
<KeyT
, ValT
, N
, Traits
>::
1883 iterator::treeErase(bool UpdateRoot
) {
1884 IntervalMap
&IM
= *this->map
;
1885 IntervalMapImpl::Path
&P
= this->path
;
1886 Leaf
&Node
= P
.leaf
<Leaf
>();
1888 // Nodes are not allowed to become empty.
1889 if (P
.leafSize() == 1) {
1890 IM
.deleteNode(&Node
);
1891 eraseNode(IM
.height
);
1892 // Update rootBranchStart if we erased begin().
1893 if (UpdateRoot
&& IM
.branched() && P
.valid() && P
.atBegin())
1894 IM
.rootBranchStart() = P
.leaf
<Leaf
>().start(0);
1898 // Erase current entry.
1899 Node
.erase(P
.leafOffset(), P
.leafSize());
1900 unsigned NewSize
= P
.leafSize() - 1;
1901 P
.setSize(IM
.height
, NewSize
);
1902 // When we erase the last entry, update stop and move to a legal position.
1903 if (P
.leafOffset() == NewSize
) {
1904 setNodeStop(IM
.height
, Node
.stop(NewSize
- 1));
1905 P
.moveRight(IM
.height
);
1906 } else if (UpdateRoot
&& P
.atBegin())
1907 IM
.rootBranchStart() = P
.leaf
<Leaf
>().start(0);
1910 /// eraseNode - Erase the current node at Level from its parent and move path to
1911 /// the first entry of the next sibling node.
1912 /// The node must be deallocated by the caller.
1913 /// @param Level 1..height, the root node cannot be erased.
1914 template <typename KeyT
, typename ValT
, unsigned N
, typename Traits
>
1915 void IntervalMap
<KeyT
, ValT
, N
, Traits
>::
1916 iterator::eraseNode(unsigned Level
) {
1917 assert(Level
&& "Cannot erase root node");
1918 IntervalMap
&IM
= *this->map
;
1919 IntervalMapImpl::Path
&P
= this->path
;
1922 IM
.rootBranch().erase(P
.offset(0), IM
.rootSize
);
1923 P
.setSize(0, --IM
.rootSize
);
1924 // If this cleared the root, switch to height=0.
1926 IM
.switchRootToLeaf();
1931 // Remove node ref from branch node at Level.
1932 Branch
&Parent
= P
.node
<Branch
>(Level
);
1933 if (P
.size(Level
) == 1) {
1934 // Branch node became empty, remove it recursively.
1935 IM
.deleteNode(&Parent
);
1938 // Branch node won't become empty.
1939 Parent
.erase(P
.offset(Level
), P
.size(Level
));
1940 unsigned NewSize
= P
.size(Level
) - 1;
1941 P
.setSize(Level
, NewSize
);
1942 // If we removed the last branch, update stop and move to a legal pos.
1943 if (P
.offset(Level
) == NewSize
) {
1944 setNodeStop(Level
, Parent
.stop(NewSize
- 1));
1949 // Update path cache for the new right sibling position.
1952 P
.offset(Level
+ 1) = 0;
1956 /// overflow - Distribute entries of the current node evenly among
1957 /// its siblings and ensure that the current node is not full.
1958 /// This may require allocating a new node.
1959 /// @tparam NodeT The type of node at Level (Leaf or Branch).
1960 /// @param Level path index of the overflowing node.
1961 /// @return True when the tree height was changed.
1962 template <typename KeyT
, typename ValT
, unsigned N
, typename Traits
>
1963 template <typename NodeT
>
1964 bool IntervalMap
<KeyT
, ValT
, N
, Traits
>::
1965 iterator::overflow(unsigned Level
) {
1966 using namespace IntervalMapImpl
;
1967 Path
&P
= this->path
;
1968 unsigned CurSize
[4];
1971 unsigned Elements
= 0;
1972 unsigned Offset
= P
.offset(Level
);
1974 // Do we have a left sibling?
1975 NodeRef LeftSib
= P
.getLeftSibling(Level
);
1977 Offset
+= Elements
= CurSize
[Nodes
] = LeftSib
.size();
1978 Node
[Nodes
++] = &LeftSib
.get
<NodeT
>();
1982 Elements
+= CurSize
[Nodes
] = P
.size(Level
);
1983 Node
[Nodes
++] = &P
.node
<NodeT
>(Level
);
1985 // Do we have a right sibling?
1986 NodeRef RightSib
= P
.getRightSibling(Level
);
1988 Elements
+= CurSize
[Nodes
] = RightSib
.size();
1989 Node
[Nodes
++] = &RightSib
.get
<NodeT
>();
1992 // Do we need to allocate a new node?
1993 unsigned NewNode
= 0;
1994 if (Elements
+ 1 > Nodes
* NodeT::Capacity
) {
1995 // Insert NewNode at the penultimate position, or after a single node.
1996 NewNode
= Nodes
== 1 ? 1 : Nodes
- 1;
1997 CurSize
[Nodes
] = CurSize
[NewNode
];
1998 Node
[Nodes
] = Node
[NewNode
];
1999 CurSize
[NewNode
] = 0;
2000 Node
[NewNode
] = this->map
->template newNode
<NodeT
>();
2004 // Compute the new element distribution.
2005 unsigned NewSize
[4];
2006 IdxPair NewOffset
= distribute(Nodes
, Elements
, NodeT::Capacity
,
2007 CurSize
, NewSize
, Offset
, true);
2008 adjustSiblingSizes(Node
, Nodes
, CurSize
, NewSize
);
2010 // Move current location to the leftmost node.
2014 // Elements have been rearranged, now update node sizes and stops.
2015 bool SplitRoot
= false;
2018 KeyT Stop
= Node
[Pos
]->stop(NewSize
[Pos
]-1);
2019 if (NewNode
&& Pos
== NewNode
) {
2020 SplitRoot
= insertNode(Level
, NodeRef(Node
[Pos
], NewSize
[Pos
]), Stop
);
2023 P
.setSize(Level
, NewSize
[Pos
]);
2024 setNodeStop(Level
, Stop
);
2026 if (Pos
+ 1 == Nodes
)
2032 // Where was I? Find NewOffset.
2033 while(Pos
!= NewOffset
.first
) {
2037 P
.offset(Level
) = NewOffset
.second
;
2041 //===----------------------------------------------------------------------===//
2042 //--- IntervalMapOverlaps ----//
2043 //===----------------------------------------------------------------------===//
2045 /// IntervalMapOverlaps - Iterate over the overlaps of mapped intervals in two
2046 /// IntervalMaps. The maps may be different, but the KeyT and Traits types
2047 /// should be the same.
2051 /// 1. Test for overlap:
2052 /// bool overlap = IntervalMapOverlaps(a, b).valid();
2054 /// 2. Enumerate overlaps:
2055 /// for (IntervalMapOverlaps I(a, b); I.valid() ; ++I) { ... }
2057 template <typename MapA
, typename MapB
>
2058 class IntervalMapOverlaps
{
2059 typedef typename
MapA::KeyType KeyType
;
2060 typedef typename
MapA::KeyTraits Traits
;
2061 typename
MapA::const_iterator posA
;
2062 typename
MapB::const_iterator posB
;
2064 /// advance - Move posA and posB forward until reaching an overlap, or until
2065 /// either meets end.
2066 /// Don't move the iterators if they are already overlapping.
2071 if (Traits::stopLess(posA
.stop(), posB
.start())) {
2072 // A ends before B begins. Catch up.
2073 posA
.advanceTo(posB
.start());
2074 if (!posA
.valid() || !Traits::stopLess(posB
.stop(), posA
.start()))
2076 } else if (Traits::stopLess(posB
.stop(), posA
.start())) {
2077 // B ends before A begins. Catch up.
2078 posB
.advanceTo(posA
.start());
2079 if (!posB
.valid() || !Traits::stopLess(posA
.stop(), posB
.start()))
2082 // Already overlapping.
2086 // Make a.end > b.start.
2087 posA
.advanceTo(posB
.start());
2088 if (!posA
.valid() || !Traits::stopLess(posB
.stop(), posA
.start()))
2090 // Make b.end > a.start.
2091 posB
.advanceTo(posA
.start());
2092 if (!posB
.valid() || !Traits::stopLess(posA
.stop(), posB
.start()))
2098 /// IntervalMapOverlaps - Create an iterator for the overlaps of a and b.
2099 IntervalMapOverlaps(const MapA
&a
, const MapB
&b
)
2100 : posA(b
.empty() ? a
.end() : a
.find(b
.start())),
2101 posB(posA
.valid() ? b
.find(posA
.start()) : b
.end()) { advance(); }
2103 /// valid - Return true if iterator is at an overlap.
2104 bool valid() const {
2105 return posA
.valid() && posB
.valid();
2108 /// a - access the left hand side in the overlap.
2109 const typename
MapA::const_iterator
&a() const { return posA
; }
2111 /// b - access the right hand side in the overlap.
2112 const typename
MapB::const_iterator
&b() const { return posB
; }
2114 /// start - Beginning of the overlapping interval.
2115 KeyType
start() const {
2116 KeyType ak
= a().start();
2117 KeyType bk
= b().start();
2118 return Traits::startLess(ak
, bk
) ? bk
: ak
;
2121 /// stop - End of the overlapping interval.
2122 KeyType
stop() const {
2123 KeyType ak
= a().stop();
2124 KeyType bk
= b().stop();
2125 return Traits::startLess(ak
, bk
) ? ak
: bk
;
2128 /// skipA - Move to the next overlap that doesn't involve a().
2134 /// skipB - Move to the next overlap that doesn't involve b().
2140 /// Preincrement - Move to the next overlap.
2141 IntervalMapOverlaps
&operator++() {
2142 // Bump the iterator that ends first. The other one may have more overlaps.
2143 if (Traits::startLess(posB
.stop(), posA
.stop()))
2150 /// advanceTo - Move to the first overlapping interval with
2151 /// stopLess(x, stop()).
2152 void advanceTo(KeyType x
) {
2155 // Make sure advanceTo sees monotonic keys.
2156 if (Traits::stopLess(posA
.stop(), x
))
2158 if (Traits::stopLess(posB
.stop(), x
))