Erlang ２分探索木 挿入 insert

今日は、２分探索木のinsertを作ってみた。
■insert/2
insert( Key, Value , Tree ) -> tree() | {key_exists, Value }

{key_exists, Value }はすでに同一キーがTreeにある場合。
tree()は挿入後のツリー


【ソース】

-module( binary_tree_insert ).
-export( [ insert/3 ] ).

-ifdef( debug ).
-include_lib( "eunit/include/eunit.hrl" ).
-define( print(Fmt, Args), io:format ( "~p:~p " Fmt "~n", [ ?MODULE, ?LINE ] ++ Args ) ).
-else.
-define( print(Fmt, Args), ok ).
-endif.

% tree()
-record( tree, { key, value, smaller, bigger } ).
-define( procCase( X, Y ),
        ( begin
               case is_record( SubTree1, tree ) of
                       false->
                               ?print( "",[] ),
                               Tree;
                       true ->
                               ?print( "",[] ),
                               Tree#tree{ X=Y }
               end
          end )
        ).
-define( ArgNode, { Key, _ } = Node ).
-define( ArgTree, #tree{ key=Key1, value=Value, smaller=Smaller, bigger=Bigger } = Tree ).
-define( procInsert( X, Y, Z), X = insert_1( Y, Z ) ).

%% @spec insert( Key, Value , Tree ) -> tree() | {key_exists, Value }
%% { key_exists, Value } = already exist.

insert( Key, Value, Tree ) ->
        insert_1( #tree{ key=Key, value=Value }, Tree ).

insert_1( Node, undefined ) ->
        Node;

insert_1( Node, Tree ) when Node#tree.key < Tree#tree.key ->
        SubTree1 = insert_1( Node, Tree#tree.smaller ),
        ?procCase( smaller, SubTree1 );

insert_1( Node, Tree ) when Node#tree.key > Tree#tree.key ->
        SubTree1 = insert_1( Node, Tree#tree.bigger ),
        ?procCase( bigger, SubTree1 );

insert_1( _, Tree ) ->
        { key_exists, Tree#tree.value }.

-ifdef(debug).
-define( E, #tree{ key=nine, value=9 } ).
-define( T1, #tree{ key=nine, value=9 } ).
%-define( T1, #tree{ ker=nine, 9, undefined, undefined } ).
-define( Tree, #tree{ key=nine, value=9, smaller=#tree{ key=five, value=5 }, bigger=#tree{ key=ten, value=10 } } ).

i1_test() ->
        #tree{ key=nine, value=9 }
        =
        insert_1( ?E, undefined ).
i2_test() ->
        { key_exists, 9 }
        =
        insert_1( ?E, ?Tree ).
i3_test() ->
        #tree{ key=nine, value=9, smaller=#tree{ key=eight, value=8 } }
        =
        insert_1( #tree{ key=eight, value=8 }, ?T1 ).
i4_test() ->
        #tree{ key=nine, value=9, bigger=#tree{ key=ten, value=10 } }
        =
        insert_1( #tree{ key=ten, value=10 }, ?T1 ).
i5_test() ->
        #tree{ key=nine,
               value=9,
               smaller=
                    #tree{ key=five,
                           value=5,
                           smaller=#tree{ key=eight, value=8 } },
               bigger=#tree{ key=ten, value=10 } }
        =
        insert_1( #tree{ key=eight, value=8 }, ?Tree ).
-endif.


参考：
M.Hiroi's Home Page / お気楽 Erlang プログラミング入門 : http://www.geocities.jp/m_hiroi/func/abcerl05.html
Erlang -- erlang : http://www.erlang.org/doc/man/erlang.html#is_record-2
letter: 2007/05 - 2007/06 : http://read-eval-print.blogspot.com/2007_05_01_archive.html
gb_tree.erlのソース