Assignment 5: MiniBrowser

Displaying Text

In this part of the assignment, you'll implement a class called LineManager that stores all the lines for the current webpage, and provides information about which lines should be displayed onscreen. The only member variable (a.k.a. instance variable; private variable; field) you are allowed to have in your implementation is a Vector of pointers to Lines. do not use any other collections or data structures in any part of your code, or have any other private instance variables.

You will need to use Line objects, which represent a single line of text (spanning the entire width of the page). Below is an image of MiniBrowser, with each line outlined in red. The widths of all the lines are the same, and you can sort lines by y-coordinate, with the top line (one with the smallest y-coordinate) as the smallest. In the example below, the line "The Princess Bride is a 1973 fantasy romance novel by American" is the first Line in the webpage.

You will not need to manipulate or interact with the text; you can just treat the lines as rectangles (potentially with space between them) that together make up the webpage. No two Line objects will overlap.

The browser already handles splitting the entire webpage into lines. However, since the webpage (generally) is not visible all at once, not all of the lines need to be drawn; in fact, drawing all of the lines would make your browser run very slowly. The solution is an optimization to only draw those lines that will be visible, so your job is to write a function to determine which lines should be drawn. As the user scrolls up or down the page, the "visible range" of lines will change.

Browsers also need to handle user clicks, recognizing, for example, if the user is attempting to follow a hyperlink. You will implement a method that, given a y-coordinate, returns a pointer to the line at that location. Our starter code will then search that line for a link, allowing the user to travel to different pages.

At this link, you will find a sample interactive webpage with 12 lines of text and a scrollbar on the right (inside the black box). The black box indicates what is actually visible on the computer, but as you drag the scrollbar (give it a try), the lines will scroll out of view. The browser could render (draw) all the lines of the webpage, but since only 4-5 are visible at a time, it can optimize and only draw those that are fully or partially on the screen. Below the screen, linesInRange's value will update with which lines are in the viewable range of the screen.
The red "x" on the screen represents a location where the user may click; the line at the location of the "x" is reflected next to lineAt at the bottom of the demo. Note that there may be space between the lines, so the element is sometimes nullptr.

A Line has the following fields and methods:

Since each line spans the width of a page, we only need to store information about its height and vertical placement, not its width or horizontal placement.

As each Line corresponds to a line of text, we can order Lines by their y-coordinate, meaning that the first Line is the line at the top of the screen.

To avoid having to store the text associated with a Line multiple times and to more easily be able to link a Line a user clicked on with the text, you will only be dealing with pointers to Lines. Thus, whenever you store or manipulate the Lines, you should do so using pointers. You should not create Lines in your implementation.

Your job is to implement the following functions:

The members listed above represent your class's required behavior. But you may add other member functions to help you implement all of the appropriate behavior. Any other member functions you provide must be private. Remember that each member function of your class should have a clear, coherent purpose. You should provide private helper members for common repeated operations. Make a member function and/or parameter const if it does not perform modification of the object's state.

Browser History

A history allows a user to navigate forwards and backwards between pages that they've already viewed. You will implement the History class using a doubly-linked list, where one end of the list is the title of the most recently viewed new page (i.e. the one that should be loaded after hitting the forwards button as many times as permitted), and the other is the title of the least recently viewed page (i.e. the first page that the user visited). You will need to maintain a "curr" pointer that represents the current page in the History (the diagrams below include labels for the front and back of the list below the list, though you may find you don't need pointers to one or both ends of the list).

To create the doubly-linked list of article titles, you can use the Node struct defined in History.h:

struct Node {
    std::string title;  // the title of the article
    Node *prev;  // the node representing the article the user visited before this one
    Node *next;  // the node representing the article the user visited after this one
};

You will implement the following methods by editing History.cpp and History.h:

None of these methods should leak memory if you need to rewire pointers.

User Action	Resulting History	Image
A History object is created.	The History should be empty. hasNext() and hasPrevious() should both return false.
User opens the "Stanford University" page, then the "Stanford Band" page, and finally, the "The Play (American football)".	The current page should be "The Play (American football)". hasNext() should return false, but hasPrevious() should return true.
The user presses the back button (calling previous() on the History object). The call to previous returned "Stanford Band".	The current page should be "Stanford Band". hasNext() and hasPrevious() should both return true.
The user searches "Scramble band".	The current page should be "Scramble band". hasNext() should be false, but hasPrevious() should be true. Note: "The Play (American football)" should no longer be in the user's history. If the user had visited any pages after "The Play (American football)", those should be removed as well.

Cache

The History component only stores article titles, meaning that as is, when the user returns to a previously loaded page, they still have to wait for the page to be downloaded from Wikipedia.

You will implement a cache to save previously loaded pages to avoid having to completely reload the page. You can't indefinitely store all articles a user loads - your computer would run out of memory! As a result, our cache will have a fixed capacity and will choose an article to remove when it gets too full (so that the total number of articles in the cache never exceeds the capacity). There are many ways to choose which article to remove, but we'll be implementing a common version called a Least-Recently Used (LRU) cache, meaning that that the article that was accessed the least recently should be the one removed.

Because Least-Recently Used caches are incredibly useful, we will create a template class. See the LinkedListClass example from lecture for an example of how to implement a templatized class. While this browser will have each node store an article, you could store anything as the value - that's the power of templates!

To keep track of the order in which elements in our cache were accessed, we'll use a doubly-linked list of Nodes structs ordered by how recently the element was accessed (i.e. the most recently loaded article should be at the end of the list, and the least recently viewed article will be at the start of the linked list). You can think of this as conceptually matching the order for the history part of this assignment - newest at the right, oldest at the left.

The Node struct is defined as follows (in Cache.h):

struct Node {
    std::string key; // the key associated with this entry. For articles, it's the article title
    ValueType value; // the actual element stored in the cache
    Node* prev; // the node with the element visited less recently than this element
    Node* next; // the node with the element visited more recently than this element

};

In creating the cache, you'll need to implement the following methods by editing Cache.cpp.

Because Cache is a template class and Node is a template struct, you may have difficulty in the .cpp file if you want to create any helper functions that return a Node or take a node as a parameter. You should use the following syntax to do so:

// returning a Node *
template <typename ValueType>
typename Cache<ValueType>::Node* Cache<ValueType>::myAwesomeFunction() {
    ...
}

// Node * as parameter
template <typename ValueType>
void Cache<ValueType>::myAwesomeFunction(typename Cache<ValueType>::Node* node) {
    ...
}

You may have realized while our cache works as described above, determining if an article is in the cache requires an O(N) search. To optimize, after you have completed the doubly-linked list implementation described above, you should add a HashMap to the cache that maps string keys to where they are stored in the doubly-linked list. Think about what data types might be useful to achieve this.

You should be careful to test your doubly-linked list implementation thoroughly before adding the HashMap. Additionally, make sure that your HashMap and the linked list always have the same articles stored.

User Action	Resulting Cache	Image
A Cache object is created with a capacity of 3.	The Cache should be empty but will be constrained to hold no more than 3 items at a time. containsKey for any article title should return false.
User searches for and opens the "Stanford University" page.	The browser first tries to call containsKey("Stanford University"). Since the cache does not contain "Stanford University," the browser will download the page and then put it in the cache. Afterwards, the cache should have one element, "Stanford University", which is also the most-recently seen element.
User searches for and opens the "Stanford Band" page, followed by "The Play (American Football)".	With both articles, the browser first tries to call containsKey on the article titles. Since the cache does not contain either title, the browser will download the page and then put it in the cache. After both searches, the cache should have three elements, with "The Play (American Football)" as the most-recently accessed, and "Stanford University" as the least recently accessed.
The user presses the back button in the browser.	The browser knows from the History object that the user wants to load the page "Stanford Band", so the browser calls containsKey("Stanford Band"), which returns true. Therefore, the browser tries to get("Stanford Band"). At this point, the article "Stanford Band" is the most recently viewed article. The articles in the cache (and, therefore, the HashMap) have not changed, but the order of the nodes in the linked list should be updated to reflect this change.
The user searches "Scramble band".	The browser first tries to call containsKey("Scramble band"), which returns false. Just as before, the browser downloads the article and then puts it in the Cache. Since the cache is now at capacity, the cache should remove the least-recently accessed element ("Stanford University") from the cache (both from the HashMap and from the linked list). "Scramble band" is the most recently used article, whereas "The Play (American Football)" is now the least-recently viewed article. containsKey("Stanford University") should now return false.

Implementation Order

This part can be daunting if you attempt to solve it all at once. Instead, try breaking the problem down as follows:

1. Doubly-Linked List: Implement the methods above with just a doubly-linked list. Don't worry about keeping the cache under the maximum size or about the HashMap; just make sure you have an implementation that can find articles in the cache.
2. Move to End: A key component of the least-recently used cache is that we need to keep the elements in order of when they were accessed, with the most recently accessed articles at the end. Implement a method to move an element in the linked list to the end, and modify your doubly-linked list to keep the elements in order of when they were accessed.
3. Evict from Cache: Now that your doubly-linked list is in sorted order, determine how to ensure that the size of the cache never exceeds the maximum size.
4. Add the HashMap: Add a HashMap mapping from the string article titles to where their nodes are in the doubly-linked list. You may find you don't need some of your doubly-linked list code anymore after doing so.

With the HashMap and linked list, your cache implementation should have the following speedy method runtimes:

As with History, be sure that your implementation does not leak any memory.