Sunday, May 4, 2014

An example of value-level programming in Java

In this post, which is just a big listing of code, I translate a C++ generic algorithm from the <algorithm> STL header into Java, using only basic features of Java. To prove that the generic algorithm can be used on any third-party data structure, I give an example of using it on a Java built-in array. I hope the example is nontrivial enough to show that many STL algorithms can be translated in the same way. More generally, I want to explore the possibility that "value-level programming" might be a good solution to the problems that C++ generic programming was intended to solve, as described in this interview with Alex Stepanov.

You can paste the code into http://www.compileonline.com/compile_java_online.php to try it out:

public class Main {

    // http://www.sgi.com/tech/stl/BidirectionalIterator.html
    static interface BidirectionalIteratorOperations<Iterator> {
        Iterator increment(Iterator iterator);
        Iterator decrement(Iterator iterator);
        boolean equal(Iterator first, Iterator second);
    }

    // This part factored out for convenience.
    static interface Dereference<Iterator, Value> {
        Value get(Iterator iterator);
        void set(Iterator iterator, Value value);
    }

    static interface UnaryPredicate<Value> {
        boolean test(Value value);
    }

    // http://www.cplusplus.com/reference/algorithm/partition/
    // Line-by-line translation.
    // Note that Iterator and Value can be _any_ types.
    static <Iterator, Value> Iterator partition(
        Iterator first,
        Iterator last,
        UnaryPredicate<Value> predicate,
        Dereference<Iterator, Value> dereference,
        BidirectionalIteratorOperations<Iterator> operations
    ) {
        while (!operations.equal(first, last)) {
            while (predicate.test(dereference.get(first))) {
                first = operations.increment(first);
                if (operations.equal(first, last)) {
                    return first;
                }
            }
            do {
                last = operations.decrement(last);
                if (operations.equal(first, last)) {
                    return first;
                }
            } while (!predicate.test(dereference.get(last)));
            swap(first, last, dereference);
            operations.increment(first);
        }
        return first;
    }
    
    // This isn't the true swap from C++, which swaps values.
    static <Iterator, Value> void swap(
        Iterator first,
        Iterator second,
        Dereference<Iterator, Value> dereference
    ) {
        Value temp = dereference.get(first);
        dereference.set(first, dereference.get(second));
        dereference.set(second, temp);
    }
    
    // Let's use the above to partition a Java built-in array,
    // using Integers as iterators.
    public static void main(String [] args) {
        final Double [] data =
            new Double [] { 1.0, 2.0, 3.0, 4.0, 5.0 };
        UnaryPredicate<Double> predicate =
            new UnaryPredicate<Double>() {
                public boolean test(Double value) {
                    return (value < 1.5) || (value > 4.5);
                }
            }
        ;
        Dereference<Integer, Double> dereference =
            new Dereference<Integer, Double>() {
                public Double get(Integer index) {
                    return data[index];
                }
                public void set(Integer index, Double value) {
                    data[index] = value;
                }
            }
        ;
        BidirectionalIteratorOperations<Integer> operations =
            new BidirectionalIteratorOperations<Integer>() {
                public Integer increment(Integer index) {
                    return index + 1;
                }
                public Integer decrement(Integer index) {
                    return index - 1;
                }
                public boolean equal(Integer first, Integer second) {
                    return first == second;
                }
            }
        ;
        partition(0, data.length, predicate, dereference, operations);
        System.out.println(java.util.Arrays.toString(data));
    }
}

No comments:

Post a Comment