ならば

音とかで遊んでいたログ

二分探索木の巡回の可聴化

ChucKは、まだ発展途上の若い言語だということもあるせいか、音響とは直接関係ない部分のライブラリの充実度がかなり低い。ファイル入出力や文字列操作といった関数群の他、リンクリストやスタック、キューなどの基本的なデータ構造もほとんど用意されていない。

ファイル入出力や文字列操作は、ChucK処理系の内部に手を入れないことにはどうにもならないと思うけど、基本的なデータ構造であれば大抵は今のChucKが持つ機能だけで実装できるだろう*1

というわけで、試しに単純なノードのクラスを作って、二分探索木を実装してみた。今回のプログラムの処理の主な流れは、

  1. 二分探索木に、40から90までの整数をランダムに100個挿入する
  2. 二分探索木を巡回する

だけ。ただ、何かしら音を鳴らしたいので、また可聴化した。可聴化の方法は、整数をMIDIノート番号とみなして、二分探索木の巡回時に各ノードに格納されているMIDIノート番号の音高の音を鳴らすようにした。巡回方法は行きがけ順、通りがけ順、帰りがけ順の3種類を用意した。

録音したもの。巡回した二分探索木は全部同じ。
行きがけ順 Download
通りがけ順 Download
帰りがけ順 Download
3種類の音の列を聴いて頭の中で木構造を作れるようになれば一人前。


ChucKのプログラム。

//18 => Std.srand;
100 => int N;
40 => int MIN;
90 => int MAX;
.3::second => dur T;

Rhodey rhodey => JCRev r => dac;
.2 => rhodey.gain;
.2 => r.mix;

// ノードのクラス
class Node {
    int value;
    Node @ left;
    Node @ right;
}

Node @ root;
for (int i; i < N; i++) {
    insert(Std.rand2(MIN, MAX));   
}
// ここで可聴化したい巡回方法を呼ぶ
// なんたらorder(root);

fun void insert(int v) {
    Node node;
    v => node.value;
    if (root == null) {
        node @=> root;
        return;
    }
    root @=> Node current;
    Node parent;
    int isLeft;
    while (current != null) {
        current @=> parent;
        if (node.value < current.value) {
            current.left @=> current;
            true => isLeft;
        } else {
            current.right @=> current;
            false => isLeft;
        }    
    }
    if (isLeft) node @=> parent.left;
    else        node @=> parent.right;
}

// 行きがけ順
fun void preorder(Node node) {
    if (node == null) return;
    output(node.value);
    preorder(node.left);
    preorder(node.right);
}

// 通りがけ順   
fun void inorder(Node node) {
    if (node == null) return;
    inorder(node.left);
    output(node.value);
    inorder(node.right);
}

// 帰りがけ順   
fun void postorder(Node node) {
    if (node == null) return;
    postorder(node.left);
    postorder(node.right);
    output(node.value);
}

fun void output(int v) {
    v => Std.mtof => rhodey.freq;
    1 => rhodey.noteOn;
    T => now;
}

*1:ただし、今のChucKは名前空間やアクセス指定子の実装が不十分だったりインポート機能がなかったりするので、標準ライブラリのような形としてまとめるのは無理