Branch data Line data Source code
1 : : /* andnotpostlist.cc: Return items which are in A, unless they're in B
2 : : *
3 : : * Copyright 1999,2000,2001 BrightStation PLC
4 : : * Copyright 2002 Ananova Ltd
5 : : * Copyright 2003,2004,2007,2009 Olly Betts
6 : : * Copyright 2009 Lemur Consulting Ltd
7 : : *
8 : : * This program is free software; you can redistribute it and/or
9 : : * modify it under the terms of the GNU General Public License as
10 : : * published by the Free Software Foundation; either version 2 of the
11 : : * License, or (at your option) any later version.
12 : : *
13 : : * This program is distributed in the hope that it will be useful,
14 : : * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 : : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 : : * GNU General Public License for more details.
17 : : *
18 : : * You should have received a copy of the GNU General Public License
19 : : * along with this program; if not, write to the Free Software
20 : : * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301
21 : : * USA
22 : : */
23 : :
24 : : #include <config.h>
25 : : #include "andnotpostlist.h"
26 : :
27 : : #include "debuglog.h"
28 : : #include "omassert.h"
29 : :
30 : : PostList *
31 : 715 : AndNotPostList::advance_to_next_match(Xapian::weight w_min, PostList *ret)
32 : : {
33 : : LOGCALL(MATCH, PostList *, "AndNotPostList::advance_to_next_match", w_min | ret);
34 : 715 : handle_prune(l, ret);
35 [ + + ]: 715 : if (l->at_end()) {
36 : 15 : lhead = 0;
37 : 15 : RETURN(NULL);
38 : : }
39 : 700 : lhead = l->get_docid();
40 : :
41 [ + + ]: 947 : while (rhead <= lhead) {
42 [ + + ]: 360 : if (lhead == rhead) {
43 : 130 : next_handling_prune(l, w_min, matcher);
44 [ + + ]: 130 : if (l->at_end()) {
45 : 78 : lhead = 0;
46 : 78 : RETURN(NULL);
47 : : }
48 : 52 : lhead = l->get_docid();
49 : : }
50 : 282 : skip_to_handling_prune(r, lhead, 0, matcher);
51 [ + + ]: 282 : if (r->at_end()) {
52 : 35 : ret = l;
53 : 35 : l = NULL;
54 : 35 : RETURN(ret);
55 : : }
56 : 247 : rhead = r->get_docid();
57 : : }
58 : 715 : RETURN(NULL);
59 : : }
60 : :
61 : 128 : AndNotPostList::AndNotPostList(PostList *left_,
62 : : PostList *right_,
63 : : MultiMatch *matcher_,
64 : : Xapian::doccount dbsize_)
65 : : : BranchPostList(left_, right_, matcher_),
66 : 128 : lhead(0), rhead(0), dbsize(dbsize_)
67 : : {
68 : : LOGCALL_CTOR(MATCH, "AndNotPostList", left_ | right_ | matcher_ | dbsize_);
69 : 128 : }
70 : :
71 : : PostList *
72 : 715 : AndNotPostList::next(Xapian::weight w_min)
73 : : {
74 : : LOGCALL(MATCH, PostList *, "AndNotPostList::next", w_min);
75 : 715 : RETURN(advance_to_next_match(w_min, l->next(w_min)));
76 : : }
77 : :
78 : : PostList *
79 : 0 : AndNotPostList::sync_and_skip_to(Xapian::docid id,
80 : : Xapian::weight w_min,
81 : : Xapian::docid lh,
82 : : Xapian::docid rh)
83 : : {
84 : : LOGCALL(MATCH, PostList *, "AndNotPostList::sync_and_skip_to", id | w_min | lh | rh);
85 : 0 : lhead = lh;
86 : 0 : rhead = rh;
87 : 0 : RETURN(skip_to(id, w_min));
88 : : }
89 : :
90 : : PostList *
91 : 0 : AndNotPostList::skip_to(Xapian::docid did, Xapian::weight w_min)
92 : : {
93 : : LOGCALL(MATCH, PostList *, "AndNotPostList::skip_to", did | w_min);
94 [ # # ]: 0 : if (did <= lhead) RETURN(NULL);
95 : 0 : RETURN(advance_to_next_match(w_min, l->skip_to(did, w_min)));
96 : : }
97 : :
98 : : Xapian::doccount
99 : 128 : AndNotPostList::get_termfreq_max() const
100 : : {
101 : : LOGCALL(MATCH, Xapian::doccount, "AndNotPostList::get_termfreq_max", NO_ARGS);
102 : : // Max is when as many docs as possible on left, and none excluded.
103 : 128 : RETURN(l->get_termfreq_max());
104 : : }
105 : :
106 : : Xapian::doccount
107 : 128 : AndNotPostList::get_termfreq_min() const
108 : : {
109 : : LOGCALL(MATCH, Xapian::doccount, "AndNotPostList::get_termfreq_min", NO_ARGS);
110 : : // Min is when as few docs as possible on left, and maximum are excluded.
111 : 128 : Xapian::doccount l_min = l->get_termfreq_min();
112 : 128 : Xapian::doccount r_max = r->get_termfreq_max();
113 [ + + ]: 128 : if (l_min > r_max) RETURN(l_min - r_max);
114 : 128 : RETURN(0u);
115 : : }
116 : :
117 : : Xapian::doccount
118 : 176 : AndNotPostList::get_termfreq_est() const
119 : : {
120 : : LOGCALL(MATCH, Xapian::doccount, "AndNotPostList::get_termfreq_est", NO_ARGS);
121 : : // Estimate assuming independence:
122 : : // P(l and r) = P(l) . P(r)
123 : : // P(l not r) = P(l) - P(l and r) = P(l) . ( 1 - P(r))
124 : 176 : double est = l->get_termfreq_est() *
125 : 176 : (1.0 - double(r->get_termfreq_est()) / dbsize);
126 : 176 : RETURN(static_cast<Xapian::doccount>(est + 0.5));
127 : : }
128 : :
129 : : TermFreqs
130 : 32 : AndNotPostList::get_termfreq_est_using_stats(
131 : : const Xapian::Weight::Internal & stats) const
132 : : {
133 : : LOGCALL(MATCH, TermFreqs, "AndNotPostList::get_termfreq_est_using_stats", stats);
134 : : // Estimate assuming independence:
135 : : // P(l and r) = P(l) . P(r)
136 : : // P(l not r) = P(l) - P(l and r) = P(l) . ( 1 - P(r))
137 : 32 : TermFreqs lfreqs(l->get_termfreq_est_using_stats(stats));
138 : 32 : TermFreqs rfreqs(r->get_termfreq_est_using_stats(stats));
139 : :
140 : : double freqest, relfreqest;
141 : :
142 : : // Our caller should have ensured this.
143 : : Assert(stats.collection_size);
144 : :
145 : : freqest = lfreqs.termfreq *
146 : 32 : (1.0 - (double(rfreqs.termfreq) / stats.collection_size));
147 : :
148 [ + - ]: 32 : if (stats.rset_size == 0) {
149 : 32 : relfreqest = 0;
150 : : } else {
151 : : relfreqest = lfreqs.reltermfreq *
152 : 0 : (1.0 - (double(rfreqs.reltermfreq) / stats.rset_size));
153 : : }
154 : :
155 : 32 : RETURN(TermFreqs(static_cast<Xapian::doccount>(freqest + 0.5),
156 : : static_cast<Xapian::doccount>(relfreqest + 0.5)));
157 : : }
158 : :
159 : : Xapian::docid
160 : 554 : AndNotPostList::get_docid() const
161 : : {
162 : : LOGCALL(MATCH, Xapian::docid, "AndNotPostList::get_docid", NO_ARGS);
163 : 554 : RETURN(lhead);
164 : : }
165 : :
166 : : // only called if we are doing a probabilistic AND NOT
167 : : Xapian::weight
168 : 561 : AndNotPostList::get_weight() const
169 : : {
170 : : LOGCALL(MATCH, Xapian::weight, "AndNotPostList::get_weight", NO_ARGS);
171 : 561 : RETURN(l->get_weight());
172 : : }
173 : :
174 : : // only called if we are doing a probabilistic AND NOT
175 : : Xapian::weight
176 : 10 : AndNotPostList::get_maxweight() const
177 : : {
178 : : LOGCALL(MATCH, Xapian::weight, "AndNotPostList::get_maxweight", NO_ARGS);
179 : 10 : RETURN(l->get_maxweight());
180 : : }
181 : :
182 : : Xapian::weight
183 : 134 : AndNotPostList::recalc_maxweight()
184 : : {
185 : : LOGCALL(MATCH, Xapian::weight, "AndNotPostList::recalc_maxweight", NO_ARGS);
186 : : // l cannot be NULL here because it is only set to NULL when the tree
187 : : // decays, so this can never be called at that point.
188 : 134 : RETURN(l->recalc_maxweight());
189 : : }
190 : :
191 : : bool
192 : 680 : AndNotPostList::at_end() const
193 : : {
194 : : LOGCALL(MATCH, bool, "AndNotPostList::at_end", NO_ARGS);
195 : 680 : RETURN(lhead == 0);
196 : : }
197 : :
198 : : std::string
199 : 0 : AndNotPostList::get_description() const
200 : : {
201 : 0 : return "(" + l->get_description() + " AndNot " + r->get_description() + ")";
202 : : }
203 : :
204 : : Xapian::termcount
205 : 26 : AndNotPostList::get_doclength() const
206 : : {
207 : : LOGCALL(MATCH, Xapian::termcount, "AndNotPostList::get_doclength", NO_ARGS);
208 : 26 : RETURN(l->get_doclength());
209 : : }
210 : :
211 : : Xapian::termcount
212 : 26 : AndNotPostList::get_wdf() const
213 : : {
214 : : LOGCALL(MATCH, Xapian::termcount, "AndNotPostList::get_wdf", NO_ARGS);
215 : 26 : RETURN(l->get_wdf());
216 : : }
217 : :
218 : : Xapian::termcount
219 : 150 : AndNotPostList::count_matching_subqs() const
220 : : {
221 : : LOGCALL(MATCH, Xapian::termcount, "AndNotPostList::count_matching_subqs", NO_ARGS);
222 : 150 : RETURN(l->count_matching_subqs());
223 : : }
|
