<lambda>null1 package shark
2
3 import kotlin.random.Random
4 import org.assertj.core.api.Assertions.assertThat
5 import org.junit.Test
6 import shark.internal.aosp.ByteArrayTimSort
7
8 class ByteArrayTimSortTest {
9
10 @Test fun smallArray1BytePerEntry() {
11 val toSort = byteArrayOf(2, 1, 4)
12
13 ByteArrayTimSort.sort(toSort, 0, 3, 1) { _, o1Array, o1Index, o2Array, o2Index ->
14 o1Array[o1Index].compareTo(o2Array[o2Index])
15 }
16 assertThat(toSort).containsExactly(1, 2, 4)
17 }
18
19 @Test fun smallArray3BytesPerEntry1ByteKey() {
20 val toSort = byteArrayOf(2, 3, 3, 1, 5, 5, 4, 6, 6)
21
22 ByteArrayTimSort.sort(toSort, 3) { entrySize, o1Array, o1Index, o2Array, o2Index ->
23 // Sort based on first byte
24 o1Array[o1Index * entrySize].compareTo(o2Array[o2Index * entrySize])
25 }
26 assertThat(toSort).containsExactly(1, 5, 5, 2, 3, 3, 4, 6, 6)
27 }
28
29 @Test fun largeRandomArray8BytesPerEntry4BytesKey() {
30 val entryCount = 10000
31 val entrySize = 8
32 val random = Random(Int.MIN_VALUE)
33 val librarySorted = random.nextBytes(entryCount * entrySize)
34
35 class Entry(val eightBytes: ByteArray) : Comparable<Entry> {
36 override fun compareTo(other: Entry): Int {
37 val compared = readInt(eightBytes, 0).compareTo(readInt(other.eightBytes, 0))
38 if (compared == 0) {
39 return readInt(eightBytes, 4).compareTo(readInt(other.eightBytes, 4))
40 }
41 return compared
42 }
43 }
44
45 val androidSorted = arrayOfNulls<Entry>(entryCount)
46 for (i in 0 until entryCount) {
47 val index = i * entrySize
48 androidSorted[i] = Entry(librarySorted.copyOfRange(index, index + entrySize))
49 }
50 androidSorted.sort()
51 val androidSortedAsBytes = ByteArray(entryCount * entrySize)
52
53 for (i in 0 until entryCount) {
54 System.arraycopy(
55 androidSorted[i]!!.eightBytes, 0, androidSortedAsBytes, i * entrySize, entrySize
56 )
57 }
58
59 ByteArrayTimSort.sort(librarySorted, entrySize) { entrySize, o1Array, o1Index, o2Array, o2Index ->
60 val compared = readInt(o1Array, o1Index * entrySize)
61 .compareTo(readInt(o2Array, o2Index * entrySize))
62 if (compared == 0) {
63 readInt(o1Array, o1Index * entrySize + 4).compareTo(
64 readInt(o2Array, o2Index * entrySize + 4)
65 )
66 }
67 compared
68 }
69
70 assertThat(librarySorted.asList()).isEqualTo(androidSortedAsBytes.asList())
71 }
72
73 fun readInt(
74 array: ByteArray,
75 index: Int
76 ): Int {
77 var pos = index
78 return (array[pos++] and 0xff shl 24
79 or (array[pos++] and 0xff shl 16)
80 or (array[pos++] and 0xff shl 8)
81 or (array[pos] and 0xff))
82 }
83
84 @Suppress("NOTHING_TO_INLINE") // Syntactic sugar.
85 private inline infix fun Byte.and(other: Int): Int = toInt() and other
86 }
87