anchor.diff:  %     OMT: Overlap Minimizing Top-down Bulk Loading Algorithm for R-tree
   -spec omt_load(Nodes::[omt_node()], MaxNodes::integer()) -> omt_node().
   omt_load(Nodes, MaxNodes) ->
  -    omt_load(Nodes, MaxNodes, 0).
  --spec omt_load(Nodes::[omt_node()], MaxNodes::integer(), Dimension::integer())
  -    -> omt_node().
  -omt_load(Nodes, MaxNodes, _Dimension) when length(Nodes) =< MaxNodes ->
  -    [Nodes];
  -omt_load(Nodes, MaxNodes, Dimension) ->
  +    NodesNum = length(Nodes),
  +    % Height of the final tree
  +    Height = log_n_ceil(MaxNodes, NodesNum),
  +    omt_load(Nodes, MaxNodes, 0, Height-1, 0).
  +% all nodes need to be on the same level
  +-spec omt_load(Nodes::[omt_node()], MaxNodes::integer(), Dimension::integer(),
  +        LeafDepth::integer(), Depth::integer()) -> omt_node().
  +omt_load(Nodes, MaxNodes, _Dimension, LeafDepth, Depth) when
  +        length(Nodes) =< MaxNodes ->
  +    lists:foldl(fun(_I, Acc) ->
  +       [Acc]
  +    end, Nodes, lists:seq(1,LeafDepth-Depth));
  +omt_load(Nodes, MaxNodes, Dimension, LeafDepth, Depth) ->
       NodesNum = length(Nodes),
       % Height of the final tree
       Height = log_n_ceil(MaxNodes, NodesNum),
  
positive.code:             {{37,163,597,911},{node,inner},{seedtree_leaf,[3732,5606],[]}},
              {{27,984,226,986},{node,inner},{seedtree_leaf,[5039],[]}}]}]},
          SeedTree7Tree).
  %    SeedTree3 = lists:foldl(fun(I, STree) ->
  %        {NodeId, {NodeMbr, NodeMeta, NodeData}} =
  %            vtree_test:random_node({I,20,30}),
  %        Node = {NodeMbr, NodeMeta, {NodeId, NodeData}},
  %        seedtree_insert(STree, Node)
  %    end, SeedTree, lists:seq(1,100)),
  %    ?LOG_DEBUG(SeedTree3).
  
  % @doc Put an on disk tree into memory and prepare it to store new nodes in
  %     the leafs
  -spec seedtree(Fd::file:io_device(), RootPos::integer(),
          MaxDepth::integer()) -> seedtree_root().
  seedtree(Fd, RootPos, MaxDepth) ->
      Tree = seedtree(Fd, RootPos, MaxDepth, 0),
      #seedtree_root{tree=Tree}.
  -spec seedtree(Fd::file:io_device(), RootPos::integer(),
          MaxDepth::integer(), Depth::integer()) -> seedtree_node().
  seedtree(Fd, RootPos, MaxDepth, Depth) when Depth == MaxDepth ->
      {ok, Parent} = couch_file:pread_term(Fd, RootPos),
      {ParentMbr, ParentMeta, EntriesPos} = Parent,
      {ParentMbr, ParentMeta, #seedtree_leaf{orig=EntriesPos}};
  seedtree(Fd, RootPos, MaxDepth, Depth) ->
      {ok, Parent} = couch_file:pread_term(Fd, RootPos),
      {ParentMbr, ParentMeta, EntriesPos} = Parent,
      Children = lists:foldl(fun(EntryPos, Acc) ->
          Child = seedtree(Fd, EntryPos, MaxDepth, Depth+1),
          [Child|Acc]
      end, [], EntriesPos),
      {ParentMbr, ParentMeta, lists:reverse(Children)}.
  
  seedtree_test() ->
      {ok, {RootPos, Fd}} = vtree_test:build_random_tree("/tmp/randtree.bin", 20),
  
negative.code:         {Status, T2} = seedtree_insert_children(T, Node),
          {Status, [H|T2]}
      end.
  
  
  % @doc Put an on disk tree into memory and prepare it to store new nodes in
  %     the leafs
  -spec seedtree(Fd::file:io_device(), RootPos::integer(),
          MaxDepth::integer()) -> seedtree_root().
  seedtree(Fd, RootPos, MaxDepth) ->
      Tree = seedtree(Fd, RootPos, MaxDepth, 0),
      #seedtree_root{tree=Tree}.
  -spec seedtree(Fd::file:io_device(), RootPos::integer(),
          MaxDepth::integer(), Depth::integer()) -> seedtree_node().
  seedtree(Fd, RootPos, MaxDepth, Depth) when Depth == MaxDepth ->
      {ok, Parent} = couch_file:pread_term(Fd, RootPos),
      {ParentMbr, ParentMeta, EntriesPos} = Parent,
      {ParentMbr, ParentMeta, #seedtree_leaf{orig=EntriesPos}};
  seedtree(Fd, RootPos, MaxDepth, Depth) ->
      {ok, Parent} = couch_file:pread_term(Fd, RootPos),
      {ParentMbr, ParentMeta, EntriesPos} = Parent,
      Children = lists:foldl(fun(EntryPos, Acc) ->
          Child = seedtree(Fd, EntryPos, MaxDepth, Depth+1),
          [Child|Acc]
      end, [], EntriesPos),
      {ParentMbr, ParentMeta, lists:reverse(Children)}.
  
  % @doc Find the first node that encloses the input MBR completely at a certain
  %     level. Return the the position relative to other children (starting
  %     with 0).
  %-spec find_enclosing(Fd::file:io_device(), RootPos::integer(),
  %        Level::integer(), InputMbr::list()) -> integer().
  %find_enclosing(Fd, RootPos, Level, InputMbr) ->
  %    ok.
  
  %find_enclosing_test() ->
  %    {ok, {RootPos, _Fd}} = vtree_test:build_random_tree("/tmp/randtree.bin", 1000),
  %    %?LOG_DEBUG(RootNode).
  %    ?debugVal(RootPos).
  
  
  %%%%% Helpers %%%%%
  
  % @doc Returns the ceiling of log_N(X)
  -spec log_n_ceil(N::integer(), X::integer()) -> integer().
  log_n_ceil(N, X) ->
      ceiling(math:log(X) / math:log(N)).
  
  % From http://www.trapexit.org/Floating_Point_Rounding (2010-10-18)
  -spec ceiling(X::number()) -> integer().
  ceiling(X) when X < 0 ->
      trunc(X);
  ceiling(X) ->
      T = trunc(X),
      case X - T == 0 of
          true -> T;
          false -> T + 1
      end.
  
  % From http://www.trapexit.org/Floating_Point_Rounding (2010-10-18)
  %-spec floor(X::number()) -> integer().
  %floor(X) when X < 0 ->
  %    T = trunc(X),
  %    case X - T == 0 of
  %        true -> T;
  %        false -> T - 1
  %    end;
  %floor(X) -> 
  %    trunc(X).
  
  % @doc split a list of elements into equally sized chunks (last element might
  %     contain less elements)
  -spec chunk_list(List::list(), Size::integer()) -> [list()].
  chunk_list(List, Size) when Size == 0 ->
      [List];
  chunk_list(List, Size) ->
      chunk_list(List, Size, 0, [], []).
  chunk_list([], _Size, _Cnt, Chunk, Result) when length(Chunk) > 0 ->
      lists:reverse([lists:reverse(Chunk)|Result]);
  chunk_list([], _Size, _Cnt, _Chunk, Result) ->
      lists:reverse(Result);
  chunk_list([H|T], Size, Cnt, Chunk, Result) when Cnt < Size ->
      chunk_list(T, Size, Cnt+1, [H|Chunk], Result);
  chunk_list([H|T], Size, _Cnt, Chunk, Result) ->
      chunk_list(T, Size, 1, [H], [lists:reverse(Chunk)|Result]).
  
  % @doc split a list of elements into equally sized chunks (last element might
  %     contain less elements). Applies Fun to every chunk and inserts the
  %     return value of this function into the result list.
  -spec chunk_list(Fun::fun(), List::list(), Size::integer()) -> [list()].
  chunk_list(_Fun, List, Size) when Size == 0 ->
      [List];
  chunk_list(Fun, List, Size) ->
      chunk_list(Fun, List, Size, 0, [], []).
  % List is processed, but some items are left in the last chunk
  chunk_list(Fun, [], _Size, _Cnt, Chunk, Result) when length(Chunk) > 0 ->
      Entry = Fun(lists:reverse(Chunk)),
      %lists:reverse(Entry ++ Result);
      lists:reverse([Entry|Result]);
  chunk_list(_Fun, [], _Size, _Cnt, _Chunk, Result) ->
      lists:reverse(Result);
  chunk_list(Fun, [H|T], Size, Cnt, Chunk, Result) when Cnt < Size ->
      chunk_list(Fun, T, Size, Cnt+1, [H|Chunk], Result);
  % Chunk is complete, add chunk to result
  chunk_list(Fun, [H|T], Size, _Cnt, Chunk, Result) ->
      Entry = Fun(lists:reverse(Chunk)),
      %chunk_list(Fun, T, Size, 1, [H], Entry ++ Result).
      chunk_list(Fun, T, Size, 1, [H], [Entry|Result]).
  
  % XXX vmx: tests with function (check_list/6 ) are missing
  chunk_list_test() ->
      List1 = [1,2,3,4,5],
      Chunked1 = chunk_list(List1, 2),
      ?assertEqual([[1,2],[3,4],[5]], Chunked1),
      Chunked2 = chunk_list(List1, 3),
      ?assertEqual([[1,2,3],[4,5]], Chunked2),
      Chunked3 = chunk_list(List1, 4),
      ?assertEqual([[1,2,3,4],[5]], Chunked3),
      Chunked4 = chunk_list(List1, 5),
      ?assertEqual([[1,2,3,4,5]], Chunked4),
      Chunked5 = chunk_list(List1, 6),
      ?assertEqual([[1,2,3,4,5]], Chunked5),
      Chunked6 = chunk_list(List1, 0),
      ?assertEqual([[1,2,3,4,5]], Chunked6),
      Chunked7 = chunk_list(List1, 1),
      ?assertEqual([[1],[2],[3],[4],[5]], Chunked7).
  
  
  %%%%% Tests %%%%%
  
  
  lookup_path_test() ->
      {ok, {RootPos, Fd}} = vtree_test:build_random_tree("/tmp/randtree.bin", 20),
      ?debugVal(RootPos),
      % Not inside 1st level
      EntryPath1 = lookup_path(Fd, RootPos, {1,3,2,4}, 2),
      ?assertEqual(-1, EntryPath1),
  
      % Inside 1st level but not inside 2nd level
      EntryPath2 = lookup_path(Fd, RootPos, {19,120,950,510}, 2),
      ?assertEqual(-1, EntryPath2),
  
      % Found in 2nd level
      EntryPath3 = lookup_path(Fd, RootPos, {542,356,698,513}, 2),
      ?assertEqual([0,0], EntryPath3),
      % Found in 3rd level (would also match [1,0,1], but we take the first
      % matching child)
      EntryPath4 = lookup_path(Fd, RootPos, {458,700,487,865}, 3),
      ?assertEqual([0,1,0], EntryPath4),
  
      EntryPath5 = lookup_path(Fd, RootPos, {542,656,598,813}, 3),
      ?assertEqual([0,1,0], EntryPath5),
      EntryPath6 = lookup_path(Fd, RootPos, {42,456,698,512}, 3),
      ?assertEqual([0,0,2], EntryPath6),
      EntryPath7 = lookup_path(Fd, RootPos, {342,456,959,513}, 3),
      ?assertEqual([0,1,1], EntryPath7).
  
  
  omt_load_test() ->
      Nodes1 = lists:foldl(fun(I, Acc) ->
          {NodeId, {NodeMbr, NodeMeta, NodeData}} =
              vtree_test:random_node({I,20+I*250,30}),
          Node = {NodeMbr, NodeMeta, {NodeId, NodeData}},
          [Node|Acc]
      end, [], lists:seq(1,9)),
      Omt1 = omt_load(Nodes1, 2),
      [L1a, L1b] = Omt1,
      [L2a, L2b] = L1a,
      [L2c, L2d] = L1b,
      [L3a, L3b] = L2a,
      [L3c] = L2b,
      [L3d] = L2c,
      [L3e] = L2d,
      [L4a, L4b] = L3a,
      [L4c] = L3b,
      [L4d, L4e] = L3c,
      [L4f, L4g] = L3d,
      [L4h, L4i] = L3e,
      ?assert(is_tuple(L4a)),
      ?assert(is_tuple(L4b)),
      ?assert(is_tuple(L4c)),
      ?assert(is_tuple(L4d)),
      ?assert(is_tuple(L4e)),
      ?assert(is_tuple(L4f)),
      ?assert(is_tuple(L4g)),
      ?assert(is_tuple(L4h)),
      ?assert(is_tuple(L4i)),
  
      Omt2 = omt_load(Nodes1, 4),
      [M1a, M1b, M1c] = Omt2,
      [M2a, M2b, M2c] = M1a,
      [M2d, M2e, M2f] = M1b,
      [M2g, M2h, M2i] = M1c,
      ?assert(is_tuple(M2a)),
      ?assert(is_tuple(M2b)),
      ?assert(is_tuple(M2c)),
      ?assert(is_tuple(M2d)),
      ?assert(is_tuple(M2e)),
      ?assert(is_tuple(M2f)),
      ?assert(is_tuple(M2g)),
      ?assert(is_tuple(M2h)),
      ?assert(is_tuple(M2i)),
  
      Omt3 = omt_load(Nodes1, 12),
      ?assertEqual(9, length(Omt3)).
  
  
  
  omt_write_tree_test() ->
      Filename = "/tmp/omt.bin",
      Nodes1 = lists:foldl(fun(I, Acc) ->
          {NodeId, {NodeMbr, NodeMeta, NodeData}} =
              vtree_test:random_node({I,20+I*250,30}),
          Node = {NodeMbr, NodeMeta, {NodeId, NodeData}},
          [Node|Acc]
      end, [], lists:seq(1,9)),
      Omt1 = omt_load(Nodes1, 2),
  
      Fd = case couch_file:open(Filename, [create, overwrite]) of
      {ok, Fd2} ->
          Fd2;
      {error, _Reason} ->
          io:format("ERROR: Couldn't open file (~s) for tree storage~n",
                    [Filename])
      end,
      
      {ok, RootPos} = omt_write_tree(Fd, Omt1),
      ?debugVal(RootPos),
  
      % just test if the number of children match on all levels
      {ok, Root} = couch_file:pread_term(Fd, RootPos),
      ?assertEqual(2, length(element(3, Root))),
      {ok, L1a} = couch_file:pread_term(Fd, lists:nth(1, element(3, Root))),
      ?assertEqual(2, length(element(3, L1a))),
      {ok, L1b} = couch_file:pread_term(Fd, lists:nth(2, element(3, Root))),
      ?assertEqual(2, length(element(3, L1b))),
      {ok, L2a} = couch_file:pread_term(Fd, lists:nth(1, element(3, L1a))),
      ?assertEqual(2, length(element(3, L2a))),
      {ok, L2b} = couch_file:pread_term(Fd, lists:nth(2, element(3, L1a))),
      ?assertEqual(1, length(element(3, L2b))),
      {ok, L2c} = couch_file:pread_term(Fd, lists:nth(1, element(3, L1b))),
      ?assertEqual(1, length(element(3, L2c))),
      {ok, L2d} = couch_file:pread_term(Fd, lists:nth(2, element(3, L1b))),
      ?assertEqual(1, length(element(3, L2d))),
      {ok, L3aNode} = couch_file:pread_term(Fd, lists:nth(1, element(3, L2a))),
      {_, _, L3a} = L3aNode,
      {ok, L3bNode} = couch_file:pread_term(Fd, lists:nth(2, element(3, L2a))),
      {_, _, L3b} = L3bNode,
      {ok, L3cNode} = couch_file:pread_term(Fd, lists:nth(1, element(3, L2b))),
      {_, _, L3c} = L3cNode,
      {ok, L3dNode} = couch_file:pread_term(Fd, lists:nth(1, element(3, L2c))),
      {_, _, L3d} = L3dNode,
      {ok, L3eNode} = couch_file:pread_term(Fd, lists:nth(1, element(3, L2d))),
      {_, _, L3e} = L3eNode,
  
      [L4a, L4b] = L3a,
      [L4c] = L3b,
      [L4d, L4e] = L3c,
      [L4f, L4g] = L3d,
      [L4h, L4i] = L3e,
      ?assert(is_tuple(L4a)),
      ?assert(is_tuple(L4b)),
      ?assert(is_tuple(L4c)),
      ?assert(is_tuple(L4d)),
      ?assert(is_tuple(L4e)),
      ?assert(is_tuple(L4f)),
      ?assert(is_tuple(L4g)),
      ?assert(is_tuple(L4h)),
      ?assert(is_tuple(L4i)),
  
      Omt2 = omt_load(Nodes1, 4),
      {ok, RootPos2} = omt_write_tree(Fd, Omt2),
      ?debugVal(RootPos2),
      {ok, Root2} = couch_file:pread_term(Fd, RootPos2),
      ?assertEqual(3, length(element(3, Root2))),
      {ok, M1aNode} = couch_file:pread_term(Fd, lists:nth(1, element(3, Root2))),
      {_, _, M1a} = M1aNode,
      ?assertEqual(3, length(M1a)),
      {ok, M1bNode} = couch_file:pread_term(Fd, lists:nth(2, element(3, Root2))),
      {_, _, M1b} = M1bNode,
      ?assertEqual(3, length(M1b)),
      {ok, M1cNode} = couch_file:pread_term(Fd, lists:nth(2, element(3, Root2))),
      {_, _, M1c} = M1cNode,
      ?assertEqual(3, length(M1c)),
      [M2a, M2b, M2c] = M1a,
      [M2d, M2e, M2f] = M1b,
      [M2g, M2h, M2i] = M1c,
      ?assert(is_tuple(M2a)),
      ?assert(is_tuple(M2b)),
      ?assert(is_tuple(M2c)),
      ?assert(is_tuple(M2d)),
      ?assert(is_tuple(M2e)),
      ?assert(is_tuple(M2f)),
      ?assert(is_tuple(M2g)),
      ?assert(is_tuple(M2h)),
      ?assert(is_tuple(M2i)),
  
      % Test round-trip: some nodes => OMT tree, write to disk, load from disk
      {ok, LeafNodes} = vtree:lookup(Fd, RootPos, {0,0,1001,1001}),
      LeafNodes2 = lists:foldl(fun(LeafNode, Acc) ->
          {NodeMbr, NodeId, NodeData} = LeafNode,
          Node = {NodeMbr, #node{type=leaf}, {NodeId, NodeData}},
          [Node|Acc]
      end, [], LeafNodes),
      Omt3 = omt_load(LeafNodes2, 2),
      ?assertEqual(Omt1, Omt3).
  
  
  
  omt_sort_nodes_test() ->
      Nodes1 = lists:foldl(fun(I, Acc) ->
          {NodeId, {NodeMbr, NodeMeta, NodeData}} =
              vtree_test:random_node({I,20+I*300,30-I*54}),
          Node = {NodeMbr, NodeMeta, {NodeId, NodeData}},
          [Node|Acc]
      end, [], lists:seq(1,6)),
      Sorted1 = omt_sort_nodes(Nodes1, 1),
      ?assertEqual([lists:nth(2, Nodes1),
          lists:nth(1, Nodes1),
          lists:nth(6, Nodes1),
          lists:nth(5, Nodes1),
          lists:nth(4, Nodes1),
          lists:nth(3, Nodes1)], Sorted1),
      Sorted2 = omt_sort_nodes(Nodes1, 2),
      ?assertEqual([lists:nth(3, Nodes1),
          lists:nth(5, Nodes1),
          lists:nth(6, Nodes1),
          lists:nth(2, Nodes1),
          lists:nth(4, Nodes1),
          lists:nth(1, Nodes1)], Sorted2).
  
  
  seedtree_insert_test() ->
      {ok, {RootPos, Fd}} = vtree_test:build_random_tree("/tmp/randtree.bin", 20),
  