{
    Range r = m_textIterator.range();
    if (!m_textIterator.atEnd()) {
        if (m_textIterator.length() <= 1) {
            assert(m_runOffset == 0);
        } else {
            Node n = r.startContainer();
            assert(n == r.endContainer());
            long offset = r.startOffset() + m_runOffset;
            r.setStart(n, offset);
            r.setEnd(n, offset + 1);
        }
    }
    return r;
}

void CharacterIterator::advance(long count)
{
    assert(!atEnd());

    m_atBreak = false;

    // easy if there is enough left in the current m_textIterator run
    long remaining = m_textIterator.length() - m_runOffset;
    if (count < remaining) {
        m_runOffset += count;
        m_offset += count;
        return;
    }

    // exhaust the current m_textIterator run
    count -= remaining;
    m_offset += remaining;
    
    // move to a subsequent m_textIterator run
    for (m_textIterator.advance(); !atEnd(); m_textIterator.advance()) {
        long runLength = m_textIterator.length();
        if (runLength == 0) {
            m_atBreak = true;
        } else {
            // see whether this is m_textIterator to use
            if (count < runLength) {
                m_runOffset = count;
                m_offset += count;
                return;
            }
            
            // exhaust this m_textIterator run
            count -= runLength;
            m_offset += runLength;
        }
    }

    // ran to the end of the m_textIterator... no more runs left
    m_atBreak = true;
    m_runOffset = 0;
}

QString CharacterIterator::string(long numChars)
{
    QString result;
    result.reserve(numChars);
    while (numChars > 0 && !atEnd()) {
        long runSize = kMin(numChars, length());
        result.append(characters(), runSize);
        numChars -= runSize;
        advance(runSize);
    }
    return result;
}

WordAwareIterator::WordAwareIterator()
: m_previousText(0), m_didLookAhead(false)
{
}

WordAwareIterator::WordAwareIterator(const Range &r)
: m_previousText(0), m_didLookAhead(false), m_textIterator(r)
{
    m_didLookAhead = true;  // so we consider the first chunk from the text iterator
    advance();              // get in position over the first chunk of text
}

// We're always in one of these modes:
// - The current chunk in the text iterator is our current chunk
//      (typically its a piece of whitespace, or text that ended with whitespace)
// - The previous chunk in the text iterator is our current chunk
//      (we looked ahead to the next chunk and found a word boundary)
// - We built up our own chunk of text from many chunks from the text iterator

//FIXME: Perf could be bad for huge spans next to each other that don't fall on word boundaries

void WordAwareIterator::advance()
{
    m_previousText = 0;
    m_buffer = "";      // toss any old buffer we built up

    // If last time we did a look-ahead, start with that looked-ahead chunk now
    if (!m_didLookAhead) {
        assert(!m_textIterator.atEnd());
        m_textIterator.advance();
    }
    m_didLookAhead = false;

    // Go to next non-empty chunk 
    while (!m_textIterator.atEnd() && m_textIterator.length() == 0) {
        m_textIterator.advance();
    }
    m_range = m_textIterator.range();

    if (m_textIterator.atEnd()) {
        return;
    }
    
    while (1) {
        // If this chunk ends in whitespace we can just use it as our chunk.
        if (m_textIterator.characters()[m_textIterator.length()-1].isSpace()) {
            return;
        }

        // If this is the first chunk that failed, save it in previousText before look ahead
        if (m_buffer.isEmpty()) {
            m_previousText = m_textIterator.characters();
            m_previousLength = m_textIterator.length();
        }

        // Look ahead to next chunk.  If it is whitespace or a break, we can use the previous stuff
        m_textIterator.advance();
        if (m_textIterator.atEnd() || m_textIterator.length() == 0 || m_textIterator.characters()[0].isSpace()) {
            m_didLookAhead = true;
            return;
        }

        if (m_buffer.isEmpty()) {
            // Start gobbling chunks until we get to a suitable stopping point
            m_buffer.append(m_previousText, m_previousLength);
            m_previousText = 0;
        }
        m_buffer.append(m_textIterator.characters(), m_textIterator.length());
        m_range.setEnd(m_textIterator.range().endContainer(), m_textIterator.range().endOffset());
    }
}

long WordAwareIterator::length() const
{
    if (!m_buffer.isEmpty()) {
        return m_buffer.length();
    } else if (m_previousText) {
        return m_previousLength;
    } else {
        return m_textIterator.length();
    }
}

const QChar *WordAwareIterator::characters() const
{
    if (!m_buffer.isEmpty()) {
        return m_buffer.unicode();
    } else if (m_previousText) {
        return m_previousText;
    } else {
        return m_textIterator.characters();
    }
}

CircularSearchBuffer::CircularSearchBuffer(const QString &s, bool isCaseSensitive)
    : m_target(s)
{
    assert(!s.isEmpty());

    if (!isCaseSensitive) {
        m_target = s.lower();
    }
    m_target.replace(nonBreakingSpace, ' ');
    m_isCaseSensitive = isCaseSensitive;

    m_buffer = static_cast<QChar *>(malloc(s.length() * sizeof(QChar)));
    m_cursor = m_buffer;
    m_bufferFull = false;
}

void CircularSearchBuffer::append(const QChar &c)
{
    if (m_isCaseSensitive) {
        *m_cursor++ = c.unicode() == nonBreakingSpace ? ' ' : c.unicode();
    } else {
        *m_cursor++ = c.unicode() == nonBreakingSpace ? ' ' : c.lower().unicode();
    }
    if (m_cursor == m_buffer + length()) {
        m_cursor = m_buffer;
        m_bufferFull = true;
    }
}

// This function can only be used when the buffer is not yet full,
// and when then count is small enough to fit in the buffer.
// No need for a more general version for the search algorithm.
void CircularSearchBuffer::append(long count, const QChar *characters)
{
    long tailSpace = m_buffer + length() - m_cursor;

    assert(!m_bufferFull);
    assert(count <= tailSpace);

    if (m_isCaseSensitive) {
        for (long i = 0; i != count; ++i) {
            QChar c = characters[i];
            m_cursor[i] = c.unicode() == nonBreakingSpace ? ' ' : c.unicode();
        }
    } else {
        for (long i = 0; i != count; ++i) {
            QChar c = characters[i];
            m_cursor[i] = c.unicode() == nonBreakingSpace ? ' ' : c.lower().unicode();
        }
    }
    if (count < tailSpace) {
        m_cursor += count;
    } else {
        m_bufferFull = true;
        m_cursor = m_buffer;
    }
}

long CircularSearchBuffer::neededCharacters() const
{
    return m_bufferFull ? 0 : m_buffer + length() - m_cursor;
}

bool CircularSearchBuffer::isMatch() const
{
    assert(m_bufferFull);

    long headSpace = m_cursor - m_buffer;
    long tailSpace = length() - headSpace;
    return memcmp(m_cursor, m_target.unicode(), tailSpace * sizeof(QChar)) == 0
        && memcmp(m_buffer, m_target.unicode() + tailSpace, headSpace * sizeof(QChar)) == 0;
}

long TextIterator::rangeLength(const Range &r)
{
    // Allocate string at the right size, rather than building it up by successive append calls.
    long length = 0;
    for (TextIterator it(r); !it.atEnd(); it.advance()) {
        length += it.length();
    }
    return length;
}

void TextIterator::setRangeFromLocationAndLength (const Range &range, Range &resultRange, long rangeLocation, long rangeLength)
{
    long docTextPosition = 0;
    long rangeEnd = rangeLocation + rangeLength;

    for (TextIterator it(range); !it.atEnd(); it.advance()) {
        long len = it.length();
        if (rangeLocation >= docTextPosition && rangeLocation <= docTextPosition + len) {
            Range textRunRange = it.range();
            if (textRunRange.startContainer().handle()->isTextNode()) {
                long offset = rangeLocation - docTextPosition;
                resultRange.setStart(textRunRange.startContainer(), offset + textRunRange.startOffset());
            } else {
                if (rangeLocation == docTextPosition) {
                    resultRange.setStart(textRunRange.startContainer(), textRunRange.startOffset());
                } else {
                    resultRange.setStart(textRunRange.endContainer(), textRunRange.endOffset());
                }
            }
        }
        if (rangeEnd >= docTextPosition && rangeEnd <= docTextPosition + len) {
            Range textRunRange = it.range();
            if (textRunRange.startContainer().handle()->isTextNode()) {
                long offset = rangeEnd - docTextPosition;
                resultRange.setEnd(textRunRange.startContainer(), offset + textRunRange.startOffset());
            } else {
                if (rangeEnd == docTextPosition) {
                    resultRange.setEnd(textRunRange.startContainer(), textRunRange.startOffset());
                } else {
                    resultRange.setEnd(textRunRange.endContainer(), textRunRange.endOffset());
                }
            }
            if ( !(rangeLength == 0 && rangeEnd == docTextPosition + len) ) {
                break;
            }
        }
        docTextPosition += it.length();
    }
}

QString plainText(const Range &r)
{
    // Allocate string at the right size, rather than building it up by successive append calls.
    long length = 0;
    for (TextIterator it(r); !it.atEnd(); it.advance()) {
        length += it.length();
    }
    QString result("");
    result.reserve(length);
    for (TextIterator it(r); !it.atEnd(); it.advance()) {
        result.append(it.characters(), it.length());
    }
    return result;
}

Range findPlainText(const Range &r, const QString &s, bool forward, bool caseSensitive)
{
    // FIXME: Can we do Boyer-Moore or equivalent instead for speed?

    // FIXME: This code does not allow \n at the moment because of issues with <br>.
    // Once we fix those, we can remove this check.
    if (s.isEmpty() || s.find('\n') != -1) {
        Range result = r;
        result.collapse(forward);
        return result;
    }

    CircularSearchBuffer buffer(s, caseSensitive);

    bool found = false;
    CharacterIterator rangeEnd;

    {
        CharacterIterator it(r);
        while (1) {
            // Fill the buffer.
            while (long needed = buffer.neededCharacters()) {
                if (it.atBreak()) {
                    if (it.atEnd()) {
                        goto done;
                    }
                    buffer.clear();
                }
                long available = it.length();
                long runLength = kMin(needed, available);
                buffer.append(runLength, it.characters());
                it.advance(runLength);
            }

            // Do the search.
            while (1) {
                if (buffer.isMatch()) {
                    // Compute the range for the result.
                    found = true;
                    rangeEnd = it;
                    // If searching forward, stop on the first match.
                    // If searching backward, don't stop, so we end up with the last match.
                    if (forward) {
                        goto done;
                    }
                }
                if (it.atBreak())
                    break;
                buffer.append(it.characters()[0]);
                it.advance(1);
            }
            buffer.clear();
        }
    }

done:
    Range result = r;
    if (!found) {
        result.collapse(!forward);
    } else {
        CharacterIterator it(r);
        it.advance(rangeEnd.characterOffset() - buffer.length());
        result.setStart(it.range().startContainer(), it.range().startOffset());
        it.advance(buffer.length() - 1);
        result.setEnd(it.range().endContainer(), it.range().endOffset());
    }
    return result;
}

}