Method FindLowerBoundImpl

svf/include/Util/SparseBitVector.h:518–562

This is like std::lower_bound, except we do linear searching from the current position.

    // This is like std::lower_bound, except we do linear searching from the
    // current position.
    ElementListIter FindLowerBoundImpl(unsigned ElementIndex) const
    {

        // We cache a non-const iterator so we're forced to resort to const_cast to
        // get the begin/end in the case where 'this' is const. To avoid duplication
        // of code with the only difference being whether the const cast is present
        // 'this' is always const in this particular function and we sort out the
        // difference in FindLowerBound and FindLowerBoundConst.
        ElementListIter Begin =
            const_cast<SparseBitVector<ElementSize> *>(this)->Elements.begin();
        ElementListIter End =
            const_cast<SparseBitVector<ElementSize> *>(this)->Elements.end();

        if (Elements.empty())
        {
            CurrElementIter = Begin;
            return CurrElementIter;
        }

        // Make sure our current iterator is valid.
        if (CurrElementIter == End)
            --CurrElementIter;

        // Search from our current iterator, either backwards or forwards,
        // depending on what element we are looking for.
        ElementListIter ElementIter = CurrElementIter;
        if (CurrElementIter->index() == ElementIndex)
        {
            return ElementIter;
        }
        else if (CurrElementIter->index() > ElementIndex)
        {
            while (ElementIter != Begin
                    && ElementIter->index() > ElementIndex)
                --ElementIter;
        }
        else
        {
            while (ElementIter != End &&
                    ElementIter->index() < ElementIndex)
                ++ElementIter;
        }
        CurrElementIter = ElementIter;
        return ElementIter;
    }
    ElementListConstIter FindLowerBoundConst(unsigned ElementIndex) const
    {
        return FindLowerBoundImpl(ElementIndex);