Method lowerBound

kdevplatform/util/embeddedfreetree.h:143–173

Returns the first valid index that has a data-value larger or equal to @p data. Returns -1 if nothing is found.

    ///Returns the first valid index that has a data-value larger or equal to @p data.
    ///Returns -1 if nothing is found.
    int lowerBound(const Data& data, int start, int end)
    {
        int currentBound = -1;
        while (1) {
            if (start >= end)
                return currentBound;

            int center = (start + end) / 2;

            //Skip free items, since they cannot be used for ordering
            for (; center < end;) {
                if (!ItemHandler::isFree(m_items[center]))
                    break;
                ++center;
            }

            if (center == end) {
                end = (start + end) / 2;       //No non-free items found in second half, so continue search in the other
            } else {
                if (ItemHandler::equals(data, m_items[center])) {
                    return center;
                } else if (data < m_items[center]) {
                    currentBound = center;
                    end = (start + end) / 2;
                } else {
                    //Continue search in second half
                    start = center + 1;
                }
            }
        }
    }

    uint countFreeItems() const
    {