# Project: Building a Browser History Manager

Your task is to create a Python class that simulates the "back" and
"forward" history of a web browser. This project is designed to help you
understand and apply the principles of linked lists by using a linked-list
data structure in Python:
[`collections.deque`](https://docs.python.org/3/library/collections.html#collections.deque).
Read through this documentation so you understand what functions are
available. You should have a good idea of how each of them are implemented and
what the runtime of each is.

In a browser, when you go "back," of course you don't delete the pages you
moved past. They are simply moved to a "forward" history stack. When you click
"forward," pages are moved to the "back" queue. When you visit a new page, the "forward" history is cleared, and the new page is added to the history. This is a perfect use case for a double-ended queue, or deque.

## Project Requirements

You will be implementing a `BrowserHistory` class in a file called
`browserhistory.py` with the following methods:

### Data Structures:

- You will need two deque objects to manage the history:

    - `self.__back`: A deque to store the history of pages you can go back to.

    - `self.__forward`: A deque to store the pages you can go forward to.

- You will also need a variable to store the `self.__current` page.

Functionality:

- `__init__()`: The initializer for your BrowserHistory class. It should
  initialize the two deque objects and the `self.__current` variable.

- `visit(url)`: This method simulates visiting a new webpage. The current page
  should go onto the end of `.__back`. It should also clear the `.__forward`
  deque, as a new visit resets the forward history. Finally, it should update
  `.__current` to the new url.

- `back()`: This method simulates clicking the "back" button. It should check
  if the `self.__back` deque is empty. If it is, you cannot go back further, so
  it should change nothing and return. If it's not empty, it should move the
  current page to the front of the `self.__forward` deque. Then, it should
  update the `self.__current` page by taking the last page from the
  `self.__back` deque.

- `forward()`: This method simulates clicking the "forward" button. It should
  check if the `self.__forward` deque is empty. If it is, you cannot go
  forward further, so change nothing and return. If it's not empty, it should
  move the current page to the `self.__back` deque. Then, it should update the
  `self.__current` page by taking the first page from the `self.__forward`
  deque.

- `get_history()`: This method should return a list that represents the full
  history in order. It should combine the `__back` deque, the `__current` page
  (which you should mark with an asterisk, like `*my_current_page.com`), and the
  `__forward` deque.

- `clear_history()`: This method should clear `__forward`, `__back`, and
  `__current` back to the initial state where no sites have been visited.

### Example

Here is a visual illustration of how your deques should change as you call
different functions. I'm illustrating the deques using list notation, but of
course they're linked lists, not Python lists (I just don't want to draw all
the boxes).

`bh = BrowserHistory()`

All fields are initialized as empty.

![](browser1.png)

If at this point we call `bh.get_history()`, it would return `[]`.

`bh.visit('a.com')`

Current is updated now that we've visited a site.

![](browser2.png)

If at this point we call `bh.get_history()`, it would return `['*a.com']`.

`bh.visit('b.org')`

Current and back is updated now that we've visited a site.

![](browser3.png)

```python
bh.visit('c.net')
bh.visit('d.com')
```

Current and back updated.

![](browser4.png)

If we called `bh.get_history()` now, it would return
`['a.com','b.org','c.net','*d.com']` (the asterisk indicating the current
page).

`bh.back()`

![](browser5.png)

If we called `bh.get_history()` now, it would return
`['a.com','b.org','*c.net','d.com']`.

`bh.back()`

![](browser6.png)

If we called `bh.get_history()` now, it would return
`['a.com','*b.org','c.net','d.com']`.

`bh.visit('e.gov')` - this visit clears out the `__forward` queue.

![](browser7.png)

## Submission

Upload your solution to the submit site as project browserhistory. There are test cases to help you check your work.