1/*
2 * Copyright (C) 2022 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *      http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17import {ArrayUtils} from './array_utils';
18
19describe('ArrayUtils', () => {
20  it('equal', () => {
21    expect(ArrayUtils.equal([], [1])).toBeFalse();
22    expect(ArrayUtils.equal([1], [])).toBeFalse();
23
24    expect(ArrayUtils.equal([], [])).toBeTrue();
25    expect(ArrayUtils.equal([undefined], [undefined])).toBeTrue();
26    expect(ArrayUtils.equal([1, 2, 3], [1, 2, 3])).toBeTrue();
27
28    expect(ArrayUtils.equal([], new Uint8Array(1))).toBeFalse();
29    expect(ArrayUtils.equal([1], new Uint8Array(1))).toBeFalse();
30
31    expect(ArrayUtils.equal([], new Uint8Array())).toBeTrue();
32    expect(ArrayUtils.equal([], new Uint8Array())).toBeTrue();
33    expect(ArrayUtils.equal([1, 2, 3], new Uint8Array([1, 2, 3]))).toBeTrue();
34
35    expect(
36      ArrayUtils.equal(new Uint8Array([]), new Uint8Array([1])),
37    ).toBeFalse();
38    expect(
39      ArrayUtils.equal(new Uint8Array([1]), new Uint8Array([])),
40    ).toBeFalse();
41
42    expect(ArrayUtils.equal(new Uint8Array([]), new Uint8Array([]))).toBeTrue();
43    expect(
44      ArrayUtils.equal(new Uint8Array([1, 2, 3]), new Uint8Array([1, 2, 3])),
45    ).toBeTrue();
46  });
47
48  it('searchSubarray', () => {
49    expect(ArrayUtils.searchSubarray([], [0])).toEqual(undefined);
50    expect(ArrayUtils.searchSubarray([], [])).toEqual(0);
51    expect(ArrayUtils.searchSubarray([0], [])).toEqual(0);
52
53    expect(ArrayUtils.searchSubarray([0, 1, 2], [-1])).toEqual(undefined);
54    expect(ArrayUtils.searchSubarray([0, 1, 2], [])).toEqual(0);
55    expect(ArrayUtils.searchSubarray([0, 1, 2], [0])).toEqual(0);
56    expect(ArrayUtils.searchSubarray([0, 1, 2], [1])).toEqual(1);
57    expect(ArrayUtils.searchSubarray([0, 1, 2], [2])).toEqual(2);
58
59    expect(ArrayUtils.searchSubarray([0, 1, 2], [0, 1])).toEqual(0);
60    expect(ArrayUtils.searchSubarray([0, 1, 2], [1, 2])).toEqual(1);
61    expect(ArrayUtils.searchSubarray([0, 1, 2], [2])).toEqual(2);
62    expect(ArrayUtils.searchSubarray([0, 1, 2], [2, 3])).toEqual(undefined);
63  });
64
65  it('binarySearchFirstGreaterOrEqual', () => {
66    // no match
67    expect(ArrayUtils.binarySearchFirstGreaterOrEqual([], 9)).toBeUndefined();
68    expect(ArrayUtils.binarySearchFirstGreaterOrEqual([8], 9)).toBeUndefined();
69    expect(
70      ArrayUtils.binarySearchFirstGreaterOrEqual([7, 8], 9),
71    ).toBeUndefined();
72    expect(
73      ArrayUtils.binarySearchFirstGreaterOrEqual([6, 7, 8], 9),
74    ).toBeUndefined();
75
76    // match (greater)
77    expect(ArrayUtils.binarySearchFirstGreaterOrEqual([6], 5)).toEqual(0);
78    expect(ArrayUtils.binarySearchFirstGreaterOrEqual([6, 7], 5)).toEqual(0);
79    expect(ArrayUtils.binarySearchFirstGreaterOrEqual([4, 6], 5)).toEqual(1);
80    expect(ArrayUtils.binarySearchFirstGreaterOrEqual([4, 6, 7, 8], 5)).toEqual(
81      1,
82    );
83    expect(
84      ArrayUtils.binarySearchFirstGreaterOrEqual([3, 4, 6, 7, 8], 5),
85    ).toEqual(2);
86
87    // match (equal)
88    expect(ArrayUtils.binarySearchFirstGreaterOrEqual([5], 5)).toEqual(0);
89    expect(ArrayUtils.binarySearchFirstGreaterOrEqual([5, 6], 5)).toEqual(0);
90    expect(ArrayUtils.binarySearchFirstGreaterOrEqual([4, 5], 5)).toEqual(1);
91    expect(ArrayUtils.binarySearchFirstGreaterOrEqual([3, 4, 5], 5)).toEqual(2);
92    expect(ArrayUtils.binarySearchFirstGreaterOrEqual([3, 4, 5, 6], 5)).toEqual(
93      2,
94    );
95    expect(
96      ArrayUtils.binarySearchFirstGreaterOrEqual([3, 4, 5, 6, 7], 5),
97    ).toEqual(2);
98
99    // match (equal with repeated values)
100    expect(ArrayUtils.binarySearchFirstGreaterOrEqual([5, 5], 5)).toEqual(0);
101    expect(ArrayUtils.binarySearchFirstGreaterOrEqual([5, 5, 5], 5)).toEqual(0);
102    expect(ArrayUtils.binarySearchFirstGreaterOrEqual([5, 5, 5, 5], 5)).toEqual(
103      0,
104    );
105    expect(ArrayUtils.binarySearchFirstGreaterOrEqual([4, 5, 5, 6], 5)).toEqual(
106      1,
107    );
108    expect(
109      ArrayUtils.binarySearchFirstGreaterOrEqual([4, 4, 5, 5, 5, 6], 5),
110    ).toEqual(2);
111    expect(
112      ArrayUtils.binarySearchFirstGreaterOrEqual([4, 4, 4, 5, 5, 5, 5, 6], 5),
113    ).toEqual(3);
114  });
115
116  it('binarySearchFirstGreater', () => {
117    // no match
118    expect(ArrayUtils.binarySearchFirstGreater([], 9)).toBeUndefined();
119    expect(ArrayUtils.binarySearchFirstGreater([8], 9)).toBeUndefined();
120    expect(ArrayUtils.binarySearchFirstGreater([7, 8], 9)).toBeUndefined();
121    expect(ArrayUtils.binarySearchFirstGreater([6, 7, 8], 9)).toBeUndefined();
122
123    // match
124    expect(ArrayUtils.binarySearchFirstGreater([6], 5)).toEqual(0);
125    expect(ArrayUtils.binarySearchFirstGreater([6, 7], 5)).toEqual(0);
126    expect(ArrayUtils.binarySearchFirstGreater([4, 6], 5)).toEqual(1);
127    expect(ArrayUtils.binarySearchFirstGreater([4, 6, 7, 8], 5)).toEqual(1);
128    expect(ArrayUtils.binarySearchFirstGreater([3, 4, 6, 7, 8], 5)).toEqual(2);
129
130    // match (ignore equal)
131    expect(ArrayUtils.binarySearchFirstGreater([5], 5)).toEqual(undefined);
132    expect(ArrayUtils.binarySearchFirstGreater([5, 6], 5)).toEqual(1);
133    expect(ArrayUtils.binarySearchFirstGreater([4, 5, 6], 5)).toEqual(2);
134    expect(ArrayUtils.binarySearchFirstGreater([3, 4, 5, 6], 5)).toEqual(3);
135    expect(ArrayUtils.binarySearchFirstGreater([3, 4, 5, 6, 7], 5)).toEqual(3);
136
137    // match (with repeated values)
138    expect(ArrayUtils.binarySearchFirstGreater([6, 6], 5)).toEqual(0);
139    expect(ArrayUtils.binarySearchFirstGreater([6, 6, 6], 5)).toEqual(0);
140    expect(ArrayUtils.binarySearchFirstGreater([6, 6, 6, 6], 5)).toEqual(0);
141    expect(ArrayUtils.binarySearchFirstGreater([5, 6, 6, 7], 5)).toEqual(1);
142    expect(ArrayUtils.binarySearchFirstGreater([5, 5, 6, 6, 6, 7], 5)).toEqual(
143      2,
144    );
145    expect(
146      ArrayUtils.binarySearchFirstGreater([5, 5, 5, 6, 6, 6, 6, 7], 5),
147    ).toEqual(3);
148  });
149
150  it('toUintLittleEndian', () => {
151    const buffer = new Uint8Array([0, 0, 1, 1]);
152
153    expect(
154      ArrayUtils.toUintLittleEndian(new Uint8Array([0xff, 0xff]), 0, -1),
155    ).toEqual(0n);
156    expect(
157      ArrayUtils.toUintLittleEndian(new Uint8Array([0xff, 0xff]), 0, 0),
158    ).toEqual(0n);
159    expect(
160      ArrayUtils.toUintLittleEndian(new Uint8Array([0xff, 0xff]), 1, 1),
161    ).toEqual(0n);
162
163    expect(
164      ArrayUtils.toUintLittleEndian(new Uint8Array([0x00, 0x01, 0xff]), 0, 1),
165    ).toEqual(0n);
166    expect(
167      ArrayUtils.toUintLittleEndian(new Uint8Array([0x00, 0x01, 0xff]), 1, 2),
168    ).toEqual(1n);
169    expect(
170      ArrayUtils.toUintLittleEndian(new Uint8Array([0x00, 0x01, 0xff]), 2, 3),
171    ).toEqual(255n);
172
173    expect(
174      ArrayUtils.toUintLittleEndian(new Uint8Array([0x00, 0x00]), 0, 2),
175    ).toEqual(0n);
176    expect(
177      ArrayUtils.toUintLittleEndian(new Uint8Array([0x01, 0x00]), 0, 2),
178    ).toEqual(1n);
179    expect(
180      ArrayUtils.toUintLittleEndian(new Uint8Array([0x00, 0x01]), 0, 2),
181    ).toEqual(256n);
182    expect(
183      ArrayUtils.toUintLittleEndian(new Uint8Array([0xff, 0xff]), 0, 2),
184    ).toEqual(0xffffn);
185
186    expect(
187      ArrayUtils.toUintLittleEndian(
188        new Uint8Array([0xff, 0xff, 0xff, 0xff]),
189        0,
190        4,
191      ),
192    ).toEqual(0xffffffffn);
193
194    expect(
195      ArrayUtils.toUintLittleEndian(
196        new Uint8Array([0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff]),
197        0,
198        8,
199      ),
200    ).toEqual(0xffffffffffffffffn);
201
202    expect(
203      ArrayUtils.toUintLittleEndian(
204        new Uint8Array([0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff]),
205        0,
206        9,
207      ),
208    ).toEqual(0xffffffffffffffffffn);
209  });
210
211  it('toIntLittleEndian', () => {
212    expect(ArrayUtils.toIntLittleEndian(new Uint8Array([0xff]), 0, -1)).toEqual(
213      0n,
214    );
215    expect(ArrayUtils.toIntLittleEndian(new Uint8Array([0xff]), 0, 0)).toEqual(
216      0n,
217    );
218
219    expect(ArrayUtils.toIntLittleEndian(new Uint8Array([0x00]), 0, 1)).toEqual(
220      0n,
221    );
222    expect(ArrayUtils.toIntLittleEndian(new Uint8Array([0x01]), 0, 1)).toEqual(
223      1n,
224    );
225    expect(ArrayUtils.toIntLittleEndian(new Uint8Array([0x7f]), 0, 1)).toEqual(
226      127n,
227    );
228    expect(ArrayUtils.toIntLittleEndian(new Uint8Array([0x80]), 0, 1)).toEqual(
229      -128n,
230    );
231    expect(ArrayUtils.toIntLittleEndian(new Uint8Array([0xff]), 0, 1)).toEqual(
232      -1n,
233    );
234
235    expect(
236      ArrayUtils.toIntLittleEndian(new Uint8Array([0xff, 0x7f]), 0, 2),
237    ).toEqual(32767n);
238    expect(
239      ArrayUtils.toIntLittleEndian(new Uint8Array([0x00, 0x80]), 0, 2),
240    ).toEqual(-32768n);
241    expect(
242      ArrayUtils.toIntLittleEndian(new Uint8Array([0x01, 0x80]), 0, 2),
243    ).toEqual(-32767n);
244    expect(
245      ArrayUtils.toIntLittleEndian(new Uint8Array([0xff, 0xff]), 0, 2),
246    ).toEqual(-1n);
247
248    expect(
249      ArrayUtils.toIntLittleEndian(
250        new Uint8Array([0xff, 0xff, 0xff, 0x7f]),
251        0,
252        4,
253      ),
254    ).toEqual(0x7fffffffn);
255    expect(
256      ArrayUtils.toIntLittleEndian(
257        new Uint8Array([0x00, 0x00, 0x00, 0x80]),
258        0,
259        4,
260      ),
261    ).toEqual(-0x80000000n);
262    expect(
263      ArrayUtils.toIntLittleEndian(
264        new Uint8Array([0x01, 0x00, 0x00, 0x80]),
265        0,
266        4,
267      ),
268    ).toEqual(-0x7fffffffn);
269    expect(
270      ArrayUtils.toIntLittleEndian(
271        new Uint8Array([0xff, 0xff, 0xff, 0xff]),
272        0,
273        4,
274      ),
275    ).toEqual(-1n);
276
277    expect(
278      ArrayUtils.toIntLittleEndian(
279        new Uint8Array([0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x7f]),
280        0,
281        8,
282      ),
283    ).toEqual(0x7fffffffffffffffn);
284    expect(
285      ArrayUtils.toIntLittleEndian(
286        new Uint8Array([0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x80]),
287        0,
288        8,
289      ),
290    ).toEqual(-0x8000000000000000n);
291    expect(
292      ArrayUtils.toIntLittleEndian(
293        new Uint8Array([0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x80]),
294        0,
295        8,
296      ),
297    ).toEqual(-0x7fffffffffffffffn);
298    expect(
299      ArrayUtils.toIntLittleEndian(
300        new Uint8Array([0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff]),
301        0,
302        8,
303      ),
304    ).toEqual(-1n);
305
306    expect(
307      ArrayUtils.toIntLittleEndian(
308        new Uint8Array([0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x7f]),
309        0,
310        9,
311      ),
312    ).toEqual(0x7fffffffffffffffffn);
313    expect(
314      ArrayUtils.toIntLittleEndian(
315        new Uint8Array([0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x80]),
316        0,
317        9,
318      ),
319    ).toEqual(-0x800000000000000000n);
320    expect(
321      ArrayUtils.toIntLittleEndian(
322        new Uint8Array([0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x80]),
323        0,
324        9,
325      ),
326    ).toEqual(-0x7fffffffffffffffffn);
327    expect(
328      ArrayUtils.toIntLittleEndian(
329        new Uint8Array([0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff]),
330        0,
331        9,
332      ),
333    ).toEqual(-1n);
334  });
335});
336