とりあえず日記

VIM→秀丸エディタ→VIM→秀丸エディタ→VIM→秀丸エディタ→VIM→秀丸エディタ→VIM→秀丸エディタ→VIM→秀丸エディタ（いまここ🍄）

秀丸エディタで赤黒木(rb_tree/red black tree)をダンプ表示してみた。

C++ 秀丸エディタ

（5月21日 追記）
空白区切りになっていたので改行区切りへ修正しました。std::cinの使い方を間違っていました。
https://github.com/ohtorii/rb_tree

（5月14日 追記）
うまく起動しないことがあったので実行ファイルへのパスを修正しました。これで大丈夫なはず。

（5月3日 追記）
スクリプトパスに空白が含まれていると実行ファイルが起動しないバグがありました。
お手数ですが、もう一度 Github から取得し直してみて下さい。

概要

昔々、オレオレSTLを開発していた頃に、自作の赤黒木をデバッグするために使用した秀丸マクロです。
VisualStudio附属のSTL（Dinkumware社製）の赤黒木をダンプ表示します。


赤黒木を自作されている方の助けになれば幸いです。


C++の仕様書にはset/mapの内部実装が赤黒木であるとは書いてなかったはずですが、多くのSTLが内部実装に赤黒木を使用しているので、ここではset/mapの内部実装は赤黒木であるものとします。

スクリプトはこちらから

右上のダウンロードボタンを押してzipを選択。
https://github.com/ohtorii/rb_tree

動作イメージ（その１）

  • 赤黒木に登録する文字を並べます。


  • マクロを起動するとメニューが開きます。ここではsetを選択します。


  • 新しいタブに赤黒木の状態がダンプ表示されます。


左側が親ノードで右側が子ノードです、テキストエディタの都合が色々とありまして、このようになっています
エクスプローラーのファイル一覧と同じような見せ方です。

動作イメージ（その２）

  • 赤黒木に登録する文字を並べます、ここでは重複する文字があります。


  • メニューからmultiset を選択します。


  • 赤黒木に重複を許して登録されています。

選択範囲について

  • 選択範囲があればその範囲を対象にします。


  • マクロ実行後（選択した４行が登録されています。）

ちょっとした使いこなし

  • 木が上下に長く見にくいときは


  • 縦書きにすると・・・


  • 多少見やすくなります。


本当に多少ですが・・・

内部実装

  • 概要

自作の実行ファイル(.exe)へ秀丸エディタのテキストを送りつけて、exe側で全て処理しています。
exeと秀丸は標準入出力でやりとりしています。

  • exe側

std::set<>が内部に持っている「赤／黒」のフラグを取り出してprintfしているだけです。
詳細は rb_tree.cpp を参照して下さい。

typedef std::set<std::string>       set_string_type;

＜＜諸々省略＞＞

{
    //rb-treeの「left-mostを最下段」「right-mostを最上段」にするため reverse_iterator を使用。
    set_string_type::const_reverse_iterator  first   = tree.rbegin();
    set_string_type::const_reverse_iterator  last    = tree.rend();
    set_string_type::const_iterator          nil_node= tree.end();

    for(; first!=last ; ++first){
        set_string_type::const_reverse_iterator tmp = first;

        //const_reverse_iterator を剥いで中身(const_iterator)を取り出す。
        ++tmp;
        set_string_type::const_iterator cur = tmp.current;

        //木の深さ分、printでスペースを挿入。
        print_space(node_depth(cur,nil_node));

        //フラグから色を判定、
        printf("[%s]%s\n", cur._Ptr->_Color==set_string_type::_Black?"B":"R", cur._Ptr->_Myval.c_str());
    }
}

//木の深さを求める
static int node_depth(set_string_type::const_iterator first, set_string_type::const_iterator last){
    int i =0;
    
    //イテレータの中身を剥いで
    for(; first._Ptr!=last._Ptr; first._Ptr=first._Ptr->_Parent){
        ++i;
    }
    
    //ルート==1 なので減じておく
    --i;
    return i;
}

//空白を挿入するだけの関数
static void print_space(int n){
    while(0<n){
        printf("    ");
        --n;
    }
}