Lines Matching refs:stop
28 // value. The interval bounds are accessible through the start() and stop()
52 // KeyT stop() const;
75 // const KeyT &stop() const;
552 // - Traits::stopLess(start(i), stop(i)) - Non-empty, sane intervals.
554 // - Traits::stopLess(stop(i), start(i + 1) - Sorted.
556 // - value(i) != value(i + 1) || !Traits::adjacent(stop(i), start(i + 1))
565 const KeyT &stop(unsigned i) const { return this->first[i].second; }
569 KeyT &stop(unsigned i) { return this->first[i].second; }
576 /// @return First index with !stopLess(key[i].stop, x), or size.
580 assert((i == 0 || Traits::stopLess(stop(i - 1), x)) &&
582 while (i != Size && Traits::stopLess(stop(i), x)) ++i;
591 /// @return First index with !stopLess(key[i].stop, x), never size.
595 assert((i == 0 || Traits::stopLess(stop(i - 1), x)) &&
597 while (Traits::stopLess(stop(i), x)) ++i;
621 /// @param b Interval stop.
632 assert((i == 0 || Traits::stopLess(stop(i - 1), a)));
633 assert((i == Size || !Traits::stopLess(stop(i), a)));
637 if (i && value(i - 1) == y && Traits::adjacent(stop(i - 1), a)) {
641 stop(i - 1) = stop(i);
645 stop(i - 1) = b;
656 stop(i) = b;
674 stop(i) = b;
685 // The key array in a branch node holds the rightmost stop key of each subtree.
686 // It is redundant to store the last stop key since it can be found in the
701 const KeyT &stop(unsigned i) const { return this->second[i]; }
704 KeyT &stop(unsigned i) { return this->second[i]; }
715 assert((i == 0 || Traits::stopLess(stop(i - 1), x)) &&
717 while (i != Size && Traits::stopLess(stop(i), x)) ++i;
729 assert((i == 0 || Traits::stopLess(stop(i - 1), x)) &&
731 while (Traits::stopLess(stop(i), x)) ++i;
743 /// insert - Insert a new (subtree, stop) pair.
747 /// @param Stop Last key in subtree.
748 void insert(unsigned i, unsigned Size, NodeRef Node, KeyT Stop) {
753 stop(i) = Stop;
1067 /// stop - Return the largest mapped key in a non-empty map.
1068 KeyT stop() const {
1069 assert(!empty() && "Empty IntervalMap has no stop");
1070 return !branched() ? rootLeaf().stop(rootSize - 1) :
1071 rootBranch().stop(rootSize - 1);
1076 if (empty() || Traits::startLess(x, start()) || Traits::stopLess(stop(), x))
1187 rootBranch().stop(n) = node[n].template get<Leaf>().stop(size[n]-1);
1226 rootBranch().stop(n) = Node[n].template get<Branch>().stop(Size[n]-1);
1325 /// unsafeStop - Writable access to stop() for iterator.
1328 return branched() ? path.leaf<Leaf>().stop(path.leafOffset()) :
1329 path.leaf<RootLeaf>().stop(path.leafOffset());
1356 /// stop - Return the end of the current interval.
1357 const KeyT &stop() const { return unsafeStop(); }
1420 /// find - Move to the first interval with stop >= x, or end().
1429 /// advanceTo - Move to the first interval with stop >= x, or end().
1473 if (!Traits::stopLess(path.leaf<Leaf>().stop(path.leafSize() - 1), x)) {
1484 if (!Traits::stopLess(path.node<Branch>(l).stop(path.offset(l)), x)) {
1493 if (!Traits::stopLess(map->rootBranch().stop(path.offset(0)), x)) {
1516 void setNodeStop(unsigned Level, KeyT Stop);
1517 bool insertNode(unsigned Level, IntervalMapImpl::NodeRef Node, KeyT Stop);
1523 bool canCoalesceRight(KeyT Stop, ValT x);
1536 /// @param b New stop key, must not overlap the following interval.
1553 /// @param b New stop key.
1609 Traits::adjacent(Node.stop(i-1), Start);
1614 return Node.value(i-1) == Value && Traits::adjacent(Node.stop(i-1), Start);
1618 return Node.value(i) == Value && Traits::adjacent(Node.stop(i), Start);
1624 /// changing stop or value?
1625 /// @param Stop New stop of current interval.
1630 iterator::canCoalesceRight(KeyT Stop, ValT Value) {
1638 return Node.value(i) == Value && Traits::adjacent(Stop, Node.start(i));
1643 return Node.value(i) == Value && Traits::adjacent(Stop, Node.start(i));
1646 return Node.value(0) == Value && Traits::adjacent(Stop, Node.start(0));
1651 /// setNodeStop - Update the stop key of the current node at level and above.
1654 iterator::setNodeStop(unsigned Level, KeyT Stop) {
1661 P.node<Branch>(Level).stop(P.offset(Level)) = Stop;
1666 P.node<RootBranch>(Level).stop(P.offset(Level)) = Stop;
1672 assert(Traits::nonEmpty(a, this->stop()) && "Cannot move start beyond stop");
1688 assert(Traits::nonEmpty(this->start(), b) && "Cannot move stop beyond start");
1689 if (Traits::startLess(b, this->stop()) ||
1704 if (canCoalesceRight(this->stop(), x)) {
1721 /// @param Stop The last index in the new node.
1725 iterator::insertNode(unsigned Level, IntervalMapImpl::NodeRef Node, KeyT Stop) {
1734 IM.rootBranch().insert(P.offset(0), IM.rootSize, Node, Stop);
1759 P.node<Branch>(Level).insert(P.offset(Level), P.size(Level), Node, Stop);
1762 setNodeStop(Level, Stop);
1809 Traits::adjacent(SibLeaf.stop(SibOfs), a)) {
1812 // 1. Extend SibLeaf.stop to b and be done, or
1820 setNodeStop(P.height(), SibLeaf.stop(SibOfs) = b);
1891 // When we erase the last entry, update stop and move to a legal position.
1893 setNodeStop(IM.height, Node.stop(NewSize - 1));
1931 // If we removed the last branch, update stop and move to a legal pos.
1933 setNodeStop(Level, Parent.stop(NewSize - 1));
2007 KeyT Stop = Node[Pos]->stop(NewSize[Pos]-1);
2009 SplitRoot = insertNode(Level, NodeRef(Node[Pos], NewSize[Pos]), Stop);
2013 setNodeStop(Level, Stop);
2060 if (Traits::stopLess(posA.stop(), posB.start())) {
2063 if (!posA.valid() || !Traits::stopLess(posB.stop(), posA.start()))
2065 } else if (Traits::stopLess(posB.stop(), posA.start())) {
2068 if (!posB.valid() || !Traits::stopLess(posA.stop(), posB.start()))
2077 if (!posA.valid() || !Traits::stopLess(posB.stop(), posA.start()))
2081 if (!posB.valid() || !Traits::stopLess(posA.stop(), posB.start()))
2110 /// stop - End of the overlapping interval.
2111 KeyType stop() const {
2112 KeyType ak = a().stop();
2113 KeyType bk = b().stop();
2132 if (Traits::startLess(posB.stop(), posA.stop()))
2140 /// stopLess(x, stop()).
2145 if (Traits::stopLess(posA.stop(), x))
2147 if (Traits::stopLess(posB.stop(), x))
