29 /// stop() iterator methods.
52 //   KeyT stop() const;
80 //   const KeyT &stop() const;
556 // - Traits::stopLess(start(i), stop(i))    - Non-empty, sane intervals.
558 // - Traits::stopLess(stop(i), start(i + 1) - Sorted.
560 // - value(i) != value(i + 1) || !Traits::adjacent(stop(i), start(i + 1))
569   const KeyT &stop(unsigned i) const { return this->first[i].second; }  in stop()  function
573   KeyT &stop(unsigned i) { return this->first[i].second; }  in stop()  function
580   /// @return     First index with !stopLess(key[i].stop, x), or size.
584     assert((i == 0 || Traits::stopLess(stop(i - 1), x)) &&  in findFrom()
586     while (i != Size && Traits::stopLess(stop(i), x)) ++i;  in findFrom()
595   /// @return  First index with !stopLess(key[i].stop, x), never size.
599     assert((i == 0 || Traits::stopLess(stop(i - 1), x)) &&  in safeFind()
601     while (Traits::stopLess(stop(i), x)) ++i;  in safeFind()
625 /// @param b    Interval stop.
636   assert((i == 0 || Traits::stopLess(stop(i - 1), a)));  in insertFrom()
637   assert((i == Size || !Traits::stopLess(stop(i), a)));  in insertFrom()
641   if (i && value(i - 1) == y && Traits::adjacent(stop(i - 1), a)) {  in insertFrom()
645       stop(i - 1) = stop(i);  in insertFrom()
649     stop(i - 1) = b;  in insertFrom()
660     stop(i) = b;  in insertFrom()
678   stop(i) = b;  in insertFrom()
689 // The key array in a branch node holds the rightmost stop key of each subtree.
690 // It is redundant to store the last stop key since it can be found in the
705   const KeyT &stop(unsigned i) const { return this->second[i]; }  in stop()  function
708   KeyT &stop(unsigned i) { return this->second[i]; }  in stop()  function
719     assert((i == 0 || Traits::stopLess(stop(i - 1), x)) &&  in findFrom()
721     while (i != Size && Traits::stopLess(stop(i), x)) ++i;  in findFrom()
733     assert((i == 0 || Traits::stopLess(stop(i - 1), x)) &&  in safeFind()
735     while (Traits::stopLess(stop(i), x)) ++i;  in safeFind()
747   /// insert - Insert a new (subtree, stop) pair.
751   /// @param Stop Last key in subtree.
752   void insert(unsigned i, unsigned Size, NodeRef Node, KeyT Stop) {  in insert()  argument
757     stop(i) = Stop;  in insert()
1059       insert(It.start(), It.stop(), It.value());
1111   /// stop - Return the largest mapped key in a non-empty map.
1112   KeyT stop() const {  in stop()  function
1113     assert(!empty() && "Empty IntervalMap has no stop");  in stop()
1114     return !branched() ? rootLeaf().stop(rootSize - 1) :  in stop()
1115                          rootBranch().stop(rootSize - 1);  in stop()
1120     if (empty() || Traits::startLess(x, start()) || Traits::stopLess(stop(), x))
1192     // second part (y = find(a).stop()), so it is sufficient to check the first  in overlaps()
1244     rootBranch().stop(n) = node[n].template get<Leaf>().stop(size[n]-1);  in branchRoot()
1283     rootBranch().stop(n) = Node[n].template get<Branch>().stop(Size[n]-1);  in splitRoot()
1387   /// unsafeStop - Writable access to stop() for iterator.
1390     return branched() ? path.leaf<Leaf>().stop(path.leafOffset()) :  in unsafeStop()
1391                         path.leaf<RootLeaf>().stop(path.leafOffset());  in unsafeStop()
1418   /// stop - Return the end of the current interval.
1419   const KeyT &stop() const { return unsafeStop(); }  in stop()  function
1482   /// find - Move to the first interval with stop >= x, or end().
1491   /// advanceTo - Move to the first interval with stop >= x, or end().
1535   if (!Traits::stopLess(path.leaf<Leaf>().stop(path.leafSize() - 1), x)) {  in treeAdvanceTo()
1546       if (!Traits::stopLess(path.node<Branch>(l).stop(path.offset(l)), x)) {  in treeAdvanceTo()
1555     if (!Traits::stopLess(map->rootBranch().stop(path.offset(0)), x)) {  in treeAdvanceTo()
1579   void setNodeStop(unsigned Level, KeyT Stop);
1580   bool insertNode(unsigned Level, IntervalMapImpl::NodeRef Node, KeyT Stop);
1586   bool canCoalesceRight(KeyT Stop, ValT x);
1599   /// @param b New stop key, must not overlap the following interval.
1616   /// @param b New stop key.
1672                 Traits::adjacent(Node.stop(i-1), Start);  in canCoalesceLeft()
1677     return Node.value(i-1) == Value && Traits::adjacent(Node.stop(i-1), Start);  in canCoalesceLeft()
1681     return Node.value(i) == Value && Traits::adjacent(Node.stop(i), Start);  in canCoalesceLeft()
1687 /// changing stop or value?
1688 /// @param Stop New stop of current interval.
1693 iterator::canCoalesceRight(KeyT Stop, ValT Value) {  in canCoalesceRight()  argument
1701     return Node.value(i) == Value && Traits::adjacent(Stop, Node.start(i));  in canCoalesceRight()
1706     return Node.value(i) == Value && Traits::adjacent(Stop, Node.start(i));  in canCoalesceRight()
1709     return Node.value(0) == Value && Traits::adjacent(Stop, Node.start(0));  in canCoalesceRight()
1714 /// setNodeStop - Update the stop key of the current node at level and above.
1717 iterator::setNodeStop(unsigned Level, KeyT Stop) {  in setNodeStop()  argument
1724     P.node<Branch>(Level).stop(P.offset(Level)) = Stop;  in setNodeStop()
1729   P.node<RootBranch>(Level).stop(P.offset(Level)) = Stop;  in setNodeStop()
1735   assert(Traits::nonEmpty(a, this->stop()) && "Cannot move start beyond stop");  in setStart()
1751   assert(Traits::nonEmpty(this->start(), b) && "Cannot move stop beyond start");  in setStop()
1752   if (Traits::startLess(b, this->stop()) ||  in setStop()
1767   if (canCoalesceRight(this->stop(), x)) {  in setValue()
1784 /// @param Stop The last index in the new node.
1788 iterator::insertNode(unsigned Level, IntervalMapImpl::NodeRef Node, KeyT Stop) {  in insertNode()  argument
1797       IM.rootBranch().insert(P.offset(0), IM.rootSize, Node, Stop);  in insertNode()
1822   P.node<Branch>(Level).insert(P.offset(Level), P.size(Level), Node, Stop);  in insertNode()
1825     setNodeStop(Level, Stop);  in insertNode()
1872           Traits::adjacent(SibLeaf.stop(SibOfs), a)) {  in treeInsert()
1875         //  1. Extend SibLeaf.stop to b and be done, or  in treeInsert()
1883           setNodeStop(P.height(), SibLeaf.stop(SibOfs) = b);  in treeInsert()
1954   // When we erase the last entry, update stop and move to a legal position.  in treeErase()
1956     setNodeStop(IM.height, Node.stop(NewSize - 1));  in treeErase()
1994       // If we removed the last branch, update stop and move to a legal pos.  in eraseNode()
1996         setNodeStop(Level, Parent.stop(NewSize - 1));  in eraseNode()
2070     KeyT Stop = Node[Pos]->stop(NewSize[Pos]-1);  in overflow()  local
2072       SplitRoot = insertNode(Level, NodeRef(Node[Pos], NewSize[Pos]), Stop);  in overflow()
2076       setNodeStop(Level, Stop);  in overflow()
2124     if (Traits::stopLess(posA.stop(), posB.start())) {  in advance()
2127       if (!posA.valid() || !Traits::stopLess(posB.stop(), posA.start()))  in advance()
2129     } else if (Traits::stopLess(posB.stop(), posA.start())) {  in advance()
2132       if (!posB.valid() || !Traits::stopLess(posA.stop(), posB.start()))  in advance()
2141       if (!posA.valid() || !Traits::stopLess(posB.stop(), posA.start()))  in advance()
2145       if (!posB.valid() || !Traits::stopLess(posA.stop(), posB.start()))  in advance()
2174   /// stop - End of the overlapping interval.
2175   KeyType stop() const {  in stop()  function
2176     KeyType ak = a().stop();  in stop()
2177     KeyType bk = b().stop();  in stop()
2196     if (Traits::startLess(posB.stop(), posA.stop()))
2204   /// stopLess(x, stop()).
2209     if (Traits::stopLess(posA.stop(), x))  in advanceTo()
2211     if (Traits::stopLess(posB.stop(), x))  in advanceTo()