Assignment 1: WikiRacer

Part A

Note: This part should be done in the main.cpp file in the WikiRacerLinks project. Don’t write this in the InternetTest project - that part is only for the screenshots.

Congratulations on completing file reading! Let’s take a step back now and return to our algorithm. As you can imagine, a really important part of our code for this assignment will involve taking a Wikipedia page’s HTML and returning a set of all links on this page. Part A of the assignment will be to implement a function

unordered_set<string> findWikiLinks(const string& page_html);

• It must be of the following form:

  <a href="/wiki/PAGE_NAME">LINK TEXT</a>

• PAGE_NAME does not contain the characters # or :

The sea otter (Enhydra lutris) is a
<a href="/wiki/Marine_mammal">marine mammal</a>
native to the coasts of the northern and eastern North Pacific Ocean.
                                

<p>
  In <a href="/wiki/Topology">topology</a>, the <b>long line</b> (or <b>Alexandroff line</b>) is a
  <a href="/wiki/Topological_space">topological space</a> somewhat similar to the <a href="/wiki/Real_line">real line</a>, but in a certain way "longer". It behaves locally just like the real line, but has different large-scale properties (e.g., it is neither
  <a href="/wiki/Lindel%C3%B6f_space">Lindelöf</a> nor
  <a href="/wiki/Separable_space">separable</a>). Therefore, it serves as one of the basic counterexamples of topology
  <a href="http://www.ams.org/mathscinet-getitem?mr=507446">[1]</a>. Intuitively, the usual real-number line consists of a countable number of line segments [0,1) laid end-to-end, whereas the long line is constructed from an uncountable number of such segments. You can consult
  <a href="/wiki/Special:BookSources/978-1-55608-010-4">this</a> book for more information.
  </p>

{"Topology", "Topological_space", "Real_line", "Lindel%C3%B6f_space", "Separable_space"}

• The function does not return links to AMS or Special:BookSources because they are not valid Wikipedia links. (The first is not of the form /wiki/PAGENAME and the second contains the invalid character :)
• The Lindelöf link seems to have weird percentage signs and letters in its hyperlink. This is how HTML handles non-standard characters like 'ö'; don't worry about this!

The code we’ll be learning over the next few STL lectures will be really helpful for this part of the assignment. Specifically, pay attention to the countOccurrences method from lecture, which will sequentially look through a text for instances of a string. You’ll use a similar approach here.

Don’t forget to test your function using the test files in the res folder! See the File Reading section in the Preliminary Task section for more information on how to test.

Your solution must use the following algorithms to do the following things:

std::search    // to find the start of a link
std::find      // to find the end of a link
std::all_of    // to check whether the link contains an invalid character

We'll get practice using algorithms in lecture. Feel free to also take a look at cppreference.com for documentation on the above algorithms.

Note: by the end of Part A, you should’ve completed everything in the WikiRacerLinks program, and been able to test your findWikiLinks function.

Hint: At some point in your code, you may find yourself having to copy a portion of an original string into a new string using only iterators of that original string. If you have iterators start_it and end_it of your original string and you want to copy all character in the range [start_it, end_it) (inclusive of start_it and exclusive of end_it), you can do something like the following: auto string_portion = std::string(start_it, end_it);.

Part B

Congratulations on finishing the first part of the assignment! You have now implemented a function

unordered_set<string> findWikiLinks(const string& page_html);

that takes the html of a page in the form of a string as a parameter and returns an unordered_set<string> containing all the valid Wikipedia links in the page_html string.

In this next part, we are going to write the code to actually find a Wikipedia ladder between two pages. We will be writing a function:

vector<string> findWikiLadder(const string& start_page,
                              const string& end_page);

Creating the Priority Queue

The next task in the assignment is to make a priority queue using a constructor from the standard library. Although this sounds like a simple task in theory, it will require you to really understand how to use lambdas and variable capture.

The first thing to do is read the documentation for std::priority_queue. The format of a std::priority_queue looks like this:

template<class T,
    class Container = std::vector<T>,
    class Compare   = std::less<typename Container::value_type>
> class priority_queue; 

• T is the type of thing the priority queue will store;
• Container is the container the priority queue will use behind the scene to hold items (the priority queue is a container adaptor, just like the stack and queue we studied in lecture!);
• Compare is the type of our comparison function that will be used to determine which element has the highest priority.

Since we want a priority_queue of ladders, where we represent a ladder as a vector<string>, we will take T to be vector<string>, and so the Container, which is of the form vector<T>, will be a vector<vector<string>>.

Lastly, we need to determine what comparator function we want to use. Remember, we want to order the elements by how many links the page at the very end of its respective ladder has in common with the target_page. To make the priority_queue we will need to write this comparator function:

To compare ladder1 and ladder2:
  page1 = word at the end of ladder1
  page2 = word at the end of ladder2
  int num1 = number of links in common between set of links on page1 and set of links on end_page
  int num2 = number of links in common between set of links on page2 and set of links on end_page
  return num1 < num2

Now that we have all of the details, we can create the priority_queue, which takes three template parameters: the thing to store (ladder), the container to use behind the scenes (vector<ladder>), and the type of the comparison function we will use.

We hit a little snag here, since if we write our comparison function as a lambda, we have no idea what its type is. Luckily, C++ provides the decltype() method which takes an object and returns its type. Then, to the constructor of the priority_queue, we actually just pass the comparison function.

Our final priority queue looks like this:

vector<string> findWikiLadder(const string& start_page,
const string& end_page) {
  // creates WikiScraper object
  WikiScraper scraper;

  // Comparison function for priority_queue
  auto cmpFn = /* declare lambda comparator function */;

  // creates a priority_queue names ladderQueue
  std::priority_queue<vector<string>, vector<vector<string>>,
    decltype(cmpFn)> ladderQueue(cmpFn);

  // ... rest of implementation

}