Assignment 3: Document Indexer

Document indexing is an interesting and useful topic.  Web search engines, online library information systems, and application search utilities all rely on indexing.  In this assignment, you will create a simple document indexing system.  The sequence of steps below is meant to serve as an implementation guide; please turn in just the final program and test output.


This is an in-memory indexing system (meaning that all index information is held in memory rather than stored on disk).  For now, it will index only files reachable through a filesystem, and will index only individual words.  For simplicity, you can say that a words are sequences of characters separated by whitespace (which is how an input iostream reads in a string using operator >>).  You may want to strip off punctuation characters as well, but it isn't required.

The indexer is an interactive application.  Users should be able to:

A simple command line interface for doing this is fine.


Create the indexing system as a reusable component.  This means separating out the UI (command line, user interaction) from the indexing engine, and creating a reusable interface.  Make sure that the engine allows multiple, unrelated search results to exist at the same time.

Here is a suggested design:

In this design, the index is maintained by the Index object.  It populates SearchResult objects, which are basically some kind of Collection in the STL sense.  (In other words, SearchResult may be a class name for a user-defined Collection, or it may be just a typedef for some STL collection.)  SearchResult contains multiple LocationInfo objects, each of which contains the name of a location (or file) and a hit count for that search.

Create and run unit tests for your classes that don't require interactive input.  Use these to test the indexer at each step as you create it.  Turn in the unit test code and results along with your interactive sessions.

You may want to create some additional member functions to make unit testing easier.  Below is a sample which uses the unit test framework published in the recent C/C++ User's Journal ( ):


class Indexer
    // Process a file/location, adding all the words
    // found to the index:
    void processLocation(std::string const &filename);

    // Add a single word to the index.  Location of
    // word is recorded along with the count.
    void addWord(std::string const &word,
                 std::string const &location);

    // Narrow a search result by adding another word.
    // Resulting (modified) collection contains only
    // locations that contain both words.
    // The new occurrence count for each location is equal to the
    // minimum of the original and the new counts.
    void intersectResult(SearchResult &result, std::string const &word);

    // Broaden a search result by adding another word.
    // Resulting (modified) collection will have
    // all locations that contain either word.
    // For locations that contain both words, the
    // occurrence count is equal to the maximum of
    // the two individual word counts.
    void unionResult(SearchResult &result, std::string const &word);

    // Remove locations that contain the given word from the
    // result set.  (Not required.)
    void subtractResult(std::string const &word, WordInfoColl &result);

    // Print out contents of index for debugging.
    void dump() const;


class IndexerTest : public Test
    Index idx;
    IndexerTest() {
    void run() {
        // Add a single word and see if we get
        // it back when we search:
        SearchResult s;
        _test(s.begin()->first == "hellogoodbye.txt");

        // Add a new document with the same word
        // and test that we get back two results:

        // Increase the word count for a single document
        // and ensure that we still get back two documents:

        // Add a couple more words and inspect index contents:

        // Look for document that contains
        // both "hello" and "goodbye"; this
        // should be just hellogoodbye.txt:
        _test(s.begin()->first == "hellogoodbye.txt");
        _test(s.begin()->second.hitCount == 1);

        // Intersect with word "boffo" which
        // is not in index:

        // Also need to test document file interface!

int main()
    Suite s("Suite Test");

    // Catch null test:
    s.addTest(new IndexerTest);;
    long fails =;
    cout << "There were " << fails << " failures." << endl;
    cout << (fails ? "FAILURE!" : "SUCCESS!") << endl;
You can download test files here.