xapian-core  1.4.25
orpositionlist.cc
Go to the documentation of this file.
1 
4 /* Copyright (C) 2007,2010,2016,2017 Olly Betts
5  *
6  * This program is free software; you can redistribute it and/or
7  * modify it under the terms of the GNU General Public License as
8  * published by the Free Software Foundation; either version 2 of the
9  * License, or (at your option) any later version.
10  *
11  * This program is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14  * GNU General Public License for more details.
15  *
16  * You should have received a copy of the GNU General Public License
17  * along with this program; if not, write to the Free Software
18  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
19  */
20 
21 #include <config.h>
22 
23 #include "orpositionlist.h"
24 
25 #include "debuglog.h"
26 
27 using namespace std;
28 
31 {
32  LOGCALL(EXPAND, Xapian::termcount, "OrPositionList::get_approx_size", NO_ARGS);
33  // This is actually the upper bound, but generally there's only one term
34  // at each position, so it'll usually be correct too.
35  Xapian::termcount size = 0;
36  for (auto pl : pls) size += pl->get_approx_size();
37  RETURN(size);
38 }
39 
42 {
43  LOGCALL(EXPAND, Xapian::termpos, "OrPositionList::get_position", NO_ARGS);
44  RETURN(current_pos);
45 }
46 
47 // PositionList::next() is actually rarely used - ExactPhrasePostList will
48 // never call it, while PhrasePostList will only call it once for the first
49 // subquery and NearPostList will call it to start subqueries if we're near
50 // the start of the document, and also if a candidate match has two subqueries
51 // at the same position.
52 bool
54 {
55  LOGCALL(EXPAND, bool, "OrPositionList::next", NO_ARGS);
56  bool first = current.empty();
57  if (first) current.resize(pls.size());
58  Xapian::termpos old_pos = current_pos;
59  current_pos = Xapian::termpos(-1);
60  size_t j = 0;
61  for (size_t i = 0; i != pls.size(); ++i) {
62  PositionList* pl = pls[i];
63  Xapian::termpos pos;
64  if (first || current[i] <= old_pos) {
65  if (!pl->next())
66  continue;
67  pos = pl->get_position();
68  } else {
69  pos = current[i];
70  }
71  current_pos = min(current_pos, pos);
72  current[j] = pos;
73  if (i != j) pls[j] = pls[i];
74  ++j;
75  }
76  pls.resize(j);
77  RETURN(j != 0);
78 }
79 
80 // A min-heap seems like an obvious optimisation here, but is only useful when
81 // handling clumps of terms - in particular when skip_to() advances all the
82 // sublists, the heap doesn't help (but we have the cost of rebuilding it, or N
83 // pop+push calls which has a worse complexity than rebuilding).
84 bool
86 {
87  LOGCALL(EXPAND, bool, "OrPositionList::skip_to", termpos);
88  bool first = current.empty();
89  if (!first && termpos <= current_pos)
90  RETURN(true);
91  if (first) current.resize(pls.size());
92  current_pos = Xapian::termpos(-1);
93  size_t j = 0;
94  for (size_t i = 0; i != pls.size(); ++i) {
95  PositionList* pl = pls[i];
96  Xapian::termpos pos;
97  if (first || termpos > current[i]) {
98  if (!pl->skip_to(termpos))
99  continue;
100  pos = pl->get_position();
101  } else {
102  pos = current[i];
103  }
104  current_pos = min(current_pos, pos);
105  current[j] = pos;
106  if (i != j) pls[j] = pls[i];
107  ++j;
108  }
109  pls.resize(j);
110  RETURN(j != 0);
111 }
#define RETURN(A)
Definition: debuglog.h:493
bool next()
Advance to the next entry in the positionlist.
virtual bool next()=0
Advance to the next entry in the positionlist.
bool skip_to(Xapian::termpos termpos)
Skip forward to the specified position.
STL namespace.
Xapian::termpos get_position() const
Return the current position.
unsigned XAPIAN_TERMCOUNT_BASE_TYPE termcount
A counts of terms.
Definition: types.h:72
Xapian::termcount get_approx_size() const
Return approximate size of this positionlist.
virtual bool skip_to(Xapian::termpos termpos)=0
Skip forward to the specified position.
virtual Xapian::termpos get_position() const =0
Return the current position.
unsigned XAPIAN_TERMPOS_BASE_TYPE termpos
A term position within a document or query.
Definition: types.h:83
Abstract base class for iterating term positions in a document.
Definition: positionlist.h:31
Debug logging macros.
#define LOGCALL(CATEGORY, TYPE, FUNC, PARAMS)
Definition: debuglog.h:487
Merge two PositionList objects using an OR operation.