xref: /arkcompiler/runtime_core/static_core/plugins/ets/templates/stdlib/Array_builtin.erb

/*
 * Copyright (c) 2021-2025 Huawei Device Co., Ltd.
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package std.core;

// NOTE: autogenerated file

% template = ERB.new(File.read("Array_header.erb"), trim_mode: '%', eoutvar: '_sub04')
<%= template.result(binding) %>

// Range is [startIndex, endIndex), i.e. startIndex included and endIndex is excluded
function checkRange(arrLen: int, startIndex: int, endIndex: int): boolean {
    // Since mostly everywhere for loop is used from startIndex till endIndex exclusive,
    // startIndex <= endIndex is used to cover empty array case
    return ((0 <= startIndex) && (startIndex <= endIndex) && (endIndex <= arrLen));
}

native function __alloc_array<T>(len: int, ofType: Object | null): FixedArray<T>

class BuiltinArrayKeysIterator implements IterableIterator<number> {
    private len: int
    private idx: int = 0
    private isDone: boolean = false

    constructor(len: int) {
        this.len = len
    }

    override next(): IteratorResult<number> {
        if (this.isDone || this.idx >= this.len) {
            this.isDone = true
            return new IteratorResult<number>()
        }
        return new IteratorResult<number>(this.idx++ as number)
    }

    override $_iterator(): IterableIterator<number> {
        return this
    }
}

% require 'ostruct'
% ctx = OpenStruct.new
% $ctx = ctx
% ctx.this = 'self'
% ctx.this_len_int = 'self.length'
% ctx.array_len_int = Proc.new { |v| "#{v}.length" }
% ctx.access_public = 'export function'
% ctx.access_private = 'function'
% ctx.override = ''
% ctx.get_unsafe = Proc.new { |t, i| "#{t}[#{i}]" }
% ctx.set_unsafe = Proc.new { |t, i, v| "#{t}[#{i}] = #{v}" }
% ctx.arr_method_call = Proc.new { |t, f, *args| "#{f}(#{args.prepend(t).join(', ')})" }
% primitive_types = ['boolean', 'byte', 'short', 'int', 'long', 'float', 'double', 'char']
% # NOTE(kprokopenko): primitive_types + ['T']
% (primitive_types).each { |el_type|
%   ctx.this_type = "FixedArray<#{el_type}>"
%   ctx.this_arg = "self: #{ctx.this_type}, "
%   ctx.this_return_type = ctx.this_type
%   ctx.el_type = el_type
%   ctx.el_type_boxed = el_type[0].upcase + el_type[1..]
%   ctx.clone_this = 'cloneArray(self)'
%   ctx.make_buffer = Proc.new { |l, elt|
%     elt ||= ctx.el_type
%     if elt == 'T'
%       "__alloc_array<#{elt}>(#{l}, self)"
%     elsif elt == 'U'
%       "__alloc_array<#{elt}>(#{l}, null)"
%     else
%       "new #{elt}[#{l}]"
%     end
%   }
%   ctx.make_fixed_array = "FixedArray<#{el_type}>"
%   ctx.from_buffer = Proc.new { |b, elt| b }
%   ctx.array_of_type = Proc.new { |t| "FixedArray<#{t}>" }
%   ctx.this_generic = ''
%   ctx.this_generic_one = ''
%   ctx.this_iterator_generic = ''
%   if el_type == 'T'
%     ctx.this_generic = '<T>'
%     ctx.this_iterator_generic = '<T>'
%     ctx.this_generic_one = 'T, '
%   end
% ctx.this_call = Proc.new { |f| "#{f}#{ctx.this_generic}(self, " }
function cloneArray<%= ctx.this_generic %>(self: <%= ctx.this_type %>): <%= ctx.this_type %> {
    const ret : <%= ctx.make_fixed_array %> = <%= ctx.make_buffer.('self.length') %>;;
    for (let i = 0; i < self.length; i++) {
        ret[i] = self[i];
    }
    return <%= ctx.from_buffer.('ret') %>;
}
% template = ERB.new(File.read("Array_common.erb"), trim_mode: '%', eoutvar: '_sub01')
<%= template.result(ctx.instance_eval { binding }) %>
% template = ERB.new(File.read("BuiltinArray.erb"), trim_mode: '%', eoutvar: '_sub02')
% primitive_types.each { |mapped|
%   ctx.mapped_type = mapped
%   ctx.map_generic = ctx.this_generic
<%# template.result(ctx.instance_eval { binding }) %>
% }

% ctx.mapped_type = ctx.el_type
% ctx.map_generic = ctx.this_generic
<%= template.result(ctx.instance_eval { binding }) %>

% ctx.mapped_type = 'U'
% ctx.map_generic = "<#{ctx.this_generic_one}U>"
<%# template.result(ctx.instance_eval { binding }) %>

/**
 * Constructs a new `Array` instance and populates it with
 * portion of a given array, filtered down to just the elements from the
 * given array that pass the test implemented by the provided function.
 *
 * @param fn test function, applied to each element of an array.
 *
 * @returns New `Array` instance constructed from `this` with elements filtered using test function `fn`.
 */
export function filter<%= ctx.this_generic %>(<%= ctx.this_arg %>fn: (v: <%= ctx.el_type %>, k: number, array: <%= ctx.this_type %>) => boolean): <%= ctx.this_type %> {
    const mask : FixedArray<boolean> = new boolean[<%= ctx.this_len_int %>]
    let cnt = 0

    for (let i: int = 0; i < <%= ctx.this_len_int %>; i++) {
        const val = self[i];
        if (fn(val, i, self)) {
            mask[i] = true
            cnt++;
        }
    }
    const res : <%= ctx.make_fixed_array %> = <%= ctx.make_buffer.('cnt') %>;
    let idx_store = 0;
    for (let i: int = 0; i < <%= ctx.this_len_int %>; i++) {
        if (mask[i]) {
            res[idx_store++] = self[i]
        }
    }
    return <%= ctx.from_buffer.('res') %>;
}

export function concat<%= ctx.this_generic %>(self: <%= ctx.this_type %>, fst: <%= ctx.this_type %>, ...more: FixedArray<<%= ctx.this_type %>>): <%= ctx.this_type %> {
    const lnMin = self.length + fst.length;
    let ln = lnMin;
    for (let i = 0; i < more.length; i++) {
        ln += more[i].length
    }
    const r : <%= ctx.make_fixed_array %> = <%= ctx.make_buffer.('ln', ctx.el_type) %>;
    try {
        copyTo(self, r, 0, 0, self.length);
        copyTo(fst, r, self.length, 0, fst.length);
        let idx = lnMin;
        for (let i = 0; i < more.length; i++) {
            copyTo(more[i], r, idx, 0, more[i].length);
            idx += more[i].length;
        }
    } catch (e) {
        // impossible
    }
    return <%= ctx.from_buffer.('r') %>
}

/**
 * Reorders elements of `this` using comparator function.
 *
 * @param comparator function that defines the sort order.
 *
 * @note Mutating method
 */
export function sort<%= ctx.this_generic %>(<%= ctx.this_arg %>comparator: (a: <%= ctx.el_type %>, b: <%= ctx.el_type %>) => number): <%= ctx.this_return_type %> {
%   sort_elem_type = ctx.el_type == 'T' ? 'NullishType' : ctx.el_type
%   from_sort_elem_type = ctx.el_type == 'T' ? ' as T' : ''
    sort_subarray(self<%= ctx.el_type == 'T' ? ' as FixedArray<NullishType>' : '' %>, 0, self.length, (l: <%= sort_elem_type %>, r: <%= sort_elem_type %>): boolean => {
        return comparator(l<%= from_sort_elem_type %>, r <%= from_sort_elem_type %>) < 0;
    });
    return self;
}

/**
 * Reorders elements of `this` using comparator function.
 *
 * @param comparator function that defines the sort order.
 *
 * @note Mutating method
 */
export function sort<%= ctx.this_generic %>(<%= ctx.this_arg.chomp(', ') %>): <%= ctx.this_return_type %> {
% if !primitive_types.include?(ctx.el_type)
    sort_subarray(self<%= ctx.el_type == 'T' ? ' as FixedArray<NullishType>' : '' %>, 0, self.length, (l: <%= sort_elem_type %>, r: <%= sort_elem_type %>): boolean => {
        return new String(l).compareTo(new String(r)) < 0;
    });
% else
    sort(self, 0, self.length);
% end
    return self;
}

export function keys<%= ctx.this_generic %>(self: <%= ctx.this_type %>): IterableIterator<number> {
    return new BuiltinArrayKeysIterator(self.length);
}

%   template = ERB.new(File.read("Array_common_top_scope.erb"), trim_mode: '%', eoutvar: '_sub03')
<%= template.result(ctx.instance_eval { binding }).gsub(/[ \t]+$/, '') %>

% }

function builtin_insertion_sort<T>(arr: FixedArray<T>, startIndex: int, endIndex: int, comp: (lhs: T, rhs: T) => number): void {
    for (let i = startIndex + 1; i < endIndex; i++) {
        const tmp = arr[i];
        if (comp(tmp, arr[startIndex]) as int < 0) {
            for (let j = i; j > startIndex; j--) {
                arr[j] = arr[j - 1]
            }
            arr[startIndex] = tmp
        } else {
            let j = i - 1;
            while (comp(tmp, arr[j]) as int < 0) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = tmp;
        }
    }
}

function perform_merge<T>(arr: FixedArray<T>, startIndex: int, midIndex: int, endIndex: int, comp: (lhs: T, rhs: T) => number): void {
    const len1 = midIndex - startIndex + 1;
    const len2 = endIndex - midIndex;
    let left : FixedArray<T | undefined> = new (T | undefined)[len1];
    let right : FixedArray<T | undefined> = new (T | undefined)[len2];
    for (let i = 0; i < len1; i++) {
        left[i] = arr[startIndex + i];
    }
    for (let i = 0; i < len2; i++) {
        right[i] = arr[midIndex + 1 + i];
    }
    let i = 0;
    let j = 0;
    let k = startIndex;
    while (i < len1 && j < len2) {
        if (comp(left[i]!, right[j]!) as int <= 0) {
            arr[k] = left[i]!;
            i++;
        } else {
            arr[k] = right[j]!;
            j++;
        }
        k++;
    }
    while (i < len1) {
        arr[k] = left[i]!;
        k++;
        i++;
    }
    while (j < len2) {
        arr[k] = right[j]!;
        k++;
        j++;
    }
}

export function sort_stable<T>(arr: FixedArray<T>, startIndex: int, endIndex: int, comp: (lhs: T, rhs: T) => number): void {
    if (endIndex <= startIndex) {
        return;
    }

    const INS_SORT_DELTA = 16
    for (let i = startIndex; i < endIndex; i += INS_SORT_DELTA ) {
        builtin_insertion_sort<T>(arr, i, min(i + INS_SORT_DELTA , endIndex), comp)
    }
    if ((endIndex - startIndex) < INS_SORT_DELTA) {
        return;
    }
    for (let size = INS_SORT_DELTA; size < endIndex; size = 2 * size) {
        for (let left = startIndex; left < endIndex; left += 2 * size) {

            // Find ending point of left subarray and right subarray
            const mid = min(left + size - 1, endIndex - 1);
            const right = min((left + 2 * size - 1), (endIndex - 1));

            // Merge sub array arr[left.....mid] and arr[mid+1....right]
            if (mid < right) {
                perform_merge(arr, left, mid, right, comp);
            }
        }
    }
}

function defaultComparatorStr(a: String, b: String): number {
    return a.compareTo(b)
}

type buffStr = String | undefined
function stringified_insertion_sort<T>(arr: FixedArray<T>, arrStr: FixedArray<buffStr>, startIndex: int, endIndex: int): void {
    for (let i = startIndex + 1; i < endIndex; i++) {
        const tmp = arr[i]
        const tmpStr = arrStr[i];
        if (defaultComparatorStr(tmpStr!, arrStr[startIndex]!) < 0) {
            for (let j = i; j > startIndex; j--) {
                arr[j] = arr[j - 1]
                arrStr[j] = arrStr[j - 1]
            }
            arrStr[startIndex] = tmpStr
            arr[startIndex] = tmp
        } else {
            let j = i - 1;
            while (defaultComparatorStr(tmpStr!, arrStr[j]!) < 0) {
                arr[j + 1] = arr[j];
                arrStr[j + 1] = arrStr[j]
                j--;
            }
            arr[j + 1] = tmp;
            arrStr[j + 1] = tmpStr
        }
    }
}

function stringified_perform_merge<T>(arr: FixedArray<T>, arrStr: FixedArray<buffStr>, startIndex: int, midIndex: int, endIndex: int): void {
    const len1 = midIndex - startIndex + 1;
    const len2 = endIndex - midIndex;
    type buffType = T | undefined
    let left : FixedArray<buffType> = new buffType[len1]
    let right : FixedArray<buffType> = new buffType[len2]
    let leftStr : FixedArray<buffStr> = new buffStr[len1]
    let rightStr : FixedArray<buffStr> = new buffStr[len2]
    for (let i = 0; i < len1; i++) {
        left[i] = arr[startIndex + i]
        leftStr[i] = arrStr[startIndex + i]
    }
    for (let i = 0; i < len2; i++) {
        right[i] = arr[midIndex + 1 + i]
        rightStr[i] = arrStr[midIndex + 1 + i]
    }
    let i = 0;
    let j = 0;
    let k = startIndex;
    while (i < len1 && j < len2) {
        if (defaultComparatorStr(leftStr[i]!, rightStr[j]!) <= 0) {
            arr[k] = left[i]!;
            arrStr[k] = leftStr[i]!;
            i++;
        } else {
            arr[k] = right[j]!;
            arrStr[k] = rightStr[j]!;
            j++;
        }
        k++;
    }
    while (i < len1) {
        arr[k] = left[i]!;
        arrStr[k] = leftStr[i]!;
        k++;
        i++;
    }
    while (j < len2) {
        arr[k] = right[j]!;
        arrStr[k] = rightStr[j]!;
        k++;
        j++;
    }
}

export function sort_default<T>(arr: FixedArray<T>, arrStr: FixedArray<buffStr>, startIndex: int, endIndex: int): void {
    if (endIndex <= startIndex) {
        return;
    }
    const INS_SORT_DELTA = 16
    for (let i = startIndex; i < endIndex; i += INS_SORT_DELTA ) {
        stringified_insertion_sort<T>(arr, arrStr, i, min(i + INS_SORT_DELTA , endIndex))
    }

    if ((endIndex - startIndex) < INS_SORT_DELTA) {
        return;
    }
    for (let size = INS_SORT_DELTA; size < endIndex; size = 2 * size) {
        for (let left = startIndex; left < endIndex; left += 2 * size) {

            // Find ending point of left subarray and right subarray
            const mid = min(left + size - 1, endIndex - 1);
            const right = min((left + 2 * size - 1), (endIndex - 1));

            // Merge sub array arr[left.....mid] and arr[mid+1....right]
            if (mid < right) {
                stringified_perform_merge(arr, arrStr, left, mid, right);
            }
        }
    }
}

/**
 * Calls the specified callback function for all the elements in an array. The return value of the callback function is the accumulated result, and is provided as an argument in the next call to the callback function.
 *
 * @param callbackfn A function that accepts up to four arguments. The reduce method calls the callbackfn function one time for each element in the array.
 *
 * @param initialValue If initialValue is specified, it is used as the initial value to start the accumulation. The first call to the callbackfn function provides this value as an argument instead of an array value.
 *
 * @returns a result after applying callbackfn over all elements of the Array
 */
export function reduce<U, T>(self: Array<U>, callbackfn: (previousValue: T, currentValue: U, index: number, array: Array<U>) => T, initialValue: T): T {
    let acc = initialValue
    for (let i = 0; i < self.length; i++) {
        acc = callbackfn(acc, self[i], i as number, self)
    }
    return acc
}