xref: /aosp_15_r20/development/tools/winscope/src/common/array_utils_test.ts (revision 90c8c64db3049935a07c6143d7fd006e26f8ecca) 
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([1, 2, 3], new Uint8Array([1, 2, 3]))).toBeTrue();
33
34    expect(
35      ArrayUtils.equal(new Uint8Array([]), new Uint8Array([1])),
36    ).toBeFalse();
37    expect(
38      ArrayUtils.equal(new Uint8Array([1]), new Uint8Array([])),
39    ).toBeFalse();
40
41    expect(ArrayUtils.equal(new Uint8Array([]), new Uint8Array([]))).toBeTrue();
42    expect(
43      ArrayUtils.equal(new Uint8Array([1, 2, 3]), new Uint8Array([1, 2, 3])),
44    ).toBeTrue();
45  });
46
47  it('equal with predicate', () => {
48    const predicate = (a: number, b: number) => a !== b;
49    expect(ArrayUtils.equal([], [1], predicate)).toBeFalse();
50    expect(ArrayUtils.equal([1], [], predicate)).toBeFalse();
51
52    expect(ArrayUtils.equal([], [], predicate)).toBeTrue();
53    expect(ArrayUtils.equal([1, 2, 3], [1, 2, 3], predicate)).toBeFalse();
54
55    expect(ArrayUtils.equal([], new Uint8Array(1), predicate)).toBeFalse();
56    expect(ArrayUtils.equal([1], new Uint8Array(1), predicate)).toBeTrue();
57
58    expect(ArrayUtils.equal([], new Uint8Array(), predicate)).toBeTrue();
59    expect(
60      ArrayUtils.equal([1, 2, 3], new Uint8Array([1, 2, 3]), predicate),
61    ).toBeFalse();
62
63    expect(
64      ArrayUtils.equal(new Uint8Array([]), new Uint8Array([1]), predicate),
65    ).toBeFalse();
66    expect(
67      ArrayUtils.equal(new Uint8Array([1]), new Uint8Array([]), predicate),
68    ).toBeFalse();
69
70    expect(
71      ArrayUtils.equal(new Uint8Array([]), new Uint8Array([]), predicate),
72    ).toBeTrue();
73    expect(
74      ArrayUtils.equal(
75        new Uint8Array([1, 2, 3]),
76        new Uint8Array([1, 2, 3]),
77        predicate,
78      ),
79    ).toBeFalse();
80
81    const predicateWithNonNumberType = (
82      a: number | undefined,
83      b: number | undefined,
84    ) => a !== b;
85    expect(
86      ArrayUtils.equal([undefined], [undefined], predicateWithNonNumberType),
87    ).toBeFalse();
88  });
89
90  it('searchSubarray', () => {
91    expect(ArrayUtils.searchSubarray([], [0])).toEqual(undefined);
92    expect(ArrayUtils.searchSubarray([], [])).toEqual(0);
93    expect(ArrayUtils.searchSubarray([0], [])).toEqual(0);
94
95    expect(ArrayUtils.searchSubarray([0, 1, 2], [-1])).toEqual(undefined);
96    expect(ArrayUtils.searchSubarray([0, 1, 2], [])).toEqual(0);
97    expect(ArrayUtils.searchSubarray([0, 1, 2], [0])).toEqual(0);
98    expect(ArrayUtils.searchSubarray([0, 1, 2], [1])).toEqual(1);
99    expect(ArrayUtils.searchSubarray([0, 1, 2], [2])).toEqual(2);
100
101    expect(ArrayUtils.searchSubarray([0, 1, 2], [0, 1])).toEqual(0);
102    expect(ArrayUtils.searchSubarray([0, 1, 2], [1, 2])).toEqual(1);
103    expect(ArrayUtils.searchSubarray([0, 1, 2], [2])).toEqual(2);
104    expect(ArrayUtils.searchSubarray([0, 1, 2], [2, 3])).toEqual(undefined);
105  });
106
107  it('binarySearchFirstGreaterOrEqual', () => {
108    // no match
109    expect(ArrayUtils.binarySearchFirstGreaterOrEqual([], 9)).toBeUndefined();
110    expect(ArrayUtils.binarySearchFirstGreaterOrEqual([8], 9)).toBeUndefined();
111    expect(
112      ArrayUtils.binarySearchFirstGreaterOrEqual([7, 8], 9),
113    ).toBeUndefined();
114    expect(
115      ArrayUtils.binarySearchFirstGreaterOrEqual([6, 7, 8], 9),
116    ).toBeUndefined();
117
118    // match (greater)
119    expect(ArrayUtils.binarySearchFirstGreaterOrEqual([6], 5)).toEqual(0);
120    expect(ArrayUtils.binarySearchFirstGreaterOrEqual([6, 7], 5)).toEqual(0);
121    expect(ArrayUtils.binarySearchFirstGreaterOrEqual([4, 6], 5)).toEqual(1);
122    expect(ArrayUtils.binarySearchFirstGreaterOrEqual([4, 6, 7, 8], 5)).toEqual(
123      1,
124    );
125    expect(
126      ArrayUtils.binarySearchFirstGreaterOrEqual([3, 4, 6, 7, 8], 5),
127    ).toEqual(2);
128
129    // match (equal)
130    expect(ArrayUtils.binarySearchFirstGreaterOrEqual([5], 5)).toEqual(0);
131    expect(ArrayUtils.binarySearchFirstGreaterOrEqual([5, 6], 5)).toEqual(0);
132    expect(ArrayUtils.binarySearchFirstGreaterOrEqual([4, 5], 5)).toEqual(1);
133    expect(ArrayUtils.binarySearchFirstGreaterOrEqual([3, 4, 5], 5)).toEqual(2);
134    expect(ArrayUtils.binarySearchFirstGreaterOrEqual([3, 4, 5, 6], 5)).toEqual(
135      2,
136    );
137    expect(
138      ArrayUtils.binarySearchFirstGreaterOrEqual([3, 4, 5, 6, 7], 5),
139    ).toEqual(2);
140
141    // match (equal with repeated values)
142    expect(ArrayUtils.binarySearchFirstGreaterOrEqual([5, 5], 5)).toEqual(0);
143    expect(ArrayUtils.binarySearchFirstGreaterOrEqual([5, 5, 5], 5)).toEqual(0);
144    expect(ArrayUtils.binarySearchFirstGreaterOrEqual([5, 5, 5, 5], 5)).toEqual(
145      0,
146    );
147    expect(ArrayUtils.binarySearchFirstGreaterOrEqual([4, 5, 5, 6], 5)).toEqual(
148      1,
149    );
150    expect(
151      ArrayUtils.binarySearchFirstGreaterOrEqual([4, 4, 5, 5, 5, 6], 5),
152    ).toEqual(2);
153    expect(
154      ArrayUtils.binarySearchFirstGreaterOrEqual([4, 4, 4, 5, 5, 5, 5, 6], 5),
155    ).toEqual(3);
156  });
157
158  it('binarySearchFirstGreater', () => {
159    // no match
160    expect(ArrayUtils.binarySearchFirstGreater([], 9)).toBeUndefined();
161    expect(ArrayUtils.binarySearchFirstGreater([8], 9)).toBeUndefined();
162    expect(ArrayUtils.binarySearchFirstGreater([7, 8], 9)).toBeUndefined();
163    expect(ArrayUtils.binarySearchFirstGreater([6, 7, 8], 9)).toBeUndefined();
164
165    // match
166    expect(ArrayUtils.binarySearchFirstGreater([6], 5)).toEqual(0);
167    expect(ArrayUtils.binarySearchFirstGreater([6, 7], 5)).toEqual(0);
168    expect(ArrayUtils.binarySearchFirstGreater([4, 6], 5)).toEqual(1);
169    expect(ArrayUtils.binarySearchFirstGreater([4, 6, 7, 8], 5)).toEqual(1);
170    expect(ArrayUtils.binarySearchFirstGreater([3, 4, 6, 7, 8], 5)).toEqual(2);
171
172    // match (ignore equal)
173    expect(ArrayUtils.binarySearchFirstGreater([5], 5)).toEqual(undefined);
174    expect(ArrayUtils.binarySearchFirstGreater([5, 6], 5)).toEqual(1);
175    expect(ArrayUtils.binarySearchFirstGreater([4, 5, 6], 5)).toEqual(2);
176    expect(ArrayUtils.binarySearchFirstGreater([3, 4, 5, 6], 5)).toEqual(3);
177    expect(ArrayUtils.binarySearchFirstGreater([3, 4, 5, 6, 7], 5)).toEqual(3);
178
179    // match (with repeated values)
180    expect(ArrayUtils.binarySearchFirstGreater([6, 6], 5)).toEqual(0);
181    expect(ArrayUtils.binarySearchFirstGreater([6, 6, 6], 5)).toEqual(0);
182    expect(ArrayUtils.binarySearchFirstGreater([6, 6, 6, 6], 5)).toEqual(0);
183    expect(ArrayUtils.binarySearchFirstGreater([5, 6, 6, 7], 5)).toEqual(1);
184    expect(ArrayUtils.binarySearchFirstGreater([5, 5, 6, 6, 6, 7], 5)).toEqual(
185      2,
186    );
187    expect(
188      ArrayUtils.binarySearchFirstGreater([5, 5, 5, 6, 6, 6, 6, 7], 5),
189    ).toEqual(3);
190  });
191
192  it('toUintLittleEndian', () => {
193    const buffer = new Uint8Array([0, 0, 1, 1]);
194
195    expect(
196      ArrayUtils.toUintLittleEndian(new Uint8Array([0xff, 0xff]), 0, -1),
197    ).toEqual(0n);
198    expect(
199      ArrayUtils.toUintLittleEndian(new Uint8Array([0xff, 0xff]), 0, 0),
200    ).toEqual(0n);
201    expect(
202      ArrayUtils.toUintLittleEndian(new Uint8Array([0xff, 0xff]), 1, 1),
203    ).toEqual(0n);
204
205    expect(
206      ArrayUtils.toUintLittleEndian(new Uint8Array([0x00, 0x01, 0xff]), 0, 1),
207    ).toEqual(0n);
208    expect(
209      ArrayUtils.toUintLittleEndian(new Uint8Array([0x00, 0x01, 0xff]), 1, 2),
210    ).toEqual(1n);
211    expect(
212      ArrayUtils.toUintLittleEndian(new Uint8Array([0x00, 0x01, 0xff]), 2, 3),
213    ).toEqual(255n);
214
215    expect(
216      ArrayUtils.toUintLittleEndian(new Uint8Array([0x00, 0x00]), 0, 2),
217    ).toEqual(0n);
218    expect(
219      ArrayUtils.toUintLittleEndian(new Uint8Array([0x01, 0x00]), 0, 2),
220    ).toEqual(1n);
221    expect(
222      ArrayUtils.toUintLittleEndian(new Uint8Array([0x00, 0x01]), 0, 2),
223    ).toEqual(256n);
224    expect(
225      ArrayUtils.toUintLittleEndian(new Uint8Array([0xff, 0xff]), 0, 2),
226    ).toEqual(0xffffn);
227
228    expect(
229      ArrayUtils.toUintLittleEndian(
230        new Uint8Array([0xff, 0xff, 0xff, 0xff]),
231        0,
232        4,
233      ),
234    ).toEqual(0xffffffffn);
235
236    expect(
237      ArrayUtils.toUintLittleEndian(
238        new Uint8Array([0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff]),
239        0,
240        8,
241      ),
242    ).toEqual(0xffffffffffffffffn);
243
244    expect(
245      ArrayUtils.toUintLittleEndian(
246        new Uint8Array([0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff]),
247        0,
248        9,
249      ),
250    ).toEqual(0xffffffffffffffffffn);
251  });
252
253  it('toIntLittleEndian', () => {
254    expect(ArrayUtils.toIntLittleEndian(new Uint8Array([0xff]), 0, -1)).toEqual(
255      0n,
256    );
257    expect(ArrayUtils.toIntLittleEndian(new Uint8Array([0xff]), 0, 0)).toEqual(
258      0n,
259    );
260
261    expect(ArrayUtils.toIntLittleEndian(new Uint8Array([0x00]), 0, 1)).toEqual(
262      0n,
263    );
264    expect(ArrayUtils.toIntLittleEndian(new Uint8Array([0x01]), 0, 1)).toEqual(
265      1n,
266    );
267    expect(ArrayUtils.toIntLittleEndian(new Uint8Array([0x7f]), 0, 1)).toEqual(
268      127n,
269    );
270    expect(ArrayUtils.toIntLittleEndian(new Uint8Array([0x80]), 0, 1)).toEqual(
271      -128n,
272    );
273    expect(ArrayUtils.toIntLittleEndian(new Uint8Array([0xff]), 0, 1)).toEqual(
274      -1n,
275    );
276
277    expect(
278      ArrayUtils.toIntLittleEndian(new Uint8Array([0xff, 0x7f]), 0, 2),
279    ).toEqual(32767n);
280    expect(
281      ArrayUtils.toIntLittleEndian(new Uint8Array([0x00, 0x80]), 0, 2),
282    ).toEqual(-32768n);
283    expect(
284      ArrayUtils.toIntLittleEndian(new Uint8Array([0x01, 0x80]), 0, 2),
285    ).toEqual(-32767n);
286    expect(
287      ArrayUtils.toIntLittleEndian(new Uint8Array([0xff, 0xff]), 0, 2),
288    ).toEqual(-1n);
289
290    expect(
291      ArrayUtils.toIntLittleEndian(
292        new Uint8Array([0xff, 0xff, 0xff, 0x7f]),
293        0,
294        4,
295      ),
296    ).toEqual(0x7fffffffn);
297    expect(
298      ArrayUtils.toIntLittleEndian(
299        new Uint8Array([0x00, 0x00, 0x00, 0x80]),
300        0,
301        4,
302      ),
303    ).toEqual(-0x80000000n);
304    expect(
305      ArrayUtils.toIntLittleEndian(
306        new Uint8Array([0x01, 0x00, 0x00, 0x80]),
307        0,
308        4,
309      ),
310    ).toEqual(-0x7fffffffn);
311    expect(
312      ArrayUtils.toIntLittleEndian(
313        new Uint8Array([0xff, 0xff, 0xff, 0xff]),
314        0,
315        4,
316      ),
317    ).toEqual(-1n);
318
319    expect(
320      ArrayUtils.toIntLittleEndian(
321        new Uint8Array([0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x7f]),
322        0,
323        8,
324      ),
325    ).toEqual(0x7fffffffffffffffn);
326    expect(
327      ArrayUtils.toIntLittleEndian(
328        new Uint8Array([0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x80]),
329        0,
330        8,
331      ),
332    ).toEqual(-0x8000000000000000n);
333    expect(
334      ArrayUtils.toIntLittleEndian(
335        new Uint8Array([0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x80]),
336        0,
337        8,
338      ),
339    ).toEqual(-0x7fffffffffffffffn);
340    expect(
341      ArrayUtils.toIntLittleEndian(
342        new Uint8Array([0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff]),
343        0,
344        8,
345      ),
346    ).toEqual(-1n);
347
348    expect(
349      ArrayUtils.toIntLittleEndian(
350        new Uint8Array([0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x7f]),
351        0,
352        9,
353      ),
354    ).toEqual(0x7fffffffffffffffffn);
355    expect(
356      ArrayUtils.toIntLittleEndian(
357        new Uint8Array([0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x80]),
358        0,
359        9,
360      ),
361    ).toEqual(-0x800000000000000000n);
362    expect(
363      ArrayUtils.toIntLittleEndian(
364        new Uint8Array([0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x80]),
365        0,
366        9,
367      ),
368    ).toEqual(-0x7fffffffffffffffffn);
369    expect(
370      ArrayUtils.toIntLittleEndian(
371        new Uint8Array([0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff]),
372        0,
373        9,
374      ),
375    ).toEqual(-1n);
376  });
377});
378