module pind.samples.ja.fibers.fibers_3;

import std.stdio;
import std.string;
import std.conv;
import std.random;
import std.range;
import std.algorithm;

/* バイナリツリーのノードを表す。この型は、
 * 以下の構造体Treeの実装で使用されるため、
 * 直接使用してはならない。 */
struct Node {
    int element;
    Node * left;     // 左サブツリー
    Node * right;    // 右サブツリー

    void insert(int element) {
        if (element < this.element) {
            /* 小さい要素は左サブツリーに入る。 */
            insertOrSet(left, element);

        } else if (element > this.element) {
            /* 大きい要素は右サブツリーに入る。 */
            insertOrSet(right, element);

        } else {
            throw new Exception(format("%s already exists",
                                       element));
        }
    }

    void print() const {
        /* まず、左サブツリーの要素を表示する */
        if (left) {
            left.print();
            write(' ');
        }

        /* 次にこの要素を表示する */
        write(element);

        /* 最後に右サブツリーの要素を表示する */
        if (right) {
            write(' ');
            right.print();
        }
    }
}

/* 指定されたサブツリーに要素を挿入し、必要に応じて
 * そのノードを初期化する。 */
void insertOrSet(ref Node * node, int element) {
    if (!node) {
        /* このサブツリーの最初の要素。 */
        node = new Node(element);

    } else {
        node.insert(element);
    }
}

/* これは実際のツリー表現。'root'が'null'である場合、空の
 * ツリーを許可する。 */
struct Tree {
    Node * root;

    /* 要素をこのツリーに挿入する。 */
    void insert(int element) {
        insertOrSet(root, element);
    }

    /* 要素をソート順に表示する。 */
    void print() const {
        if (root) {
            root.print();
        }
    }
}

/* '10 * n'個の数字からランダムに選んだ
 * 'n'個の数字でツリーを埋める。 */
Tree makeRandomTree(size_t n) {
    auto numbers = iota((n * 10).to!int)
                   .randomSample(n, Random(unpredictableSeed))
                   .array;

    randomShuffle(numbers);

    /* それらの数字でツリーを埋める。 */
    auto tree = Tree();
    numbers.each!(e => tree.insert(e));

    return tree;
}

void main() {
    auto tree = makeRandomTree(10);
    tree.print();
}