[Ruby]破壊操作版 keymap

Emacs 風コマンド解釈器は、 キー結合を入れ子 Hash によるトライ木に保持していました。 Emacs では、 Hash ではなくリストを使って同じように入れ子構造のトライ木を使っていますが、 トライ木をあたかも文字列の連想配列のように扱えるようにしてあります。 真似して、 次のように結合を記述できるようにしてみます。

keymap = Keymap.new
keymap["\C-x\C-x"] = :exchange_point_and_mark
p keymap["\C-x\C-x"] #=> :exchange_point_and_mark
keymap2 = keymap.copy
keymap2.delete("\C-x\C-x")
p keymap["\C-x\C-x"] #=> :exchange_point_and_mark
p keymap2["\C-x\C-x"] #=> nil

このトライ木は破壊操作で関連を追加・削除します。 元のトライ木を破壊操作せずに関連を変更するために深いコピーをできるようにしてあります。 match は Command クラスの match へ根を渡して、 キー入力をおこないます。 clear は全部空にします。

class Keymap
  attr_reader :root

  def initialize(root={})
    @root = root
  end

  def match(tty, &blk) Command.match(@root, tty, &blk) end

  def clear()
    @root.clear
    self
  end

#@<関連付け追加@>
#@<参照@>
#@<delete@>
#@<copy@>
end

新しい関連付けを追加します。 キーがシンボルのときは、 根に追加しておしまいです。 キーが文字列のときはコード・ポイント列にばらして、 根から順に Hash を辿って葉へ行き着けるようにトライ木を作ります。 C-x 等の既に Hash になっているものを葉で再定義しようとすると conflict のメッセージで例外を発生します。

#@<関連付け追加@>=
  def []=(key, definition)
    case key
    when Symbol
      @root[key] = definition
    when String
      a = key.each_char.to_a
      d = a.pop
      h = @root
      a.each {|c| h = (h[c] ||= {}) }
      not Hash === h[d] or raise 'conflict'
      h[d] = definition
    else
      raise ArgumentError
    end
  end

関連付けの参照は、 追加と同じように葉まで辿って値を返します。

#@<参照@>=
  def [](keys)
    case keys
    when Symbol
      @root[keys]
    when String
      h = @root
      keys.each_char do |c|
        Hash === h or return nil
        h = h[c]
      end
      h
    else
      raise ArgumentError
    end
  end

トライ木からキー文字列の関連付けを削除します。 削除可能なものは、 葉へたどり着くキー文字列の経路に限ります。 葉まで経路を記録しながら降りていき、 今度は根へ戻りながら、 要素数がゼロになった Hash も削除していきます。

#@<delete@>=
  def delete(key)
    case key
    when Symbol
      @root.delete(key)
    when String
      path = []
      h = @root
      key.each_char do |c|
        Hash === h or return nil
        path << [h, c]
        h = h[c]
      end
      not Hash === h or return nil
      path.reverse_each do |h, c|
        h.delete(c)
        h.empty? or return nil
      end
      nil
    else
      raise ArgumentError
    end
  end

キーマップを複製します。 循環構造がないことと、 木が浅いことを前提にしています。

#@<copy@>=
  def copy()
    self.class.new(trie_copy(@root))
  end

  def trie_copy(trie)
    r = {}
    trie.each_pair do |k, v|
      r[k] = (Hash === v) ? trie_copy(v) : v
    end
    r
  end