3
\$\begingroup\$

I happened to need to find both the maximum and the minimum of an array, so I decided to implement a minMax function in D.

Questions:

  1. Is this an efficient implementation?
  2. Is it readable?
  3. Any general feedback is appreciated.

Thanks!

import std.range;
import std.traits;
import std.typecons;
import std.functional;

class EmptyContainerException : Exception {
    this(string msg, string file = __FILE__, size_t line = __LINE__) {
        super(msg, file, line);
    }
}

// returns a tuple containing the minimum and maximum elements of a finite InputRange
template minMax(alias pred = "a") {
    alias map = unaryFun!pred;

    auto minMax(Range)(Range r)
    if(isInputRange!Range && !isInfinite!Range && is(typeof(map(r.front)))) {
        if(r.empty) {
            throw new EmptyContainerException(
                "minMax expected a container with at least 1 element, got an empty container."
            );
        }
        auto front = r.front;
        auto frontMap = map(front);

        auto min = front;
        auto max = front;
        auto minMap = frontMap;
        auto maxMap = frontMap;

        r.popFront;
        while(!r.empty) {
            front = r.front;
            frontMap = map(front);
            if(frontMap > maxMap) {
                max = front;
                maxMap = frontMap;
            }
            if(frontMap < minMap) {
                min = front;
                minMap = frontMap;
            }
            r.popFront;
        }
        return tuple!("min", "max")(min, max);
    }
}

unittest {
    import std.exception : assertThrown;

    int[] test1 = [1, 2, 3, 4, 5];
    auto test1result = test1.minMax;
    assert(test1result.min == 1 && test1result.max == 5);

    string test2 = "Hello, World!";
    auto test2result = test2.minMax;
    assert(test2result.min == ' ' && test2result.max == 'r');

    int[] test3 = [];
    assertThrown!EmptyContainerException(test3.minMax);

    string[] test4 = ["who", "is", "the", "longest", "word"];
    auto test4result = test4.minMax!"a.length";
    assert(test4result.min == "is" && test4result.max == "longest");
}
\$\endgroup\$
3
\$\begingroup\$

Is this an efficient implementation?

Yup. It calls map exactly once per item, and otherwise does nothing but the regular range calls. A specialized implementation could be more efficient in some cases (but probably only if using vector instructions), as could a parallel implementation, but neither of these have the genericity that your code does.

Is it readable?

Absolutely, it's some of the most readable code I've seen. The content of the loop is somewhat dense. You could perhaps make it less dense like this:

    auto front = tuple!("elem", "map")(r.front, map(r.front));
    auto min = front;
    auto max = front;

    r.popFront;
    foreach (e; r) {
        front = tuple(e, map(e));
        if(front.map > max.map) max = front;
        if(front.map < min.map) min = front;
    }
    return tuple!("min", "max")(min.elem, max.elem);

Apart from that, I got nuthin'.

Any general feedback is appreciated.

As hinted at in the section above, instead of while (!empty), you might want to use foreach. This reduces your code by one line (r.popFront()), and makes it clearer that you're going to iterate over every element of the range. It shouldn't change the performance of the code in any way.

You should put an if (is(typeof(unaryFun!pred))) constraint on the template, so the user of the function gets an error message on the line where he or she tries to instantiate it with arr.minMax!"invalid string".

Also, the name pred is wrong - a predicate is a boolean-valued function, like equal, same color or contains bees. I'd call it Fn or Fun.

As a minor nit, I'd also change the name of map, probably to fn or fun (note the difference in capitalization). This because I kept conflating your map with std.algorithm.map. The concept is correct, but essentially the name is already taken.

All in all, very good - my only comments are essentially nitpicks.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.