text: /* -*- 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)
      { }
  
      /**
       * 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*/
  