view release on metacpan or  search on metacpan

xs/heap/heap.c  view on Meta::CPAN

        if (right < size) {
            NV right_nv = SvNV(data[right]);
            if (right_nv < best_nv) {
                best = right;
                best_nv = right_nv;
            }
        }

        if (best_nv < val_nv) {
            data[idx] = data[best];
            idx = best;
        } else {
            break;
        }
    }
    data[idx] = val;
}

static void heap_sift_down_max(Heap *h, IV idx) {
    SV **data = h->data;
    IV size = h->size;
    SV *val = data[idx];
    NV val_nv = SvNV(val);
    IV half = size >> 1;

    while (idx < half) {
        IV left = (idx << 1) + 1;
        IV right = left + 1;
        IV best = left;
        NV best_nv = SvNV(data[left]);

        if (right < size) {
            NV right_nv = SvNV(data[right]);
            if (right_nv > best_nv) {
                best = right;
                best_nv = right_nv;
            }
        }

        if (best_nv > val_nv) {
            data[idx] = data[best];
            idx = best;
        } else {
            break;
        }
    }
    data[idx] = val;
}

/* Custom comparator sift operations */
static bool heap_compare_custom(pTHX_ Heap *h, SV *a, SV *b) {
    dSP;
    IV result;
    int count;

    ENTER; SAVETMPS;
    PUSHMARK(SP);
    XPUSHs(a);
    XPUSHs(b);
    PUTBACK;

    count = call_sv(h->comparator, G_SCALAR);

    SPAGAIN;
    if (count != 1) croak("Comparator must return exactly one value");
    result = POPi;
    PUTBACK;
    FREETMPS; LEAVE;

    return h->type == HEAP_MIN ? result < 0 : result > 0;
}

static void heap_sift_up_custom(pTHX_ Heap *h, IV idx) {
    while (idx > 0) {
        IV parent = (idx - 1) >> 1;
        if (heap_compare_custom(aTHX_ h, h->data[idx], h->data[parent])) {
            SV *tmp = h->data[idx];
            h->data[idx] = h->data[parent];
            h->data[parent] = tmp;
            idx = parent;
        } else {
            break;
        }
    }
}

static void heap_sift_down_custom(pTHX_ Heap *h, IV idx) {
    while (1) {
        IV left = (idx << 1) + 1;
        IV right = left + 1;
        IV best = idx;

        if (left < h->size && heap_compare_custom(aTHX_ h, h->data[left], h->data[best])) {
            best = left;
        }
        if (right < h->size && heap_compare_custom(aTHX_ h, h->data[right], h->data[best])) {
            best = right;
        }

        if (best != idx) {
            SV *tmp = h->data[idx];
            h->data[idx] = h->data[best];
            h->data[best] = tmp;
            idx = best;
        } else {
            break;
        }
    }
}

static void heap_sift_up(pTHX_ Heap *h, IV idx) {
    if (h->comparator) {
        heap_sift_up_custom(aTHX_ h, idx);
    } else if (h->type == HEAP_MIN) {
        heap_sift_up_min(h, idx);
    } else {
        heap_sift_up_max(h, idx);
    }
}

static void heap_sift_down(pTHX_ Heap *h, IV idx) {
    if (h->comparator) {
        heap_sift_down_custom(aTHX_ h, idx);
    } else if (h->type == HEAP_MIN) {
        heap_sift_down_min(h, idx);
    } else {
        heap_sift_down_max(h, idx);