C0 code coverage information

Generated on 2009-08-09 21:22:55 with etap 0.3.4.

....1 % Licensed under the Apache License, Version 2.0 (the "License"); you may not
....2 % use this file except in compliance with the License. You may obtain a copy of
....3 % the License at
....4 %
....5 %   http://www.apache.org/licenses/LICENSE-2.0
....6 %
....7 % Unless required by applicable law or agreed to in writing, software
....8 % distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
....9 % WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
...10 % License for the specific language governing permissions and limitations under
...11 % the License.
...12 
...13 -module(couch_key_tree).
...14 
...15 -export([merge/2, find_missing/2, get_key_leafs/2, get_full_key_paths/2, get/2]).
...16 -export([map/2, get_all_leafs/1, count_leafs/1, remove_leafs/2,
...17     get_all_leafs_full/1,stem/2,map_leafs/2]).
...18 
...19 % a key tree looks like this:
...20 % Tree -> [] or [{Key, Value, ChildTree} | SiblingTree]
...21 % ChildTree -> Tree
...22 % SiblingTree -> [] or [{SiblingKey, Value, Tree} | Tree]
...23 % And each Key < SiblingKey
...24 
...25 
...26 % partial trees arranged by how much they are cut off.
...27 
...28 merge(A, B) ->
...29     {Merged, HasConflicts} =
...30     lists:foldl(
...31         fun(InsertTree, {AccTrees, AccConflicts}) ->
...32             {ok, Merged, Conflicts} = merge_one(AccTrees, InsertTree, [], false),
...33             {Merged, Conflicts or AccConflicts}
...34         end,
...35         {A, false}, B),
...36     if HasConflicts or
...37             ((length(Merged) /= length(A)) and (length(Merged) /= length(B))) ->
...38         Conflicts = conflicts;
...39     true ->
...40         Conflicts = no_conflicts
...41     end,
...42     {lists:sort(Merged), Conflicts}.
...43 
...44 merge_one([], Insert, OutAcc, ConflictsAcc) ->
...45     {ok, [Insert | OutAcc], ConflictsAcc};
...46 merge_one([{Start, Tree}|Rest], {StartInsert, TreeInsert}, OutAcc, ConflictsAcc) ->
...47     if Start =< StartInsert ->
...48         StartA = Start,
...49         StartB = StartInsert,
...50         TreeA = Tree,
...51         TreeB = TreeInsert;
...52     true ->
...53         StartB = Start,
...54         StartA = StartInsert,
...55         TreeB = Tree,
...56         TreeA = TreeInsert
...57     end,
...58     case merge_at([TreeA], StartB - StartA, TreeB) of
...59     {ok, [CombinedTrees], Conflicts} ->
...60         merge_one(Rest, {StartA, CombinedTrees}, OutAcc, Conflicts or ConflictsAcc);
...61     no ->
...62         merge_one(Rest, {StartB, TreeB}, [{StartA, TreeA} | OutAcc], ConflictsAcc)
...63     end.
...64 
...65 merge_at([], _Place, _Insert) ->
...66     no;
...67 merge_at([{Key, Value, SubTree}|Sibs], 0, {InsertKey, InsertValue, InsertSubTree}) ->
...68     if Key == InsertKey ->
...69         {Merge, Conflicts} = merge_simple(SubTree, InsertSubTree),
...70         {ok, [{Key, Value, Merge} | Sibs], Conflicts};
...71     true ->
...72         case merge_at(Sibs, 0, {InsertKey, InsertValue, InsertSubTree}) of
...73         {ok, Merged, Conflicts} ->
...74             {ok, [{Key, Value, SubTree} | Merged], Conflicts};
...75         no ->
...76             no
...77         end
...78     end;
...79 merge_at([{Key, Value, SubTree}|Sibs], Place, Insert) ->
...80     case merge_at(SubTree, Place - 1,Insert) of
...81     {ok, Merged, Conflicts} ->
...82         {ok, [{Key, Value, Merged} | Sibs], Conflicts};
...83     no ->
...84         case merge_at(Sibs, Place, Insert) of
...85         {ok, Merged, Conflicts} ->
...86             {ok, [{Key, Value, SubTree} | Merged], Conflicts};
...87         no ->
...88             no
...89         end
...90     end.
...91 
...92 % key tree functions
...93 merge_simple([], B) ->
...94     {B, false};
...95 merge_simple(A, []) ->
...96     {A, false};
...97 merge_simple([ATree | ANextTree], [BTree | BNextTree]) ->
...98     {AKey, AValue, ASubTree} = ATree,
...99     {BKey, _BValue, BSubTree} = BTree,
..100     if
..101     AKey == BKey ->
..102         %same key
..103         {MergedSubTree, Conflict1} = merge_simple(ASubTree, BSubTree),
..104         {MergedNextTree, Conflict2} = merge_simple(ANextTree, BNextTree),
..105         {[{AKey, AValue, MergedSubTree} | MergedNextTree], Conflict1 or Conflict2};
..106     AKey < BKey ->
..107         {MTree, _} = merge_simple(ANextTree, [BTree | BNextTree]),
..108         {[ATree | MTree], true};
..109     true ->
..110         {MTree, _} = merge_simple([ATree | ANextTree], BNextTree),
..111         {[BTree | MTree], true}
..112     end.
..113 
..114 find_missing(_Tree, []) ->
..115     [];
..116 find_missing([], SeachKeys) ->
..117     SeachKeys;
..118 find_missing([{Start, {Key, Value, SubTree}} | RestTree], SeachKeys) ->
..119     PossibleKeys = [{KeyPos, KeyValue} || {KeyPos, KeyValue} <- SeachKeys, KeyPos >= Start],
..120     ImpossibleKeys = [{KeyPos, KeyValue} || {KeyPos, KeyValue} <- SeachKeys, KeyPos < Start],
..121     Missing = find_missing_simple(Start, [{Key, Value, SubTree}], PossibleKeys),
..122     find_missing(RestTree, ImpossibleKeys ++ Missing).
..123 
..124 find_missing_simple(_Pos, _Tree, []) ->
..125     [];
..126 find_missing_simple(_Pos, [], SeachKeys) ->
..127     SeachKeys;
..128 find_missing_simple(Pos, [{Key, _, SubTree} | RestTree], SeachKeys) ->
..129     PossibleKeys = [{KeyPos, KeyValue} || {KeyPos, KeyValue} <- SeachKeys, KeyPos >= Pos],
..130     ImpossibleKeys = [{KeyPos, KeyValue} || {KeyPos, KeyValue} <- SeachKeys, KeyPos < Pos],
..131 
..132     SrcKeys2 = PossibleKeys -- [{Pos, Key}],
..133     SrcKeys3 = find_missing_simple(Pos + 1, SubTree, SrcKeys2),
..134     ImpossibleKeys ++ find_missing_simple(Pos, RestTree, SrcKeys3).
..135 
..136 
..137 filter_leafs([], _Keys, FilteredAcc, RemovedKeysAcc) ->
..138     {FilteredAcc, RemovedKeysAcc};
..139 filter_leafs([{Pos, [{LeafKey, _}|_]} = Path |Rest], Keys, FilteredAcc, RemovedKeysAcc) ->
..140     FilteredKeys = lists:delete({Pos, LeafKey}, Keys),
..141     if FilteredKeys == Keys ->
..142         % this leaf is not a key we are looking to remove
..143         filter_leafs(Rest, Keys, [Path | FilteredAcc], RemovedKeysAcc);
..144     true ->
..145         % this did match a key, remove both the node and the input key
..146         filter_leafs(Rest, FilteredKeys, FilteredAcc, [{Pos, LeafKey} | RemovedKeysAcc])
..147     end.
..148 
..149 % Removes any branches from the tree whose leaf node(s) are in the Keys
..150 remove_leafs(Trees, Keys) ->
..151     % flatten each branch in a tree into a tree path
..152     Paths = get_all_leafs_full(Trees),
..153 
..154     % filter out any that are in the keys list.
..155     {FilteredPaths, RemovedKeys} = filter_leafs(Paths, Keys, [], []),
..156 
..157     % convert paths back to trees
..158     NewTree = lists:foldl(
..159         fun({PathPos, Path},TreeAcc) ->
..160             [SingleTree] = lists:foldl(
..161                 fun({K,V},NewTreeAcc) -> [{K,V,NewTreeAcc}] end, [], Path),
..162             {NewTrees, _} = merge(TreeAcc, [{PathPos + 1 - length(Path), SingleTree}]),
..163             NewTrees
..164         end, [], FilteredPaths),
..165     {NewTree, RemovedKeys}.
..166 
..167 
..168 % get the leafs in the tree matching the keys. The matching key nodes can be
..169 % leafs or an inner nodes. If an inner node, then the leafs for that node
..170 % are returned.
..171 get_key_leafs(Tree, Keys) ->
..172     get_key_leafs(Tree, Keys, []).
..173 
..174 get_key_leafs(_, [], Acc) ->
..175     {Acc, []};
..176 get_key_leafs([], Keys, Acc) ->
..177     {Acc, Keys};
..178 get_key_leafs([{Pos, Tree}|Rest], Keys, Acc) ->
..179     {Gotten, RemainingKeys} = get_key_leafs_simple(Pos, [Tree], Keys, []),
..180     get_key_leafs(Rest, RemainingKeys, Gotten ++ Acc).
..181 
..182 get_key_leafs_simple(_Pos, _Tree, [], _KeyPathAcc) ->
..183     {[], []};
..184 get_key_leafs_simple(_Pos, [], KeysToGet, _KeyPathAcc) ->
..185     {[], KeysToGet};
..186 get_key_leafs_simple(Pos, [{Key, _Value, SubTree}=Tree | RestTree], KeysToGet, KeyPathAcc) ->
..187     case lists:delete({Pos, Key}, KeysToGet) of
..188     KeysToGet -> % same list, key not found
..189         {LeafsFound, KeysToGet2} = get_key_leafs_simple(Pos + 1, SubTree, KeysToGet, [Key | KeyPathAcc]),
..190         {RestLeafsFound, KeysRemaining} = get_key_leafs_simple(Pos, RestTree, KeysToGet2, KeyPathAcc),
..191         {LeafsFound ++ RestLeafsFound, KeysRemaining};
..192     KeysToGet2 ->
..193         LeafsFound = get_all_leafs_simple(Pos, [Tree], KeyPathAcc),
..194         LeafKeysFound = [LeafKeyFound || {LeafKeyFound, _} <- LeafsFound],
..195         KeysToGet2 = KeysToGet2 -- LeafKeysFound,
..196         {RestLeafsFound, KeysRemaining} = get_key_leafs_simple(Pos, RestTree, KeysToGet2, KeyPathAcc),
..197         {LeafsFound ++ RestLeafsFound, KeysRemaining}
..198     end.
..199 
..200 get(Tree, KeysToGet) ->
..201     {KeyPaths, KeysNotFound} = get_full_key_paths(Tree, KeysToGet),
..202     FixedResults = [ {Value, {Pos, [Key0 || {Key0, _} <- Path]}} || {Pos, [{_Key, Value}|_]=Path} <- KeyPaths],
..203     {FixedResults, KeysNotFound}.
..204 
..205 get_full_key_paths(Tree, Keys) ->
..206     get_full_key_paths(Tree, Keys, []).
..207 
..208 get_full_key_paths(_, [], Acc) ->
..209     {Acc, []};
..210 get_full_key_paths([], Keys, Acc) ->
..211     {Acc, Keys};
..212 get_full_key_paths([{Pos, Tree}|Rest], Keys, Acc) ->
..213     {Gotten, RemainingKeys} = get_full_key_paths(Pos, [Tree], Keys, []),
..214     get_full_key_paths(Rest, RemainingKeys, Gotten ++ Acc).
..215 
..216 
..217 get_full_key_paths(_Pos, _Tree, [], _KeyPathAcc) ->
..218     {[], []};
..219 get_full_key_paths(_Pos, [], KeysToGet, _KeyPathAcc) ->
..220     {[], KeysToGet};
..221 get_full_key_paths(Pos, [{KeyId, Value, SubTree} | RestTree], KeysToGet, KeyPathAcc) ->
..222     KeysToGet2 = KeysToGet -- [{Pos, KeyId}],
..223     CurrentNodeResult =
..224     case length(KeysToGet2) == length(KeysToGet) of
..225     true -> % not in the key list.
..226         [];
..227     false -> % this node is the key list. return it
..228         [{Pos, [{KeyId, Value} | KeyPathAcc]}]
..229     end,
..230     {KeysGotten, KeysRemaining} = get_full_key_paths(Pos + 1, SubTree, KeysToGet2, [{KeyId, Value} | KeyPathAcc]),
..231     {KeysGotten2, KeysRemaining2} = get_full_key_paths(Pos, RestTree, KeysRemaining, KeyPathAcc),
..232     {CurrentNodeResult ++ KeysGotten ++ KeysGotten2, KeysRemaining2}.
..233 
..234 get_all_leafs_full(Tree) ->
..235     get_all_leafs_full(Tree, []).
..236 
..237 get_all_leafs_full([], Acc) ->
..238     Acc;
..239 get_all_leafs_full([{Pos, Tree} | Rest], Acc) ->
..240     get_all_leafs_full(Rest, get_all_leafs_full_simple(Pos, [Tree], []) ++ Acc).
..241 
..242 get_all_leafs_full_simple(_Pos, [], _KeyPathAcc) ->
..243     [];
..244 get_all_leafs_full_simple(Pos, [{KeyId, Value, []} | RestTree], KeyPathAcc) ->
..245     [{Pos, [{KeyId, Value} | KeyPathAcc]} | get_all_leafs_full_simple(Pos, RestTree, KeyPathAcc)];
..246 get_all_leafs_full_simple(Pos, [{KeyId, Value, SubTree} | RestTree], KeyPathAcc) ->
..247     get_all_leafs_full_simple(Pos + 1, SubTree, [{KeyId, Value} | KeyPathAcc]) ++ get_all_leafs_full_simple(Pos, RestTree, KeyPathAcc).
..248 
..249 get_all_leafs(Trees) ->
..250     get_all_leafs(Trees, []).
..251 
..252 get_all_leafs([], Acc) ->
..253     Acc;
..254 get_all_leafs([{Pos, Tree}|Rest], Acc) ->
..255     get_all_leafs(Rest, get_all_leafs_simple(Pos, [Tree], []) ++ Acc).
..256 
..257 get_all_leafs_simple(_Pos, [], _KeyPathAcc) ->
..258     [];
..259 get_all_leafs_simple(Pos, [{KeyId, Value, []} | RestTree], KeyPathAcc) ->
..260     [{Value, {Pos, [KeyId | KeyPathAcc]}} | get_all_leafs_simple(Pos, RestTree, KeyPathAcc)];
..261 get_all_leafs_simple(Pos, [{KeyId, _Value, SubTree} | RestTree], KeyPathAcc) ->
..262     get_all_leafs_simple(Pos + 1, SubTree, [KeyId | KeyPathAcc]) ++ get_all_leafs_simple(Pos, RestTree, KeyPathAcc).
..263 
..264 
..265 count_leafs([]) ->
..266     0;
..267 count_leafs([{_Pos,Tree}|Rest]) ->
..268     count_leafs_simple([Tree]) + count_leafs(Rest).
..269 
..270 count_leafs_simple([]) ->
..271     0;
..272 count_leafs_simple([{_Key, _Value, []} | RestTree]) ->
..273     1 + count_leafs_simple(RestTree);
..274 count_leafs_simple([{_Key, _Value, SubTree} | RestTree]) ->
..275     count_leafs_simple(SubTree) + count_leafs_simple(RestTree).
..276 
..277 
..278 map(_Fun, []) ->
..279     [];
..280 map(Fun, [{Pos, Tree}|Rest]) ->
..281     case erlang:fun_info(Fun, arity) of
..282     {arity, 2} ->
..283         [NewTree] = map_simple(fun(A,B,_C) -> Fun(A,B) end, Pos, [Tree]),
..284         [{Pos, NewTree} | map(Fun, Rest)];
..285     {arity, 3} ->
..286         [NewTree] = map_simple(Fun, Pos, [Tree]),
..287         [{Pos, NewTree} | map(Fun, Rest)]
..288     end.
..289 
..290 map_simple(_Fun, _Pos, []) ->
..291     [];
..292 map_simple(Fun, Pos, [{Key, Value, SubTree} | RestTree]) ->
..293     Value2 = Fun({Pos, Key}, Value, 
..294             if SubTree == [] -> leaf; true -> branch end),
..295     [{Key, Value2, map_simple(Fun, Pos + 1, SubTree)} | map_simple(Fun, Pos, RestTree)].
..296 
..297 
..298 map_leafs(_Fun, []) ->
..299     [];
..300 map_leafs(Fun, [{Pos, Tree}|Rest]) ->
..301     [NewTree] = map_leafs_simple(Fun, Pos, [Tree]),
..302     [{Pos, NewTree} | map_leafs(Fun, Rest)].
..303 
..304 map_leafs_simple(_Fun, _Pos, []) ->
..305     [];
..306 map_leafs_simple(Fun, Pos, [{Key, Value, []} | RestTree]) ->
..307     Value2 = Fun({Pos, Key}, Value),
..308     [{Key, Value2, []} | map_leafs_simple(Fun, Pos, RestTree)];
..309 map_leafs_simple(Fun, Pos, [{Key, Value, SubTree} | RestTree]) ->
..310     [{Key, Value, map_leafs_simple(Fun, Pos + 1, SubTree)} | map_leafs_simple(Fun, Pos, RestTree)].
..311 
..312 
..313 stem(Trees, Limit) ->
..314     % flatten each branch in a tree into a tree path
..315     Paths = get_all_leafs_full(Trees),
..316 
..317     Paths2 = [{Pos, lists:sublist(Path, Limit)} || {Pos, Path} <- Paths],
..318 
..319     % convert paths back to trees
..320     lists:foldl(
..321         fun({PathPos, Path},TreeAcc) ->
..322             [SingleTree] = lists:foldl(
..323                 fun({K,V},NewTreeAcc) -> [{K,V,NewTreeAcc}] end, [], Path),
..324             {NewTrees, _} = merge(TreeAcc, [{PathPos + 1 - length(Path), SingleTree}]),
..325             NewTrees
..326         end, [], Paths2).
..327 
..328 % Tests moved to test/etap/06?-*.t
..329 

Generated using etap 0.3.4.