anchor.diff:                   zone_ids :: list(doko_doc:zone_id())}).
   
   %% Type definitions
  --type q() :: {and_q,  q(), q()} |
  -             {or_q,   q(), q()} |
  -             {not_q,  q()     } |
  +-type q() :: {and_q, q(), q()} |
  +             {or_q,  q(), q()} |
  +             {not_q, q()} |
                {term_q, string(), list(string())}.
   
   %%----------------------------------------------------------------------------
  
positive.code:     tree_to_query(ParseTree).
  
  scan(<<>>) ->
      [{'$end',1}];
  scan(<<C/utf8,Rest/bytes>>) ->
      case C of
          %% parentheses
          $( -> [{'(',1}|scan(Rest)];
          $) -> [{')',1}|scan(Rest)];
          $[ -> [{'[',1}|scan(Rest)];
          $] -> [{']',1}|scan(Rest)];
          %% boolean operators
          $& -> [{'&',1}|scan(Rest)];
          $| -> [{'|',1}|scan(Rest)];
          $! -> [{'!',1}|scan(Rest)];
          %% comma
          $, -> [{',', 1} | scan(Rest)];
          %% space (ignored)
          32 -> scan(Rest);
          %% begin of a single quoted string
          $' ->
              Regex = [<<"^((?:[^'\\\\]|\\\\')*)'(.*)$">>],
              Options = [unicode,{capture,all_but_first,binary}],
              case re:run(Rest, Regex, Options) of
                  {match,[String,RestRest]} ->
                      [{string,String,1}|scan(RestRest)]
              end;
          %% begin of a keyword or an ID
          _ ->
              Regex = [<<"^([a-z0-9_]*)(.*)$">>],
              Options = [unicode,{capture,all_but_first,binary}],
              case re:run(<<C/utf8,Rest/bytes>>, Regex, Options) of
                  {match,[Word,RestRest]} ->
                      Token = case Word of
                                  <<"in">> -> {'in',1};
                                  Id       -> {id,Id,1}
                              end,
                      [Token|scan(RestRest)]
              end
      end.
  
  tree_to_query({and_q,SubTreeL,SubTreeR}) ->
      {L, DepthL} = tree_to_query(SubTreeL),
      {R, DepthR} = tree_to_query(SubTreeR),
      {#and_q{l_sub_q = L,r_sub_q = R},max(DepthL, DepthR)+1};
  tree_to_query({or_q,SubTreeL,SubTreeR}) ->
      {L, DepthL} = tree_to_query(SubTreeL),
      {R, DepthR} = tree_to_query(SubTreeR),
      {#or_q{l_sub_q = L,r_sub_q = R},max(DepthL, DepthR)+1};
  tree_to_query({not_q,SubTree}) ->
      {Sub,Depth} = tree_to_query(SubTree),
      {#not_q{sub_q = Sub},Depth+1};
  tree_to_query({term_q,{string,Keyword,_},ZoneIds}) ->
      Ids = [binary:bin_to_list(Id)||{_,Id,_} <- ZoneIds],
      {#term_q{keyword  = Keyword,zone_ids = Ids},0}.
  
  %% @doc Rewrites a query to disjunctive normal form.
  -spec dnf({q(),pos_integer()}) -> q().
  dnf({Q,0}) ->
      Q;
  dnf({Q,D}) ->
      dnf(mv_not(Q), D).
  
  dnf(Q, 1) ->
      Q;
  dnf(Q, D) ->
      dnf(mv_and(Q), D-1).
  
  mv_not({and_q, L, R}) ->
      {and_q, mv_not(L), mv_not(R)};
  
negative.code:     Calculate = fun ({Keywords,NotKeywords}) ->
                          gb_sets:subtract(
                            gb_sets:intersection(
                              lists:flatten([DocIds(X) || X <- Keywords])),
                            gb_sets:union(
                              lists:flatten([DocIds(X) || X <- NotKeywords])))
                  end,
      gb_sets:union(plists:map(Calculate, Clauses)).
  
  