2012年1月22日日曜日

Erlang 2分探索木 更新 update

今日は、2分探索木の更新(update/3)を。青文字部分はユニットテストのためのソース。

仕様は以下の2点。
1.更新するノード(Key)がある場合、Valueを更新する。
2.更新するノード(Key)がない場合、対象ノードを挿入する。

◆ソース

-module( binary_tree_update ).
-export( [ update/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.

-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 } } ).
-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 update( Key, Value, Tree ) -> tree()
%% Tree内にKeyが存在する場合、Valueを更新する.
%% Tree内にKeyが存在しない場合、Key/Valueのノードを挿入する.
update( Key, Value, Tree ) ->
        update_1( #tree{ key=Key, value=Value }, Tree ).

update_1( Node, undefined ) ->
        Node;

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

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

update_1( Node, Tree ) ->
        Tree#tree{ value=Node#tree.value }.

-ifdef(debug).
%% insert test
u1_test() -> 
        #tree{ key=nine, value=9 } 
        = 
        update_1( ?E, undefined ).
u3_test() -> 
        #tree{ key=nine, value=9, smaller=#tree{ key=eight, value=8 } } 
        = 
        update_1( #tree{ key=eight, value=8 }, ?T1 ).
u4_test() -> 
        #tree{ key=nine, value=9, bigger=#tree{ key=ten, value=10 } } 
        = 
        update_1( #tree{ key=ten, value=10 }, ?T1 ).
u5_test() ->
        #tree{ key=nine,
               value=9,
               smaller=
                    #tree{ key=five, 
                           value=5,
                           smaller=#tree{ key=eight, value=8 } },
               bigger=#tree{ key=ten, value=10 } } 
        =
        update_1( #tree{ key=eight, value=8 }, ?Tree ).
%% update test
u6_test() ->?assert(
        #tree{ key=nine, value=90 }
       =:=
        update_1( #tree{ key=nine, value=90 }, ?T1 )
        ).
u2_test() -> ?assert(
        ?Tree 
        =:=
        update_1( ?E, ?Tree ) ).
u7_test() -> ?assert(
        #tree { key=nine, value=9, smaller=#tree{ key=five, value=50 }, bigger=#tree{ key=ten, value=10 } }
        =:=
        update_1( #tree{ key=five, value=50 }, ?Tree ) ).
u8_test() -> ?assert(
        #tree { key=nine, value=9, smaller=#tree{ key=five, value=5 }, bigger=#tree{ key=ten, value=100 } }
        =:=
        update_1( #tree{ key=ten, value=100 }, ?Tree ) ).
-endif.

0 件のコメント:

コメントを投稿