10#include "llvm/ADT/STLExtras.h"
25class AndIterator :
public Iterator {
27 explicit AndIterator(std::vector<std::unique_ptr<Iterator>> AllChildren)
28 : Iterator(
Kind::And),
Children(std::move(AllChildren)) {
29 assert(!
Children.empty() &&
"AND iterator should have at least one child.");
31 for (
const auto &Child : Children)
32 ReachedEnd |= Child->reachedEnd();
41 llvm::sort(Children, [](
const std::unique_ptr<Iterator> &LHS,
42 const std::unique_ptr<Iterator> &RHS) {
43 return LHS->estimateSize() < RHS->estimateSize();
47 bool reachedEnd()
const override {
return ReachedEnd; }
50 void advance()
override {
51 assert(!reachedEnd() &&
"AND iterator can't advance() at the end.");
57 void advanceTo(
DocID ID)
override {
58 assert(!reachedEnd() &&
"AND iterator can't advanceTo() at the end.");
63 DocID peek()
const override {
return Children.front()->peek(); }
66 assert(!reachedEnd() &&
"AND iterator can't consume() at the end.");
68 for (
const auto &Child : Children)
69 Boost *= Child->consume();
73 size_t estimateSize()
const override {
74 return Children.front()->estimateSize();
78 llvm::raw_ostream &dump(llvm::raw_ostream &
OS)
const override {
81 for (
const auto &Child : Children) {
92 ReachedEnd |=
Children.front()->reachedEnd();
95 auto SyncID =
Children.front()->peek();
97 bool NeedsAdvance =
false;
100 for (
auto &Child : Children) {
101 Child->advanceTo(SyncID);
102 ReachedEnd |= Child->reachedEnd();
122 }
while (NeedsAdvance);
128 std::vector<std::unique_ptr<Iterator>>
Children;
132 bool ReachedEnd =
false;
142class OrIterator :
public Iterator {
144 explicit OrIterator(std::vector<std::unique_ptr<Iterator>> AllChildren)
145 : Iterator(
Kind::Or),
Children(std::move(AllChildren)) {
146 assert(!
Children.empty() &&
"OR iterator should have at least one child.");
150 bool reachedEnd()
const override {
151 for (
const auto &Child : Children)
152 if (!Child->reachedEnd())
158 void advance()
override {
159 assert(!reachedEnd() &&
"OR iterator can't advance() at the end.");
160 const auto SmallestID = peek();
161 for (
const auto &Child : Children)
162 if (!Child->reachedEnd() && Child->peek() == SmallestID)
167 void advanceTo(
DocID ID)
override {
168 assert(!reachedEnd() &&
"OR iterator can't advanceTo() at the end.");
169 for (
const auto &Child : Children)
170 if (!Child->reachedEnd())
171 Child->advanceTo(
ID);
176 DocID peek()
const override {
177 assert(!reachedEnd() &&
"OR iterator can't peek() at the end.");
178 DocID Result = std::numeric_limits<DocID>::max();
180 for (
const auto &Child : Children)
181 if (!Child->reachedEnd())
182 Result = std::min(Result, Child->peek());
190 assert(!reachedEnd() &&
"OR iterator can't consume() at the end.");
193 for (
const auto &Child : Children)
194 if (!Child->reachedEnd() && Child->peek() ==
ID)
195 Boost = std::max(Boost, Child->consume());
199 size_t estimateSize()
const override {
201 for (
const auto &Child : Children)
202 Size = std::max(Size, Child->estimateSize());
207 llvm::raw_ostream &dump(llvm::raw_ostream &
OS)
const override {
210 for (
const auto &Child : Children) {
218 std::vector<std::unique_ptr<Iterator>>
Children;
225class TrueIterator :
public Iterator {
227 explicit TrueIterator(
DocID Size) : Iterator(
Kind::True), Size(Size) {}
229 bool reachedEnd()
const override {
return Index >= Size; }
231 void advance()
override {
232 assert(!reachedEnd() &&
"TRUE iterator can't advance() at the end.");
236 void advanceTo(
DocID ID)
override {
237 assert(!reachedEnd() &&
"TRUE iterator can't advanceTo() at the end.");
238 Index = std::min(
ID, Size);
241 DocID peek()
const override {
242 assert(!reachedEnd() &&
"TRUE iterator can't peek() at the end.");
247 assert(!reachedEnd() &&
"TRUE iterator can't consume() at the end.");
251 size_t estimateSize()
const override {
return Size; }
254 llvm::raw_ostream &dump(llvm::raw_ostream &
OS)
const override {
264class FalseIterator :
public Iterator {
266 FalseIterator() : Iterator(
Kind::False) {}
267 bool reachedEnd()
const override {
return true; }
268 void advance()
override { assert(
false); }
269 void advanceTo(
DocID ID)
override { assert(
false); }
270 DocID peek()
const override {
278 size_t estimateSize()
const override {
return 0; }
281 llvm::raw_ostream &dump(llvm::raw_ostream &
OS)
const override {
282 return OS <<
"false";
288class BoostIterator :
public Iterator {
290 BoostIterator(std::unique_ptr<Iterator> Child,
float Factor)
291 : Child(std::move(Child)), Factor(Factor) {}
293 bool reachedEnd()
const override {
return Child->reachedEnd(); }
295 void advance()
override { Child->advance(); }
297 void advanceTo(
DocID ID)
override { Child->advanceTo(
ID); }
299 DocID peek()
const override {
return Child->peek(); }
301 float consume()
override {
return Child->consume() * Factor; }
303 size_t estimateSize()
const override {
return Child->estimateSize(); }
306 llvm::raw_ostream &dump(llvm::raw_ostream &
OS)
const override {
307 return OS <<
"(* " << Factor <<
' ' << *Child <<
')';
310 std::unique_ptr<Iterator> Child;
318class LimitIterator :
public Iterator {
320 LimitIterator(std::unique_ptr<Iterator> Child,
size_t Limit)
321 : Child(std::move(Child)), Limit(Limit), ItemsLeft(Limit) {}
323 bool reachedEnd()
const override {
324 return ItemsLeft == 0 || Child->reachedEnd();
327 void advance()
override { Child->advance(); }
329 void advanceTo(
DocID ID)
override { Child->advanceTo(
ID); }
331 DocID peek()
const override {
return Child->peek(); }
336 assert(!reachedEnd() &&
"LimitIterator can't consume() at the end.");
338 return Child->consume();
341 size_t estimateSize()
const override {
342 return std::min(Child->estimateSize(), Limit);
346 llvm::raw_ostream &dump(llvm::raw_ostream &
OS)
const override {
347 return OS <<
"(LIMIT " << Limit <<
" " << *Child <<
')';
350 std::unique_ptr<Iterator> Child;
358 std::vector<std::pair<DocID, float>> Result;
364std::unique_ptr<Iterator>
366 std::vector<std::unique_ptr<Iterator>> RealChildren;
368 switch (Child->kind()) {
372 return std::move(Child);
375 auto &NewChildren =
static_cast<AndIterator *
>(Child.get())->
Children;
376 std::move(NewChildren.begin(), NewChildren.end(),
377 std::back_inserter(RealChildren));
381 RealChildren.push_back(std::move(Child));
384 switch (RealChildren.size()) {
388 return std::move(RealChildren.front());
390 return std::make_unique<AndIterator>(std::move(RealChildren));
394std::unique_ptr<Iterator>
396 std::vector<std::unique_ptr<Iterator>> RealChildren;
398 switch (Child->kind()) {
403 auto &NewChildren =
static_cast<OrIterator *
>(Child.get())->
Children;
404 std::move(NewChildren.begin(), NewChildren.end(),
405 std::back_inserter(RealChildren));
411 RealChildren.push_back(std::move(Child));
414 switch (RealChildren.size()) {
418 return std::move(RealChildren.front());
420 return std::make_unique<OrIterator>(std::move(RealChildren));
425 return std::make_unique<TrueIterator>(Size);
429 return std::make_unique<FalseIterator>();
433 float Factor)
const {
438 return std::make_unique<BoostIterator>(std::move(Child), Factor);
442 size_t Limit)
const {
445 return std::make_unique<LimitIterator>(std::move(Child), Limit);
std::vector< std::unique_ptr< HTMLNode > > Children
Symbol index queries consist of specific requirements for the requested symbol, such as high fuzzy ma...
std::unique_ptr< Iterator > none() const
Returns FALSE Iterator which iterates over no documents.
std::unique_ptr< Iterator > limit(std::unique_ptr< Iterator > Child, size_t Limit) const
Returns LIMIT iterator, which yields up to N elements of its child iterator.
std::unique_ptr< Iterator > intersect(std::vector< std::unique_ptr< Iterator > > Children) const
Returns AND Iterator which performs the intersection of the PostingLists of its children.
std::unique_ptr< Iterator > boost(std::unique_ptr< Iterator > Child, float Factor) const
Returns BOOST iterator which multiplies the score of each item by given factor.
std::unique_ptr< Iterator > all() const
Returns TRUE Iterator which iterates over "virtual" PostingList containing all items in range [0,...
std::unique_ptr< Iterator > unionOf(std::vector< std::unique_ptr< Iterator > > Children) const
Returns OR Iterator which performs the union of the PostingLists of its children.
Iterator is the interface for Query Tree node.
virtual float consume()=0
Informs the iterator that the current document was consumed, and returns its boost.
virtual bool reachedEnd() const =0
Returns true if all valid DocIDs were processed and hence the iterator is exhausted.
virtual void advance()=0
Moves to next valid DocID.
virtual DocID peek() const =0
Returns the current element this iterator points to.
std::vector< std::pair< DocID, float > > consume(Iterator &It)
Advances the iterator until it is exhausted.
uint32_t DocID
Symbol position in the list of all index symbols sorted by a pre-computed symbol quality.
===– Representation.cpp - ClangDoc Representation --------—*- C++ -*-===//