Cross Reference: /external/llvm/include/llvm/ADT/IntervalMap.h

Lines Matching refs:Traits
23 // A Traits class specifies how keys are compared. It also allows IntervalMap to
38 // template <typename KeyT, typename ValT, unsigned N, typename Traits>
66 // template <typename KeyT, typename ValT, unsigned N, typename Traits>
90 // template <typename KeyT, typename ValT, unsigned N, typename Traits>
549 // - Traits::stopLess(start(i), stop(i))    - Non-empty, sane intervals.
551 // - Traits::stopLess(stop(i), start(i + 1) - Sorted.
553 // - value(i) != value(i + 1) || !Traits::adjacent(stop(i), start(i + 1))
558 template <typename KeyT, typename ValT, unsigned N, typename Traits>
577     assert((i == 0 || Traits::stopLess(stop(i - 1), x)) &&
579     while (i != Size && Traits::stopLess(stop(i), x)) ++i;
592     assert((i == 0 || Traits::stopLess(stop(i - 1), x)) &&
594     while (Traits::stopLess(stop(i), x)) ++i;
606     return Traits::startLess(x, start(i)) ? NotFound : value(i);
621 template <typename KeyT, typename ValT, unsigned N, typename Traits>
622 unsigned LeafNode<KeyT, ValT, N, Traits>::
626   assert(!Traits::stopLess(b, a) && "Invalid interval");
629   assert((i == 0 || Traits::stopLess(stop(i - 1), a)));
630   assert((i == Size || !Traits::stopLess(stop(i), a)));
631   assert((i == Size || Traits::stopLess(b, start(i))) && "Overlapping insert");
634   if (i && value(i - 1) == y && Traits::adjacent(stop(i - 1), a)) {
637     if (i != Size && value(i) == y && Traits::adjacent(b, start(i))) {
659   if (value(i) == y && Traits::adjacent(b, start(i))) {
696 template <typename KeyT, typename ValT, unsigned N, typename Traits>
713     assert((i == 0 || Traits::stopLess(stop(i - 1), x)) &&
715     while (i != Size && Traits::stopLess(stop(i), x)) ++i;
727     assert((i == 0 || Traits::stopLess(stop(i - 1), x)) &&
729     while (Traits::stopLess(stop(i), x)) ++i;
930           typename Traits = IntervalMapInfo<KeyT> >
933   typedef IntervalMapImpl::LeafNode<KeyT, ValT, Sizer::LeafSize, Traits> Leaf;
934   typedef IntervalMapImpl::BranchNode<KeyT, ValT, Sizer::BranchSize, Traits>
936   typedef IntervalMapImpl::LeafNode<KeyT, ValT, N, Traits> RootLeaf;
947   typedef IntervalMapImpl::BranchNode<KeyT, ValT, RootBranchCap, Traits>
965   typedef Traits KeyTraits;
1084     if (empty() || Traits::startLess(x, start()) || Traits::stopLess(stop(), x))
1151 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1152 ValT IntervalMap<KeyT, ValT, N, Traits>::
1165 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1166 IntervalMapImpl::IdxPair IntervalMap<KeyT, ValT, N, Traits>::
1206 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1207 IntervalMapImpl::IdxPair IntervalMap<KeyT, ValT, N, Traits>::
1244 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1245 void IntervalMap<KeyT, ValT, N, Traits>::
1271 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1272 void IntervalMap<KeyT, ValT, N, Traits>::
1280 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1281 void IntervalMap<KeyT, ValT, N, Traits>::
1294 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1295 class IntervalMap<KeyT, ValT, N, Traits>::const_iterator :
1454 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1455 void IntervalMap<KeyT, ValT, N, Traits>::
1468 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1469 void IntervalMap<KeyT, ValT, N, Traits>::
1478 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1479 void IntervalMap<KeyT, ValT, N, Traits>::
1482   if (!Traits::stopLess(path.leaf<Leaf>().stop(path.leafSize() - 1), x)) {
1493       if (!Traits::stopLess(path.node<Branch>(l).stop(path.offset(l)), x)) {
1502     if (!Traits::stopLess(map->rootBranch().stop(path.offset(0)), x)) {
1518 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1519 class IntervalMap<KeyT, ValT, N, Traits>::iterator : public const_iterator {
1610 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1611 bool IntervalMap<KeyT, ValT, N, Traits>::
1619                 Traits::adjacent(Node.stop(i-1), Start);
1624     return Node.value(i-1) == Value && Traits::adjacent(Node.stop(i-1), Start);
1628     return Node.value(i) == Value && Traits::adjacent(Node.stop(i), Start);
1638 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1639 bool IntervalMap<KeyT, ValT, N, Traits>::
1648     return Node.value(i) == Value && Traits::adjacent(Stop, Node.start(i));
1653     return Node.value(i) == Value && Traits::adjacent(Stop, Node.start(i));
1656     return Node.value(0) == Value && Traits::adjacent(Stop, Node.start(0));
1662 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1663 void IntervalMap<KeyT, ValT, N, Traits>::
1679 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1680 void IntervalMap<KeyT, ValT, N, Traits>::
1682   assert(Traits::stopLess(a, this->stop()) && "Cannot move start beyond stop");
1684   if (!Traits::startLess(a, CurStart) || !canCoalesceLeft(a, this->value())) {
1695 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1696 void IntervalMap<KeyT, ValT, N, Traits>::
1698   assert(Traits::stopLess(this->start(), b) && "Cannot move stop beyond start");
1699   if (Traits::startLess(b, this->stop()) ||
1710 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1711 void IntervalMap<KeyT, ValT, N, Traits>::
1733 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1734 bool IntervalMap<KeyT, ValT, N, Traits>::
1778 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1779 void IntervalMap<KeyT, ValT, N, Traits>::
1804 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1805 void IntervalMap<KeyT, ValT, N, Traits>::
1814   if (P.leafOffset() == 0 && Traits::startLess(a, P.leaf<Leaf>().start(0))) {
1820           Traits::adjacent(SibLeaf.stop(SibOfs), a)) {
1828         if (Traits::stopLess(b, CurLeaf.start(0)) &&
1829             (y != CurLeaf.value(0) || !Traits::adjacent(b, CurLeaf.start(0)))) {
1868 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1869 void IntervalMap<KeyT, ValT, N, Traits>::
1881 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1882 void IntervalMap<KeyT, ValT, N, Traits>::
1914 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1915 void IntervalMap<KeyT, ValT, N, Traits>::
1962 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1964 bool IntervalMap<KeyT, ValT, N, Traits>::
2046 /// IntervalMaps. The maps may be different, but the KeyT and Traits types
2060   typedef typename MapA::KeyTraits Traits;
2071     if (Traits::stopLess(posA.stop(), posB.start())) {
2074       if (!posA.valid() || !Traits::stopLess(posB.stop(), posA.start()))
2076     } else if (Traits::stopLess(posB.stop(), posA.start())) {
2079       if (!posB.valid() || !Traits::stopLess(posA.stop(), posB.start()))
2088       if (!posA.valid() || !Traits::stopLess(posB.stop(), posA.start()))
2092       if (!posB.valid() || !Traits::stopLess(posA.stop(), posB.start()))
2118     return Traits::startLess(ak, bk) ? bk : ak;
2125     return Traits::startLess(ak, bk) ? ak : bk;
2143     if (Traits::startLess(posB.stop(), posA.stop()))
2156     if (Traits::stopLess(posA.stop(), x))
2158     if (Traits::stopLess(posB.stop(), x))