rope ライブラリ - まめめもICFPC で話題になった rope/cord ですが、特定の言語環境でしか使えないのはもったいない話です。そこで Ruby の拡張ライブラリとして実装しようとしました。 rope とは 以下の特徴を持った文字列の実装です。 文字列と文字列の結合が速い (O(log n)) らしい 部分文字列の切り出しが速い (O(log n)) らしい 部分の書き換えはできない 指定位置からの文字の取り出しは遅い (O(log n)) でも一文字ずつ順にたどるのは実用上は O(n) らしい 詳しい話はいなばさんの解説なり元論文なりを見てください *1 。 実装方針 Boehm GC 付属の Cord のコードを Boehm GC なしで動くようにする (リファレンスカウントを実装する) 。 Ruby 側のインターフェイスは String 互換 (ただし破壊的操作と正規表現機能はなし) ただ、C の文字列
