/* -*- Mode: C++; tab-width: 20; indent-tabs-mode: nil; c-basic-offset: 4 -*-

 * This Source Code Form is subject to the terms of the Mozilla Public

 * License, v. 2.0. If a copy of the MPL was not distributed with this

 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

#ifndef GFX_SKIP_CHARS_H

#define GFX_SKIP_CHARS_H

#include "nsTArray.h"

/*

 * gfxSkipChars is a data structure representing a list of characters that

 * have been skipped. The initial string is called the "original string"

 * and after skipping some characters, the result is called the "skipped string".

 * gfxSkipChars provides efficient ways to translate between offsets in the

 * original string and the skipped string. It is used by textrun code to keep

 * track of offsets before and after text transformations such as whitespace

 * compression and control code deletion.

 */

/**

 * The gfxSkipChars is represented as a sorted array of skipped ranges.

 *

 * A freshly-created gfxSkipChars means "all chars kept".

 */

class gfxSkipChars

{

    friend struct SkippedRangeStartComparator;

    friend struct SkippedRangeOffsetComparator;

private:

    class SkippedRange

    {

    public:

        SkippedRange(uint32_t aOffset, uint32_t aLength, uint32_t aDelta)

            : mOffset(aOffset), mLength(aLength), mDelta(aDelta)

        { }

        uint32_t Start() const

        {

            return mOffset;

        }

        uint32_t End() const

        {

            return mOffset + mLength;

        }

        uint32_t Length() const

        {

            return mLength;

        }

        uint32_t SkippedOffset() const

        {

            return mOffset - mDelta;

        }

        uint32_t Delta() const

        {

            return mDelta;

        }

        uint32_t NextDelta() const

        {

            return mDelta + mLength;

        }

        void Extend(uint32_t aChars)

        {

            mLength += aChars;

        }

    private:

        uint32_t mOffset; // original-string offset at which we want to skip

        uint32_t mLength; // number of skipped chars at this offset

        uint32_t mDelta;  // sum of lengths of preceding skipped-ranges

    };

public:

    gfxSkipChars()

        : mCharCount(0)

    { }

    void SkipChars(uint32_t aChars)

    {

        NS_ASSERTION(mCharCount + aChars > mCharCount,

                     "Character count overflow");

        uint32_t rangeCount = mRanges.Length();

        uint32_t delta = 0;

        if (rangeCount > 0) {

            SkippedRange& lastRange = mRanges[rangeCount - 1];

            if (lastRange.End() == mCharCount) {

                lastRange.Extend(aChars);

                mCharCount += aChars;

                return;

            }

            delta = lastRange.NextDelta();

        }

        mRanges.AppendElement(SkippedRange(mCharCount, aChars, delta));

        mCharCount += aChars;

    }

    void KeepChars(uint32_t aChars)

    {

        NS_ASSERTION(mCharCount + aChars > mCharCount,

                     "Character count overflow");

        mCharCount += aChars;

    }

    void SkipChar()

    {

        SkipChars(1);

    }

    void KeepChar()

    {

        KeepChars(1);

    }

    void TakeFrom(gfxSkipChars* aSkipChars)

    {

        mRanges.SwapElements(aSkipChars->mRanges);

        mCharCount = aSkipChars->mCharCount;

        aSkipChars->mCharCount = 0;

    }

    int32_t GetOriginalCharCount() const

    {

        return mCharCount;

    }

    const SkippedRange& LastRange() const

    {

        // this is only valid if mRanges is non-empty; no assertion here

        // because nsTArray will already assert if we abuse it

        return mRanges[mRanges.Length() - 1];

    }

    friend class gfxSkipCharsIterator;

private:

    nsTArray<SkippedRange> mRanges;

    uint32_t               mCharCount;

};

/**

 * A gfxSkipCharsIterator represents a position in the original string. It lets you

 * map efficiently to and from positions in the string after skipped characters

 * have been removed. You can also specify an offset that is added to all

 * incoming original string offsets and subtracted from all outgoing original

 * string offsets --- useful when the gfxSkipChars corresponds to something

 * offset from the original DOM coordinates, which it often does for gfxTextRuns.

 *

 * The current positions (in both the original and skipped strings) are

 * always constrained to be >= 0 and <= the string length. When the position

 * is equal to the string length, it is at the end of the string. The current

 * positions do not include any aOriginalStringToSkipCharsOffset.

 *

 * When the position in the original string corresponds to a skipped character,

 * the skipped-characters offset is the offset of the next unskipped character,

 * or the skipped-characters string length if there is no next unskipped character.

 */

class gfxSkipCharsIterator

{

public:

    /**

     * @param aOriginalStringToSkipCharsOffset add this to all incoming and

     * outgoing original string offsets

     */

    gfxSkipCharsIterator(const gfxSkipChars& aSkipChars,

                         int32_t aOriginalStringToSkipCharsOffset,

                         int32_t aOriginalStringOffset)

        : mSkipChars(&aSkipChars),

          mOriginalStringOffset(0),

          mSkippedStringOffset(0),

          mCurrentRangeIndex(-1),

          mOriginalStringToSkipCharsOffset(aOriginalStringToSkipCharsOffset)

    {

        SetOriginalOffset(aOriginalStringOffset);

    }

    explicit gfxSkipCharsIterator(const gfxSkipChars& aSkipChars,

                                  int32_t aOriginalStringToSkipCharsOffset = 0)

        : mSkipChars(&aSkipChars),

          mOriginalStringOffset(0),

          mSkippedStringOffset(0),

          mOriginalStringToSkipCharsOffset(aOriginalStringToSkipCharsOffset)

    {

        mCurrentRangeIndex =

            mSkipChars->mRanges.IsEmpty() ||

            mSkipChars->mRanges[0].Start() > 0 ? -1 : 0;

    }

    gfxSkipCharsIterator(const gfxSkipCharsIterator& aIterator)

        : mSkipChars(aIterator.mSkipChars),

          mOriginalStringOffset(aIterator.mOriginalStringOffset),

          mSkippedStringOffset(aIterator.mSkippedStringOffset),

          mCurrentRangeIndex(aIterator.mCurrentRangeIndex),

          mOriginalStringToSkipCharsOffset(aIterator.mOriginalStringToSkipCharsOffset)

    { }

    /**

     * The empty constructor creates an object that is useless until it is assigned.

     */

    gfxSkipCharsIterator()

        : mSkipChars(nullptr),

          mOriginalStringOffset(0),

          mSkippedStringOffset(0),

          mCurrentRangeIndex(0),

          mOriginalStringToSkipCharsOffset(0)

    { }

    /**

     * Return true if this iterator is properly initialized and usable.

     */

    bool IsInitialized()

    {

        return mSkipChars != nullptr;

    }

    /**

     * Set the iterator to aOriginalStringOffset in the original string.

     * This can efficiently move forward or backward from the current position.

     * aOriginalStringOffset is clamped to [0,originalStringLength].

     */

    void SetOriginalOffset(int32_t aOriginalStringOffset);

    /**

     * Set the iterator to aSkippedStringOffset in the skipped string.

     * This can efficiently move forward or backward from the current position.

     * aSkippedStringOffset is clamped to [0,skippedStringLength].

     */

    void SetSkippedOffset(uint32_t aSkippedStringOffset);

    uint32_t ConvertOriginalToSkipped(int32_t aOriginalStringOffset)

    {

        SetOriginalOffset(aOriginalStringOffset);

        return GetSkippedOffset();

    }

    int32_t ConvertSkippedToOriginal(uint32_t aSkippedStringOffset)

    {

        SetSkippedOffset(aSkippedStringOffset);

        return GetOriginalOffset();

    }

    /**

     * Test if the character at the current position in the original string

     * is skipped or not. If aRunLength is non-null, then *aRunLength is set

     * to a number of characters all of which are either skipped or not, starting

     * at this character. When the current position is at the end of the original

     * string, we return true and *aRunLength is set to zero.

     */

    bool IsOriginalCharSkipped(int32_t* aRunLength = nullptr) const;

    void AdvanceOriginal(int32_t aDelta)

    {

        SetOriginalOffset(GetOriginalOffset() + aDelta);

    }

    void AdvanceSkipped(int32_t aDelta)

    {

        SetSkippedOffset(GetSkippedOffset() + aDelta);

    }

    /**

     * @return the offset within the original string

     */

    int32_t GetOriginalOffset() const

    {

        return mOriginalStringOffset - mOriginalStringToSkipCharsOffset;

    }

    /**

     * @return the offset within the skipped string corresponding to the

     * current position in the original string. If the current position

     * in the original string is a character that is skipped, then we return

     * the position corresponding to the first non-skipped character in the

     * original string after the current position, or the length of the skipped

     * string if there is no such character.

     */

    uint32_t GetSkippedOffset() const

    {

        return mSkippedStringOffset;

    }

    int32_t GetOriginalEnd() const

    {

        return mSkipChars->GetOriginalCharCount() -

            mOriginalStringToSkipCharsOffset;

    }

private:

    const gfxSkipChars* mSkipChars;

    // Current position

    int32_t mOriginalStringOffset;

    uint32_t mSkippedStringOffset;

    // Index of the last skippedRange that precedes or contains the current

    // position in the original string.

    // If index == -1 then we are before the first skipped char.

    int32_t mCurrentRangeIndex;

    // This offset is added to map from "skipped+unskipped characters in

    // the original DOM string" character space to "skipped+unskipped

    // characters in the textrun's gfxSkipChars" character space

    int32_t mOriginalStringToSkipCharsOffset;

};

#endif /*GFX_SKIP_CHARS_H*/