class Tokenizer
{
public:
                Tokenizer();
                Tokenizer(const Tokenizer& other);
                ~Tokenizer();    uint32_t    acquire();
    status_t    reserve(uint32_t token);
    status_t    release(uint32_t token);
    bool        isAcquired(uint32_t token) const;    void dump() const;    struct run_t {
        run_t() {};
        run_t(uint32_t f, uint32_t l) : first(f), length(l) {}
        uint32_t    first;
        uint32_t    length;
    };
private:
    ssize_t _indexOrderOf(uint32_t token, size_t* order=0) const;
    ssize_t _insertTokenAt(uint32_t token, size_t index);
    Vector<run_t>   mRanges;
};}; // namespace android
Tokenizer::Tokenizer()
{
}Tokenizer::Tokenizer(const Tokenizer& other)
    : mRanges(other.mRanges)
{
}Tokenizer::~Tokenizer()
{
}uint32_t Tokenizer::acquire()
{
    if (!mRanges.size() || mRanges[0].first) {
        _insertTokenAt(0,0);
        return 0;
    }
    
    // just extend the first run
    const run_t& run = mRanges[0];
    uint32_t token = run.first + run.length;
    _insertTokenAt(token, 1);
    return token;
}bool Tokenizer::isAcquired(uint32_t token) const
{
    return (_indexOrderOf(token) >= 0);
}status_t Tokenizer::reserve(uint32_t token)
{
    size_t o;
    const ssize_t i = _indexOrderOf(token, &o);
    if (i >= 0) {
        return BAD_VALUE; // this token is already taken
    }
    ssize_t err = _insertTokenAt(token, o);
    return (err<0) ? err : status_t(NO_ERROR);
}status_t Tokenizer::release(uint32_t token)
{
    const ssize_t i = _indexOrderOf(token);
    if (i >= 0) {
        const run_t& run = mRanges[i];
        if ((token >= run.first) && (token < run.first+run.length)) {
            // token in this range, we need to split
            run_t& run = mRanges.editItemAt(i);
            if ((token == run.first) || (token == run.first+run.length-1)) {
                if (token == run.first) {
                    run.first += 1;
                }
                run.length -= 1;
                if (run.length == 0) {
                    // XXX: should we systematically remove a run that's empty?
                    mRanges.removeItemsAt(i);
                }
            } else {
                // split the run
                run_t new_run;
                new_run.first = token+1;
                new_run.length = run.first+run.length - new_run.first;
                run.length = token - run.first;
                mRanges.insertAt(new_run, i+1);
            }
            return NO_ERROR;
        }
    }
    return NAME_NOT_FOUND;
}ssize_t Tokenizer::_indexOrderOf(uint32_t token, size_t* order) const
{
    // binary search
    ssize_t err = NAME_NOT_FOUND;
    ssize_t l = 0;
    ssize_t h = mRanges.size()-1;
    ssize_t mid;
    const run_t* a = mRanges.array();
    while (l <= h) {
        mid = l + (h - l)/2;
        const run_t* const curr = a + mid;
        int c = 0;
        if (token < curr->first)                        c = 1;
        else if (token >= curr->first+curr->length)     c = -1;
        if (c == 0) {
            err = l = mid;
            break;
        } else if (c < 0) {
            l = mid + 1;
        } else {
            h = mid - 1;
        }
    }
    if (order) *order = l;
    return err;
}ssize_t Tokenizer::_insertTokenAt(uint32_t token, size_t index)
{
    const size_t c = mRanges.size();    if (index >= 1) {
        // do we need to merge with the previous run?
        run_t& p = mRanges.editItemAt(index-1);
        if (p.first+p.length == token) {
            p.length += 1;
            if (index < c) {
                const run_t& n = mRanges[index];
                if (token+1 == n.first) {
                    p.length += n.length;
                    mRanges.removeItemsAt(index);
                }
            }
            return index;
        }
    }
    
    if (index < c) {
        // do we need to merge with the next run?
        run_t& n = mRanges.editItemAt(index);
        if (token+1 == n.first) {
            n.first -= 1;
            n.length += 1;
            return index;
        }
    }    return mRanges.insertAt(run_t(token,1), index);
}void Tokenizer::dump() const
{
    const run_t* ranges = mRanges.array();
    const size_t c = mRanges.size();
    printf("Tokenizer (%p, size = %d)\n", this, int(c));
    for (size_t i=0 ; i<c ; i++) {
        printf("%u: (%u, %u)\n", i,
                uint32_t(ranges[i].first), uint32_t(ranges[i].length));
    }
}