Introduction
Remembering two words should narrow your search to notes containing both. The words may be on different lines, and two notes with the same filename must still remain distinct.
This independent lab supplies a correct word-to-document index. You implement its query intersection, rebuild the real CLI executable, distinguish a normal empty result from invalid input, and search after practice edits. It builds on the previous lab's maps, sets, ASCII tokens, and terminal/file operations. The 55-minute duration is an author estimate.
Keep Only Documents Shared by Every Word
In this step, implement document-level AND: a note matches only if it contains every query word, even when those words occur on different lines. This lab starts independently. A correct index is already provided; it does not depend on your previous environment. Use the Terminal tab, not a terminal inside WebIDE. It starts a UTF-8 shell without changing your files. cd changes this shell's directory; repeat it if you open another connection.
cd /home/labex/project/note-search
The complete sample takes a directory and a query. Single quotes keep two words as one shell argument. The program parses that argument using the same ASCII rule as the notes:
./sample notes 'cat blue'
Expect practice/旅行 notes.txt and reference/archive/notes.txt. The archive group contains:
File: reference/archive/notes.txt
1: CAT, cat!
2: Blue ledger — 東京
3: cat blue together
Every line containing either query word appears once, with its real 1-based line number. The AND decision applies to the entire document, not to one line. A note with cat only on line 1 and blue only on line 2 must still match. Multiple occurrences or two query terms on the same line do not repeat the line. Original Unicode bytes remain in the snippets.
cat prints a file. Read the interface and the prepared index implementation:
cat search.hpp
cat provided.inc
Index is a map from a word to a set of full relative document identities. A word's document set is also called its posting set. provided.inc supplies the correct buildIndex in this unit. engine.cpp contains the incomplete findAll:
cat engine.cpp
Preserve search.hpp, provided.inc, support.cpp, main.cpp, sample, and all paths and contents under notes/reference/. Edit engine.cpp; helpers and equivalent algorithms are allowed. Only notes/practice/ is mutable data, and its original file membership is not required. The prepared loader recursively reads regular UTF-8 LF .txt files. Spaces and Unicode paths are supported; path tabs/newlines, symlinks, NUL bytes, and arbitrary binary files are outside the input format. Read failures produce an error with no partial search results.
The prepared parser words() produces maximal ASCII letter runs, lowercased from A-Z to a-z. Digits, underscore, punctuation, spaces, and every non-ASCII byte delimit tokens. cat is not catalog; CAT-blue_42 gives cat and blue; 猫cat狗 gives cat; café gives caf, not cafe. This does not claim multilingual word segmentation. findAll receives already normalized lowercase ASCII terms from that parser, possibly with duplicates. It must safely return an empty vector for empty terms. The CLI separately rejects a raw query that contains no ASCII words with exit status 2 and no result stdout; an unknown word or valid query with no matches is normal exit 0 and No matching documents.
bash runs the self-check; query selects the complete query behavior. The starter intentionally fails, normally at FAIL all documents, not only the first. A nonzero status now means work remains:
bash /opt/labex-note-search/check.sh query
For an AND query, start with a copy of the first word's posting set. Then remove each candidate identity absent from any other term's set. This is set intersection. If a query term is unknown, no document can contain all terms. Never combine all postings by adding them together: that would be OR, accepting notes that contain only one of the requested words.
terms.empty() must be checked before terms.front() accesses the first element. index.find(word) looks up a map key without inserting one; index.end() means no such key. Do not dereference that missing entry. For a found entry, first->second or posting->second uses -> to access the entry through its iterator; second is the entry's value, the set of IDs. Copy that set into found so querying does not change the index.
The loop uses an iterator, a position within the set. found.begin() is its first position; found.end() marks the position after the last. *it is the current ID. .count(*it) is 0 when that ID is absent from another posting set. Erasing invalidates the old position, so erase(it) returns the next valid iterator. Otherwise ++it advances normally. Do not increment twice after erasing.
Replace engine.cpp with the following implementation. As in the previous lab, the here-document writes a complete file; > replaces it, and the quoted 'CPP' delimiter prevents shell expansion. CPP must end the command alone on a line. The includes retain the interface and correct prepared index.
cat > engine.cpp <<'CPP'
#include "search.hpp"
#include "provided.inc"
std::vector<std::string> findAll(const Index& index,
const std::vector<std::string>& terms) {
if (terms.empty()) return {};
auto first = index.find(terms.front());
if (first == index.end()) return {};
std::set<std::string> found = first->second;
for (const auto& term : terms) {
auto posting = index.find(term);
if (posting == index.end()) return {};
for (auto it = found.begin(); it != found.end();) {
if (posting->second.count(*it) == 0) it = found.erase(it);
else ++it;
}
}
return std::vector<std::string>(found.begin(), found.end());
}
CPP
The final constructor copies the remaining set range into a vector. Sets contain unique IDs, so each document is returned once. Checking the first term again in the loop is harmless: intersecting a set with itself does not change it. Repeated query words are harmless for the same reason. An empty posting intersection naturally returns an empty vector. A repeatable alternative group order, including descending paths, is allowed; line numbers within each group must still increase.
Compile your current source. g++ compiles the three .cpp files; -std=c++17 selects C++17, -Wall -Wextra enables warnings, and -o names the executable. Included files are compiled through engine.cpp automatically:
g++ -std=c++17 -Wall -Wextra engine.cpp support.cpp main.cpp -o findnotes
Success normally prints nothing. On failure, read the first file/line diagnostic, correct engine.cpp or repeat its replacement, and rebuild. A failed compilation can leave an older binary; the check tests both source functions and your actual existing findnotes, without rebuilding it. A missing or stale executable is not a completed deliverable.
./findnotes notes 'cat blue'
Compare the complete groups and line evidence with the sample. The prepared renderer uses your returned IDs to select real source lines; changing source notes or printing fixed success text is not a search implementation.
Distinguish Empty Results from Invalid Queries
In this step, exercise repeated words, token boundaries, errors, and current-file rebuilding. Stay in Terminal in the project directory. The completed function must not mutate its const Index& input or duplicate documents when a word repeats:
./findnotes notes 'cat cat blue'
The document groups and lines are the same as for cat blue. Now add an unknown term:
./findnotes notes 'cat absent'
Expect No matching documents. A document containing cat alone is insufficient. This is a valid query with no answer, so it exits 0. Immediately after a command, the shell variable $? holds its exit status; double quotes expand it as one argument. printf displays it, and \n ends the output line:
printf 'Exit status: %s\n' "$?"
It prints Exit status: 0. Test case folding and separators:
./findnotes notes 'CAT-blue_42'
It has the same meaning as cat blue. Neither digits nor underscores become part of the tokens. Querying a whole word does not use substring matching:
./findnotes notes catalog
Only reference/catalog.txt and the practice note containing catalog match. It does not mean cat.
An empty string is written as two adjacent single quotes, ''. It is a supplied but empty shell argument. The following command is an intentional failure, printing Query needs at least one ASCII word on stderr and no result stdout:
./findnotes notes ''
Read its status immediately:
printf 'Exit status: %s\n' "$?"
It prints 2. A query with only digits, separators, and non-ASCII characters is invalid for the same reason:
./findnotes notes '42_東京'
This is also an intentional status-2 failure. It does not imply broken Unicode storage: the query simply has no supported ASCII word. Recover by supplying a word query, not by editing original text or changing the tokenizer.
A misspelled directory is a different error. This next command deliberately names a directory that is not present:
./findnotes missing-notes cat
It prints Cannot read notes directory and exits 2 without partial results. Use find notes -type f if you need to inspect the actual paths, then recover with the correct root:
./findnotes notes cat
The normal results return. The same all-or-error rule applies if any source file is unreadable. An empty but readable notes directory, by contrast, is valid and gives no matches.
Now change the prepared writable practice copy. Single quotes preserve a filename with spaces and Unicode. printf writes text, \n makes LF line breaks, and > replaces that practice file. The originals under reference remain untouched:
printf 'cat green\n東京 — preserved\n' > 'notes/practice/旅行 notes.txt'
./findnotes notes 'cat blue'
Only the archive document remains: the practice note no longer contains blue. Every invocation rereads current files and builds a new in-memory index. There is no saved cache or extra refresh command. Changing data needs a rerun; changing C++ needs recompilation.
Add a note whose query words occur on separate lines:
printf 'BLUE here\ncat elsewhere 東京\n' > 'notes/practice/new notes.txt'
./findnotes notes 'cat blue'
practice/new notes.txt now matches and shows lines 1 and 2, along with the archive result. This is direct evidence of document-level AND across lines. rm removes only the named practice file:
rm 'notes/practice/new notes.txt'
./findnotes notes 'cat blue'
The extra group disappears. If a path is misspelled, list files and use the exact path; do not reset the VM. If you target a protected original, leave it unchanged and use a practice file. All legitimate practice changes remain allowed by grading.
Run the self-check. It reads your live project and uses disposable fixtures for additional inputs; it never repairs your binary, edits live notes, or resets progress. Invalid-input probes can print their expected errors beside PASS lines; successful completion ends with CLI CHECKS PASSED:
bash /opt/labex-note-search/check.sh query
If source tests pass but the actual executable fails, recompile findnotes from the current source and retry. Repeated checks should leave your engine, executable, prepared files, originals, and current practice contents unchanged.
Summary
You implemented AND as intersection of document identities, including terms on separate lines. Repeated terms are harmless, unknown words give normal empty results, and malformed queries or unreadable input fail explicitly. Your existing executable now reads current practice data and shows every relevant original line once. The challenge combines this query behavior with index construction on a different notebook collection.
