Hatena::Grouperlang

檜山正幸のErlang未確認情報 RSSフィード

 | 

2009-04-01 (水)

tree-like構造の変更

| 09:04

あのひとりごとの背景をまとめる。

ファイルシステムに似た木構造を考える。

ファイルシステム ここでのデータ構図
ディレクトリ 中間ノード
ファイル ノード
ファイルの中身
ファイルの種類 値の型

中間ノードを単にノードと呼ぶことにして、

-record(node, {
          options = [],
          children = []
          }).

つう感じ。optionsはXMLの属性みたいな雰囲気。都合により、値の型情報は値ノードには含まれず、別なところ(スキーマ)に入っている。

パス /a/b/c の内部表現は [a, b, c] というアトム・リスト。パスを渡されて値を取ってくるのは割と簡単。[追記]「このほうが見やすい」に従って書き換えるのがよろし。[/追記]

%% -*- coding: utf-8 -*-

%% @doc tree-like構造のサンプル.
%% いろいろと手抜き。
-module(toytree).

%-export([]).
-compile(export_all).

-record(node, {
          options = [], % サンプルでは未使用
          children = []
         }).

-define(is_node(X), is_record(X, node)).
-define(get_children(Node), Node#node.children).
-define(set_children(Children, Node), 
        Node#node{children = Children,
                  options = Node#node.options}).

get_value(Name, Data) ->
  if ?is_node(Data) -> % proplists:get_value/1 にお任せー
      % 注意:
      % proplists:get_value/1 は、Nameに対応する値がないと
      % undefinedを返す。undefinedという値があったときと
      % 区別がつかいない。まーイイトシヨウ。
      proplists:get_value(Name, ?get_children(Data));
     true ->
      throw(not_a_node_cannot_get)
  end.

get_value_path(_Path = [], Data) -> % まんま出してしまう、ちとヤバイが
  Data;
get_value_path([Name|Rest], Data) ->
  Next = get_value(Name, Data), % undefinedの判定もしなくていいや、死にます
  get_value_path(Rest, Next).

さて、パスを渡されて、そこの値を書き換えることが問題。まず、パスのリストを左から見て木を下にたどる。パスが [A1, A2, ..., An]のとき、Root = N0とすると、次のような感じでたどる。

  • N0 -(A1)→ N1 -(A2)→ ... Nn -1-(An)→ Nn

このとき、くだってきたパスの履歴を引数で記録しておいて、木全体の再構築を下から上に実行。文章で説明はメンドウだが;

set_value(Name, Value, Data) ->
  if ?is_node(Data) ->
      Children = proplists:delete(Name, ?get_children(Data)),
      ?set_children([{Name, Value} | Children], Data);
     true ->
      throw(not_a_node_cannot_set)
  end.

set_value_path(_Path = [], Value, _Data) ->
  Value;
set_value_path(Path, Value, Data) ->
  set_value_path(_Visited = , _Walked = , Path, Value, Data).

set_value_path(Visited, Walked, [Key], Value, Current) ->
  NewCurrent = set_value(Key, Value, Current),
  rebuild(Visited, Walked, NewCurrent);
set_value_path(Visited, Walked, [Key|Rest], Value, Current) ->
  {SavingCurrent , Next} = 
    case get_value(Key, Current) of
      undefined -> % ノードがないときは新しく作る、ここがメンドー
        NewNext = new_node(),
        NewCurrent = set_value(Key, NewNext, Current),
        {NewCurrent, NewNext};
      Data ->
        {Current, Data}
    end,
  set_value_path([SavingCurrent|Visited], [Key|Walked], Rest, Value, Next).

rebuild(_Visited = [UpperNode|V_Rest], _Walked = [Key|W_Rest], NewNode) ->
  NewUpperNode = set_value(Key, NewNode, UpperNode),
  rebuild(V_Rest, W_Rest, NewUpperNode);
rebuild([], [], Node) ->
  Node.

ここで、rebuildがミソ。変更箇所は常にリーフ、記録しておいたルートからのチェーンを逆向きにたどりながら、次々と構造を作り替えていく。メモリのお祭り騒ぎでコピーしては捨てながら完全に作り直す。その再構築はボトムアップ

このtoytreeをもう少し複雑にしたモノを考えていて、その挙動を試行錯誤するために、minshを作った。toytreeのminshに対するコールバックは次のよう。

%%%% minshのコールバック関数 %%%%%

print(Data) ->
  print(0, ".", Data).

print(Indent, Name, Data) ->
  do_indent(Indent),
  if ?is_node(Data) ->
      io:format("+- ~s~n", [Name]),
      Children = ?get_children(Data),
      lists:foreach(
        fun({Key, Value}) ->
            print(Indent + 1, Key, Value)
        end,
        Children);
     true ->
      io:format("|- ~s ~p~n", [Name, Data])
  end.

do_indent(Indent) ->
  io:format(lists:duplicate(Indent*3, 32)).

command_init(_InitArg) ->
  new_node().

help_str() ->
  ("s {Path, Val}  -- set_value_path(Path, Val, Tree)\n"
   "ENTER          -- prety-print\n"
   "SP {Path, Val} -- set_value_path and pretty-print\n"
   "SP Path        -- get_value_path(Path, Tree)\n"
   ).

command('?', _Arg, State) ->
  io:format(help_str()),
  {ok, State};
command(s, {Path, Val}, State) ->
  NewState = set_value_path(Path, Val, State),
  {ok, NewState};
command('', Arg, State) -> % 改行だけは
  case Arg of
    none ->
      print(State),
      {ok, State};
    {Path, Val} ->
      NewState = set_value_path(Path, Val, State),
      print(NewState),
      {ok, NewState};
    Path when is_list(Path) ->
      V = get_value_path(Path, State),
      io:format("Value = ~p~n", [V]),
      {ok, State};
    _ ->
      io:format("command syntax error~n"),
      {ok, State}
  end;
command(_, _, State) ->
  io:format("illegal command~n"),
  {ok, State}.

 |