algorithms.expr

Go to the documentation of this file.

# Copyright (C) 2025 yuygfgg
# 
# This file is part of Vapoursynth-llvmexpr.
# 
# Vapoursynth-llvmexpr is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.
# 
# Vapoursynth-llvmexpr is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
# 
# You should have received a copy of the GNU General Public License
# along with Vapoursynth-llvmexpr.  If not, see <https://www.gnu.org/licenses/>.
 
@ifdef __EXPR__
    @define ___STDLIB_ALGORITHMS_RANGE_PARAM_TYPE Literal
@else
    @define ___STDLIB_ALGORITHMS_RANGE_PARAM_TYPE Value
@endif
 
function ___stdlib_algorithms_swap(Array a, Value i, Value j) {
    tmp = a[i];
    a[i] = a[j];
    a[j] = tmp;
}
 
function ___stdlib_algorithms_heapify(Array a, Value n, Value i, Value offset) {
    current_i = i;
    while (1) {
        largest = current_i;
        left = 2 * current_i + 1;
        right = 2 * current_i + 2;
 
        if (left < n && a[offset + largest] < a[offset + left]) {
            largest = left;
        }
        if (right < n && a[offset + largest] < a[offset + right]) {
            largest = right;
        }
 
        if (largest == current_i) {
            goto heapify_loop_end;
        }
 
        ___stdlib_algorithms_swap(a, offset + current_i, offset + largest);
        current_i = largest;
    }
    heapify_loop_end:
}
 
function ___stdlib_algorithms_insertion_sort(Array a, Value begin, Value end) {
    i = begin + 1;
    while (i < end) {
        key = a[i];
        j = i - 1;
        while (j >= begin && a[j] > key) {
            a[j + 1] = a[j];
            j = j - 1;
        }
        a[j + 1] = key;
        i = i + 1;
    }
}
 
function ___stdlib_algorithms_heapsort(Array a, Value begin, Value end) {
    n = end - begin;
 
    i = n / 2 - 1;
    while (i >= 0) {
        ___stdlib_algorithms_heapify(a, n, i, begin);
        i = i - 1;
    }
 
    i = n - 1;
    while (i > 0) {
        ___stdlib_algorithms_swap(a, begin, begin + i);
        ___stdlib_algorithms_heapify(a, i, 0, begin);
        i = i - 1;
    }
}
 
function ___stdlib_algorithms_median_of_three(Array a, Value low, Value high) {
    mid = floor(low + (high - low) / 2);
    if (a[low] > a[mid]) {
        ___stdlib_algorithms_swap(a, low, mid);
    }
    if (a[low] > a[high]) {
        ___stdlib_algorithms_swap(a, low, high);
    }
    if (a[mid] > a[high]) {
        ___stdlib_algorithms_swap(a, mid, high);
    }
    ___stdlib_algorithms_swap(a, mid, high);
}
 
function ___stdlib_algorithms_partition(Array a, Value low, Value high) {
    pivot = a[high];
    i = low - 1;
    j = low;
    while (j < high) {
        if (a[j] <= pivot) {
            i = i + 1;
            ___stdlib_algorithms_swap(a, i, j);
        }
        j = j + 1;
    }
    ___stdlib_algorithms_swap(a, i + 1, high);
    return i + 1;
}
 
function ___stdlib_algorithms_copy_range(Array dest, Value dest_start, Array src, Value src_start, Value len) {
    i = 0;
    while (i < len) {
        dest[dest_start + i] = src[src_start + i];
        i = i + 1;
    }
}
 
function ___stdlib_algorithms_find_kth_smallest_fast(Array a, ___STDLIB_ALGORITHMS_RANGE_PARAM_TYPE begin, ___STDLIB_ALGORITHMS_RANGE_PARAM_TYPE end, ___STDLIB_ALGORITHMS_RANGE_PARAM_TYPE len, Value k) {
    temp_arr = new(len);
    ___stdlib_algorithms_copy_range(temp_arr, 0, a, begin, len);
 
    low = 0;
    high = len - 1;
    result = -1.0; # Default error value
 
    while (low <= high) {
        pivot_idx = ___stdlib_algorithms_partition(temp_arr, low, high);
        if (pivot_idx == k) {
            result = temp_arr[k];
            goto find_kth_fast_end;
        }
        if (pivot_idx < k) {
            low = pivot_idx + 1;
        } else {
            high = pivot_idx - 1;
        }
    }
 
    find_kth_fast_end:
    return result;
}
 
function ___stdlib_algorithms_find_kth_smallest_slow(Array arr, Value begin, Value end, Value k) {
    i = begin;
    while (i < end) {
        candidate_val = arr[i];
        less_count = 0;
        equal_count = 0;
        j = begin;
        while (j < end) {
            elem = arr[j];
            if (elem < candidate_val) {
                less_count = less_count + 1;
            } else if (elem == candidate_val) {
                equal_count = equal_count + 1;
            }
            j = j + 1;
        }
        if (k >= less_count && k < (less_count + equal_count)) {
            return candidate_val;
        }
        i = i + 1;
    }
    return -1.0;
}
 
function ___stdlib_algorithms_sort(Array a, Value begin, Value end) {
    n = end - begin;
    if (n <= 1) {
        return;
    }
 
    INSERTION_SORT_THRESHOLD = 16;
    if (n < INSERTION_SORT_THRESHOLD) {
        ___stdlib_algorithms_insertion_sort(a, begin, end);
        return;
    }
 
    stack = new(192);
    stack_ptr = 0;
 
    stack[stack_ptr] = begin;
    stack[stack_ptr + 1] = end;
    stack[stack_ptr + 2] = 2 * floor(log2(n));
    stack_ptr = stack_ptr + 3;
 
    while (stack_ptr > 0) {
        stack_ptr = stack_ptr - 3;
        current_begin = stack[stack_ptr];
        current_end = stack[stack_ptr + 1];
        depth_limit = stack[stack_ptr + 2];
 
        current_n = current_end - current_begin;
        if (current_n > 1) {
            if (current_n < INSERTION_SORT_THRESHOLD) {
                ___stdlib_algorithms_insertion_sort(a, current_begin, current_end);
            } else if (depth_limit == 0) {
                ___stdlib_algorithms_heapsort(a, current_begin, current_end);
            } else {
                p_high = current_end - 1;
                ___stdlib_algorithms_median_of_three(a, current_begin, p_high);
                pivot_idx = ___stdlib_algorithms_partition(a, current_begin, p_high);
 
                stack[stack_ptr] = pivot_idx + 1;
                stack[stack_ptr + 1] = current_end;
                stack[stack_ptr + 2] = depth_limit - 1;
                stack_ptr = stack_ptr + 3;
 
                stack[stack_ptr] = current_begin;
                stack[stack_ptr + 1] = pivot_idx;
                stack[stack_ptr + 2] = depth_limit - 1;
                stack_ptr = stack_ptr + 3;
            }
        }
    }
}
 
function ___stdlib_algorithms_reverse(Array a, Value begin, Value end) {
    left = begin;
    right = end - 1;
    while (left < right) {
        ___stdlib_algorithms_swap(a, left, right);
        left = left + 1;
        right = right - 1;
    }
}
 
@define ___STDLIB_ALGORITHMS_CALC_LEN(b, e) ((e) - (b))
@define ___STDLIB_ALGORITHMS_USE_SLOW_IMPL(begin, end) (!is_consteval(___STDLIB_ALGORITHMS_CALC_LEN(begin, end)) && defined(__EXPR__))
@define ___stdlib_algorithms_find_kth_smallest(a, begin, end, k) (___STDLIB_ALGORITHMS_USE_SLOW_IMPL(begin, end) ? ___stdlib_algorithms_find_kth_smallest_slow(a, begin, end, k) : ___stdlib_algorithms_find_kth_smallest_fast(a, begin, end, ___STDLIB_ALGORITHMS_CALC_LEN(begin, end), k))