EIC code displayed by LXR master/​include/​llvm/​ADT/​IntervalMap.h	Source navigation Diff markup Identifier search General search
	Version: master test Revert   Change

File indexing completed on 2026-05-10 08:43:06

 //===- llvm/ADT/IntervalMap.h - A sorted interval map -----------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 ///
 /// \file
 /// This file implements a coalescing interval map for small objects.
 ///
 /// KeyT objects are mapped to ValT objects. Intervals of keys that map to the
 /// same value are represented in a compressed form.
 ///
 /// Iterators provide ordered access to the compressed intervals rather than the
 /// individual keys, and insert and erase operations use key intervals as well.
 ///
 /// Like SmallVector, IntervalMap will store the first N intervals in the map
 /// object itself without any allocations. When space is exhausted it switches
 /// to a B+-tree representation with very small overhead for small key and
 /// value objects.
 ///
 /// A Traits class specifies how keys are compared. It also allows IntervalMap
 /// to work with both closed and half-open intervals.
 ///
 /// Keys and values are not stored next to each other in a std::pair, so we
 /// don't provide such a value_type. Dereferencing iterators only returns the
 /// mapped value. The interval bounds are accessible through the start() and
 /// stop() iterator methods.
 ///
 /// IntervalMap is optimized for small key and value objects, 4 or 8 bytes
 /// each is the optimal size. For large objects use std::map instead.
 //
 //===----------------------------------------------------------------------===//
 //
 // Synopsis:
 //
 // template <typename KeyT, typename ValT, unsigned N, typename Traits>
 // class IntervalMap {
 // public:
 //   typedef KeyT key_type;
 //   typedef ValT mapped_type;
 //   typedef RecyclingAllocator<...> Allocator;
 //   class iterator;
 //   class const_iterator;
 //
 //   explicit IntervalMap(Allocator&);
 //   ~IntervalMap():
 //
 //   bool empty() const;
 //   KeyT start() const;
 //   KeyT stop() const;
 //   ValT lookup(KeyT x, Value NotFound = Value()) const;
 //
 //   const_iterator begin() const;
 //   const_iterator end() const;
 //   iterator begin();
 //   iterator end();
 //   const_iterator find(KeyT x) const;
 //   iterator find(KeyT x);
 //
 //   void insert(KeyT a, KeyT b, ValT y);
 //   void clear();
 // };
 //
 // template <typename KeyT, typename ValT, unsigned N, typename Traits>
 // class IntervalMap::const_iterator {
 // public:
 //   using iterator_category = std::bidirectional_iterator_tag;
 //   using value_type = ValT;
 //   using difference_type = std::ptrdiff_t;
 //   using pointer = value_type *;
 //   using reference = value_type &;
 //
 //   bool operator==(const const_iterator &) const;
 //   bool operator!=(const const_iterator &) const;
 //   bool valid() const;
 //
 //   const KeyT &start() const;
 //   const KeyT &stop() const;
 //   const ValT &value() const;
 //   const ValT &operator*() const;
 //   const ValT *operator->() const;
 //
 //   const_iterator &operator++();
 //   const_iterator &operator++(int);
 //   const_iterator &operator--();
 //   const_iterator &operator--(int);
 //   void goToBegin();
 //   void goToEnd();
 //   void find(KeyT x);
 //   void advanceTo(KeyT x);
 // };
 //
 // template <typename KeyT, typename ValT, unsigned N, typename Traits>
 // class IntervalMap::iterator : public const_iterator {
 // public:
 //   void insert(KeyT a, KeyT b, Value y);
 //   void erase();
 // };
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ADT_INTERVALMAP_H
 #define LLVM_ADT_INTERVALMAP_H
 
 #include "llvm/ADT/PointerIntPair.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/Support/Allocator.h"
 #include "llvm/Support/RecyclingAllocator.h"
 #include <algorithm>
 #include <cassert>
 #include <iterator>
 #include <new>
 #include <utility>
 
 namespace llvm {
 
 //===----------------------------------------------------------------------===//
 //---                              Key traits                              ---//
 //===----------------------------------------------------------------------===//
 //
 // The IntervalMap works with closed or half-open intervals.
 // Adjacent intervals that map to the same value are coalesced.
 //
 // The IntervalMapInfo traits class is used to determine if a key is contained
 // in an interval, and if two intervals are adjacent so they can be coalesced.
 // The provided implementation works for closed integer intervals, other keys
 // probably need a specialized version.
 //
 // The point x is contained in [a;b] when !startLess(x, a) && !stopLess(b, x).
 //
 // It is assumed that (a;b] half-open intervals are not used, only [a;b) is
 // allowed. This is so that stopLess(a, b) can be used to determine if two
 // intervals overlap.
 //
 //===----------------------------------------------------------------------===//
 
 template <typename T>
 struct IntervalMapInfo {
   /// startLess - Return true if x is not in [a;b].
   /// This is x < a both for closed intervals and for [a;b) half-open intervals.
   static inline bool startLess(const T &x, const T &a) {
     return x < a;
   }
 
   /// stopLess - Return true if x is not in [a;b].
   /// This is b < x for a closed interval, b <= x for [a;b) half-open intervals.
   static inline bool stopLess(const T &b, const T &x) {
     return b < x;
   }
 
   /// adjacent - Return true when the intervals [x;a] and [b;y] can coalesce.
   /// This is a+1 == b for closed intervals, a == b for half-open intervals.
   static inline bool adjacent(const T &a, const T &b) {
     return a+1 == b;
   }
 
   /// nonEmpty - Return true if [a;b] is non-empty.
   /// This is a <= b for a closed interval, a < b for [a;b) half-open intervals.
   static inline bool nonEmpty(const T &a, const T &b) {
     return a <= b;
   }
 };
 
 template <typename T>
 struct IntervalMapHalfOpenInfo {
   /// startLess - Return true if x is not in [a;b).
   static inline bool startLess(const T &x, const T &a) {
     return x < a;
   }
 
   /// stopLess - Return true if x is not in [a;b).
   static inline bool stopLess(const T &b, const T &x) {
     return b <= x;
   }
 
   /// adjacent - Return true when the intervals [x;a) and [b;y) can coalesce.
   static inline bool adjacent(const T &a, const T &b) {
     return a == b;
   }
 
   /// nonEmpty - Return true if [a;b) is non-empty.
   static inline bool nonEmpty(const T &a, const T &b) {
     return a < b;
   }
 };
 
 /// IntervalMapImpl - Namespace used for IntervalMap implementation details.
 /// It should be considered private to the implementation.
 namespace IntervalMapImpl {
 
 using IdxPair = std::pair<unsigned,unsigned>;
 
 //===----------------------------------------------------------------------===//
 //---                    IntervalMapImpl::NodeBase                         ---//
 //===----------------------------------------------------------------------===//
 //
 // Both leaf and branch nodes store vectors of pairs.
 // Leaves store ((KeyT, KeyT), ValT) pairs, branches use (NodeRef, KeyT).
 //
 // Keys and values are stored in separate arrays to avoid padding caused by
 // different object alignments. This also helps improve locality of reference
 // when searching the keys.
 //
 // The nodes don't know how many elements they contain - that information is
 // stored elsewhere. Omitting the size field prevents padding and allows a node
 // to fill the allocated cache lines completely.
 //
 // These are typical key and value sizes, the node branching factor (N), and
 // wasted space when nodes are sized to fit in three cache lines (192 bytes):
 //
 //   T1  T2   N Waste  Used by
 //    4   4  24   0    Branch<4> (32-bit pointers)
 //    8   4  16   0    Leaf<4,4>, Branch<4>
 //    8   8  12   0    Leaf<4,8>, Branch<8>
 //   16   4   9  12    Leaf<8,4>
 //   16   8   8   0    Leaf<8,8>
 //
 //===----------------------------------------------------------------------===//
 
 template <typename T1, typename T2, unsigned N>
 class NodeBase {
 public:
   static constexpr unsigned Capacity = N;
 
   T1 first[N];
   T2 second[N];
 
   /// copy - Copy elements from another node.
   /// @param Other Node elements are copied from.
   /// @param i     Beginning of the source range in other.
   /// @param j     Beginning of the destination range in this.
   /// @param Count Number of elements to copy.
   template <unsigned M>
   void copy(const NodeBase<T1, T2, M> &Other, unsigned i,
             unsigned j, unsigned Count) {
     assert(i + Count <= M && "Invalid source range");
     assert(j + Count <= N && "Invalid dest range");
     for (unsigned e = i + Count; i != e; ++i, ++j) {
       first[j]  = Other.first[i];
       second[j] = Other.second[i];
     }
   }
 
   /// moveLeft - Move elements to the left.
   /// @param i     Beginning of the source range.
   /// @param j     Beginning of the destination range.
   /// @param Count Number of elements to copy.
   void moveLeft(unsigned i, unsigned j, unsigned Count) {
     assert(j <= i && "Use moveRight shift elements right");
     copy(*this, i, j, Count);
   }
 
   /// moveRight - Move elements to the right.
   /// @param i     Beginning of the source range.
   /// @param j     Beginning of the destination range.
   /// @param Count Number of elements to copy.
   void moveRight(unsigned i, unsigned j, unsigned Count) {
     assert(i <= j && "Use moveLeft shift elements left");
     assert(j + Count <= N && "Invalid range");
     while (Count--) {
       first[j + Count]  = first[i + Count];
       second[j + Count] = second[i + Count];
     }
   }
 
   /// erase - Erase elements [i;j).
   /// @param i    Beginning of the range to erase.
   /// @param j    End of the range. (Exclusive).
   /// @param Size Number of elements in node.
   void erase(unsigned i, unsigned j, unsigned Size) {
     moveLeft(j, i, Size - j);
   }
 
   /// erase - Erase element at i.
   /// @param i    Index of element to erase.
   /// @param Size Number of elements in node.
   void erase(unsigned i, unsigned Size) {
     erase(i, i+1, Size);
   }
 
   /// shift - Shift elements [i;size) 1 position to the right.
   /// @param i    Beginning of the range to move.
   /// @param Size Number of elements in node.
   void shift(unsigned i, unsigned Size) {
     moveRight(i, i + 1, Size - i);
   }
 
   /// transferToLeftSib - Transfer elements to a left sibling node.
   /// @param Size  Number of elements in this.
   /// @param Sib   Left sibling node.
   /// @param SSize Number of elements in sib.
   /// @param Count Number of elements to transfer.
   void transferToLeftSib(unsigned Size, NodeBase &Sib, unsigned SSize,
                          unsigned Count) {
     Sib.copy(*this, 0, SSize, Count);
     erase(0, Count, Size);
   }
 
   /// transferToRightSib - Transfer elements to a right sibling node.
   /// @param Size  Number of elements in this.
   /// @param Sib   Right sibling node.
   /// @param SSize Number of elements in sib.
   /// @param Count Number of elements to transfer.
   void transferToRightSib(unsigned Size, NodeBase &Sib, unsigned SSize,
                           unsigned Count) {
     Sib.moveRight(0, Count, SSize);
     Sib.copy(*this, Size-Count, 0, Count);
   }
 
   /// adjustFromLeftSib - Adjust the number if elements in this node by moving
   /// elements to or from a left sibling node.
   /// @param Size  Number of elements in this.
   /// @param Sib   Right sibling node.
   /// @param SSize Number of elements in sib.
   /// @param Add   The number of elements to add to this node, possibly < 0.
   /// @return      Number of elements added to this node, possibly negative.
   int adjustFromLeftSib(unsigned Size, NodeBase &Sib, unsigned SSize, int Add) {
     if (Add > 0) {
       // We want to grow, copy from sib.
       unsigned Count = std::min(std::min(unsigned(Add), SSize), N - Size);
       Sib.transferToRightSib(SSize, *this, Size, Count);
       return Count;
     } else {
       // We want to shrink, copy to sib.
       unsigned Count = std::min(std::min(unsigned(-Add), Size), N - SSize);
       transferToLeftSib(Size, Sib, SSize, Count);
       return -Count;
     }
   }
 };
 
 /// IntervalMapImpl::adjustSiblingSizes - Move elements between sibling nodes.
 /// @param Node  Array of pointers to sibling nodes.
 /// @param Nodes Number of nodes.
 /// @param CurSize Array of current node sizes, will be overwritten.
 /// @param NewSize Array of desired node sizes.
 template <typename NodeT>
 void adjustSiblingSizes(NodeT *Node[], unsigned Nodes,
                         unsigned CurSize[], const unsigned NewSize[]) {
   // Move elements right.
   for (int n = Nodes - 1; n; --n) {
     if (CurSize[n] == NewSize[n])
       continue;
     for (int m = n - 1; m != -1; --m) {
       int d = Node[n]->adjustFromLeftSib(CurSize[n], *Node[m], CurSize[m],
                                          NewSize[n] - CurSize[n]);
       CurSize[m] -= d;
       CurSize[n] += d;
       // Keep going if the current node was exhausted.
       if (CurSize[n] >= NewSize[n])
           break;
     }
   }
 
   if (Nodes == 0)
     return;
 
   // Move elements left.
   for (unsigned n = 0; n != Nodes - 1; ++n) {
     if (CurSize[n] == NewSize[n])
       continue;
     for (unsigned m = n + 1; m != Nodes; ++m) {
       int d = Node[m]->adjustFromLeftSib(CurSize[m], *Node[n], CurSize[n],
                                         CurSize[n] -  NewSize[n]);
       CurSize[m] += d;
       CurSize[n] -= d;
       // Keep going if the current node was exhausted.
       if (CurSize[n] >= NewSize[n])
           break;
     }
   }
 
 #ifndef NDEBUG
   for (unsigned n = 0; n != Nodes; n++)
     assert(CurSize[n] == NewSize[n] && "Insufficient element shuffle");
 #endif
 }
 
 /// IntervalMapImpl::distribute - Compute a new distribution of node elements
 /// after an overflow or underflow. Reserve space for a new element at Position,
 /// and compute the node that will hold Position after redistributing node
 /// elements.
 ///
 /// It is required that
 ///
 ///   Elements == sum(CurSize), and
 ///   Elements + Grow <= Nodes * Capacity.
 ///
 /// NewSize[] will be filled in such that:
 ///
 ///   sum(NewSize) == Elements, and
 ///   NewSize[i] <= Capacity.
 ///
 /// The returned index is the node where Position will go, so:
 ///
 ///   sum(NewSize[0..idx-1]) <= Position
 ///   sum(NewSize[0..idx])   >= Position
 ///
 /// The last equality, sum(NewSize[0..idx]) == Position, can only happen when
 /// Grow is set and NewSize[idx] == Capacity-1. The index points to the node
 /// before the one holding the Position'th element where there is room for an
 /// insertion.
 ///
 /// @param Nodes    The number of nodes.
 /// @param Elements Total elements in all nodes.
 /// @param Capacity The capacity of each node.
 /// @param CurSize  Array[Nodes] of current node sizes, or NULL.
 /// @param NewSize  Array[Nodes] to receive the new node sizes.
 /// @param Position Insert position.
 /// @param Grow     Reserve space for a new element at Position.
 /// @return         (node, offset) for Position.
 IdxPair distribute(unsigned Nodes, unsigned Elements, unsigned Capacity,
                    const unsigned *CurSize, unsigned NewSize[],
                    unsigned Position, bool Grow);
 
 //===----------------------------------------------------------------------===//
 //---                   IntervalMapImpl::NodeSizer                         ---//
 //===----------------------------------------------------------------------===//
 //
 // Compute node sizes from key and value types.
 //
 // The branching factors are chosen to make nodes fit in three cache lines.
 // This may not be possible if keys or values are very large. Such large objects
 // are handled correctly, but a std::map would probably give better performance.
 //
 //===----------------------------------------------------------------------===//
 
 enum {
   // Cache line size. Most architectures have 32 or 64 byte cache lines.
   // We use 64 bytes here because it provides good branching factors.
   Log2CacheLine = 6,
   CacheLineBytes = 1 << Log2CacheLine,
   DesiredNodeBytes = 3 * CacheLineBytes
 };
 
 template <typename KeyT, typename ValT>
 struct NodeSizer {
   enum {
     // Compute the leaf node branching factor that makes a node fit in three
     // cache lines. The branching factor must be at least 3, or some B+-tree
     // balancing algorithms won't work.
     // LeafSize can't be larger than CacheLineBytes. This is required by the
     // PointerIntPair used by NodeRef.
     DesiredLeafSize = DesiredNodeBytes /
       static_cast<unsigned>(2*sizeof(KeyT)+sizeof(ValT)),
     MinLeafSize = 3,
     LeafSize = DesiredLeafSize > MinLeafSize ? DesiredLeafSize : MinLeafSize
   };
 
   using LeafBase = NodeBase<std::pair<KeyT, KeyT>, ValT, LeafSize>;
 
   enum {
     // Now that we have the leaf branching factor, compute the actual allocation
     // unit size by rounding up to a whole number of cache lines.
     AllocBytes = (sizeof(LeafBase) + CacheLineBytes-1) & ~(CacheLineBytes-1),
 
     // Determine the branching factor for branch nodes.
     BranchSize = AllocBytes /
       static_cast<unsigned>(sizeof(KeyT) + sizeof(void*))
   };
 
   /// Allocator - The recycling allocator used for both branch and leaf nodes.
   /// This typedef is very likely to be identical for all IntervalMaps with
   /// reasonably sized entries, so the same allocator can be shared among
   /// different kinds of maps.
   using Allocator =
       RecyclingAllocator<BumpPtrAllocator, char, AllocBytes, CacheLineBytes>;
 };
 
 //===----------------------------------------------------------------------===//
 //---                     IntervalMapImpl::NodeRef                         ---//
 //===----------------------------------------------------------------------===//
 //
 // B+-tree nodes can be leaves or branches, so we need a polymorphic node
 // pointer that can point to both kinds.
 //
 // All nodes are cache line aligned and the low 6 bits of a node pointer are
 // always 0. These bits are used to store the number of elements in the
 // referenced node. Besides saving space, placing node sizes in the parents
 // allow tree balancing algorithms to run without faulting cache lines for nodes
 // that may not need to be modified.
 //
 // A NodeRef doesn't know whether it references a leaf node or a branch node.
 // It is the responsibility of the caller to use the correct types.
 //
 // Nodes are never supposed to be empty, and it is invalid to store a node size
 // of 0 in a NodeRef. The valid range of sizes is 1-64.
 //
 //===----------------------------------------------------------------------===//
 
 class NodeRef {
   struct CacheAlignedPointerTraits {
     static inline void *getAsVoidPointer(void *P) { return P; }
     static inline void *getFromVoidPointer(void *P) { return P; }
     static constexpr int NumLowBitsAvailable = Log2CacheLine;
   };
   PointerIntPair<void*, Log2CacheLine, unsigned, CacheAlignedPointerTraits> pip;
 
 public:
   /// NodeRef - Create a null ref.
   NodeRef() = default;
 
   /// operator bool - Detect a null ref.
   explicit operator bool() const { return pip.getOpaqueValue(); }
 
   /// NodeRef - Create a reference to the node p with n elements.
   template <typename NodeT>
   NodeRef(NodeT *p, unsigned n) : pip(p, n - 1) {
     assert(n <= NodeT::Capacity && "Size too big for node");
   }
 
   /// size - Return the number of elements in the referenced node.
   unsigned size() const { return pip.getInt() + 1; }
 
   /// setSize - Update the node size.
   void setSize(unsigned n) { pip.setInt(n - 1); }
 
   /// subtree - Access the i'th subtree reference in a branch node.
   /// This depends on branch nodes storing the NodeRef array as their first
   /// member.
   NodeRef &subtree(unsigned i) const {
     return reinterpret_cast<NodeRef*>(pip.getPointer())[i];
   }
 
   /// get - Dereference as a NodeT reference.
   template <typename NodeT>
   NodeT &get() const {
     return *reinterpret_cast<NodeT*>(pip.getPointer());
   }
 
   bool operator==(const NodeRef &RHS) const {
     if (pip == RHS.pip)
       return true;
     assert(pip.getPointer() != RHS.pip.getPointer() && "Inconsistent NodeRefs");
     return false;
   }
 
   bool operator!=(const NodeRef &RHS) const {
     return !operator==(RHS);
   }
 };
 
 //===----------------------------------------------------------------------===//
 //---                      IntervalMapImpl::LeafNode                       ---//
 //===----------------------------------------------------------------------===//
 //
 // Leaf nodes store up to N disjoint intervals with corresponding values.
 //
 // The intervals are kept sorted and fully coalesced so there are no adjacent
 // intervals mapping to the same value.
 //
 // These constraints are always satisfied:
 //
 // - Traits::stopLess(start(i), stop(i))    - Non-empty, sane intervals.
 //
 // - Traits::stopLess(stop(i), start(i + 1) - Sorted.
 //
 // - value(i) != value(i + 1) || !Traits::adjacent(stop(i), start(i + 1))
 //                                          - Fully coalesced.
 //
 //===----------------------------------------------------------------------===//
 
 template <typename KeyT, typename ValT, unsigned N, typename Traits>
 class LeafNode : public NodeBase<std::pair<KeyT, KeyT>, ValT, N> {
 public:
   const KeyT &start(unsigned i) const { return this->first[i].first; }
   const KeyT &stop(unsigned i) const { return this->first[i].second; }
   const ValT &value(unsigned i) const { return this->second[i]; }
 
   KeyT &start(unsigned i) { return this->first[i].first; }
   KeyT &stop(unsigned i) { return this->first[i].second; }
   ValT &value(unsigned i) { return this->second[i]; }
 
   /// findFrom - Find the first interval after i that may contain x.
   /// @param i    Starting index for the search.
   /// @param Size Number of elements in node.
   /// @param x    Key to search for.
   /// @return     First index with !stopLess(key[i].stop, x), or size.
   ///             This is the first interval that can possibly contain x.
   unsigned findFrom(unsigned i, unsigned Size, KeyT x) const {
     assert(i <= Size && Size <= N && "Bad indices");
     assert((i == 0 || Traits::stopLess(stop(i - 1), x)) &&
            "Index is past the needed point");
     while (i != Size && Traits::stopLess(stop(i), x)) ++i;
     return i;
   }
 
   /// safeFind - Find an interval that is known to exist. This is the same as
   /// findFrom except is it assumed that x is at least within range of the last
   /// interval.
   /// @param i Starting index for the search.
   /// @param x Key to search for.
   /// @return  First index with !stopLess(key[i].stop, x), never size.
   ///          This is the first interval that can possibly contain x.
   unsigned safeFind(unsigned i, KeyT x) const {
     assert(i < N && "Bad index");
     assert((i == 0 || Traits::stopLess(stop(i - 1), x)) &&
            "Index is past the needed point");
     while (Traits::stopLess(stop(i), x)) ++i;
     assert(i < N && "Unsafe intervals");
     return i;
   }
 
   /// safeLookup - Lookup mapped value for a safe key.
   /// It is assumed that x is within range of the last entry.
   /// @param x        Key to search for.
   /// @param NotFound Value to return if x is not in any interval.
   /// @return         The mapped value at x or NotFound.
   ValT safeLookup(KeyT x, ValT NotFound) const {
     unsigned i = safeFind(0, x);
     return Traits::startLess(x, start(i)) ? NotFound : value(i);
   }
 
   unsigned insertFrom(unsigned &Pos, unsigned Size, KeyT a, KeyT b, ValT y);
 };
 
 /// insertFrom - Add mapping of [a;b] to y if possible, coalescing as much as
 /// possible. This may cause the node to grow by 1, or it may cause the node
 /// to shrink because of coalescing.
 /// @param Pos  Starting index = insertFrom(0, size, a)
 /// @param Size Number of elements in node.
 /// @param a    Interval start.
 /// @param b    Interval stop.
 /// @param y    Value be mapped.
 /// @return     (insert position, new size), or (i, Capacity+1) on overflow.
 template <typename KeyT, typename ValT, unsigned N, typename Traits>
 unsigned LeafNode<KeyT, ValT, N, Traits>::
 insertFrom(unsigned &Pos, unsigned Size, KeyT a, KeyT b, ValT y) {
   unsigned i = Pos;
   assert(i <= Size && Size <= N && "Invalid index");
   assert(!Traits::stopLess(b, a) && "Invalid interval");
 
   // Verify the findFrom invariant.
   assert((i == 0 || Traits::stopLess(stop(i - 1), a)));
   assert((i == Size || !Traits::stopLess(stop(i), a)));
   assert((i == Size || Traits::stopLess(b, start(i))) && "Overlapping insert");
 
   // Coalesce with previous interval.
   if (i && value(i - 1) == y && Traits::adjacent(stop(i - 1), a)) {
     Pos = i - 1;
     // Also coalesce with next interval?
     if (i != Size && value(i) == y && Traits::adjacent(b, start(i))) {
       stop(i - 1) = stop(i);
       this->erase(i, Size);
       return Size - 1;
     }
     stop(i - 1) = b;
     return Size;
   }
 
   // Detect overflow.
   if (i == N)
     return N + 1;
 
   // Add new interval at end.
   if (i == Size) {
     start(i) = a;
     stop(i) = b;
     value(i) = y;
     return Size + 1;
   }
 
   // Try to coalesce with following interval.
   if (value(i) == y && Traits::adjacent(b, start(i))) {
     start(i) = a;
     return Size;
   }
 
   // We must insert before i. Detect overflow.
   if (Size == N)
     return N + 1;
 
   // Insert before i.
   this->shift(i, Size);
   start(i) = a;
   stop(i) = b;
   value(i) = y;
   return Size + 1;
 }
 
 //===----------------------------------------------------------------------===//
 //---                   IntervalMapImpl::BranchNode                        ---//
 //===----------------------------------------------------------------------===//
 //
 // A branch node stores references to 1--N subtrees all of the same height.
 //
 // The key array in a branch node holds the rightmost stop key of each subtree.
 // It is redundant to store the last stop key since it can be found in the
 // parent node, but doing so makes tree balancing a lot simpler.
 //
 // It is unusual for a branch node to only have one subtree, but it can happen
 // in the root node if it is smaller than the normal nodes.
 //
 // When all of the leaf nodes from all the subtrees are concatenated, they must
 // satisfy the same constraints as a single leaf node. They must be sorted,
 // sane, and fully coalesced.
 //
 //===----------------------------------------------------------------------===//
 
 template <typename KeyT, typename ValT, unsigned N, typename Traits>
 class BranchNode : public NodeBase<NodeRef, KeyT, N> {
 public:
   const KeyT &stop(unsigned i) const { return this->second[i]; }
   const NodeRef &subtree(unsigned i) const { return this->first[i]; }
 
   KeyT &stop(unsigned i) { return this->second[i]; }
   NodeRef &subtree(unsigned i) { return this->first[i]; }
 
   /// findFrom - Find the first subtree after i that may contain x.
   /// @param i    Starting index for the search.
   /// @param Size Number of elements in node.
   /// @param x    Key to search for.
   /// @return     First index with !stopLess(key[i], x), or size.
   ///             This is the first subtree that can possibly contain x.
   unsigned findFrom(unsigned i, unsigned Size, KeyT x) const {
     assert(i <= Size && Size <= N && "Bad indices");
     assert((i == 0 || Traits::stopLess(stop(i - 1), x)) &&
            "Index to findFrom is past the needed point");
     while (i != Size && Traits::stopLess(stop(i), x)) ++i;
     return i;
   }
 
   /// safeFind - Find a subtree that is known to exist. This is the same as
   /// findFrom except is it assumed that x is in range.
   /// @param i Starting index for the search.
   /// @param x Key to search for.
   /// @return  First index with !stopLess(key[i], x), never size.
   ///          This is the first subtree that can possibly contain x.
   unsigned safeFind(unsigned i, KeyT x) const {
     assert(i < N && "Bad index");
     assert((i == 0 || Traits::stopLess(stop(i - 1), x)) &&
            "Index is past the needed point");
     while (Traits::stopLess(stop(i), x)) ++i;
     assert(i < N && "Unsafe intervals");
     return i;
   }
 
   /// safeLookup - Get the subtree containing x, Assuming that x is in range.
   /// @param x Key to search for.
   /// @return  Subtree containing x
   NodeRef safeLookup(KeyT x) const {
     return subtree(safeFind(0, x));
   }
 
   /// insert - Insert a new (subtree, stop) pair.
   /// @param i    Insert position, following entries will be shifted.
   /// @param Size Number of elements in node.
   /// @param Node Subtree to insert.
   /// @param Stop Last key in subtree.
   void insert(unsigned i, unsigned Size, NodeRef Node, KeyT Stop) {
     assert(Size < N && "branch node overflow");
     assert(i <= Size && "Bad insert position");
     this->shift(i, Size);
     subtree(i) = Node;
     stop(i) = Stop;
   }
 };
 
 //===----------------------------------------------------------------------===//
 //---                         IntervalMapImpl::Path                        ---//
 //===----------------------------------------------------------------------===//
 //
 // 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 contains the tree navigation code that doesn't have to
 // be templatized.
 //
 //===----------------------------------------------------------------------===//
 
 class Path {
   /// Entry - Each step in the path is a node pointer and an offset into that
   /// node.
   struct Entry {
     void *node;
     unsigned size;
     unsigned offset;
 
     Entry(void *Node, unsigned Size, unsigned Offset)
       : node(Node), size(Size), offset(Offset) {}
 
     Entry(NodeRef Node, unsigned Offset)
       : node(&Node.subtree(0)), size(Node.size()), offset(Offset) {}
 
     NodeRef &subtree(unsigned i) const {
       return reinterpret_cast<NodeRef*>(node)[i];
     }
   };
 
   /// path - The path entries, path[0] is the root node, path.back() is a leaf.
   SmallVector<Entry, 4> path;
 
 public:
   // Node accessors.
   template <typename NodeT> NodeT &node(unsigned Level) const {
     return *reinterpret_cast<NodeT*>(path[Level].node);
   }
   unsigned size(unsigned Level) const { return path[Level].size; }
   unsigned offset(unsigned Level) const { return path[Level].offset; }
   unsigned &offset(unsigned Level) { return path[Level].offset; }
 
   // Leaf accessors.
   template <typename NodeT> NodeT &leaf() const {
     return *reinterpret_cast<NodeT*>(path.back().node);
   }
   unsigned leafSize() const { return path.back().size; }
   unsigned leafOffset() const { return path.back().offset; }
   unsigned &leafOffset() { return path.back().offset; }
 
   /// valid - Return true if path is at a valid node, not at end().
   bool valid() const {
     return !path.empty() && path.front().offset < path.front().size;
   }
 
   /// height - Return the height of the tree corresponding to this path.
   /// This matches map->height in a full path.
   unsigned height() const { return path.size() - 1; }
 
   /// subtree - Get the subtree referenced from Level. When the path is
   /// consistent, node(Level + 1) == subtree(Level).
   /// @param Level 0..height-1. The leaves have no subtrees.
   NodeRef &subtree(unsigned Level) const {
     return path[Level].subtree(path[Level].offset);
   }
 
   /// reset - Reset cached information about node(Level) from subtree(Level -1).
   /// @param Level 1..height. The node to update after parent node changed.
   void reset(unsigned Level) {
     path[Level] = Entry(subtree(Level - 1), offset(Level));
   }
 
   /// push - Add entry to path.
   /// @param Node Node to add, should be subtree(path.size()-1).
   /// @param Offset Offset into Node.
   void push(NodeRef Node, unsigned Offset) {
     path.push_back(Entry(Node, Offset));
   }
 
   /// pop - Remove the last path entry.
   void pop() {
     path.pop_back();
   }
 
   /// setSize - Set the size of a node both in the path and in the tree.
   /// @param Level 0..height. Note that setting the root size won't change
   ///              map->rootSize.
   /// @param Size New node size.
   void setSize(unsigned Level, unsigned Size) {
     path[Level].size = Size;
     if (Level)
       subtree(Level - 1).setSize(Size);
   }
 
   /// setRoot - Clear the path and set a new root node.
   /// @param Node New root node.
   /// @param Size New root size.
   /// @param Offset Offset into root node.
   void setRoot(void *Node, unsigned Size, unsigned Offset) {
     path.clear();
     path.push_back(Entry(Node, Size, Offset));
   }
 
   /// replaceRoot - Replace the current root node with two new entries after the
   /// tree height has increased.
   /// @param Root The new root node.
   /// @param Size Number of entries in the new root.
   /// @param Offsets Offsets into the root and first branch nodes.
   void replaceRoot(void *Root, unsigned Size, IdxPair Offsets);
 
   /// getLeftSibling - Get the left sibling node at Level, or a null NodeRef.
   /// @param Level Get the sibling to node(Level).
   /// @return Left sibling, or NodeRef().
   NodeRef getLeftSibling(unsigned Level) const;
 
   /// moveLeft - Move path to the left sibling at Level. Leave nodes below Level
   /// unaltered.
   /// @param Level Move node(Level).
   void moveLeft(unsigned Level);
 
   /// fillLeft - Grow path to Height by taking leftmost branches.
   /// @param Height The target height.
   void fillLeft(unsigned Height) {
     while (height() < Height)
       push(subtree(height()), 0);
   }
 
   /// getLeftSibling - Get the left sibling node at Level, or a null NodeRef.
   /// @param Level Get the sibling to node(Level).
   /// @return Left sibling, or NodeRef().
   NodeRef getRightSibling(unsigned Level) const;
 
   /// moveRight - Move path to the left sibling at Level. Leave nodes below
   /// Level unaltered.
   /// @param Level Move node(Level).
   void moveRight(unsigned Level);
 
   /// atBegin - Return true if path is at begin().
   bool atBegin() const {
     for (unsigned i = 0, e = path.size(); i != e; ++i)
       if (path[i].offset != 0)
         return false;
     return true;
   }
 
   /// atLastEntry - Return true if the path is at the last entry of the node at
   /// Level.
   /// @param Level Node to examine.
   bool atLastEntry(unsigned Level) const {
     return path[Level].offset == path[Level].size - 1;
   }
 
   /// legalizeForInsert - Prepare the path for an insertion at Level. When the
   /// path is at end(), node(Level) may not be a legal node. legalizeForInsert
   /// ensures that node(Level) is real by moving back to the last node at Level,
   /// and setting offset(Level) to size(Level) if required.
   /// @param Level The level where an insertion is about to take place.
   void legalizeForInsert(unsigned Level) {
     if (valid())
       return;
     moveLeft(Level);
     ++path[Level].offset;
   }
 };
 
 } // end namespace IntervalMapImpl
 
 //===----------------------------------------------------------------------===//
 //---                          IntervalMap                                ----//
 //===----------------------------------------------------------------------===//
 
 template <typename KeyT, typename ValT,
           unsigned N = IntervalMapImpl::NodeSizer<KeyT, ValT>::LeafSize,
           typename Traits = IntervalMapInfo<KeyT>>
 class IntervalMap {
   using Sizer = IntervalMapImpl::NodeSizer<KeyT, ValT>;
   using Leaf = IntervalMapImpl::LeafNode<KeyT, ValT, Sizer::LeafSize, Traits>;
   using Branch =
       IntervalMapImpl::BranchNode<KeyT, ValT, Sizer::BranchSize, Traits>;
   using RootLeaf = IntervalMapImpl::LeafNode<KeyT, ValT, N, Traits>;
   using IdxPair = IntervalMapImpl::IdxPair;
 
   // The RootLeaf capacity is given as a template parameter. We must compute the
   // corresponding RootBranch capacity.
   enum {
     DesiredRootBranchCap = (sizeof(RootLeaf) - sizeof(KeyT)) /
       (sizeof(KeyT) + sizeof(IntervalMapImpl::NodeRef)),
     RootBranchCap = DesiredRootBranchCap ? DesiredRootBranchCap : 1
   };
 
   using RootBranch =
       IntervalMapImpl::BranchNode<KeyT, ValT, RootBranchCap, Traits>;
 
   // When branched, we store a global start key as well as the branch node.
   struct RootBranchData {
     KeyT start;
     RootBranch node;
   };
 
 public:
   using Allocator = typename Sizer::Allocator;
   using KeyType = KeyT;
   using ValueType = ValT;
   using KeyTraits = Traits;
 
 private:
   // The root data is either a RootLeaf or a RootBranchData instance.
   union {
     RootLeaf leaf;
     RootBranchData branchData;
   };
 
   // Tree height.
   // 0: Leaves in root.
   // 1: Root points to leaf.
   // 2: root->branch->leaf ...
   unsigned height = 0;
 
   // Number of entries in the root node.
   unsigned rootSize = 0;
 
   // Allocator used for creating external nodes.
   Allocator *allocator = nullptr;
 
   const RootLeaf &rootLeaf() const {
     assert(!branched() && "Cannot acces leaf data in branched root");
     return leaf;
   }
   RootLeaf &rootLeaf() {
     assert(!branched() && "Cannot acces leaf data in branched root");
     return leaf;
   }
 
   const RootBranchData &rootBranchData() const {
     assert(branched() && "Cannot access branch data in non-branched root");
     return branchData;
   }
   RootBranchData &rootBranchData() {
     assert(branched() && "Cannot access branch data in non-branched root");
     return branchData;
   }
 
   const RootBranch &rootBranch() const { return rootBranchData().node; }
   RootBranch &rootBranch()             { return rootBranchData().node; }
   KeyT rootBranchStart() const { return rootBranchData().start; }
   KeyT &rootBranchStart()      { return rootBranchData().start; }
 
   template <typename NodeT> NodeT *newNode() {
     return new (allocator->template Allocate<NodeT>()) NodeT();
   }
 
   template <typename NodeT> void deleteNode(NodeT *P) {
     P->~NodeT();
     allocator->Deallocate(P);
   }
 
   IdxPair branchRoot(unsigned Position);
   IdxPair splitRoot(unsigned Position);
 
   void switchRootToBranch() {
     rootLeaf().~RootLeaf();
     height = 1;
     new (&rootBranchData()) RootBranchData();
   }
 
   void switchRootToLeaf() {
     rootBranchData().~RootBranchData();
     height = 0;
     new(&rootLeaf()) RootLeaf();
   }
 
   bool branched() const { return height > 0; }
 
   ValT treeSafeLookup(KeyT x, ValT NotFound) const;
   void visitNodes(void (IntervalMap::*f)(IntervalMapImpl::NodeRef,
                   unsigned Level));
   void deleteNode(IntervalMapImpl::NodeRef Node, unsigned Level);
 
 public:
   explicit IntervalMap(Allocator &a) : allocator(&a) {
     new (&rootLeaf()) RootLeaf();
   }
 
   ///@{
   /// NOTE: The moved-from or copied-from object's allocator needs to have a
   /// lifetime equal to or exceeding the moved-to or copied-to object to avoid
   /// undefined behaviour.
   IntervalMap(IntervalMap const &RHS) : IntervalMap(*RHS.allocator) {
     // Future-proofing assertion: this function assumes the IntervalMap
     // constructor doesn't add any nodes.
     assert(empty() && "Expected emptry tree");
     *this = RHS;
   }
   IntervalMap &operator=(IntervalMap const &RHS) {
     clear();
     allocator = RHS.allocator;
     for (auto It = RHS.begin(), End = RHS.end(); It != End; ++It)
       insert(It.start(), It.stop(), It.value());
     return *this;
   }
 
   IntervalMap(IntervalMap &&RHS) : IntervalMap(*RHS.allocator) {
     // Future-proofing assertion: this function assumes the IntervalMap
     // constructor doesn't add any nodes.
     assert(empty() && "Expected emptry tree");
     *this = std::move(RHS);
   }
   IntervalMap &operator=(IntervalMap &&RHS) {
     // Calling clear deallocates memory and switches to rootLeaf.
     clear();
     // Destroy the new rootLeaf.
     rootLeaf().~RootLeaf();
 
     height = RHS.height;
     rootSize = RHS.rootSize;
     allocator = RHS.allocator;
 
     // rootLeaf and rootBranch are both uninitialized. Move RHS data into
     // appropriate field.
     if (RHS.branched()) {
       rootBranch() = std::move(RHS.rootBranch());
       // Prevent RHS deallocating memory LHS now owns by replacing RHS
       // rootBranch with a new rootLeaf.
       RHS.rootBranch().~RootBranch();
       RHS.height = 0;
       new (&RHS.rootLeaf()) RootLeaf();
     } else {
       rootLeaf() = std::move(RHS.rootLeaf());
     }
     return *this;
   }
   ///@}
 
   ~IntervalMap() {
     clear();
     rootLeaf().~RootLeaf();
   }
 
   /// empty -  Return true when no intervals are mapped.
   bool empty() const {
     return rootSize == 0;
   }
 
   /// start - Return the smallest mapped key in a non-empty map.
   KeyT start() const {
     assert(!empty() && "Empty IntervalMap has no start");
     return !branched() ? rootLeaf().start(0) : rootBranchStart();
   }
 
   /// stop - Return the largest mapped key in a non-empty map.
   KeyT stop() const {
     assert(!empty() && "Empty IntervalMap has no stop");
     return !branched() ? rootLeaf().stop(rootSize - 1) :
                          rootBranch().stop(rootSize - 1);
   }
 
   /// lookup - Return the mapped value at x or NotFound.
   ValT lookup(KeyT x, ValT NotFound = ValT()) const {
     if (empty() || Traits::startLess(x, start()) || Traits::stopLess(stop(), x))
       return NotFound;
     return branched() ? treeSafeLookup(x, NotFound) :
                         rootLeaf().safeLookup(x, NotFound);
   }
 
   /// insert - Add a mapping of [a;b] to y, coalesce with adjacent intervals.
   /// It is assumed that no key in the interval is mapped to another value, but
   /// overlapping intervals already mapped to y will be coalesced.
   void insert(KeyT a, KeyT b, ValT y) {
     if (branched() || rootSize == RootLeaf::Capacity)
       return find(a).insert(a, b, y);
 
     // Easy insert into root leaf.
     unsigned p = rootLeaf().findFrom(0, rootSize, a);
     rootSize = rootLeaf().insertFrom(p, rootSize, a, b, y);
   }
 
   /// clear - Remove all entries.
   void clear();
 
   class const_iterator;
   class iterator;
   friend class const_iterator;
   friend class iterator;
 
   const_iterator begin() const {
     const_iterator I(*this);
     I.goToBegin();
     return I;
   }
 
   iterator begin() {
     iterator I(*this);
     I.goToBegin();
     return I;
   }
 
   const_iterator end() const {
     const_iterator I(*this);
     I.goToEnd();
     return I;
   }
 
   iterator end() {
     iterator I(*this);
     I.goToEnd();
     return I;
   }
 
   /// find - Return an iterator pointing to the first interval ending at or
   /// after x, or end().
   const_iterator find(KeyT x) const {
     const_iterator I(*this);
     I.find(x);
     return I;
   }
 
   iterator find(KeyT x) {
     iterator I(*this);
     I.find(x);
     return I;
   }
 
   /// overlaps(a, b) - Return true if the intervals in this map overlap with the
   /// interval [a;b].
   bool overlaps(KeyT a, KeyT b) const {
     assert(Traits::nonEmpty(a, b));
     const_iterator I = find(a);
     if (!I.valid())
       return false;
     // [a;b] and [x;y] overlap iff x<=b and a<=y. The find() call guarantees the
     // second part (y = find(a).stop()), so it is sufficient to check the first
     // one.
     return !Traits::stopLess(b, I.start());
   }
 };
 
 /// treeSafeLookup - Return the mapped value at x or NotFound, assuming a
 /// branched root.
 template <typename KeyT, typename ValT, unsigned N, typename Traits>
 ValT IntervalMap<KeyT, ValT, N, Traits>::
 treeSafeLookup(KeyT x, ValT NotFound) const {
   assert(branched() && "treeLookup assumes a branched root");
 
   IntervalMapImpl::NodeRef NR = rootBranch().safeLookup(x);
   for (unsigned h = height-1; h; --h)
     NR = NR.get<Branch>().safeLookup(x);
   return NR.get<Leaf>().safeLookup(x, NotFound);
 }
 
 // branchRoot - Switch from a leaf root to a branched root.
 // Return the new (root offset, node offset) corresponding to Position.
 template <typename KeyT, typename ValT, unsigned N, typename Traits>
 IntervalMapImpl::IdxPair IntervalMap<KeyT, ValT, N, Traits>::
 branchRoot(unsigned Position) {
   using namespace IntervalMapImpl;
   // How many external leaf nodes to hold RootLeaf+1?
   const unsigned Nodes = RootLeaf::Capacity / Leaf::Capacity + 1;
 
   // Compute element distribution among new nodes.
   unsigned size[Nodes];
   IdxPair NewOffset(0, Position);
 
   // It is very common for the root node to be smaller than external nodes.
   if (Nodes == 1)
     size[0] = rootSize;
   else
     NewOffset = distribute(Nodes, rootSize, Leaf::Capacity,  nullptr, size,
                            Position, true);
 
   // Allocate new nodes.
   unsigned pos = 0;
   NodeRef node[Nodes];
   for (unsigned n = 0; n != Nodes; ++n) {
     Leaf *L = newNode<Leaf>();
     L->copy(rootLeaf(), pos, 0, size[n]);
     node[n] = NodeRef(L, size[n]);
     pos += size[n];
   }
 
   // Destroy the old leaf node, construct branch node instead.
   switchRootToBranch();
   for (unsigned n = 0; n != Nodes; ++n) {
     rootBranch().stop(n) = node[n].template get<Leaf>().stop(size[n]-1);
     rootBranch().subtree(n) = node[n];
   }
   rootBranchStart() = node[0].template get<Leaf>().start(0);
   rootSize = Nodes;
   return NewOffset;
 }
 
 // splitRoot - Split the current BranchRoot into multiple Branch nodes.
 // Return the new (root offset, node offset) corresponding to Position.
 template <typename KeyT, typename ValT, unsigned N, typename Traits>
 IntervalMapImpl::IdxPair IntervalMap<KeyT, ValT, N, Traits>::
 splitRoot(unsigned Position) {
   using namespace IntervalMapImpl;
   // How many external leaf nodes to hold RootBranch+1?
   const unsigned Nodes = RootBranch::Capacity / Branch::Capacity + 1;
 
   // Compute element distribution among new nodes.
   unsigned Size[Nodes];
   IdxPair NewOffset(0, Position);
 
   // It is very common for the root node to be smaller than external nodes.
   if (Nodes == 1)
     Size[0] = rootSize;
   else
     NewOffset = distribute(Nodes, rootSize, Leaf::Capacity,  nullptr, Size,
                            Position, true);
 
   // Allocate new nodes.
   unsigned Pos = 0;
   NodeRef Node[Nodes];
   for (unsigned n = 0; n != Nodes; ++n) {
     Branch *B = newNode<Branch>();
     B->copy(rootBranch(), Pos, 0, Size[n]);
     Node[n] = NodeRef(B, Size[n]);
     Pos += Size[n];
   }
 
   for (unsigned n = 0; n != Nodes; ++n) {
     rootBranch().stop(n) = Node[n].template get<Branch>().stop(Size[n]-1);
     rootBranch().subtree(n) = Node[n];
   }
   rootSize = Nodes;
   ++height;
   return NewOffset;
 }
 
 /// visitNodes - Visit each external node.
 template <typename KeyT, typename ValT, unsigned N, typename Traits>
 void IntervalMap<KeyT, ValT, N, Traits>::
 visitNodes(void (IntervalMap::*f)(IntervalMapImpl::NodeRef, unsigned Height)) {
   if (!branched())
     return;
   SmallVector<IntervalMapImpl::NodeRef, 4> Refs, NextRefs;
 
   // Collect level 0 nodes from the root.
   for (unsigned i = 0; i != rootSize; ++i)
     Refs.push_back(rootBranch().subtree(i));
 
   // Visit all branch nodes.
   for (unsigned h = height - 1; h; --h) {
     for (unsigned i = 0, e = Refs.size(); i != e; ++i) {
       for (unsigned j = 0, s = Refs[i].size(); j != s; ++j)
         NextRefs.push_back(Refs[i].subtree(j));
       (this->*f)(Refs[i], h);
     }
     Refs.clear();
     Refs.swap(NextRefs);
   }
 
   // Visit all leaf nodes.
   for (unsigned i = 0, e = Refs.size(); i != e; ++i)
     (this->*f)(Refs[i], 0);
 }
 
 template <typename KeyT, typename ValT, unsigned N, typename Traits>
 void IntervalMap<KeyT, ValT, N, Traits>::
 deleteNode(IntervalMapImpl::NodeRef Node, unsigned Level) {
   if (Level)
     deleteNode(&Node.get<Branch>());
   else
     deleteNode(&Node.get<Leaf>());
 }
 
 template <typename KeyT, typename ValT, unsigned N, typename Traits>
 void IntervalMap<KeyT, ValT, N, Traits>::
 clear() {
   if (branched()) {
     visitNodes(&IntervalMap::deleteNode);
     switchRootToLeaf();
   }
   rootSize = 0;
 }
 
 //===----------------------------------------------------------------------===//
 //---                   IntervalMap::const_iterator                       ----//
 //===----------------------------------------------------------------------===//
 
 template <typename KeyT, typename ValT, unsigned N, typename Traits>
 class IntervalMap<KeyT, ValT, N, Traits>::const_iterator {
   friend class IntervalMap;
 
 public:
   using iterator_category = std::bidirectional_iterator_tag;
   using value_type = ValT;
   using difference_type = std::ptrdiff_t;
   using pointer = value_type *;
   using reference = value_type &;
 
 protected:
   // The map referred to.
   IntervalMap *map = nullptr;
 
   // We store a full path from the root to the current position.
   // The path may be partially filled, but never between iterator calls.
   IntervalMapImpl::Path path;
 
   explicit const_iterator(const IntervalMap &map) :
     map(const_cast<IntervalMap*>(&map)) {}
 
   bool branched() const {
     assert(map && "Invalid iterator");
     return map->branched();
   }
 
   void setRoot(unsigned Offset) {
     if (branched())
       path.setRoot(&map->rootBranch(), map->rootSize, Offset);
     else
       path.setRoot(&map->rootLeaf(), map->rootSize, Offset);
   }
 
   void pathFillFind(KeyT x);
   void treeFind(KeyT x);
   void treeAdvanceTo(KeyT x);
 
   /// unsafeStart - Writable access to start() for iterator.
   KeyT &unsafeStart() const {
     assert(valid() && "Cannot access invalid iterator");
     return branched() ? path.leaf<Leaf>().start(path.leafOffset()) :
                         path.leaf<RootLeaf>().start(path.leafOffset());
   }
 
   /// unsafeStop - Writable access to stop() for iterator.
   KeyT &unsafeStop() const {
     assert(valid() && "Cannot access invalid iterator");
     return branched() ? path.leaf<Leaf>().stop(path.leafOffset()) :
                         path.leaf<RootLeaf>().stop(path.leafOffset());
   }
 
   /// unsafeValue - Writable access to value() for iterator.
   ValT &unsafeValue() const {
     assert(valid() && "Cannot access invalid iterator");
     return branched() ? path.leaf<Leaf>().value(path.leafOffset()) :
                         path.leaf<RootLeaf>().value(path.leafOffset());
   }
 
 public:
   /// const_iterator - Create an iterator that isn't pointing anywhere.
   const_iterator() = default;
 
   /// 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(); }
 
   /// stop - Return the end of the current interval.
   const KeyT &stop() const { return unsafeStop(); }
 
   /// value - Return the mapped value at the current interval.
   const ValT &value() const { return unsafeValue(); }
 
   const ValT &operator*() const { return value(); }
 
   bool operator==(const const_iterator &RHS) const {
     assert(map == RHS.map && "Cannot compare iterators from different maps");
     if (!valid())
       return !RHS.valid();
     if (path.leafOffset() != RHS.path.leafOffset())
       return false;
     return &path.template leaf<Leaf>() == &RHS.path.template leaf<Leaf>();
   }
 
   bool operator!=(const const_iterator &RHS) const {
     return !operator==(RHS);
   }
 
   /// goToBegin - Move to the first interval in map.
   void goToBegin() {
     setRoot(0);
     if (branched())
       path.fillLeft(map->height);
   }
 
   /// goToEnd - Move beyond the last interval in map.
   void goToEnd() {
     setRoot(map->rootSize);
   }
 
   /// preincrement - Move to the next interval.
   const_iterator &operator++() {
     assert(valid() && "Cannot increment end()");
     if (++path.leafOffset() == path.leafSize() && branched())
       path.moveRight(map->height);
     return *this;
   }
 
   /// postincrement - Don't do that!
   const_iterator operator++(int) {
     const_iterator tmp = *this;
     operator++();
     return tmp;
   }
 
   /// predecrement - Move to the previous interval.
   const_iterator &operator--() {
     if (path.leafOffset() && (valid() || !branched()))
       --path.leafOffset();
     else
       path.moveLeft(map->height);
     return *this;
   }
 
   /// postdecrement - Don't do that!
   const_iterator operator--(int) {
     const_iterator tmp = *this;
     operator--();
     return tmp;
   }
 
   /// find - Move to the first interval with stop >= x, or end().
   /// This is a full search from the root, the current position is ignored.
   void find(KeyT x) {
     if (branched())
       treeFind(x);
     else
       setRoot(map->rootLeaf().findFrom(0, map->rootSize, x));
   }
 
   /// advanceTo - Move to the first interval with stop >= x, or end().
   /// 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
       path.leafOffset() =
         map->rootLeaf().findFrom(path.leafOffset(), map->rootSize, x);
   }
 };
 
 /// pathFillFind - Complete path by searching for x.
 /// @param x Key to search for.
 template <typename KeyT, typename ValT, unsigned N, typename Traits>
 void IntervalMap<KeyT, ValT, N, Traits>::
 const_iterator::pathFillFind(KeyT x) {
   IntervalMapImpl::NodeRef NR = path.subtree(path.height());
   for (unsigned i = map->height - path.height() - 1; i; --i) {
     unsigned p = NR.get<Branch>().safeFind(0, x);
     path.push(NR, p);
     NR = NR.subtree(p);
   }
   path.push(NR, NR.get<Leaf>().safeFind(0, x));
 }
 
 /// treeFind - Find in a branched tree.
 /// @param x Key to search for.
 template <typename KeyT, typename ValT, unsigned N, typename Traits>
 void IntervalMap<KeyT, ValT, N, Traits>::
 const_iterator::treeFind(KeyT x) {
   setRoot(map->rootBranch().findFrom(0, map->rootSize, x));
   if (valid())
     pathFillFind(x);
 }
 
 /// treeAdvanceTo - Find position after the current one.
 /// @param x Key to search for.
 template <typename KeyT, typename ValT, unsigned N, typename Traits>
 void IntervalMap<KeyT, ValT, N, Traits>::
 const_iterator::treeAdvanceTo(KeyT x) {
   // Can we stay on the same leaf node?
   if (!Traits::stopLess(path.leaf<Leaf>().stop(path.leafSize() - 1), x)) {
     path.leafOffset() = path.leaf<Leaf>().safeFind(path.leafOffset(), x);
     return;
   }
 
   // Drop the current leaf.
   path.pop();
 
   // Search towards the root for a usable subtree.
   if (path.height()) {
     for (unsigned l = path.height() - 1; l; --l) {
       if (!Traits::stopLess(path.node<Branch>(l).stop(path.offset(l)), x)) {
         // The branch node at l+1 is usable
         path.offset(l + 1) =
           path.node<Branch>(l + 1).safeFind(path.offset(l + 1), x);
         return pathFillFind(x);
       }
       path.pop();
     }
     // Is the level-1 Branch usable?
     if (!Traits::stopLess(map->rootBranch().stop(path.offset(0)), x)) {
       path.offset(1) = path.node<Branch>(1).safeFind(path.offset(1), x);
       return pathFillFind(x);
     }
   }
 
   // We reached the root.
   setRoot(map->rootBranch().findFrom(path.offset(0), map->rootSize, x));
   if (valid())
     pathFillFind(x);
 }
 
 //===----------------------------------------------------------------------===//
 //---                       IntervalMap::iterator                         ----//
 //===----------------------------------------------------------------------===//
 
 template <typename KeyT, typename ValT, unsigned N, typename Traits>
 class IntervalMap<KeyT, ValT, N, Traits>::iterator : public const_iterator {
   friend class IntervalMap;
 
   using IdxPair = IntervalMapImpl::IdxPair;
 
   explicit iterator(IntervalMap &map) : const_iterator(map) {}
 
   void setNodeStop(unsigned Level, KeyT Stop);
   bool insertNode(unsigned Level, IntervalMapImpl::NodeRef Node, KeyT Stop);
   template <typename NodeT> bool overflow(unsigned Level);
   void treeInsert(KeyT a, KeyT b, ValT y);
   void eraseNode(unsigned Level);
   void treeErase(bool UpdateRoot = true);
   bool canCoalesceLeft(KeyT Start, ValT x);
   bool canCoalesceRight(KeyT Stop, ValT x);
 
 public:
   /// iterator - Create null iterator.
   iterator() = default;
 
   /// setStart - Move the start of the current interval.
   /// This may cause coalescing with the previous interval.
   /// @param a New start key, must not overlap the previous interval.
   void setStart(KeyT a);
 
   /// setStop - Move the end of the current interval.
   /// This may cause coalescing with the following interval.
   /// @param b New stop key, must not overlap the following interval.
   void setStop(KeyT b);
 
   /// setValue - Change the mapped value of the current interval.
   /// This may cause coalescing with the previous and following intervals.
   /// @param x New value.
   void setValue(ValT x);
 
   /// setStartUnchecked - Move the start of the current interval without
   /// checking for coalescing or overlaps.
   /// This should only be used when it is known that coalescing is not required.
   /// @param a New start key.
   void setStartUnchecked(KeyT a) { this->unsafeStart() = a; }
 
   /// setStopUnchecked - Move the end of the current interval without checking
   /// for coalescing or overlaps.
   /// This should only be used when it is known that coalescing is not required.
   /// @param b New stop key.
   void setStopUnchecked(KeyT b) {
     this->unsafeStop() = b;
     // Update keys in branch nodes as well.
     if (this->path.atLastEntry(this->path.height()))
       setNodeStop(this->path.height(), b);
   }
 
   /// setValueUnchecked - Change the mapped value of the current interval
   /// without checking for coalescing.
   /// @param x New value.
   void setValueUnchecked(ValT x) { this->unsafeValue() = x; }
 
   /// insert - Insert mapping [a;b] -> y before the current position.
   void insert(KeyT a, KeyT b, ValT y);
 
   /// erase - Erase the current interval.
   void erase();
 
   iterator &operator++() {
     const_iterator::operator++();
     return *this;
   }
 
   iterator operator++(int) {
     iterator tmp = *this;
     operator++();
     return tmp;
   }
 
   iterator &operator--() {
     const_iterator::operator--();
     return *this;
   }
 
   iterator operator--(int) {
     iterator tmp = *this;
     operator--();
     return tmp;
   }
 };
 
 /// canCoalesceLeft - Can the current interval coalesce to the left after
 /// changing start or value?
 /// @param Start New start of current interval.
 /// @param Value New value for current interval.
 /// @return True when updating the current interval would enable coalescing.
 template <typename KeyT, typename ValT, unsigned N, typename Traits>
 bool IntervalMap<KeyT, ValT, N, Traits>::
 iterator::canCoalesceLeft(KeyT Start, ValT Value) {
   using namespace IntervalMapImpl;
   Path &P = this->path;
   if (!this->branched()) {
     unsigned i = P.leafOffset();
     RootLeaf &Node = P.leaf<RootLeaf>();
     return i && Node.value(i-1) == Value &&
                 Traits::adjacent(Node.stop(i-1), Start);
   }
   // Branched.
   if (unsigned i = P.leafOffset()) {
     Leaf &Node = P.leaf<Leaf>();
     return Node.value(i-1) == Value && Traits::adjacent(Node.stop(i-1), Start);
   } else if (NodeRef NR = P.getLeftSibling(P.height())) {
     unsigned i = NR.size() - 1;
     Leaf &Node = NR.get<Leaf>();
     return Node.value(i) == Value && Traits::adjacent(Node.stop(i), Start);
   }
   return false;
 }
 
 /// canCoalesceRight - Can the current interval coalesce to the right after
 /// changing stop or value?
 /// @param Stop New stop of current interval.
 /// @param Value New value for current interval.
 /// @return True when updating the current interval would enable coalescing.
 template <typename KeyT, typename ValT, unsigned N, typename Traits>
 bool IntervalMap<KeyT, ValT, N, Traits>::
 iterator::canCoalesceRight(KeyT Stop, ValT Value) {
   using namespace IntervalMapImpl;
   Path &P = this->path;
   unsigned i = P.leafOffset() + 1;
   if (!this->branched()) {
     if (i >= P.leafSize())
       return false;
     RootLeaf &Node = P.leaf<RootLeaf>();
     return Node.value(i) == Value && Traits::adjacent(Stop, Node.start(i));
   }
   // Branched.
   if (i < P.leafSize()) {
     Leaf &Node = P.leaf<Leaf>();
     return Node.value(i) == Value && Traits::adjacent(Stop, Node.start(i));
   } else if (NodeRef NR = P.getRightSibling(P.height())) {
     Leaf &Node = NR.get<Leaf>();
     return Node.value(0) == Value && Traits::adjacent(Stop, Node.start(0));
   }
   return false;
 }
 
 /// setNodeStop - Update the stop key of the current node at level and above.
 template <typename KeyT, typename ValT, unsigned N, typename Traits>
 void IntervalMap<KeyT, ValT, N, Traits>::
 iterator::setNodeStop(unsigned Level, KeyT Stop) {
   // There are no references to the root node, so nothing to update.
   if (!Level)
     return;
   IntervalMapImpl::Path &P = this->path;
   // Update nodes pointing to the current node.
   while (--Level) {
     P.node<Branch>(Level).stop(P.offset(Level)) = Stop;
     if (!P.atLastEntry(Level))
       return;
   }
   // Update root separately since it has a different layout.
   P.node<RootBranch>(Level).stop(P.offset(Level)) = Stop;
 }
 
 template <typename KeyT, typename ValT, unsigned N, typename Traits>
 void IntervalMap<KeyT, ValT, N, Traits>::
 iterator::setStart(KeyT a) {
   assert(Traits::nonEmpty(a, this->stop()) && "Cannot move start beyond stop");
   KeyT &CurStart = this->unsafeStart();
   if (!Traits::startLess(a, CurStart) || !canCoalesceLeft(a, this->value())) {
     CurStart = a;
     return;
   }
   // Coalesce with the interval to the left.
   --*this;
   a = this->start();
   erase();
   setStartUnchecked(a);
 }
 
 template <typename KeyT, typename ValT, unsigned N, typename Traits>
 void IntervalMap<KeyT, ValT, N, Traits>::
 iterator::setStop(KeyT b) {
   assert(Traits::nonEmpty(this->start(), b) && "Cannot move stop beyond start");
   if (Traits::startLess(b, this->stop()) ||
       !canCoalesceRight(b, this->value())) {
     setStopUnchecked(b);
     return;
   }
   // Coalesce with interval to the right.
   KeyT a = this->start();
   erase();
   setStartUnchecked(a);
 }
 
 template <typename KeyT, typename ValT, unsigned N, typename Traits>
 void IntervalMap<KeyT, ValT, N, Traits>::
 iterator::setValue(ValT x) {
   setValueUnchecked(x);
   if (canCoalesceRight(this->stop(), x)) {
     KeyT a = this->start();
     erase();
     setStartUnchecked(a);
   }
   if (canCoalesceLeft(this->start(), x)) {
     --*this;
     KeyT a = this->start();
     erase();
     setStartUnchecked(a);
   }
 }
 
 /// insertNode - insert a node before the current path at level.
 /// Leave the current path pointing at the new node.
 /// @param Level path index of the node to be inserted.
 /// @param Node The node to be inserted.
 /// @param Stop The last index in the new node.
 /// @return True if the tree height was increased.
 template <typename KeyT, typename ValT, unsigned N, typename Traits>
 bool IntervalMap<KeyT, ValT, N, Traits>::
 iterator::insertNode(unsigned Level, IntervalMapImpl::NodeRef Node, KeyT Stop) {
   assert(Level && "Cannot insert next to the root");
   bool SplitRoot = false;
   IntervalMap &IM = *this->map;
   IntervalMapImpl::Path &P = this->path;
 
   if (Level == 1) {
     // Insert into the root branch node.
     if (IM.rootSize < RootBranch::Capacity) {
       IM.rootBranch().insert(P.offset(0), IM.rootSize, Node, Stop);
       P.setSize(0, ++IM.rootSize);
       P.reset(Level);
       return SplitRoot;
     }
 
     // We need to split the root while keeping our position.
     SplitRoot = true;
     IdxPair Offset = IM.splitRoot(P.offset(0));
     P.replaceRoot(&IM.rootBranch(), IM.rootSize, Offset);
 
     // Fall through to insert at the new higher level.
     ++Level;
   }
 
   // When inserting before end(), make sure we have a valid path.
   P.legalizeForInsert(--Level);
 
   // Insert into the branch node at Level-1.
   if (P.size(Level) == Branch::Capacity) {
     // Branch node is full, handle the overflow.
     assert(!SplitRoot && "Cannot overflow after splitting the root");
     SplitRoot = overflow<Branch>(Level);
     Level += SplitRoot;
   }
   P.node<Branch>(Level).insert(P.offset(Level), P.size(Level), Node, Stop);
   P.setSize(Level, P.size(Level) + 1);
   if (P.atLastEntry(Level))
     setNodeStop(Level, Stop);
   P.reset(Level + 1);
   return SplitRoot;
 }
 
 // insert
 template <typename KeyT, typename ValT, unsigned N, typename Traits>
 void IntervalMap<KeyT, ValT, N, Traits>::
 iterator::insert(KeyT a, KeyT b, ValT y) {
   if (this->branched())
     return treeInsert(a, b, y);
   IntervalMap &IM = *this->map;
   IntervalMapImpl::Path &P = this->path;
 
   // Try simple root leaf insert.
   unsigned Size = IM.rootLeaf().insertFrom(P.leafOffset(), IM.rootSize, a, b, y);
 
   // Was the root node insert successful?
   if (Size <= RootLeaf::Capacity) {
     P.setSize(0, IM.rootSize = Size);
     return;
   }
 
   // Root leaf node is full, we must branch.
   IdxPair Offset = IM.branchRoot(P.leafOffset());
   P.replaceRoot(&IM.rootBranch(), IM.rootSize, Offset);
 
   // Now it fits in the new leaf.
   treeInsert(a, b, y);
 }
 
 template <typename KeyT, typename ValT, unsigned N, typename Traits>
 void IntervalMap<KeyT, ValT, N, Traits>::
 iterator::treeInsert(KeyT a, KeyT b, ValT y) {
   using namespace IntervalMapImpl;
   Path &P = this->path;
 
   if (!P.valid())
     P.legalizeForInsert(this->map->height);
 
   // Check if this insertion will extend the node to the left.
   if (P.leafOffset() == 0 && Traits::startLess(a, P.leaf<Leaf>().start(0))) {
     // Node is growing to the left, will it affect a left sibling node?
     if (NodeRef Sib = P.getLeftSibling(P.height())) {
       Leaf &SibLeaf = Sib.get<Leaf>();
       unsigned SibOfs = Sib.size() - 1;
       if (SibLeaf.value(SibOfs) == y &&
           Traits::adjacent(SibLeaf.stop(SibOfs), a)) {
         // This insertion will coalesce with the last entry in SibLeaf. We can
         // handle it in two ways:
         //  1. Extend SibLeaf.stop to b and be done, or
         //  2. Extend a to SibLeaf, erase the SibLeaf entry and continue.
         // We prefer 1., but need 2 when coalescing to the right as well.
         Leaf &CurLeaf = P.leaf<Leaf>();
         P.moveLeft(P.height());
         if (Traits::stopLess(b, CurLeaf.start(0)) &&
             (y != CurLeaf.value(0) || !Traits::adjacent(b, CurLeaf.start(0)))) {
           // Easy, just extend SibLeaf and we're done.
           setNodeStop(P.height(), SibLeaf.stop(SibOfs) = b);
           return;
         } else {
           // We have both left and right coalescing. Erase the old SibLeaf entry
           // and continue inserting the larger interval.
           a = SibLeaf.start(SibOfs);
           treeErase(/* UpdateRoot= */false);
         }
       }
     } else {
       // No left sibling means we are at begin(). Update cached bound.
       this->map->rootBranchStart() = a;
     }
   }
 
   // When we are inserting at the end of a leaf node, we must update stops.
   unsigned Size = P.leafSize();
   bool Grow = P.leafOffset() == Size;
   Size = P.leaf<Leaf>().insertFrom(P.leafOffset(), Size, a, b, y);
 
   // Leaf insertion unsuccessful? Overflow and try again.
   if (Size > Leaf::Capacity) {
     overflow<Leaf>(P.height());
     Grow = P.leafOffset() == P.leafSize();
     Size = P.leaf<Leaf>().insertFrom(P.leafOffset(), P.leafSize(), a, b, y);
     assert(Size <= Leaf::Capacity && "overflow() didn't make room");
   }
 
   // Inserted, update offset and leaf size.
   P.setSize(P.height(), Size);
 
   // Insert was the last node entry, update stops.
   if (Grow)
     setNodeStop(P.height(), b);
 }
 
 /// erase - erase the current interval and move to the next position.
 template <typename KeyT, typename ValT, unsigned N, typename Traits>
 void IntervalMap<KeyT, ValT, N, Traits>::
 iterator::erase() {
   IntervalMap &IM = *this->map;
   IntervalMapImpl::Path &P = this->path;
   assert(P.valid() && "Cannot erase end()");
   if (this->branched())
     return treeErase();
   IM.rootLeaf().erase(P.leafOffset(), IM.rootSize);
   P.setSize(0, --IM.rootSize);
 }
 
 /// treeErase - erase() for a branched tree.
 template <typename KeyT, typename ValT, unsigned N, typename Traits>
 void IntervalMap<KeyT, ValT, N, Traits>::
 iterator::treeErase(bool UpdateRoot) {
   IntervalMap &IM = *this->map;
   IntervalMapImpl::Path &P = this->path;
   Leaf &Node = P.leaf<Leaf>();
 
   // Nodes are not allowed to become empty.
   if (P.leafSize() == 1) {
     IM.deleteNode(&Node);
     eraseNode(IM.height);
     // Update rootBranchStart if we erased begin().
     if (UpdateRoot && IM.branched() && P.valid() && P.atBegin())
       IM.rootBranchStart() = P.leaf<Leaf>().start(0);
     return;
   }
 
   // Erase current entry.
   Node.erase(P.leafOffset(), P.leafSize());
   unsigned NewSize = P.leafSize() - 1;
   P.setSize(IM.height, NewSize);
   // When we erase the last entry, update stop and move to a legal position.
   if (P.leafOffset() == NewSize) {
     setNodeStop(IM.height, Node.stop(NewSize - 1));
     P.moveRight(IM.height);
   } else if (UpdateRoot && P.atBegin())
     IM.rootBranchStart() = P.leaf<Leaf>().start(0);
 }
 
 /// eraseNode - Erase the current node at Level from its parent and move path to
 /// the first entry of the next sibling node.
 /// The node must be deallocated by the caller.
 /// @param Level 1..height, the root node cannot be erased.
 template <typename KeyT, typename ValT, unsigned N, typename Traits>
 void IntervalMap<KeyT, ValT, N, Traits>::
 iterator::eraseNode(unsigned Level) {
   assert(Level && "Cannot erase root node");
   IntervalMap &IM = *this->map;
   IntervalMapImpl::Path &P = this->path;
 
   if (--Level == 0) {
     IM.rootBranch().erase(P.offset(0), IM.rootSize);
     P.setSize(0, --IM.rootSize);
     // If this cleared the root, switch to height=0.
     if (IM.empty()) {
       IM.switchRootToLeaf();
       this->setRoot(0);
       return;
     }
   } else {
     // Remove node ref from branch node at Level.
     Branch &Parent = P.node<Branch>(Level);
     if (P.size(Level) == 1) {
       // Branch node became empty, remove it recursively.
       IM.deleteNode(&Parent);
       eraseNode(Level);
     } else {
       // Branch node won't become empty.
       Parent.erase(P.offset(Level), P.size(Level));
       unsigned NewSize = P.size(Level) - 1;
       P.setSize(Level, NewSize);
       // If we removed the last branch, update stop and move to a legal pos.
       if (P.offset(Level) == NewSize) {
         setNodeStop(Level, Parent.stop(NewSize - 1));
         P.moveRight(Level);
       }
     }
   }
   // Update path cache for the new right sibling position.
   if (P.valid()) {
     P.reset(Level + 1);
     P.offset(Level + 1) = 0;
   }
 }
 
 /// overflow - Distribute entries of the current node evenly among
 /// its siblings and ensure that the current node is not full.
 /// This may require allocating a new node.
 /// @tparam NodeT The type of node at Level (Leaf or Branch).
 /// @param Level path index of the overflowing node.
 /// @return True when the tree height was changed.
 template <typename KeyT, typename ValT, unsigned N, typename Traits>
 template <typename NodeT>
 bool IntervalMap<KeyT, ValT, N, Traits>::
 iterator::overflow(unsigned Level) {
   using namespace IntervalMapImpl;
   Path &P = this->path;
   unsigned CurSize[4];
   NodeT *Node[4];
   unsigned Nodes = 0;
   unsigned Elements = 0;
   unsigned Offset = P.offset(Level);
 
   // Do we have a left sibling?
   NodeRef LeftSib = P.getLeftSibling(Level);
   if (LeftSib) {
     Offset += Elements = CurSize[Nodes] = LeftSib.size();
     Node[Nodes++] = &LeftSib.get<NodeT>();
   }
 
   // Current node.
   Elements += CurSize[Nodes] = P.size(Level);
   Node[Nodes++] = &P.node<NodeT>(Level);
 
   // Do we have a right sibling?
   NodeRef RightSib = P.getRightSibling(Level);
   if (RightSib) {
     Elements += CurSize[Nodes] = RightSib.size();
     Node[Nodes++] = &RightSib.get<NodeT>();
   }
 
   // Do we need to allocate a new node?
   unsigned NewNode = 0;
   if (Elements + 1 > Nodes * NodeT::Capacity) {
     // Insert NewNode at the penultimate position, or after a single node.
     NewNode = Nodes == 1 ? 1 : Nodes - 1;
     CurSize[Nodes] = CurSize[NewNode];
     Node[Nodes] = Node[NewNode];
     CurSize[NewNode] = 0;
     Node[NewNode] = this->map->template newNode<NodeT>();
     ++Nodes;
   }
 
   // Compute the new element distribution.
   unsigned NewSize[4];
   IdxPair NewOffset = distribute(Nodes, Elements, NodeT::Capacity,
                                  CurSize, NewSize, Offset, true);
   adjustSiblingSizes(Node, Nodes, CurSize, NewSize);
 
   // Move current location to the leftmost node.
   if (LeftSib)
     P.moveLeft(Level);
 
   // Elements have been rearranged, now update node sizes and stops.
   bool SplitRoot = false;
   unsigned Pos = 0;
   while (true) {
     KeyT Stop = Node[Pos]->stop(NewSize[Pos]-1);
     if (NewNode && Pos == NewNode) {
       SplitRoot = insertNode(Level, NodeRef(Node[Pos], NewSize[Pos]), Stop);
       Level += SplitRoot;
     } else {
       P.setSize(Level, NewSize[Pos]);
       setNodeStop(Level, Stop);
     }
     if (Pos + 1 == Nodes)
       break;
     P.moveRight(Level);
     ++Pos;
   }
 
   // Where was I? Find NewOffset.
   while(Pos != NewOffset.first) {
     P.moveLeft(Level);
     --Pos;
   }
   P.offset(Level) = NewOffset.second;
   return SplitRoot;
 }
 
 //===----------------------------------------------------------------------===//
 //---                       IntervalMapOverlaps                           ----//
 //===----------------------------------------------------------------------===//
 
 /// IntervalMapOverlaps - Iterate over the overlaps of mapped intervals in two
 /// IntervalMaps. The maps may be different, but the KeyT and Traits types
 /// should be the same.
 ///
 /// Typical uses:
 ///
 /// 1. Test for overlap:
 ///    bool overlap = IntervalMapOverlaps(a, b).valid();
 ///
 /// 2. Enumerate overlaps:
 ///    for (IntervalMapOverlaps I(a, b); I.valid() ; ++I) { ... }
 ///
 template <typename MapA, typename MapB>
 class IntervalMapOverlaps {
   using KeyType = typename MapA::KeyType;
   using Traits = typename MapA::KeyTraits;
 
   typename MapA::const_iterator posA;
   typename MapB::const_iterator posB;
 
   /// advance - Move posA and posB forward until reaching an overlap, or until
   /// 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;
 
     while (true) {
       // Make a.end > b.start.
       posA.advanceTo(posB.start());
       if (!posA.valid() || !Traits::stopLess(posB.stop(), posA.start()))
         return;
       // Make b.end > a.start.
       posB.advanceTo(posA.start());
       if (!posB.valid() || !Traits::stopLess(posA.stop(), posB.start()))
         return;
     }
   }
 
 public:
   /// 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()) { advance(); }
 
   /// valid - Return true if iterator is at an overlap.
   bool valid() const {
     return posA.valid() && posB.valid();
   }
 
   /// a - access the left hand side in the overlap.
   const typename MapA::const_iterator &a() const { return posA; }
 
   /// 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;
     advance();
   }
 
   /// skipB - Move to the next overlap that doesn't involve b().
   void skipB() {
     ++posB;
     advance();
   }
 
   /// Preincrement - Move to the next overlap.
   IntervalMapOverlaps &operator++() {
     // Bump the iterator that ends first. The other one may have more overlaps.
     if (Traits::startLess(posB.stop(), posA.stop()))
       skipB();
     else
       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();
   }
 };
 
 } // end namespace llvm
 
 #endif // LLVM_ADT_INTERVALMAP_H

This page was automatically generated by the 2.3.7 LXR engine. The LXR team