Guy E. Blelloch, et. al., "Just Join for Parallel Ordered Sets" (2016) のアルゴリズムを ruby に直訳することで、 赤黒木の非破壊 join 関数で順序付き集合演算を書いていきます。join 関数は既に見たように、 2本の木の間にキーをはさんで新しい木を求…
2 本の赤黒木を左右のどちらかに非破壊で連結した新しい赤黒木を求める JOIN 関数を、 Guy E. Blelloch, et. al., Just Join for Parallel Ordered Sets (2016) に基づいて書いてみます。 ただし、 元論文から安直化してシングルスレッド用の関数を書くこと…
Array オブジェクトを正規リストとみなしてみましょう。 空の Array オブジェクトは、 当然、 空リストです。 では、 3 個の要素を持つ Array オブジェクトではどうでしょうか。 car は先頭の要素なのは明らかです。 一方、 cdr は先頭を除く残りの要素が並…
GNU Emacs の編集コマンドは interactive 特殊形式を持つだけでなく、 この特殊形式で対話時に引数をどのように得るかを指定します。 この仕掛けは、 関数と編集コマンドの差異をなくす働きをします。 エディタの read-eval-print ループからは、 特殊形式を…
「行の折り返し表示 その 3」 でテキスト・エディタで長い文書ファイルを開いても、 表示速度が極端に落ちないようにと、 行の折り返し表示のための書記素クラスタ情報をキャッシュすることにしました。 ところが、 キャッシュは良いことばかりではないよう…
ここまでで、 マルチ・バッファにする下地は整っているので、 まずは、 落穂拾いから始めます。テキスト挿入もしくは削除に伴い、 マークと行折り返しレイアウト・キャッシュを更新する目的で、 Window に buffer 属性を、 Buffer に window 属性を設けて相…
Emacs のインクリメンタル・サーチを真似してみます。 このサーチ法は、 1 文字入力するごとに、 パターンを 1 文字増やしながら同時に文字列を探します。 開始方法は 2 つあります。 isearch-forward (C-s) コマンドで現点から後方への検索を開始し、 isear…
ミニバッファは、 コマンド実行に必要な文字列を利用者との対話によって得たいときに使います。 普段、 キーボード入力は Window につながっています。 それを一時的にミニバッファが譲り受けて、 対話が終わると、 Window へ返却します。 キーボード入力の…
Window は WindowBase の派生クラスです。 同じ WindowBase の派生クラス MiniWindow との違い、 MiniWindow が画面出力専用であるのに対し、 Window はコマンド実行による編集作業を補助するメソッドをいくつか備えています。 また、 モード行をもっており…
テキスト・エディタが端末画面に複数のウィンドウを表示するとき、 画面を分割して隙間なくウィンドウをタイルのように並べる方式が定番になっています。 ここで作ろうとしているエディタも複数のウィンドウをタイリング方式で表示できるようにしていきます…
Emacs は文字列補完機能をもっています。 補完機能を使うには、 文字をいくつかタイプして TAB キーを押します。 すると、 タイプ済みの文字列で始まるコマンド名やファイル名を探して長い文字列に展開してくれます。 Emacs のコマンド名には長いものが多い…
エコー領域は端末画面最下にあり、 エディタからのメッセージを表示する場所です。 ここでは、 エコー領域兼ミニバッファの表示に MiniWindow を使います。 MiniWindow のインスタンスはエディタ稼働中に 1 個存在し続け、 Screen が保持しています。 Screen…
Craig Finseth は、 文字単位で現点を前後へ動かす関数を point_move としていました。 その関数は移動量を示す count を引数にとってました。 count が負のときは前方向へ現点を動かし、 正のときは後方向へ現点を動かしていました。 count の絶対値は移動…
Emacs 系のテキスト・エディタは文字を一文字ずつバッファに self-insert-command で挿入していきます。 ところが、 Undo コマンド (C-x u) は、 挿入単位の一文字ごとではなく、 一連の文字挿入をまとめて巻き戻すように作ってあります。 一連の文字削除も…
ruby 添付ライブラリ optparse は、 オプションの省略可引数を Optional と Placed の 2 種類に分けて区別します。 特に理由がなければ、 Optional を使わず、 Placed を使いましょう。 この 2 つには、 コマンドライン解釈時に、 オプションと省略可引数の…
test-unit の test-unit-runner-tap を使って Test Anything Protocol (TAP) 出力をおこなわせる備忘録です。bundler で sample gem を作ります。 $ gem install bundler $ bundle gem sample --test minitest --mit $ cd sampleGEM テンプレート sample.gem…
行の書記素クラスタの開始配列 Line、 行の折り返し配置情報 Grid の両方ともキャッシュで最近使ったものを保持しています。 キャッシュに保持可能な項目数は、 キャッシュ・オブジェクト生成時に指定し、 以後、 保持可能項目数を変更することはできません…
昨日の Layout は対象行の書記素クラスタの開始位置の配列 Line を使いました。 これを求めるのは Buffer の役目です。 Line = Struct.new(:first, :last, :h) # Line[first=200, last=211, h=[0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11]] # |H |e |l |l |o |こ|…
C. Finseth The Craft of Text Editing の基本エディタ部は、 画面表示部から独立しています。 そのため、 どこが画面に表示されているかに依存せず、 現点を自在に移動することができます。 画面表示部では、 現点を画面に表示できるように表示開始点を求め…
カレント・ディレクトリを ls (1) コマンドのカラム形式の真似をして表示します。 だいぶ前に書いたコードがあるのですが、 必要以上に複雑に書きすぎていて反省。 今度は、 必要最小限のシンプルさを心がけてみました。 Point2d = Struct.new(:y, :x) class…
前のキー入力部は、 ESC f のように、 ESC に文字を組み合わせることを前提にしていました。 そのため、 keymap で ESC にシンボルを指定しても、 ESC を押した後にキー入力待ちをしてしまいました。 これでは、 インクリメンタル・サーチのように ESC を単…
Emacs 風のコマンド入力を解釈するのに必要な端末入力機能は、 コード・ポイント 1 個分の文字列を get メッセージで得ることができ、 unget でコード・ポイント 1 個分の文字列を読み戻せなければなりません。 さらに、 一連のキー入力の途中でエコー表示を…
Emacs のキー入力は、 コマンドに結びつけたキー入力文字列の前に数値引数をくっつけることができます。 この前置引数には 2 通りの打ち込み方があります。 私が良く使う汎引数と、 めったに使わない数値引数です。 デフォルトでは、 汎引数 universal-argum…
Ruby では、 オブジェクトをキャッシュする用途に添付ライブラリ WeakRef が使えるようになっています。 ただし、 WeakRef を使うとオブジェクトをゴミ集め時に廃棄するため、 短命のキャッシュにしか使えません。 そこで、 ゴミ集めの頻度よりも長い時間に…
前回のギャップ・バッファのギャップ移動を使って、 挿入・削除・置換を試してみます。挿入では、 現点にギャップを移動します。 ギャップのバイト数が挿入したい文字列のバイト数よりも大きくなるように適宜バッファを grow メソッドで長くします。 そして…
xterm は ANSI 画面制御シーケンスに、 行削除 (\e[L) と行挿入 (\e[M) をもっています。 1 行だけでなくパラメータで行数を指定して、 複数の行を一度に削除したり挿入することもできます。 挿入するのは空行です。 さらに、 この 2 つを組み合わせることで…
Unicode Character Database の EastAsianWidth に対応する wcwidth です。 コード・ポイントに対する文字が、 端末上で必ず半角なら 1、 必ず全角なら 2 を返します。 フォントによって半角かもしれず、 全角かもしれないなら 3 を返します。文字幅情報は 2…
Terminfo (5) ケーパビリティは、 様々な端末のエスケープ・シーケンスに柔軟に対応するために、 スタック計算機を組み込んであります。 それを使って、 パラメータを加工して、 望みの位置に望みの形式でパラメータを展開していきます。 そのスタック演算と…
4 年前に書いたロープに手を入れました。⇒ https://gist.github.com/tociyuki/10372481 avlrope.rb ⇒ AVL 木なロープもどき ⇒ Rope もどきの落ち穂拾い算法は同じです。 このロープの木は、 部分木に含まれている文字数による Weight 木になっていて、 木の…
Seeing double: how Ruby shares string values の内容に次の 4 点を追記しておきます。 リテラル文字列は SHARED です。 リテラル文字列へ束縛している String オブジェクトを破壊操作すると、 文字列実体であるバイト列を複製して書き込みます (copy-on-wr…
