Doubly linked-lists: Implement the “history” feature of a web browser using a do
ID: 3736835 • Letter: D
Question
Doubly linked-lists:
Implement the “history” feature of a web browser using a doubly linked list:
Implement the BrowserHistory class using the browserhistory.cpp file
------------------------------
browserhistory.cpp
#include "browserhistory.h"
// Creates a new browser history with only one page visited: default_url
BrowserHistory::BrowserHistory(string default_url)
{
}
// Returns the current page.
string BrowserHistory::current_url()
{
}
// Moves the browser to a new page url via,
// e.g., clicking a link, typing into the address bar, etc.
void BrowserHistory::go_to_url(string url)
{
}
// Moves back (into the past) by one url.
void BrowserHistory::back()
{
}
// Returns whether there is a url in the past,
// i.e. whether the back button can be pushed.
bool BrowserHistory::can_go_back()
{
}
// Returns how many urls are in the past,
// i.e. how many times in a row the back button could be pushed.
int BrowserHistory::past_url_count()
{
}
// Moves forward (into the future) by one url.
void BrowserHistory::forward()
{
}
// Returns whether there is a url in future,
// i.e. whether the future button can be pushed.
bool BrowserHistory::can_go_forward()
{
}
// Returns how many urls are in the future,
// i.e. how many times in a row the forward button could be pushed.
int BrowserHistory::future_url_count()
{
}
---------------------------------
browserhistory.h:
#ifndef BROWSERHISTORY_H
#define BROWSERHISTORY_H
#include <string>
#include <stack>
using namespace std;
class BrowserHistory
{
public:
// Creates a new browser history with only one page visited: default_url
BrowserHistory(string default_url);
// Returns the current page.
string current_url();
// Moves the browser to a new page url via,
// e.g., clicking a link, typing into the address bar, etc.
void go_to_url(string url);
// Moves back (into the past) by one url.
void back();
// Returns whether there is a url in the past,
// i.e. whether the back button can be pushed.
bool can_go_back();
// Returns how many urls are in the past,
// i.e. how many times in a row the back button could be pushed.
int past_url_count();
// Moves forward (into the future) by one url.
void forward();
// Returns whether there is a url in future,
// i.e. whether the future button can be pushed.
bool can_go_forward();
// Returns how many urls are in the future,
// i.e. how many times in a row the forward button could be pushed.
int future_url_count();
private:
class Node
{
public:
string url;
Node* next;
Node* prev;
};
// A head and a tail pointer
Node* head;
Node* tail;
Node* current;
};
#endif
-------------------------------
main.cpp:
#include <iostream>
#include "browserhistory.h"
inline void _test(const char* expression, const char* file, int line)
{
cerr << "test(" << expression << ") failed in file " << file << ", line " << line << "." << endl;
abort();
}
#define test(EXPRESSION) ((EXPRESSION) ? (void)0 : _test(#EXPRESSION, __FILE__, __LINE__))
void interactive_mode()
{
BrowserHistory bh("http://google.com");
cout << "Starting at " << bh.current_url() << "." << endl;
cout << "Choose (B)ack, (F)orward, or enter a url to go to." << endl;
string line;
while (cin)
{
string line;
getline(cin, line);
if (line == "B")
{
if (bh.can_go_back())
{
bh.back();
cout << " Now at " << bh.current_url() << endl;
}
else
cout << " Cannot go back." << endl;
}
else if (line == "F")
{
if (bh.can_go_forward())
{
bh.forward();
cout << " Now at " << bh.current_url() << endl;
}
else
cout << " Cannot go forward." << endl;
}
else if (line.size() > 0)
{
bh.go_to_url(line);
cout << " Now at " << bh.current_url() << endl;
}
}
exit(0);
}
int main()
{
// Uncomment line below to use your BrowserHistory interactively.
//
// interactive_mode();
// Comments below indicate the current (expected) state of the history.
// Example: [url1, url2, url3, (url4), url5, url6]
// The urls are listed oldest to newest from left to right,
// and the url in parentheses is the current url.
// History: [(google.com)]
BrowserHistory bh("http://google.com");
test(bh.current_url() == "http://google.com");
test(!bh.can_go_back());
test(!bh.can_go_forward());
test(bh.past_url_count() == 0);
test(bh.future_url_count() == 0);
bh.go_to_url("http://netflix.com");
bh.go_to_url("http://amazon.com");
bh.go_to_url("http://utrgv.edu");
// History: [google.com, netflix.com, amazon.com, (utrgv.edu)]
test(bh.current_url() == "http://utrgv.edu");
test(bh.can_go_back());
test(!bh.can_go_forward());
test(bh.past_url_count() == 3);
test(bh.future_url_count() == 0);
bh.back();
bh.back();
// History: [google.com, (netflix.com), amazon.com, utrgv.edu]
test(bh.current_url() == "http://netflix.com");
test(bh.can_go_back());
test(bh.can_go_forward());
test(bh.past_url_count() == 1);
test(bh.future_url_count() == 2);
bh.forward();
// History: [google.com, netflix.com, (amazon.com), utrgv.edu]
test(bh.current_url() == "http://amazon.com");
test(bh.can_go_back());
test(bh.can_go_forward());
test(bh.past_url_count() == 2);
test(bh.future_url_count() == 1);
// History: [google.com, netflix.com, amazon.com, (youtube.com)]
bh.go_to_url("http://youtube.com");
test(bh.current_url() == "http://youtube.com");
test(bh.can_go_back());
test(!bh.can_go_forward());
test(bh.past_url_count() == 3);
test(bh.future_url_count() == 0);
bh.forward(); // Can't go forward any more, so do nothing
test(bh.current_url() == "http://youtube.com");
bh.back();
bh.back();
bh.back();
// History: [(google.com), netflix.com, amazon.com, youtube.com]
test(bh.current_url() == "http://google.com");
bh.back(); // Can't go back any more, so do nothing
test(bh.current_url() == "http://google.com");
// Larger test
string url("http://url00.com");
for (int i = 0; i < 100; ++i)
{
url[10] = i / 10 + '0';
url[11] = i % 10 + '0';
bh.go_to_url(url);
}
// History: [url00.com, url01.com, url02.com, ..., (url99.com)]
for (int i = 0; i < 49; ++i)
bh.back();
// History: [url00.com, url01.com, ..., (url50.com), ..., url99.com]
test(bh.current_url() == "http://url50.com");
cout << "Assignment complete." << endl;
}
Explanation / Answer
// browserhistory.h
#ifndef BROWSERHISTORY_H_
#define BROWSERHISTORY_H_
#include <string>
#include <stack>
using namespace std;
class BrowserHistory
{
public:
// Creates a new browser history with only one page visited: default_url
BrowserHistory(string default_url);
// Returns the current page.
string current_url();
// Moves the browser to a new page url via,
// e.g., clicking a link, typing into the address bar, etc.
void go_to_url(string url);
// Moves back (into the past) by one url.
void back();
// Returns whether there is a url in the past,
// i.e. whether the back button can be pushed.
bool can_go_back();
// Returns how many urls are in the past,
// i.e. how many times in a row the back button could be pushed.
int past_url_count();
// Moves forward (into the future) by one url.
void forward();
// Returns whether there is a url in future,
// i.e. whether the future button can be pushed.
bool can_go_forward();
// Returns how many urls are in the future,
// i.e. how many times in a row the forward button could be pushed.
int future_url_count();
private:
class Node
{
public:
string url;
Node* next;
Node* prev;
};
// A head and a tail pointer
Node* head;
Node* tail;
Node* current;
};
#endif /* BROWSERHISTORY_H_ */
// end of browserhistory.h
// browserhistory.cpp
#include "browserhistory.h"
// Creates a new browser history with only one page visited: default_url
BrowserHistory::BrowserHistory(string default_url)
{
head = new Node();
head->url = default_url;
head->prev = NULL;
head->next = NULL;
tail = head;
current = head;
}
// Returns the current page.
string BrowserHistory::current_url()
{
if(current != NULL)
return current->url;
return "";
}
// Moves the browser to a new page url via,
// e.g., clicking a link, typing into the address bar, etc.
void BrowserHistory::go_to_url(string url)
{
Node *newPage = new Node;
newPage->url = url;
newPage->next = NULL;
if(current == NULL)
{
newPage->next = head;
head->prev = newPage;
head = newPage;
current = newPage;
}else{
Node *temp = head;
while(temp != current)
{
temp = temp->next;
}
newPage->prev = current;
current->next = newPage;
current = newPage;
}
}
// Moves back (into the past) by one url.
void BrowserHistory::back()
{
if(can_go_back())
current = current->prev;
}
// Returns whether there is a url in the past,
// i.e. whether the back button can be pushed.
bool BrowserHistory::can_go_back()
{
if(current->prev != NULL)
return true;
return false;
}
// Returns how many urls are in the past,
// i.e. how many times in a row the back button could be pushed.
int BrowserHistory::past_url_count()
{
int count = 0;
Node *temp = current;
while(temp->prev != NULL)
{
temp = temp->prev;
count++;
}
return count;
}
// Moves forward (into the future) by one url.
void BrowserHistory::forward()
{
if(can_go_forward())
current = current->next;
}
// Returns whether there is a url in future,
// i.e. whether the future button can be pushed.
bool BrowserHistory::can_go_forward()
{
if(current->next != NULL)
return true;
return false;
}
// Returns how many urls are in the future,
// i.e. how many times in a row the forward button could be pushed.
int BrowserHistory::future_url_count()
{
int count = 0;
Node *temp = current;
while(temp->next != NULL)
{
temp = temp->next;
count++;
}
return count;
}
// end of browserhistory.cpp
//main.cpp
#include <iostream>
#include "browserhistory.h"
inline void _test(const char* expression, const char* file, int line)
{
cerr << "test(" << expression << ") failed in file " << file << ", line " << line << "." << endl;
abort();
}
#define test(EXPRESSION) ((EXPRESSION) ? (void)0 : _test(#EXPRESSION, __FILE__, __LINE__))
void interactive_mode()
{
BrowserHistory bh("http://google.com");
cout << "Starting at " << bh.current_url() << "." << endl;
cout << "Choose (B)ack, (F)orward, or enter a url to go to." << endl;
string line;
while (cin)
{
string line;
getline(cin, line);
if (line == "B")
{
if (bh.can_go_back())
{
bh.back();
cout << " Now at " << bh.current_url() << endl;
}
else
cout << " Cannot go back." << endl;
}
else if (line == "F")
{
if (bh.can_go_forward())
{
bh.forward();
cout << " Now at " << bh.current_url() << endl;
}
else
cout << " Cannot go forward." << endl;
}
else if (line.size() > 0)
{
bh.go_to_url(line);
cout << " Now at " << bh.current_url() << endl;
}
}
exit(0);
}
int main()
{
// Uncomment line below to use your BrowserHistory interactively.
//
// interactive_mode();
// Comments below indicate the current (expected) state of the history.
// Example: [url1, url2, url3, (url4), url5, url6]
// The urls are listed oldest to newest from left to right,
// and the url in parentheses is the current url.
// History: [(google.com)]
BrowserHistory bh("http://google.com");
test(bh.current_url() == "http://google.com");
test(!bh.can_go_back());
test(!bh.can_go_forward());
test(bh.past_url_count() == 0);
test(bh.future_url_count() == 0);
bh.go_to_url("http://netflix.com");
bh.go_to_url("http://amazon.com");
bh.go_to_url("http://utrgv.edu");
// History: [google.com, netflix.com, amazon.com, (utrgv.edu)]
test(bh.current_url() == "http://utrgv.edu");
test(bh.can_go_back());
test(!bh.can_go_forward());
test(bh.past_url_count() == 3);
test(bh.future_url_count() == 0);
bh.back();
bh.back();
// History: [google.com, (netflix.com), amazon.com, utrgv.edu]
test(bh.current_url() == "http://netflix.com");
test(bh.can_go_back());
test(bh.can_go_forward());
test(bh.past_url_count() == 1);
test(bh.future_url_count() == 2);
bh.forward();
// History: [google.com, netflix.com, (amazon.com), utrgv.edu]
test(bh.current_url() == "http://amazon.com");
test(bh.can_go_back());
test(bh.can_go_forward());
test(bh.past_url_count() == 2);
test(bh.future_url_count() == 1);
// History: [google.com, netflix.com, amazon.com, (youtube.com)]
bh.go_to_url("http://youtube.com");
test(bh.current_url() == "http://youtube.com");
test(bh.can_go_back());
test(!bh.can_go_forward());
test(bh.past_url_count() == 3);
test(bh.future_url_count() == 0);
bh.forward(); // Can't go forward any more, so do nothing
test(bh.current_url() == "http://youtube.com");
bh.back();
bh.back();
bh.back();
// History: [(google.com), netflix.com, amazon.com, youtube.com]
test(bh.current_url() == "http://google.com");
bh.back(); // Can't go back any more, so do nothing
test(bh.current_url() == "http://google.com");
// Larger test
string url("http://url00.com");
for (int i = 0; i < 100; ++i)
{
url[10] = i / 10 + '0';
url[11] = i % 10 + '0';
bh.go_to_url(url);
}
// History: [url00.com, url01.com, url02.com, ..., (url99.com)]
for (int i = 0; i < 49; ++i)
bh.back();
// History: [url00.com, url01.com, ..., (url50.com), ..., url99.com]
test(bh.current_url() == "http://url50.com");
cout << "Assignment complete." << endl;
}
// end of main.cpp
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.