ByteArrayTimSortTest.kt

TLDR

This file contains a test class ByteArrayTimSortTest that tests the functionality of the ByteArrayTimSort class. It includes multiple test methods that sort arrays of bytes using different strategies and compare the results to expected values.

Methods

smallArray1BytePerEntry

This method tests the sorting of a small array with 1 byte per entry using the ByteArrayTimSort.sort method. It compares the sorted result to the expected array.

smallArray3BytesPerEntry1ByteKey

This method tests the sorting of a small array with 3 bytes per entry and 1 byte key using the ByteArrayTimSort.sort method. It sorts the array based on the first byte and compares the result to the expected array.

largeRandomArray8BytesPerEntry4BytesKey

This method tests the sorting of a large random array with 8 bytes per entry and 4 bytes key using the ByteArrayTimSort.sort method. It creates an array of custom Entry objects, sorts them using the compareTo method, converts the sorted array back to bytes, and compares it to the expected result.

readInt

This method reads an integer from a byte array starting from the specified index.

Classes

ByteArrayTimSortTest

This class contains test methods for the ByteArrayTimSort class. It tests the sorting functionality of the ByteArrayTimSort.sort method using different scenarios.

package shark

import kotlin.random.Random
import org.assertj.core.api.Assertions.assertThat
import org.junit.Test
import shark.internal.aosp.ByteArrayTimSort

class ByteArrayTimSortTest {

  @Test fun smallArray1BytePerEntry() {
    val toSort = byteArrayOf(2, 1, 4)

    ByteArrayTimSort.sort(toSort, 0, 3, 1) { _, o1Array, o1Index, o2Array, o2Index ->
      o1Array[o1Index].compareTo(o2Array[o2Index])
    }
    assertThat(toSort).containsExactly(1, 2, 4)
  }

  @Test fun smallArray3BytesPerEntry1ByteKey() {
    val toSort = byteArrayOf(2, 3, 3, 1, 5, 5, 4, 6, 6)

    ByteArrayTimSort.sort(toSort, 3) { entrySize, o1Array, o1Index, o2Array, o2Index ->
      // Sort based on first byte
      o1Array[o1Index * entrySize].compareTo(o2Array[o2Index * entrySize])
    }
    assertThat(toSort).containsExactly(1, 5, 5, 2, 3, 3, 4, 6, 6)
  }

  @Test fun largeRandomArray8BytesPerEntry4BytesKey() {
    val entryCount = 10000
    val entrySize = 8
    val random = Random(Int.MIN_VALUE)
    val librarySorted = random.nextBytes(entryCount * entrySize)

    class Entry(val eightBytes: ByteArray) : Comparable<Entry> {
      override fun compareTo(other: Entry): Int {
        val compared = readInt(eightBytes, 0).compareTo(readInt(other.eightBytes, 0))
        if (compared == 0) {
          return readInt(eightBytes, 4).compareTo(readInt(other.eightBytes, 4))
        }
        return compared
      }
    }

    val androidSorted = arrayOfNulls<Entry>(entryCount)
    for (i in 0 until entryCount) {
      val index = i * entrySize
      androidSorted[i] = Entry(librarySorted.copyOfRange(index, index + entrySize))
    }
    androidSorted.sort()
    val androidSortedAsBytes = ByteArray(entryCount * entrySize)

    for (i in 0 until entryCount) {
      System.arraycopy(
        androidSorted[i]!!.eightBytes, 0, androidSortedAsBytes, i * entrySize, entrySize
      )
    }

    ByteArrayTimSort.sort(librarySorted, entrySize) { entrySize, o1Array, o1Index, o2Array, o2Index ->
      val compared = readInt(o1Array, o1Index * entrySize)
        .compareTo(readInt(o2Array, o2Index * entrySize))
      if (compared == 0) {
        readInt(o1Array, o1Index * entrySize + 4).compareTo(
          readInt(o2Array, o2Index * entrySize + 4)
        )
      }
      compared
    }

    assertThat(librarySorted.asList()).isEqualTo(androidSortedAsBytes.asList())
  }

  fun readInt(
    array: ByteArray,
    index: Int
  ): Int {
    var pos = index
    return (array[pos++] and 0xff shl 24
      or (array[pos++] and 0xff shl 16)
      or (array[pos++] and 0xff shl 8)
      or (array[pos] and 0xff))
  }

  @Suppress("NOTHING_TO_INLINE") // Syntactic sugar.
  private inline infix fun Byte.and(other: Int): Int = toInt() and other
}