blog-static/code/cs325-langs/sols/hw3.lang

function qselect(xs, k, c) {
    if xs == [] {
        return 0;
    }

    traverser bisector(list: xs, span: (0,len(xs)));
    traverser pivot(list: xs, random: true);

    let pivotE = pop!(pivot);
    let (leftList, rightList) = bisect!(bisector, (x) -> c(x) < c(pivotE));
    
    if k > len(leftList) + 1 {
        return qselect(rightList, k - len(leftList) - 1, c);
    } elsif k == len(leftList) + 1 {
        return pivotE;
    } else {
        return qselect(leftList, k, c);
    }
}

function closestUnsorted(xs, k, n) {
    let min = qselect(list(xs), k, (x) -> abs(x - n));
    let out = [];
    let countEqual = k;

    traverser iter(list: xs, span: (0, len(xs)));
    while valid!(iter) {
        if abs(at!(iter)-n) < abs(min-n) {
            let countEqual = countEqual - 1;
        }
        step!(iter);
    }

    traverser iter(list: xs, span: (0, len(xs)));
    while valid!(iter) {
        if abs(at!(iter)-n) == abs(min-n) and countEqual > 0 {
            let countEqual = countEqual - 1;
            let out = out + [at!(iter)];
        } elsif abs(at!(iter)-n) < abs(min-n) {
            let out = out + [at!(iter)];
        }
        step!(iter);
    }

    return out;
}

function closestSorted(xs, k, n) {
    let start = bisect(xs, n);
    let counter = 0;
    traverser left(list: xs, span: (0, start), reverse: true);
    traverser right(list: xs, span: (start, len(xs)));

    while counter != k and canstep!(left) and valid!(right) {
        if abs(at!(left, 1) - n) < abs(at!(right) - n) {
            step!(left);
        } else {
            step!(right);
        }
        let counter = counter + 1;
    }

    while counter != k and (canstep!(left) or valid!(right)) {
        if canstep!(left) { step!(left); }
        else { step!(right); }
        let counter = counter + 1;
    }

    return subset!(left, right);
}

sorted function xyz(xs, k) {
    traverser x(list: xs, span: (0,len(xs)));
    let dest = [];

    while valid!(x) {
        traverser z(list: xs, span: (pos!(x)+2,len(xs)));
        traverser y(list: xs, span: (pos!(x)+1,pos!(z)));

        while valid!(y) and valid!(z) {
            if at!(x) + at!(y) == at!(z) {
                let dest = dest + [(at!(x), at!(y), at!(z))];
                step!(z);
            } elsif at!(x) + at!(y) > at!(z) {
                step!(z);
            } else {
                step!(y);
            }
        }

        step!(x);
    }

    return dest;
}