/**
n-way trees in D language, by maffi leonardo, V.1.0, Feb 25 2008
*/

module tree;

import std.string: str = format, join;
import d.func: putr, map, xmap, fmin = min; // from www.fantascienza.net/leonardo/so/libs_d.zip

/// n-way tree node, code designed to be simple and very short, even if not efficient
class Tree(T) {
    T data;
    Tree!(T)[] subs; // children

    static Tree opCall(T d) {
        auto t = new Tree;
        t.data = d;
        return t;
    }
    string toString() {
        // Warning: data can't a string with a '%' char inside
        return "(" ~ join(str(data) ~ map(&str, subs), ", ")  ~ ")";
    }
    /// replace every node-data with a fixed value
    void replace(T repl) {
        data = repl;
        foreach(s; subs)
        s.replace(repl);
    }
    /// to walk (pre-visit) all the tree nodes lazily
    int opApply(int delegate(ref Tree) dg) {
        int result;
        result = dg(this); if (result) return result;
        foreach(t; subs)
            foreach(s; t) {
                result = dg(s);
                if (result) return result;
            }
        return result;
    }
    /// minimum node-data for the whole tree
    T min() {
        return fmin(xmap((Tree t){return t.data;}, this));
    }
    // T min(){Tree t; return len(subs) ? fmin(data, fmin(select(t.min, t, subs))) : data;}
    // to simplify the code necessary to built the tree
    void opCatAssign(Tree t) { subs ~= t; } /// add a new child
    Tree opIndex(int i) { return subs[i]; } /// reference a child
    void opIndexAssign(Tree t, int i) { subs[i] = t; } /// assign to a child
}

void main() {
    alias Tree!(int) Itree;
    auto t = Itree(1);
    putr(t.min, " ", t); // Prints: 1 (1)
    t.replace(10);
    putr(t.min, " ", t); // Prints: 10 (10)
    t ~= Itree(-1);
    t ~= Itree(-2);
    putr(t.min, " ", t); // Prints: -2 (10, (-1), (-2))
    t[1] ~= Itree(3);
    t[1] ~= Itree(0);
    t[1][1] ~= Itree(-5);
    putr(t.min, " ", t); // Prints: -5 (10, (-1), (-2, (3), (0, (-5))))
    t.replace(t.min);
    putr(t.min, " ", t); // Prints: -5 (-5, (-5), (-5, (-5), (-5, (-5))))
}