Branch data Line data Source code
1 : : /** @file matchspy.cc
2 : : * @brief MatchSpy implementation.
3 : : */
4 : : /* Copyright (C) 2007,2008,2009,2010 Olly Betts
5 : : * Copyright (C) 2007,2009 Lemur Consulting Ltd
6 : : * Copyright (C) 2010 Richard Boulton
7 : : *
8 : : * This program is free software; you can redistribute it and/or modify
9 : : * it under the terms of the GNU General Public License as published by
10 : : * the Free Software Foundation; either version 2 of the License, or
11 : : * (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 USA
21 : : */
22 : :
23 : : #include <config.h>
24 : : #include <xapian/matchspy.h>
25 : :
26 : : #include <xapian/document.h>
27 : : #include <xapian/error.h>
28 : : #include <xapian/queryparser.h>
29 : : #include <xapian/registry.h>
30 : :
31 : : #include <map>
32 : : #include <string>
33 : : #include <vector>
34 : :
35 : : #include "autoptr.h"
36 : : #include "debuglog.h"
37 : : #include "omassert.h"
38 : : #include "serialise.h"
39 : : #include "stringutils.h"
40 : : #include "str.h"
41 : : #include "termlist.h"
42 : :
43 : : #include <cfloat>
44 : : #include <cmath>
45 : :
46 : : using namespace std;
47 : : using namespace Xapian;
48 : :
49 [ # # ][ # # ]: 176984 : MatchSpy::~MatchSpy() {}
[ - + ]
50 : :
51 : : MatchSpy *
52 : 1 : MatchSpy::clone() const {
53 : 1 : throw UnimplementedError("MatchSpy not suitable for use with remote searches - clone() method unimplemented");
54 : : }
55 : :
56 : : string
57 : 1 : MatchSpy::name() const {
58 : 1 : throw UnimplementedError("MatchSpy not suitable for use with remote searches - name() method unimplemented");
59 : : }
60 : :
61 : : string
62 : 1 : MatchSpy::serialise() const {
63 : 1 : throw UnimplementedError("MatchSpy not suitable for use with remote searches - serialise() method unimplemented");
64 : : }
65 : :
66 : : MatchSpy *
67 : 1 : MatchSpy::unserialise(const string &, const Registry &) const {
68 : 1 : throw UnimplementedError("MatchSpy not suitable for use with remote searches - unserialise() method unimplemented");
69 : : }
70 : :
71 : : string
72 : 1 : MatchSpy::serialise_results() const {
73 : 1 : throw UnimplementedError("MatchSpy not suitable for use with remote searches - serialise_results() method unimplemented");
74 : : }
75 : :
76 : : void
77 : 1 : MatchSpy::merge_results(const string &) {
78 : 1 : throw UnimplementedError("MatchSpy not suitable for use with remote searches - merge_results() method unimplemented");
79 : : }
80 : :
81 : : string
82 : 1 : MatchSpy::get_description() const {
83 : 1 : return "Xapian::MatchSpy()";
84 : : }
85 : :
86 : : XAPIAN_NORETURN(static void unsupported_method());
87 : 0 : static void unsupported_method() {
88 : 0 : throw Xapian::InvalidOperationError("Method not supported for this type of termlist");
89 : : }
90 : :
91 : : /// A termlist iterator over the contents of a ValueCountMatchSpy
92 [ + - ][ # # ]: 56 : class ValueCountTermList : public TermList {
93 : : private:
94 : : map<string, Xapian::doccount>::const_iterator it;
95 : : bool started;
96 : : Xapian::Internal::RefCntPtr<Xapian::ValueCountMatchSpy::Internal> spy;
97 : : public:
98 : :
99 : 56 : ValueCountTermList(ValueCountMatchSpy::Internal * spy_) : spy(spy_) {
100 : 56 : it = spy->values.begin();
101 : 56 : started = false;
102 : 56 : }
103 : :
104 : 242 : string get_termname() const {
105 : : Assert(started);
106 : : Assert(!at_end());
107 : 242 : return it->first;
108 : : }
109 : :
110 : 242 : Xapian::doccount get_termfreq() const {
111 : : Assert(started);
112 : : Assert(!at_end());
113 : 242 : return it->second;
114 : : }
115 : :
116 : 298 : TermList * next() {
117 [ + + ]: 298 : if (!started) {
118 : 56 : started = true;
119 : : } else {
120 : : Assert(!at_end());
121 : 242 : ++it;
122 : : }
123 : 298 : return NULL;
124 : : }
125 : :
126 : 0 : TermList * skip_to(const string & term) {
127 [ # # ][ # # ]: 0 : while (it != spy->values.end() && it->first < term) {
[ # # ]
128 : 0 : ++it;
129 : : }
130 : 0 : started = true;
131 : 0 : return NULL;
132 : : }
133 : :
134 : 298 : bool at_end() const {
135 : : Assert(started);
136 : 298 : return it == spy->values.end();
137 : : }
138 : :
139 : 0 : Xapian::termcount get_approx_size() const { unsupported_method(); return 0; }
140 : 0 : Xapian::termcount get_wdf() const { unsupported_method(); return 0; }
141 : 0 : Xapian::PositionIterator positionlist_begin() const {
142 : 0 : unsupported_method();
143 : : return Xapian::PositionIterator(NULL);
144 : : }
145 : 0 : Xapian::termcount positionlist_count() const { unsupported_method(); return 0; }
146 : : };
147 : :
148 : : /** A string with a corresponding frequency.
149 : : */
150 : 78500 : class StringAndFrequency {
151 : : std::string str;
152 : : Xapian::doccount frequency;
153 : : public:
154 : : /// Construct a StringAndFrequency object.
155 : 6500 : StringAndFrequency(std::string str_, Xapian::doccount frequency_)
156 : 6500 : : str(str_), frequency(frequency_) {}
157 : :
158 : : /// Return the string.
159 : 16300 : std::string get_string() const { return str; }
160 : :
161 : : /// Return the frequency.
162 : 51420 : Xapian::doccount get_frequency() const { return frequency; }
163 : : };
164 : :
165 : : /** Compare two StringAndFrequency objects.
166 : : *
167 : : * The comparison is firstly by frequency (higher is better), then by string
168 : : * (earlier lexicographic sort is better).
169 : : */
170 : : class StringAndFreqCmpByFreq {
171 : : public:
172 : : /// Default constructor
173 : 820 : StringAndFreqCmpByFreq() {}
174 : :
175 : : /// Return true if a has a higher frequency than b.
176 : : /// If equal, compare by the str, to provide a stable sort order.
177 : 14280 : bool operator()(const StringAndFrequency &a,
178 : : const StringAndFrequency &b) const {
179 [ + + ]: 14280 : if (a.get_frequency() > b.get_frequency()) return true;
180 [ + + ]: 9900 : if (a.get_frequency() < b.get_frequency()) return false;
181 [ + + ]: 6620 : if (a.get_string() > b.get_string()) return false;
182 : 14280 : return true;
183 : : }
184 : : };
185 : :
186 : : /// A termlist iterator over a vector of StringAndFrequency objects.
187 [ + - ][ # # ]: 1640 : class StringAndFreqTermList : public TermList {
188 : : private:
189 : : vector<StringAndFrequency>::const_iterator it;
190 : : bool started;
191 : : public:
192 : : vector<StringAndFrequency> values;
193 : :
194 : : /** init should be called after the values have been set, but before
195 : : * iteration begins.
196 : : */
197 : 820 : void init() {
198 : 820 : it = values.begin();
199 : 820 : started = false;
200 : 820 : }
201 : :
202 : 3060 : string get_termname() const {
203 : : Assert(started);
204 : : Assert(!at_end());
205 : 3060 : return it->get_string();
206 : : }
207 : :
208 : 3060 : Xapian::doccount get_termfreq() const {
209 : : Assert(started);
210 : : Assert(!at_end());
211 : 3060 : return it->get_frequency();
212 : : }
213 : :
214 : 3880 : TermList * next() {
215 [ + + ]: 3880 : if (!started) {
216 : 820 : started = true;
217 : : } else {
218 : : Assert(!at_end());
219 : 3060 : ++it;
220 : : }
221 : 3880 : return NULL;
222 : : }
223 : :
224 : 0 : TermList * skip_to(const string & term) {
225 [ # # ][ # # ]: 0 : while (it != values.end() && it->get_string() < term) {
[ # # ][ # # ]
[ # # ]
226 : 0 : ++it;
227 : : }
228 : 0 : started = true;
229 : 0 : return NULL;
230 : : }
231 : :
232 : 3880 : bool at_end() const {
233 : : Assert(started);
234 : 3880 : return it == values.end();
235 : : }
236 : :
237 : 0 : Xapian::termcount get_approx_size() const { unsupported_method(); return 0; }
238 : 0 : Xapian::termcount get_wdf() const { unsupported_method(); return 0; }
239 : 0 : Xapian::PositionIterator positionlist_begin() const {
240 : 0 : unsupported_method();
241 : : return Xapian::PositionIterator(NULL);
242 : : }
243 : 0 : Xapian::termcount positionlist_count() const { unsupported_method(); return 0; }
244 : : };
245 : :
246 : : /** Get the most frequent items from a map from string to frequency.
247 : : *
248 : : * This takes input such as that in ValueCountMatchSpy::Internal::values and
249 : : * returns a vector of the most frequent items in the input.
250 : : *
251 : : * @param result A vector which will be filled with the most frequent
252 : : * items, in descending order of frequency. Items with
253 : : * the same frequency will be sorted in ascending
254 : : * alphabetical order.
255 : : *
256 : : * @param items The map from string to frequency, from which the most
257 : : * frequent items will be selected.
258 : : *
259 : : * @param maxitems The maximum number of items to return.
260 : : */
261 : : static void
262 : 820 : get_most_frequent_items(vector<StringAndFrequency> & result,
263 : : const map<string, doccount> & items,
264 : : size_t maxitems)
265 : : {
266 : 820 : result.clear();
267 : 820 : result.reserve(maxitems);
268 : 820 : StringAndFreqCmpByFreq cmpfn;
269 : 820 : bool is_heap(false);
270 : :
271 [ + + ]: 7320 : for (map<string, doccount>::const_iterator i = items.begin();
272 : : i != items.end(); i++) {
273 : : Assert(result.size() <= maxitems);
274 : 6500 : result.push_back(StringAndFrequency(i->first, i->second));
275 [ + + ]: 6500 : if (result.size() > maxitems) {
276 : : // Make the list back into a heap.
277 [ + + ]: 1720 : if (is_heap) {
278 : : // Only the new element isn't in the right place.
279 : 1340 : push_heap(result.begin(), result.end(), cmpfn);
280 : : } else {
281 : : // Need to build heap from scratch.
282 : 380 : make_heap(result.begin(), result.end(), cmpfn);
283 : 380 : is_heap = true;
284 : : }
285 : 1720 : pop_heap(result.begin(), result.end(), cmpfn);
286 : 1720 : result.pop_back();
287 : : }
288 : : }
289 : :
290 [ + + ]: 820 : if (is_heap) {
291 : 380 : sort_heap(result.begin(), result.end(), cmpfn);
292 : : } else {
293 : 440 : sort(result.begin(), result.end(), cmpfn);
294 : : }
295 : 820 : }
296 : :
297 : : void
298 : 2406 : ValueCountMatchSpy::operator()(const Document &doc, weight) {
299 : 2406 : ++(internal->total);
300 : 2406 : string val(doc.get_value(internal->slot));
301 [ + - ]: 2406 : if (!val.empty()) ++(internal->values[val]);
302 : 2406 : }
303 : :
304 : : TermIterator
305 : 56 : ValueCountMatchSpy::values_begin() const
306 : : {
307 : 56 : AutoPtr<ValueCountTermList> termlist(new ValueCountTermList(internal.get()));
308 : 56 : return Xapian::TermIterator(termlist.release());
309 : : }
310 : :
311 : : TermIterator
312 : 820 : ValueCountMatchSpy::top_values_begin(size_t maxvalues) const
313 : : {
314 : 820 : AutoPtr<StringAndFreqTermList> termlist(new StringAndFreqTermList);
315 : 820 : get_most_frequent_items(termlist->values, internal->values, maxvalues);
316 : 820 : termlist->init();
317 : 820 : return Xapian::TermIterator(termlist.release());
318 : : }
319 : :
320 : : MatchSpy *
321 : 0 : ValueCountMatchSpy::clone() const {
322 : 0 : return new ValueCountMatchSpy(internal->slot);
323 : : }
324 : :
325 : : string
326 : 1642 : ValueCountMatchSpy::name() const {
327 : 1642 : return "Xapian::ValueCountMatchSpy";
328 : : }
329 : :
330 : : string
331 : 66 : ValueCountMatchSpy::serialise() const {
332 : 66 : string result;
333 : 66 : result += encode_length(internal->slot);
334 : 0 : return result;
335 : : }
336 : :
337 : : MatchSpy *
338 : 66 : ValueCountMatchSpy::unserialise(const string & s, const Registry &) const
339 : : {
340 : 66 : const char * p = s.data();
341 : 66 : const char * end = p + s.size();
342 : :
343 : 66 : valueno new_slot = decode_length(&p, end, false);
344 [ - + ]: 66 : if (p != end) {
345 : 0 : throw NetworkError("Junk at end of serialised ValueCountMatchSpy");
346 : : }
347 : :
348 : 66 : return new ValueCountMatchSpy(new_slot);
349 : : }
350 : :
351 : : string
352 : 66 : ValueCountMatchSpy::serialise_results() const {
353 : : LOGCALL(REMOTE, string, "ValueCountMatchSpy::serialise_results", NO_ARGS);
354 : 66 : string result;
355 : 66 : result += encode_length(internal->total);
356 : 66 : result += encode_length(internal->values.size());
357 [ + + ]: 432 : for (map<string, doccount>::const_iterator i = internal->values.begin();
358 : : i != internal->values.end(); ++i) {
359 : 366 : result += encode_length(i->first.size());
360 : 366 : result += i->first;
361 : 366 : result += encode_length(i->second);
362 : : }
363 : 0 : RETURN(result);
364 : : }
365 : :
366 : : void
367 : 66 : ValueCountMatchSpy::merge_results(const string & s) {
368 : : LOGCALL_VOID(REMOTE, "ValueCountMatchSpy::merge_results", s);
369 : 66 : const char * p = s.data();
370 : 66 : const char * end = p + s.size();
371 : :
372 : 66 : internal->total += decode_length(&p, end, false);
373 : :
374 : 66 : map<string, doccount>::size_type items = decode_length(&p, end, false);
375 [ + + ]: 132 : while (p != end) {
376 [ + + ]: 432 : while (items != 0) {
377 : 366 : size_t vallen = decode_length(&p, end, true);
378 : 366 : string val(p, vallen);
379 : 366 : p += vallen;
380 : 366 : doccount freq = decode_length(&p, end, false);
381 : 366 : internal->values[val] += freq;
382 : 366 : --items;
383 : : }
384 : : }
385 : 66 : }
386 : :
387 : : string
388 : 1 : ValueCountMatchSpy::get_description() const {
389 : : return "Xapian::ValueCountMatchSpy(" + str(internal->total) +
390 : 1 : " docs seen, looking in " + str(internal->values.size()) + " slots)";
391 : 0 : }
|
