#### Bzip2 Implementation
#### Copyright (C) 2023-2024 Remilia Scarlet
#### Copyright (C) 2015 Jaime Olivares
#### Copyright (c) 2011 Matthew Francis
#### Copyright (c) 2003-2008 Yuta Mori
#### MIT License
####
#### Ported from the Java implementation by Matthew Francis:
#### https://github.com/MateuszBartosiewicz/bzip2.
####
#### Ported by Remilia Scarlet from the C# implementation by Jamie Olivares:
#### http://github.com/jaime-olivares/bzip2

####
#### Burrows-Wheeler Transform/Suffix Sorting
####
#### Remi: TODO Clean this code up.  There are a LOT of while loops that need to be
#### converted to #times, #downto, etc., no comments, and bad variable names.
####

module RemiLib::Compression::BZip2
  private class DivSufSort
    ###
    ### DivSufSort suffix array generator
    ### Based on libdivsufsort 1.2.3 patched to support BZip2
    ###
    ### This is a port of the C# version, which is a port of the Java version,
    ### which is a simple conversion of the original C with two minor bugfixes
    ### applied (see "BUGFIX" comments within the class). Documentation within
    ### the original code was largely absent.
    ###

    STACK_SIZE = 64
    BUCKET_A_SIZE = 256
    BUCKET_B_SIZE = 65536
    SS_BLOCK_SIZE = 1024
    INSERTION_SORT_THRESHOLD = 8

    LOG2TABLE = [
      -1, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
      5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
      6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
      6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
      7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
      7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
      7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
      7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7
    ]

    ############################################################################

    private class StackEntry
      property a : Int32 = 0
      property b : Int32 = 0
      property c : Int32 = 0
      property d : Int32 = 0

      def initialize
      end

      @[AlwaysInline]
      def set(@a : Int32, @b : Int32, @c : Int32, @d : Int32) : Nil
      end

      @[AlwaysInline]
      def reset : Nil
        @a = 0
        @b = 0
        @c = 0
        @d = 0
      end
    end

    alias Stack = Array(StackEntry)

    ############################################################################

    private struct PartitionResult
      getter first : Int32
      getter last : Int32

      def initialize(@first : Int32, @last : Int32)
      end
    end

    ############################################################################

    private class TRBudget
      @budget : Int32
      property chance : Int32

      def initialize(@budget : Int32, @chance : Int32)
      end

      @[AlwaysInline]
      def update(size : Int, n : Int) : Bool
        @budget -= n
        if @budget <= 0
          @chance -= 1
          return false if @chance == 0
          @budget += size
        end

        true
      end
    end

    ############################################################################

    @stack : Stack
    @ssize : UInt8 = 0u8
    @sa : Array(Int32)
    @t : Bytes
    @n : Int32

    # Creates a new `DivSufSort` instance.  `t` The input array, `sa` is the
    # output array, and `n` is the length of the input data.
    def initialize(@t : Bytes, @sa : Array(Int32), @n : Int32, @int32Pool : ArrayPool(Int32))
      @stack = Stack.new(STACK_SIZE) { |_| StackEntry.new }
    end

    @[AlwaysInline]
    private def makeStack : Nil
      @stack.each &.reset
      @ssize = 0u8
    end

    @[AlwaysInline]
    private def pushStack(a : Int32, b : Int32, c : Int32, d : Int32) : Nil
      @stack[@ssize].set(a, b, c, d)
      @ssize += 1
    end

    @[AlwaysInline]
    private def popStack : StackEntry
      @ssize -= 1
      @stack[@ssize]
    end

    @[AlwaysInline]
    private def stackEmpty? : Bool
      @ssize == 0
    end

    # Performs a Burrows Wheeler Transform on the input array.  Returns the
    # index of the first character of the input array within the output array.
    def bwt : Int32
      case @n
      when 0
        return 0
      when 1
        @sa[0] = @t[0].to_i32!
        return 0
      end

      @int32Pool.withRentedArray(BUCKET_A_SIZE) do |bucketA|
        @int32Pool.withRentedArray(BUCKET_B_SIZE) do |bucketB|
          bucketA.fill(0)
          bucketB.fill(0)

          m = sortTypeBstar(bucketA, bucketB)
          if 0 < m
            constructBWT(bucketA, bucketB)
          else
            0
          end
        end
      end
    end

    @[AlwaysInline]
    private def swap(arr1 : Array, idx1 : Int, arr2 : Array, idx2 : Int) : Nil
      tmp = arr1[idx1]
      arr1[idx1] = arr2[idx2]
      arr2[idx2] = tmp
    end

    private def ssCompare(p1 : Int32, p2 : Int32, depth : Int32) : Int32
      u1n : Int32 = @sa[p1 + 1] + 2
      u2n : Int32 = @sa[p2 + 1] + 2
      u1 : Int32 = depth + @sa[p1]
      u2 : Int32 = depth + @sa[p2]

      while u1 < u1n && u2 < u2n && @t[u1] == @t[u2]
        u1 += 1
        u2 += 1
      end

      if u1 < u1n
        if u2 < u2n
          @t[u1].to_i32! - @t[u2].to_i32!
        else
          1
        end
      elsif u2 < u2n
        -1
      else
        0
      end
    end

    private def ssCompareLast(pa : Int32, p1 : Int32, p2 : Int32, depth : Int32, size : Int32) : Int32
      u1 : Int32 = depth + @sa[p1]
      u2 : Int32 = depth + @sa[p2]
      u1n : Int32 = size
      u2n : Int32 = @sa[p2 + 1] + 2

      while u1 < u1n && u2 < u2n && @t[u1] == @t[u2]
        u1 += 1
        u2 += 1
      end

      if u1 < u1n
        if u2 < u2n
          return @t[u1].to_i32! - @t[u2].to_i32!
        else
          return 1
        end
      end

      return 1 if u2 == u2n

      u1 = u1 % size
      u1n = @sa[pa] + 2
      while u1 < u1n && u2 < u2n && @t[u1] == @t[u2]
        u1 += 1
        u2 += 1
      end

      if u1 < u1n
        if u2 < u2n
          @t[u1].to_i32! - @t[u2].to_i32!
        else
          1
        end
      elsif u2 < u2n
        -1
      else
        0
      end
    end

    private def ssInsertionSort(pa : Int32, first : Int32, last : Int32, depth : Int32) : Nil
      i : Int32 = last - 2
      j : Int32 = 0
      t : Int32 = 0
      r : Int32 = 0

      while first <= i
        j = i + 1
        t = @sa[i]

        while 0 < (r = ssCompare(pa + t, pa + @sa[j], depth))
          loop do
            @sa[j - 1] = @sa[j]
            break unless (j += 1) < last && @sa[j] < 0
          end
          break if last <= j
        end

        @sa[j] = ~(@sa[j]) if r == 0
        @sa[j - 1] = t
        i -= 1
      end
    end

    private def ssFixdown(td : Int32, pa : Int32, sa : Int32, i : Int32, size : Int32) : Nil
      v : Int32 = @sa[sa + i]
      c : Int32 = @t[td + @sa[pa + v]].to_i32!
      j : Int32 = 0
      k : Int32 = 0
      d : Int32 = 0
      e : Int32 = 0

      while (j = 2 * i + 1) < size
        d = @t[td + @sa[pa + @sa[sa + (k = j)]]].to_i32!
        j += 1
        if d < (e = @t[td + @sa[pa + @sa[sa + j]]].to_i32!)
          k = j
          d = e
        end
        break if d <= c

        @sa[sa + i] = @sa[sa + k]
        i = k
      end

      @sa[sa + i] = v
    end

    private def ssHeapSort(td : Int32, pa : Int32, sa : Int32, size : Int32) : Nil
      m : Int32 = size
      if size % 2 == 0
        m -= 1
        if @t[td + @sa[pa + @sa[sa + m.tdiv(2)]]] < @t[td + @sa[pa + @sa[sa + m]]]
          swap(@sa, sa + m, @sa, sa + m.tdiv(2))
        end
      end

      (m.tdiv(2) - 1).downto(0) do |i|
        ssFixdown(td, pa, sa, i, m)
      end

      if size % 2 == 0
        swap(@sa, sa, @sa, sa + m)
        ssFixdown(td, pa, sa, 0, m)
      end

      t : Int32 = 0
      (m - 1).downto(1) do |i|
        t = @sa[sa]
        @sa[sa] = @sa[sa + i]
        ssFixdown(td, pa, sa, 0, i)
        @sa[sa + i] = t
      end
    end

    @[AlwaysInline]
    private def ssMedian3(td : Int32, pa : Int32, v1 : Int32, v2 : Int32, v3 : Int32) : Int32
      tv1 : Int32 = @t[td + @sa[pa + @sa[v1]]].to_i32!
      tv2 : Int32 = @t[td + @sa[pa + @sa[v2]]].to_i32!
      tv3 : Int32 = @t[td + @sa[pa + @sa[v3]]].to_i32!

      if tv1 > tv2
        tmp = v1
        v1 = v2
        v2 = tmp

        tmp = tv1
        tv1 = tv2
        tv2 = tmp
      end

      if tv2 > tv3
        if tv1 > tv3
          v1
        else
          v3
        end
      else
        v2
      end
    end

    private def ssMedian5(td : Int32, pa : Int32, v1 : Int32, v2 : Int32, v3 : Int32, v4 : Int32, v5 : Int32) : Int32
      tv1 : Int32 = @t[td + @sa[pa + @sa[v1]]].to_i32!
      tv2 : Int32 = @t[td + @sa[pa + @sa[v2]]].to_i32!
      tv3 : Int32 = @t[td + @sa[pa + @sa[v3]]].to_i32!
      tv4 : Int32 = @t[td + @sa[pa + @sa[v4]]].to_i32!
      tv5 : Int32 = @t[td + @sa[pa + @sa[v5]]].to_i32!
      temp : Int32 = 0
      tvtemp : Int32 = 0

      if tv2 > tv3
        temp = v2
        v2 = v3
        v3 = temp
        tvtemp = tv2
        tv2 = tv3
        tv3 = tvtemp
      end

      if tv4 > tv5
        temp = v4
        v4 = v5
        v5 = temp
        tvtemp = tv4
        tv4 = tv5
        tv5 = tvtemp
      end

      if tv2 > tv4
        temp = v2
        #v2 = v4
        v4 = temp
        tvtemp = tv2
        tv2 = tv4
        tv4 = tvtemp
        temp = v3
        v3 = v5
        v5 = temp
        tvtemp = tv3
        tv3 = tv5
        tv5 = tvtemp
      end

      if tv1 > tv3
        temp = v1
        v1 = v3
        v3 = temp
        tvtemp = tv1
        tv1 = tv3
        tv3 = tvtemp
      end

      if tv1 > tv4
        temp = v1
        #v1 = v4
        v4 = temp
        tvtemp = tv1
        tv1 = tv4
        tv4 = tvtemp
        temp = v3
        v3 = v5
        #v5 = temp
        tvtemp = tv3
        tv3 = tv5
        tv5 = tvtemp
      end

      tv3 > tv4 ? v4 : v3
    end

    private def ssPivot(td : Int32, pa : Int32, first : Int32, last : Int32) : Int32
      t : Int32 = last - first
      middle : Int32 = first + t.tdiv(2)

      if t <= 512
        if t <= 32
          return ssMedian3(td, pa, first, middle, last - 1)
        end

        t >>= 2
        return ssMedian5(td, pa, first, first + t, middle, last - 1 - t, last - 1)
      end

      t >>= 3
      ssMedian3(td, pa,
                ssMedian3(td, pa, first, first + t, first + (t << 1)),
                ssMedian3(td, pa, middle - t, middle, middle + t),
                ssMedian3(td, pa, last - 1 - (t << 1), last - 1 - t, last - 1))
    end

    @[AlwaysInline]
    private def ssLog(x : Int32) : Int32
      if (x & 0xff00) != 0
        8 + LOG2TABLE[(x >> 8) & 0xff]
      else
        LOG2TABLE[x & 0xff]
      end
    end

    private def ssSubstringPartition(pa : Int32, first : Int32, last : Int32, depth : Int32) : Int32
      a : Int32 = first - 1
      b : Int32 = last
      t : Int32 = 0

      loop do
        while (a += 1) < b && ((@sa[pa + @sa[a]] + depth) >= (@sa[pa + @sa[a] + 1] + 1))
          @sa[a] = ~(@sa[a])
        end

        while a < (b -= 1) && ((@sa[pa + @sa[b]] + depth) < (@sa[pa + @sa[b] + 1] + 1))
        end

        break if b <= a
        t = ~(@sa[b])
        @sa[b] = @sa[a]
        @sa[a] = t
      end

      @sa[first] = ~(@sa[first]) if first < a
      a
    end

    private def ssMultiKeyIntroSort(pa : Int32, first : Int32, last : Int32, depth : Int32) : Nil
      makeStack
      x : Int32 = 0
      td : Int32 = 0
      a : Int32 = 0
      v : Int32 = 0
      b : Int32 = 0
      c : Int32 = 0
      d : Int32 = 0
      s : Int32 = 0
      t : Int32 = 0
      e : Int32 = 0
      limit : Int32 = ssLog(last - first)

      loop do
        if last - first <= INSERTION_SORT_THRESHOLD
          ssInsertionSort(pa, first, last, depth) if 1 < last - first
          return if stackEmpty?
          entry : StackEntry = popStack
          first = entry.a
          last = entry.b
          depth = entry.c
          limit = entry.d
          next
        end

        td = depth
        if limit == 0
          ssHeapSort(td, pa, first, last - first)
        end
        limit -= 1

        if limit < 0
          a = first + 1
          v = @t[td + @sa[pa + @sa[first]]].to_i32!

          while a < last
            if (x = @t[td + @sa[pa + @sa[a]]].to_i32!) != v
              break if 1 < a - first
              v = x
              first = a
            end

            a += 1
          end

          if @t[td + @sa[pa + @sa[first]] - 1] < v
            first = ssSubstringPartition(pa, first, a, depth)
          end

          if a - first <= last - a
            if 1 < a - first
              pushStack(a, last, depth, -1)
              last = a
              depth += 1
              limit = ssLog(a - first)
            else
              first = a
              limit = -1
            end
          else
            if 1 < last - a
              pushStack(first, a, depth + 1, ssLog(a - first))
              first = a
              limit = -1
            else
              last = a
              depth += 1
              limit = ssLog(a - first)
            end
          end

          next
        end # if limit < 0

        a = ssPivot(td, pa, first, last)
        v = @t[td + @sa[pa + @sa[a]]].to_i32!
        swap(@sa, first, @sa, a)

        b = first
        while (b += 1) < last && (x = @t[td + @sa[pa + @sa[b]]].to_i32!) == v
        end

        if (a = b) < last && x < v
          while (b += 1) < last && (x = @t[td + @sa[pa + @sa[b]]].to_i32!) <= v
            if x == v
              swap(@sa, b, @sa, a)
              a += 1
            end
          end
        end

        c = last
        while b < (c -= 1) && (x = @t[td + @sa[pa + @sa[c]]].to_i32!) == v
        end

        if b < (d = c) && x > v
          while b < (c -= 1) && (x = @t[td + @sa[pa + @sa[c]]].to_i32!) >= v
            if x == v
              swap(@sa, c, @sa, d)
              d -= 1
            end
          end
        end

        while b < c
          swap(@sa, b, @sa, c)

          while (b += 1) < c && (x = @t[td + @sa[pa + @sa[b]]].to_i32!) <= v
            if x == v
              swap(@sa, b, @sa, a)
              a += 1
            end
          end

          while b < (c -= 1) && (x = @t[td + @sa[pa + @sa[c]]].to_i32!) >= v
            if x == v
              swap(@sa, c, @sa, d)
              d -= 1
            end
          end
        end

        if a <= d
          c = b - 1

          if (s = a - first) > (t = b - a)
            s = t
          end

          e = first
          f = b - s
          while 0 < s
            swap(@sa, e, @sa, f)
            s -= 1
            e += 1
            f += 1
          end

          if (s = d - c) > (t = last - d - 1)
            s = t
          end

          e = b
          f = last - s
          while 0 < s
            swap(@sa, e, @sa, f)
            s -= 1
            e += 1
            f += 1
          end

          a = first + (b - a)
          c = last - (d - c)
          b = if v <= @t[td + @sa[pa + @sa[a]] - 1]
                a
              else
                ssSubstringPartition(pa, a, c, depth)
              end

          if a - first <= last - c
            if last - c <= c - b
              pushStack(b, c, depth + 1, ssLog(c - b))
              pushStack(c, last, depth, limit)
              last = a

            elsif a - first <= c - b
              pushStack(c, last, depth, limit)
              pushStack(b, c, depth + 1, ssLog(c - b))
              last = a

            else
              pushStack(c, last, depth, limit)
              pushStack(first, a, depth, limit)
              first = b
              last = c
              depth += 1
              limit = ssLog(c - b)
            end
          else
            if a - first <= c - b
              pushStack(b, c, depth + 1, ssLog(c - b))
              pushStack(first, a, depth, limit)
              first = c

            elsif last - c <= c - b
              pushStack(first, a, depth, limit)
              pushStack(b, c, depth + 1, ssLog(c - b))
              first = c

            else
              pushStack(first, a, depth, limit)
              pushStack(c, last, depth, limit)
              first = b
              last = c
              depth += 1
              limit = ssLog(c - b)
            end
          end # if a - first < last - c
        else # if a <= d
          limit += 1
          if @t[td + @sa[pa + @sa[first]] - 1] < v
            first = ssSubstringPartition(pa, first, last, depth)
            limit = ssLog(last - first)
          end
          depth += 1
        end
      end
    end

    private def ssBlockSwap(arr1 : Array, first1 : Int32, arr2 : Array, first2 : Int32, size : Int32) : Nil
      a : Int32 = first1
      b : Int32 = first2
      i : Int32 = size
      while 0 < i
        swap(arr1, a, arr2, b)
        i -= 1
        a += 1
        b += 1
      end
    end

    private def ssMergeForward(pa : Int32, buf : Array(Int32), bufOffset : Int32, first : Int32, middle : Int32,
                               last : Int32, depth : Int32) : Nil
      bufEnd : Int32 = bufOffset + (middle - last) - 1
      ssBlockSwap(buf, bufOffset, @sa, first, middle - first)

      t : Int32 = @sa[first]
      i : Int32 = first
      j : Int32 = bufOffset
      k : Int32 = middle
      r : Int32 = 0

      loop do
        r = ssCompare(pa + buf[j], pa + @sa[k], depth)
        if r < 0
          loop do
            @sa[i] = buf[j]
            i += 1
            if bufEnd <= j
              buf[j] = t
              return
            end
            buf[j] = @sa[i]
            j += 1

            break unless buf[j] < 0
          end

        elsif r > 0
          loop do
            @sa[i] = @sa[k]
            i += 1
            @sa[k] = @sa[i]
            k += 1

            if last <= k
              while j < bufEnd
                @sa[i] = buf[j]
                i += 1
                buf[j] = @sa[i]
                j += 1
              end

              @sa[i] = buf[j]
              buf[j] = t
              return
            end

            break unless @sa[k] < 0
          end

        else
          @sa[k] = ~(@sa[k])
          loop do
            @sa[i] = buf[j]
            i += 1
            if bufEnd <= j
              buf[j] = t
              return
            end

            buf[j] = @sa[i]
            j += 1

            break unless buf[j] < 0
          end

          loop do
            @sa[i] = @sa[k]
            i += 1
            @sa[k] = @sa[i]
            k += 1

            if last <= k
              while j < bufEnd
                @sa[i] = buf[j]
                i += 1
                buf[j] = @sa[i]
                j += 1
              end

              @sa[i] = buf[j]
              buf[j] = t
              return
            end

            break unless @sa[k] < 0
          end
        end
      end
    end

    private def ssMergeBackward(pa : Int32, buf : Array(Int32), bufOffset : Int32, first : Int32, middle : Int32,
                                last : Int32, depth : Int32) : Nil
      bufEnd : Int32 = bufOffset + (last - middle)
      ssBlockSwap(buf, bufOffset, @sa, middle, last - middle)

      p1 : Int32 = 0
      p2 : Int32 = 0
      x : Int32 = 0

      if buf[bufEnd - 1] < 0
        x |= 1
        p1 = pa + ~(buf[bufEnd - 1])
      else
        p1 = pa + buf[bufEnd - 1]
      end

      if @sa[middle - 1] < 0
        x |= 2
        p2 = pa + ~(@sa[middle - 1])
      else
        p2 = pa + @sa[middle - 1]
      end

      t : Int32 = @sa[last - 1]
      i : Int32 = last - 1
      j : Int32 = bufEnd - 1
      k : Int32 = middle - 1
      r : Int32 = 0
      loop do
        r = ssCompare(p1, p2, depth)
        if r > 0
          if (x & 1) != 0
            loop do
              @sa[i] = buf[j]
              i -= 1
              buf[j] = @sa[i]
              j -= 1
              break unless buf[j] < 0
            end

            x ^= 1
          end

          @sa[i] = buf[j]
          i -= 1
          if j <= bufOffset
            buf[j] = t
            return
          end

          buf[j] = @sa[i]
          j -= 1

          if buf[j] < 0
            x |= 1
            p1 = pa + ~(buf[j])
          else
            p1 = pa + buf[j]
          end

        elsif r < 0
          if (x & 2) != 0
            loop do
              @sa[i] = @sa[k]
              i -= 1
              @sa[k] = @sa[i]
              k -= 1
              break unless @sa[k] < 0
            end

            x ^= 2
          end

          @sa[i] = @sa[k]
          i -= 1
          @sa[k] = @sa[i]
          k -= 1

          if k < first
            while bufOffset < j
              @sa[i] = buf[j]
              i -= 1
              buf[j] = @sa[i]
              j -= 1
            end

            @sa[i] = buf[j]
            buf[j] = t
            return
          end

          if @sa[k] < 0
            x |= 2
            p2 = pa + ~(@sa[k])
          else
            p2 = pa + @sa[k]
          end

        else
          if (x & 1) != 0
            loop do
              @sa[i] = buf[j]
              i -= 1
              buf[j] = @sa[i]
              j -= 1
              break unless buf[j] < 0
            end

            x ^= 1
          end

          @sa[i] = ~(buf[j])
          i -= 1
          if j <= bufOffset
            buf[j] = t
            return
          end

          buf[j] = @sa[i]
          j -= 1

          if (x & 2) != 0
            loop do
              @sa[i] = @sa[k]
              i -= 1
              @sa[k] = @sa[i]
              k -= 1
              break unless @sa[k] < 0
            end

            x ^= 2
          end

          @sa[i] = @sa[k]
          i -= 1
          @sa[k] = @sa[i]
          k -= 1

          if k < first
            while bufOffset < j
              @sa[i] = buf[j]
              i -= 1
              buf[j] = @sa[i]
              j -= 1
            end

            @sa[i] = buf[j]
            buf[j] = t
            return
          end

          if buf[j] < 0
            x |= 1
            p1 = pa + ~(buf[j])
          else
            p1 = pa + buf[j]
          end

          if @sa[k] < 0
            x |= 2
            p2 = pa + ~(@sa[k])
          else
            p2 = pa + @sa[k]
          end
        end
      end
    end

    @[AlwaysInline]
    protected def self.getIdx(a : Int32) : Int32
      0 <= a ? a : ~a
    end

    @[AlwaysInline]
    private def ssMergeCheckEqual(pa : Int32, depth : Int32, a : Int32) : Nil
      if 0 <= @sa[a] && ssCompare(pa + DivSufSort.getIdx(@sa[a - 1]), pa + @sa[a], depth) == 0
        @sa[a] = ~(@sa[a])
      end
    end

    private def ssMerge(pa : Int32, first : Int32, middle : Int32, last : Int32, buf : Array(Int32),
                        bufOffset : Int32, bufSize : Int32, depth : Int32) : Nil
      makeStack
      check : Int32 = 0
      m : Int32 = 0
      len : Int32 = 0
      half : Int32 = 0
      j : Int32 = 0
      i : Int32 = 0
      nxt : Int32 = 0

      loop do
        if last - middle <= bufSize
          if first < middle && middle < last
            ssMergeBackward(pa, buf, bufOffset, first, middle, last, depth)
          end

          ssMergeCheckEqual(pa, depth, first) if (check & 1) != 0
          ssMergeCheckEqual(pa, depth, last) if (check & 2) != 0

          return if stackEmpty?
          entry : StackEntry = popStack
          first = entry.a
          middle = entry.b
          last = entry.c
          check = entry.d
          next
        end

        if middle - first <= bufSize
          if first < middle
            ssMergeForward(pa, buf, bufOffset, first, middle, last, depth)
          end

          ssMergeCheckEqual(pa, depth, first) if (check & 1) != 0
          ssMergeCheckEqual(pa, depth, last) if (check & 2) != 0

          return if stackEmpty?
          entry = popStack
          first = entry.a
          middle = entry.b
          last = entry.c
          check = entry.d
          next
        end

        m = 0
        len = Math.min(middle - first, last - middle)
        half = len >> 1

        while 0 < len
          if ssCompare(pa + DivSufSort.getIdx(@sa[middle + m + half]),
                       pa + DivSufSort.getIdx(@sa[middle - m - half - 1]),
                       depth) < 0
            m += half + 1
            half -= (len & 1) ^ 1
          end

          len = half
          half >>= 1
        end

        if 0 < m
          ssBlockSwap(@sa, middle - m, @sa, middle, m)

          j = middle
          i = middle
          nxt = 0

          if middle + m < last
            if @sa[middle + m] < 0
              while @sa[i - 1] < 0
                i -= 1
              end
              @sa[middle + m] = ~(@sa[middle + m])
            end

            j = middle
            while @sa[j] < 0
              j += 1
            end
            nxt = 1
          end

          if i - first <= last - j
            pushStack(j, middle + m, last, (check & 2) | (nxt & 1))
            middle -= m
            last = i
            check = check & 1
          else
            nxt <<= 1 if i == middle && middle == j
            pushStack(first, middle - m, i, (check & 1) | (nxt & 2))
            first = j
            middle += m
            check = (check & 2) | (nxt & 1)
          end
        else # if 0 < m
          ssMergeCheckEqual(pa, depth, first) if (check & 1) != 0
          ssMergeCheckEqual(pa, depth, middle)
          ssMergeCheckEqual(pa, depth, last) if (check & 2) != 0

          return if stackEmpty?
          entry = popStack
          first = entry.a
          middle = entry.b
          last = entry.c
          check = entry.d
        end
      end
    end

    private def subStringSort(pa : Int32, first : Int32, last : Int32, buf : Array(Int32),
                              bufOffset : Int32, bufSize : Int32, depth : Int32,
                              lastSuffix? : Bool, size : Int32) : Nil
      a : Int32 = 0
      i : Int32 = 0
      k : Int32 = 0
      curBufOffset : Int32 = 0
      curBufSize : Int32 = 0
      b : Int32 = 0
      j : Int32 = 0

      first += 1 if lastSuffix?

      a = first
      while (a + SS_BLOCK_SIZE) < last
        ssMultiKeyIntroSort(pa, a, a + SS_BLOCK_SIZE, depth)
        curBuf : Array(Int32) = @sa
        curBufOffset = a + SS_BLOCK_SIZE
        curBufSize = last - (a + SS_BLOCK_SIZE)
        if curBufSize <= bufSize
          curBufSize = bufSize
          curBuf = buf
          curBufOffset = bufOffset
        end

        b = a
        k = SS_BLOCK_SIZE
        j = i

        while (j & 1) != 0
          ssMerge(pa, b - k, b, b + k, curBuf, curBufOffset, curBufSize, depth)
          b -= k
          k <<= 1
          j >>= 1
        end

        a += SS_BLOCK_SIZE
        i += 1
      end

      ssMultiKeyIntroSort(pa, a, last, depth)

      k = SS_BLOCK_SIZE
      while i != 0
        if (i & 1) != 0
          ssMerge(pa, a - k, a, last, buf, bufOffset, bufSize, depth)
          a -= k
        end
        k <<= 1
        i >>= 1
      end

      if lastSuffix?
        a = first
        i = @sa[first - 1]
        r : Int32 = 1

        while a < last &&
              (@sa.unsafe_fetch(a) < 0 || 0 < (r = ssCompareLast(pa, pa + i, pa + @sa.unsafe_fetch(a), depth, size)))
          @sa.unsafe_put(a - 1, @sa.unsafe_fetch(a))
          a += 1
        end

        @sa.unsafe_put(a, ~(@sa.unsafe_fetch(a))) if r == 0
        @sa.unsafe_put(a - 1, i)
      end
    end

    @[AlwaysInline]
    private def trGetC(isa : Int32, isad : Int32, isan : Int32, x : Int32) : Int32
      if isad + x < isan
        @sa[isad + x]
      else
        @sa[isa + ((isad - isa + x) % (isan - isa))]
      end
    end

    private def trFixdown(isa : Int32, isad : Int32, isan : Int32, sa : Int32, i : Int32, size : Int32) : Nil
      j : Int32 = 0
      k : Int32 = 0
      v : Int32 = @sa[sa + i]
      c : Int32 = trGetC(isa, isad, isan, v)
      d : Int32 = 0
      e : Int32 = 0

      while (j = 2 * i + 1) < size
        k = j
        j += 1
        d = trGetC(isa, isad, isan, @sa[sa + k])
        if d < (e = trGetC(isa, isad, isan, @sa[sa + j]))
          k = j
          d = e
        end

        break if d <= c
        @sa[sa + i] = @sa[sa + k]
        i = k
      end

      @sa[sa + i] = v
    end

    private def trHeapSort(isa : Int32, isad : Int32, isan : Int32, sa : Int32, size : Int32) : Nil
      m : Int32 = size
      if size % 2 == 0
        m -= 1
        if trGetC(isa, isad, isan, @sa[sa + m.tdiv(2)]) < trGetC(isa, isad, isan, @sa[sa + m])
          swap(@sa, sa + m, @sa, sa + m.tdiv(2))
        end
      end


      (m.tdiv(2) - 1).downto(0) do |i|
        trFixdown(isa, isad, isan, sa, i, m)
      end

      if size % 2 == 0
        swap(@sa, sa, @sa, sa + m)
        trFixdown(isa, isad, isan, sa, 0, m)
      end

      t : Int32 = 0
      (m - 1).downto(1) do |i|
        t = @sa[sa]
        @sa[sa] = @sa[sa + i]
        trFixdown(isa, isad, isan, sa, 0, i)
        @sa[sa + i] = t
      end
    end

    private def trInsertionSort(isa : Int32, isad : Int32, isan : Int32, first : Int32, last : Int32) : Nil
      a : Int32 = first + 1
      b : Int32 = 0
      t : Int32 = 0
      r : Int32 = 0

      while a < last
        t =  @sa[a]
        b = a - 1
        r = 0
        while 0 > (r = trGetC(isa, isad, isan, t) - trGetC(isa, isad, isan, @sa[b]))
          loop do
            @sa[b + 1] = @sa[b]
            break unless first <= (b -= 1) && @sa[b] < 0
          end
          break if b < first
        end

        @sa[b] = ~(@sa[b]) if r == 0
        @sa[b + 1] = t
        a += 1
      end
    end

    @[AlwaysInline]
    private def trLog(x : Int32) : Int32
      if (x & 0xFFFF0000) != 0
        if (x & 0xFF000000) != 0
          24 + LOG2TABLE[(x >> 24) & 0xFF]
        else
          16 + LOG2TABLE[(x >> 16) & 0xFF]
        end
      else
        if(x & 0x0000FF00) != 0
          8 + LOG2TABLE[(x >> 8) & 0xFF]
        else
          LOG2TABLE[x & 0xFF]
        end
      end
    end

    @[AlwaysInline]
    private def trMedian3(isa : Int32, isad : Int32, isan : Int32, v1 : Int32, v2 : Int32, v3 : Int32) : Int32
      sav1 : Int32 = trGetC(isa, isad, isan, @sa[v1])
      sav2 : Int32 = trGetC(isa, isad, isan, @sa[v2])
      sav3 : Int32 = trGetC(isa, isad, isan, @sa[v3])

      if sav1 > sav2
        temp : Int32 = v1
        v1 = v2
        v2 = temp
        savtemp : Int32 = sav1
        sav1 = sav2
        sav2 = savtemp
      end

      if sav2 > sav3
        sav1 > sav3 ? v1 : v3
      else
        v2
      end
    end

    private def trMedian5(isa : Int32, isad : Int32, isan : Int32,
                          v1 : Int32, v2 : Int32, v3 : Int32, v4 : Int32, v5 : Int32) : Int32

      sav1 : Int32 = trGetC(isa, isad, isan, @sa[v1])
      sav2 : Int32 = trGetC(isa, isad, isan, @sa[v2])
      sav3 : Int32 = trGetC(isa, isad, isan, @sa[v3])
      sav4 : Int32 = trGetC(isa, isad, isan, @sa[v4])
      sav5 : Int32 = trGetC(isa, isad, isan, @sa[v5])
      temp : Int32 = 0
      savtemp : Int32 = 0

      if sav2 > sav3
        temp = v2
        v2 = v3
        v3 = temp
        savtemp = sav2
        sav2 = sav3
        sav3 = savtemp
      end

      if sav4 > sav5
        temp = v4
        v4 = v5
        v5 = temp
        savtemp = sav4
        sav4 = sav5
        sav5 = savtemp
      end

      if sav2 > sav4
        temp = v2
        #v2 = v4
        v4 = temp
        savtemp = sav2
        sav2 = sav4
        sav4 = savtemp
        temp = v3
        v3 = v5
        v5 = temp
        savtemp = sav3
        sav3 = sav5
        sav5 = savtemp
      end

      if sav1 > sav3
        temp = v1
        v1 = v3
        v3 = temp
        savtemp = sav1
        sav1 = sav3
        sav3 = savtemp
      end

      if sav1 > sav4
        temp = v1
        #v1 = v4
        v4 = temp
        savtemp = sav1
        sav1 = sav4
        sav4 = savtemp
        temp = v3
        v3 = v5
        #v5 = temp
        savtemp = sav3
        sav3 = sav5
        sav5 = savtemp
      end

      sav3 > sav4 ? v4 : v3
    end

    private def trPivot(isa : Int32, isad : Int32, isan : Int32, first : Int32, last : Int32) : Int32
      t : Int32 = last - first
      middle : Int32 = first + t.tdiv(2)

      if t <= 512
        if t <= 32
          return trMedian3(isa, isad, isan, first, middle, last - 1)
        end
        t >>= 2
        return trMedian5(isa, isad, isan, first, first + t, middle, last - 1 - t, last - 1)
      end

      t >>= 3
      trMedian3(isa, isad, isan,
                trMedian3(isa, isad, isan, first, first + t, first + (t << 1)),
                trMedian3(isa, isad, isan, middle - t, middle, middle + t),
                trMedian3(isa, isad, isan, last - 1 - (t << 1), last - 1 - t, last - 1))
    end

    private def lsUpdateGroup(isa : Int32, first : Int32, last : Int32) : Nil
      b : Int32 = 0
      t : Int32 = 0

      (first...last).each do |a|
        b = 0
        if 0 <= @sa[a]
          b = a
          loop do
            @sa[isa + @sa[a]] = a
            break unless (a += 1) < last && 0 <= @sa[a]
          end

          @sa[b] = b - a
          break if last <= a
        end

        b = a
        loop do
          @sa[a] = ~(@sa[a])
          break unless @sa[a += 1] < 0
        end

        t = a
        loop do
          @sa[isa + @sa[b]] = t
          break unless (b += 1) <= a
        end
      end
    end

    private def lsIntroSort(isa : Int32, isad : Int32, isan : Int32, first : Int32, last : Int32) : Nil
      makeStack
      x : Int32 = 0
      a : Int32 = 0
      b : Int32 = 0
      v : Int32 = 0
      c : Int32 = 0
      d : Int32 = 0
      s : Int32 = 0
      t : Int32 = 0
      e : Int32 = 0
      f : Int32 = 0
      limit : Int32 = trLog(last - first)

      loop do
        if last - first <= INSERTION_SORT_THRESHOLD
          if 1 < last - first
            trInsertionSort(isa, isad, isan, first, last)
            lsUpdateGroup(isa, first, last)
          elsif last - first == 1
            @sa[first] = -1
          end

          return if stackEmpty?
          entry : StackEntry = popStack
          first = entry.a
          last = entry.b
          limit = entry.c
          next
        end

        a = 0
        b = 0
        if limit == 0
          limit -= 1
          trHeapSort(isa, isad, isan, first, last - first)
          a = last - 1
          while first < a
            x = trGetC(isa, isad, isan, @sa[a])
            b = a - 1

            while first <= b && trGetC(isa, isad, isan, @sa[b]) == x
              @sa[b] = ~(@sa[b])
              b -= 1
            end

            a = b
          end

          lsUpdateGroup(isa, first, last)
          return if stackEmpty?
          entry = popStack
          first = entry.a
          last = entry.b
          limit = entry.c
          next
        else
          limit -= 1
        end

        a = trPivot(isa, isad, isan, first, last)
        swap(@sa, first, @sa, a)
        v = trGetC(isa, isad, isan, @sa[first])

        b = first
        while (b += 1) < last && (x = trGetC(isa, isad, isan, @sa[b])) == v
        end

        if (a = b) < last && x < v
          while (b += 1) < last && (x = trGetC(isa, isad, isan, @sa[b])) <= v
            if x == v
              swap(@sa, b, @sa, a)
              a += 1
            end
          end
        end

        c = last
        while b < (c -= 1) && (x = trGetC(isa, isad, isan, @sa[c])) == v
        end

        if b < (d = c) && x > v
          while b < (c -= 1) && (x = trGetC(isa, isad, isan, @sa[c])) >= v
            if x == v
              swap(@sa, c, @sa, d)
              d -= 1
            end
          end
        end

        while b < c
          swap(@sa, b, @sa, c)
          while (b += 1) < c && (c = trGetC(isa, isad, isan, @sa[b])) <= v
            if x == v
              swap(@sa, b, @sa, a)
              a += 1
            end
          end

          while b < (c -= 1) && (x = trGetC(isa, isad, isan, @sa[c])) >= v
            if x == v
              swap(@sa, c, @sa, d)
              d -= 1
            end
          end
        end

        if a <= d
          c = b - 1

          if (s = a - first) > (t = b - a)
            s = t
          end

          e = first
          f = b - s
          while 0 < s
            swap(@sa, e, @sa, f)
            s -= 1
            e += 1
            f += 1
          end

          if (s = d - c) > (t = last - d - 1)
            s = t
          end

          e = b
          f = last - s
          while 0 < s
            swap(@sa, e, @sa, f)
            s -= 1
            e += 1
            f += 1
          end

          a = first + (b - a)
          b = last - (d - c)

          c = first
          v = a - 1
          while c < a
            @sa[isa + @sa[c]] = v
            c +=1
          end

          if b < last
            c = a
            v = b - 1
            while c < b
              @sa[isa + @sa[c]] = v
              c += 1
            end
          end

          @sa[a] = -1 if (b - a) == 1

          if a - first <= last - b
            if first < a
              pushStack(b, last, limit, 0)
              last = a
            else
              first = b
            end
          else
            if b < last
              pushStack(first, a, limit, 0)
              first = b
            else
              last = a
            end
          end
        else # if a <= d
          return if stackEmpty?
          entry = popStack
          first = entry.a
          last = entry.b
          limit = entry.c
        end
      end
    end

    private def lsSort(isa : Int32, x : Int32, depth : Int32) : Nil
      isad : Int32 = isa + depth
      first : Int32 = 0
      skip : Int32 = 0
      last : Int32 = 0
      t : Int32 = 0

      while -x < @sa[0]
        first = 0
        skip = 0
        last = 0
        t = 0

        loop do
          if (t = @sa[first]) < 0
            first -= t
            skip += t
          else
            if skip != 0
              @sa[first + skip] = skip
              skip = 0
            end
            last = @sa[isa + t] + 1
            lsIntroSort(isa, isad, isa + x, first, last)
            first = last
          end

          break unless first < x
        end

        @sa[first + skip] = skip if skip != 0

        if x < (isad - isa)
          first = 0
          loop do
            if (t = @sa[first]) < 0
              first -= t
            else
              last = @sa[isa + t] + 1
              (first...last).each do |i|
                @sa[isa + @sa[i]] = i
              end
              first = last
            end

            break unless first < x
          end
          break
        end

        isad += (isad - isa)
      end
    end

    private def trPartition(isa : Int32, isad : Int32, isan : Int32, first : Int32, last : Int32,
                            v : Int32) : PartitionResult
      a : Int32 = 0
      c : Int32 = 0
      d : Int32 = 0
      t : Int32 = 0
      s : Int32 = 0
      e : Int32 = 0
      f : Int32 = 0
      x : Int32 = 0

      b : Int32 = first - 1
      while (b += 1) < last && (x = trGetC(isa, isad, isan, @sa[b])) == v
      end

      if (a = b) < last && x < v
        while (b += 1) < last && (x = trGetC(isa, isad, isan, @sa[b])) <= v
          if x == v
            swap(@sa, b, @sa, a)
            a += 1
          end
        end
      end

      c = last
      while b < (c -= 1) && (x = trGetC(isa, isad, isan, @sa[c])) == v
      end

      if b < (d = c) && x > v
        while b < (c -= 1) && (x = trGetC(isa, isad, isan, @sa[c])) >= v
          if x == v
            swap(@sa, c, @sa, d)
            d -= 1
          end
        end
      end

      while b < c
        swap(@sa, b, @sa, c)
        while (b += 1) < c && (x = trGetC(isa, isad, isan, @sa[b])) <= v
          if x == v
            swap(@sa, b, @sa, a)
            a += 1
          end
        end

        while b < (c -= 1) && (x = trGetC(isa, isad, isan, @sa[c])) >= v
          if x == v
            swap(@sa, c, @sa, d)
            d -= 1
          end
        end
      end

      if a <= d
        c = b - 1

        if (s = a - first) > (t = b - a)
          s = t
        end

        e = first
        f = b - s
        while 0 < s
          swap(@sa, e, @sa, f)
          s -= 1
          e += 1
          f += 1
        end

        if (s = d - c) > (t = last - d - 1)
          s = t
        end

        e = b
        f = last - s
        while 0 < s
          swap(@sa, e, @sa, f)
          s -=1
          e += 1
          f += 1
        end

        first += (b - a)
        last -= (d - c)
      end

      PartitionResult.new(first, last)
    end

    private def trCopy(isa : Int32, isan : Int32, first : Int32, a : Int32, b : Int32,
                       last : Int32, depth : Int32) : Nil
      c : Int32 = first
      d : Int32 = a - 1
      e : Int32 = 0
      s : Int32 = 0
      v : Int32 = b - 1

      while c <= d
        if (s = @sa[c] - depth) < 0
          s += isan - isa
        end

        if @sa[isa + s] == v
          d += 1
          @sa[d] = s
          @sa[isa + s] = d
        end

        c += 1
      end

      c = last - 1
      e = d + 1
      d = b
      while e < d
        if (s = @sa[c] - depth) < 0
          s += isan - isa
        end

        if @sa[isa + s] == v
          @sa[d -= 1] = s
          @sa[isa + s] = d
        end

        c -= 1
      end
    end

    private def trIntroSort(isa : Int32, isad : Int32, isan : Int32, first : Int32, last : Int32,
                            budget : TRBudget, size : Int32) : Nil
      makeStack
      s : Int32 = 0
      x : Int32 = 0
      a : Int32 = 0
      b : Int32 = 0
      c : Int32 = 0
      v : Int32 = 0
      d : Int32 = 0
      t : Int32 = 0
      e : Int32 = 0
      f : Int32 = 0
      nxt : Int32 = 0

      limit : Int32 = trLog(last - first)
      loop do
        a = 0
        b = 0
        c = 0
        v = 0
        nxt = 0

        if limit < 0
          if limit == -1
            break unless budget.update(size, last - first)
            result : PartitionResult = trPartition(isa, isad - 1, isan, first, last, last - 1)
            a = result.first
            b = result.last

            if first < a || b < last
              if a < last
                c = first
                v = a - 1
                while c < a
                  @sa[isa + @sa[c]] = v
                  c += 1
                end
              end

              if b < last
                c = a
                v = b - 1
                while c < b
                  @sa[isa + @sa[c]] = v
                  c += 1
                end
              end

              pushStack(0, a, b, 0)
              pushStack(isad - 1, first, last, -2)

              if a - first <= last - b
                if 1 < a - first
                  pushStack(isad, b, last, trLog(last - b))
                  last = a
                  limit = trLog(a - first)
                elsif 1 < last - b
                  first = b
                  limit = trLog(last - b)
                else
                  return if stackEmpty?
                  entry : StackEntry = popStack
                  isad = entry.a
                  first = entry.b
                  last = entry.c
                  limit = entry.d
                end

              else
                if 1 < last - b
                  pushStack(isad, first, a, trLog(a - first))
                  first = b
                  limit = trLog(last - b)
                elsif 1 < a - first
                  last = a
                  limit = trLog(a - first)
                else
                  return if stackEmpty?
                  entry = popStack
                  isad = entry.a
                  first = entry.b
                  last = entry.c
                  limit = entry.d
                end
              end

            else
              c = first
              while c < last
                @sa[isa + @sa[c]] = c
                c += 1
              end

              return if stackEmpty?
              entry = popStack
              isad = entry.a
              first = entry.b
              last = entry.c
              limit = entry.d
            end

          elsif limit == -2 # if limit == -1
            entry = popStack
            a = entry.b
            b = entry.c
            trCopy(isa, isan, first, a, b, last, isad - isa)

            return if stackEmpty?
            entry = popStack
            isad = entry.a
            first = entry.b
            last = entry.c
            limit = entry.d

          else
            if 0 <= @sa[first]
              a = first
              loop do
                @sa[isa + @sa[a]] = a
                break unless (a += 1) < last && 0 <= @sa[a]
              end
              first = a
            end

            if first < last
              a = first
              loop do
                @sa[a] = ~(@sa[a])
                break unless @sa[a += 1] < 0
              end

              nxt = if @sa[isa + @sa[a]] != @sa[isad + @sa[a]]
                      trLog(a - first + 1)
                    else
                      -1
                    end

              if (a += 1) < last
                b = first
                v = a - 1
                while b < a
                  @sa[isa + @sa[b]] = v
                  b += 1
                end
              end

              if a - first <= last - a
                pushStack(isad, a, last, -3)
                isad += 1
                last = a
                limit = nxt
              else
                if 1 < last - a
                  pushStack(isad + 1, first, a, nxt)
                  first = a
                  limit = -3
                else
                  isad += 1
                  last = a
                  limit = nxt
                end
              end

            else # if first < last
              return if stackEmpty?
              entry = popStack
              isad = entry.a
              first = entry.b
              last = entry.c
              limit = entry.d
            end
          end # if limit == -1
          next
        end # if limit < 0

        if last - first <= INSERTION_SORT_THRESHOLD
          break unless budget.update(size, last - first)
          trInsertionSort(isa, isad, isan, first, last)
          limit = -3
          next
        end

        if limit == 0
          limit -= 1
          break unless budget.update(size, last - first)
          trHeapSort(isa, isad, isan, first, last - first)

          a = last - 1
          while first < a
            x = trGetC(isa, isad, isan, @sa[a])
            b = a - 1

            while first <= b && trGetC(isa, isad, isan, @sa[b]) == x
              @sa[b] = ~(@sa[b])
              b -= 1
            end

            a = b
          end

          limit = -3
          next
        else
          limit -= 1
        end

        a = trPivot(isa, isad, isan, first, last)

        swap(@sa, first, @sa, a)
        v = trGetC(isa, isad, isan, @sa[first])
        b = first
        while (b += 1) < last && (x = trGetC(isa, isad, isan, @sa[b])) == v
        end

        if (a = b) < last && x < v
          while (b += 1) < last && (x = trGetC(isa, isad, isan, @sa[b])) <= v
            if x == v
              swap(@sa, b, @sa, a)
              a += 1
            end
          end
        end

        c = last
        while b < (c -= 1) && (x = trGetC(isa, isad, isan, @sa[c])) == v
        end

        if b < (d = c) && x > v
          while b < (c -= 1) && (x = trGetC(isa, isad, isan, @sa[c])) >= v
            if x == v
              swap(@sa, c, @sa, d)
              d -= 1
            end
          end
        end

        while b < c
          swap(@sa, b, @sa, c)

          while (b += 1) < c && (x = trGetC(isa, isad, isan, @sa[b])) <= v
            if x == v
              swap(@sa, b, @sa, a)
              a += 1
            end
          end

          while b < (c -= 1) && (x = trGetC(isa, isad, isan, @sa[c])) >= v
            if x == v
              swap(@sa, c, @sa, d)
              d -= 1
            end
          end
        end

        if a <= d
          c = b - 1

          if (s = a - first) > (t = b - a)
            s = t
          end

          e = first
          f = b - s
          while 0 < s
            swap(@sa, e, @sa, f)
            s -= 1
            e += 1
            f += 1
          end

          if (s = d - c) > (t = last - d - 1)
            s = t
          end

          e = b
          f = last - s
          while 0 < s
            swap(@sa, e, @sa, f)
            s -= 1
            e += 1
            f += 1
          end

          a = first + (b - a)
          b = last - (d - c)
          nxt = if @sa[isa + @sa[a]] != v
                  trLog(b - a)
                else
                  -1
                end

          c = first
          v = a - 1
          while c < a
            @sa[isa + @sa[c]] = v
            c += 1
          end

          if b < last
            c = a
            v = b - 1
            while c < b
              @sa[isa + @sa[c]] = v
              c += 1
            end
          end

          if a - first <= last - b
            if last - b <= b - a
              if 1 < a - first
                pushStack(isad + 1, a, b, nxt)
                pushStack(isad, b, last, limit)
                last = a
              elsif 1 < last - b
                pushStack(isad + 1, a, b, nxt)
                first = b
              elsif 1 < b - a
                isad += 1
                first = a
                last = b
                limit = nxt
              else
                return if stackEmpty?
                entry = popStack
                isad = entry.a
                first = entry.b
                last = entry.c
                limit = entry.d
              end

            elsif a - first <= b - a
              if 1 < a - first
                pushStack(isad, b, last, limit)
                pushStack(isad + 1, a, b, nxt)
                last = a
              elsif 1 < b - a
                pushStack(isad, b, last, limit)
                isad += 1
                first = a
                last = b
                limit = nxt
              else
                first = b
              end

            else
              if 1 < b - a
                pushStack(isad, b, last, limit)
                pushStack(isad, first, a, limit)
                isad += 1
                first = a
                last = b
                limit = nxt
              else
                pushStack(isad, b, last, limit)
                last = a
              end
            end # if last - b <= b - a

          else # if a - first <= last - b
            if a - first <= b - a
              if 1 < last - b
                pushStack(isad + 1, a, b, nxt)
                pushStack(isad, first, a, limit)
                first = b
              elsif 1 < a - first
                pushStack(isad + 1, a, b, nxt)
                last = a
              elsif 1 < b - a
                isad += 1
                first = a
                last = b
                limit = nxt
              else
                pushStack(isad, first, last, limit)
              end

            elsif last - b <= b - a
              if 1 < last - b
                pushStack(isad, first, a, limit)
                pushStack(isad + 1, a, b, nxt)
                first = b
              elsif 1 < b - a
                pushStack(isad, first, a, limit)
                isad += 1
                first = a
                last = b
                limit = nxt
              else
                last = a
              end

            else
              if 1 < b - a
                pushStack(isad, first, a, limit)
                pushStack(isad, b, last, limit)
                isad += 1
                first = a
                last = b
                limit = nxt
              else
                pushStack(isad, first, a, limit)
                first = b
              end
            end
          end
        else
          break unless budget.update(size, last - first)
          limit += 1
          isad += 1
        end
      end # loop do

      @ssize.times do |z|
        if @stack[z].d == -3
          lsUpdateGroup(isa, @stack[z].b, @stack[z].c)
        end
      end
    end

    private def trSort(isa : Int32, x : Int32, depth : Int32) : Nil
      first : Int32 = 0

      if -x < @sa.unsafe_fetch(0)
        budget : TRBudget = TRBudget.new(x, (trLog(x) * 2 / 3 + 1).to_i32!)
        t : Int32 = 0
        last : Int32 = 0

        loop do
          if (t = @sa.unsafe_fetch(first)) < 0
            first -= t
          else
            last = @sa.unsafe_fetch(isa + t) + 1
            if 1 < (last - first)
              trIntroSort(isa, isa + depth, isa + x, first, last, budget, x)
              if budget.chance == 0
                # Switch to Larsson-Sadakane sorting algorithm.
                @sa.unsafe_put(0, -first) if 0 < first
                lsSort(isa, x, depth)
                break
              end
            end

            first = last
          end

          break unless first < x
        end
      end
    end

    @[AlwaysInline]
    protected def self.bucketB(c0 : Int32, c1 : Int32) : Int32
      (c1 << 8) | c0
    end

    @[AlwaysInline]
    protected def self.bucketBStar(c0 : Int32, c1 : Int32) : Int32
      (c0 << 8) | c1
    end

    private def sortTypeBstar(bucketA : Array(Int32), bucketB : Array(Int32)) : Int32
      @int32Pool.withRentedArray(256) do |tempBuf|
        tempBuf.fill(0)
        j : Int32 = 0
        k : Int32 = 0
        t : Int32 = 0
        c0 : Int32 = 0
        c1 : Int32 = 0

        i : Int32 = 1
        flag : Int32 = 1
        while i < @n
          if @t[i - 1] != @t[i]
            if @t[i - 1] > @t[i]
              flag = 0
            end
            break
          end
          i += 1
        end

        i = @n - 1
        m : Int32 = @n

        ti : Int32 = @t[i].to_i32!
        t0 : Int32 = @t[0].to_i32!
        ti1 : Int32 = 0
        if ti < t0 || (@t[i] == @t[0] && flag != 0)
          if flag == 0
            bucketB[DivSufSort.bucketBStar(ti, t0)] += 1
            @sa[m -= 1] = i
          else
            bucketB[DivSufSort.bucketB(ti, t0)] += 1
          end

          i -= 1
          while 0 <= i && (ti = @t[i].to_i32!) <= (ti1 = @t[i + 1].to_i32!)
            bucketB[DivSufSort.bucketB(ti, ti1)] += 1
            i -= 1
          end
        end

        while 0 <= i
          loop do
            bucketA[@t[i]] += 1
            break unless 0 <= (i -= 1) && @t[i] >= @t[i + 1]
          end

          if 0 <= i
            bucketB[DivSufSort.bucketBStar(@t[i].to_i32!, @t[i + 1].to_i32!)] += 1
            @sa[m -= 1] = i

            i -= 1
            while 0 <= i && (ti = @t[i].to_i32!) <= (ti1 = @t[i + 1].to_i32!)
              bucketB[DivSufSort.bucketB(ti, ti1)] += 1
              i -= 1
            end
          end
        end

        m = @n - m
        if m == 0
          @n.times { |z| @sa[z] = z }
          return 0
        end

        c0 = 0
        i = -1
        j = 0
        while c0 < 256
          t = i + bucketA[c0]
          bucketA[c0] = i + j
          i = t + bucketB[DivSufSort.bucketB(c0, c0)]

          c1 = c0 + 1
          while c1 < 256
            j += bucketB[DivSufSort.bucketBStar(c0, c1)]
            bucketB[(c0 << 8) | c1] = j
            i += bucketB[DivSufSort.bucketB(c0, c1)]
            c1 += 1
          end

          c0 += 1
        end

        pab : Int32 = @n - m
        isab : Int32 = m
        i = m - 2
        while 0 <= i
          t = @sa[pab + i]
          c0 = @t[t].to_i32!
          c1 = @t[t + 1].to_i32!
          @sa[(bucketB[DivSufSort.bucketBStar(c0, c1)] -= 1)] = i
          i -= 1
        end

        t = @sa[pab + m - 1]
        c0 = @t[t].to_i32!
        c1 = @t[t + 1].to_i32!
        @sa[bucketB[DivSufSort.bucketBStar(c0, c1)] -= 1] = m - 1

        buf : Array(Int32) = @sa
        bufOffset : Int32 = m
        bufSize : Int32 = @n - (2 * m)
        if bufSize <= 256
          buf = tempBuf
          bufOffset = 0
          bufSize = 256
        end

        c0 = 255
        j = m
        while 0 < j
          c1 = 255
          while c0 < c1
            i = bucketB[DivSufSort.bucketBStar(c0, c1)]
            if 1 < j - i
              subStringSort(pab, i, j, buf, bufOffset, bufSize, 2, @sa[i] == (m - 1), @n)
            end

            j = i
            c1 -= 1
          end

          c0 -= 1
        end

        i = m - 1
        while 0 <= i
          if 0 <= @sa[i]
            j = i
            loop do
              @sa[isab + @sa[i]] = i
              break unless 0 <= (i -= 1) && 0 <= @sa[i]
            end

            @sa[i + 1] = i - j
            break if i <= 0
          end

          j = i
          loop do
            @sa[isab + (@sa[i] = ~(@sa[i]))] = j
            break unless @sa[i -= 1] < 0
          end

          @sa[isab + @sa[i]] = j
          i -= 1
        end

        trSort(isab, m, 1)

        i = @n - 1
        j = m

        if @t[i] < @t[0] || (@t[i] == @t[0] && flag != 0)
          if flag == 0
            @sa[@sa[isab + (j -= 1)]] = i
          end

          i -= 1
          while 0 <= i && @t[i] <= @t[i + 1]
            i -= 1
          end
        end

        while 0 <= i
          i -= 1
          while 0 <= i && @t[i] >= @t[i + 1]
            i -= 1
          end

          if 0 <= i
            @sa[@sa[isab + (j -= 1)]] = i

            i -= 1
            while 0 <= i && @t[i] <= @t[i + 1]
              i -= 1
            end
          end
        end

        c0 = 255
        i = @n - 1
        k = m - 1
        while 0 <= c0
          c1 = 255
          while c0 < c1
            t = i - bucketB[DivSufSort.bucketB(c0, c1)]
            bucketB[DivSufSort.bucketB(c0, c1)] = i + 1

            i = t
            j = bucketB[DivSufSort.bucketBStar(c0, c1)]
            while j <= k
              @sa[i] = @sa[k]
              i -= 1
              k -= 1
            end

            c1 -= 1
          end

          t = i - bucketB[DivSufSort.bucketB(c0, c0)]
          bucketB[DivSufSort.bucketB(c0, c0)] = i + 1
          if c0 < 255
            bucketB[DivSufSort.bucketBStar(c0, c0 + 1)] = t + 1
          end
          i = bucketA[c0]

          c0 -= 1
        end

        m
      end
    end

    private def constructBWT(bucketA : Array(Int32), bucketB : Array(Int32)) : Int32
      i : Int32 = 0
      t : Int32 = 0
      s : Int32 = 0
      s1 : Int32 = 0
      c0 : Int32 = 0
      c2 : Int32 = 0
      orig : Int32 = -1
      j : Int32 = 0

      c1 : Int32 = 254
      while 0 <= c1
        i = bucketB[DivSufSort.bucketBStar(c1, c1 + 1)]
        j = bucketA[c1 + 1]
        t = 0
        c2 = -1

        while i <= j
          s1 = s = @sa[j]
          if 0 <= s1
            if (s -= 1) < 0
              s = @n - 1
            end

            c0 = @t[s].to_i32!
            if c0 <= c1
              @sa[j] = ~s1
              if 0 < s && @t[s - 1] > c0
                s = ~s
              end

              if c2 == c0
                @sa[t -= 1] = s
              else
                if 0 <= c2
                  bucketB[DivSufSort.bucketB(c2, c1)] = t
                end

                c2 = c0
                t = bucketB[DivSufSort.bucketB(c2, c1)] - 1
                @sa[t] = s
              end
            end
          else
            @sa[j] = ~s
          end

          j -= 1
        end

        c1 -= 1
      end

      @n.times do |i|
        s1 = s = @sa[i]

        if 0 <= s1
          if (s -= 1) < 0
            s = @n - 1
          end

          if (c0 = @t[s].to_i32!) >= @t[s + 1]
            if 0 < s && @t[s - 1] < c0
              s = ~s
            end

            if c0 == c2
              @sa[t += 1] = s
            else
              if c2 != -1 # BUGFIX: Original code can write to bucketA[-1]
                bucketA[c2] = t
              end

              c2 = c0
              t = bucketA[c2] + 1
              @sa[t] = s
            end
          end
        else
          s1 = ~s1
        end

        if s1 == 0
          @sa[i] = @t[@n - 1].to_i32!
          orig = i
        else
          @sa[i] = @t[s1 - 1].to_i32!
        end
      end

      orig
    end
  end
end
