6. Browsing system for Deque

Point

---

1. Browsing system 알고리즘 원리

2. Deque의 주요 함수 (push_back, push_front, pop_back, pop_front, front, back)

Problem

---

With what you've learned about deques, it's time to apply your knowledge to create a more advanced data structure — a BrowserHistory management system. This system will enable users to visit new URLs, navigate backward and forward through their browsing history, and efficiently manage these operations using deques to handle past and future navigations. Your challenge is to implement the three methods that drive this functionality:

void visit(const std::string& url) — Adds a new URL to the browsing history and clears any forward history.
std::string back(int steps) — Moves back in history by the specified number of steps, if possible, and updates the forward history. Returns the current URL after the update.
std::string forward(int steps) — Moves forward in history by the specified number of steps, if possible, and updates the current browsing history. Returns the current URL after the update.
Example:

visit("codesignal.com") - Visits codesignal.com; current history: ["codesignal.com"].
visit("learn.codesignal.com") - Visits learn.codesignal.com; current history: ["codesignal.com", "learn.codesignal.com"].
visit("learn.codesignal.com/course-paths") - Visits learn.codesignal.com/course-paths; current history: ["codesignal.com", "learn.codesignal.com", "learn.codesignal.com/course-paths"].
back(2) - Moves back 2 steps; current history: ["codesignal.com"]. Returns codesignal.com.
forward(1) - Moves forward 1 step; current history: ["codesignal.com", "learn.codesignal.com"]. Returns learn.codesignal.com.

#include "solution.hpp"
#include <algorithm>

void BrowserHistory::visit(const std::string &url) {
    // TODO: Add the visited URL to the history and clear the future
    history_.push_back(url);
    future_.clear();
}

std::string BrowserHistory::back(int steps) {
    // TODO: Move the specified number of steps back in the history, if possible, and update the future accordingly
    // std::rotate(history_.rbegin(), history_.rbegin()+steps, history_.rend());
    // Return the current URL after updating
    
    if (history_.empty()) {
        return "No back";
    }
    
    for (int index = 0; index < steps; ++index) {
        std::string current = history_.back();
        future_.push_front(current);
        history_.pop_back();
        
        if (history_.empty()) {
            return "No back";
        }
    }
    
    return history_.front();
}

std::string BrowserHistory::forward(int steps) {
    // TODO: Move the specified number of steps forward in the history, if possible, and update the history accordingly
    // Return the current URL after updating
    if (future_.empty()) {
        return "No back";
    }

    for (int index = 0; index < steps; ++index) {
        std::string current = future_.front();
        history_.push_back(current);
        future_.pop_back();
        
        if (future_.empty()) {
            return "No back";
        }
    }
    
    return history_.back();
}

int main() {
    BrowserHistory browser;

    // TODO: Use the BrowserHistory class to simulate visiting some URLs, then going back and forward in the history, printing the resulting URL after each move
    
    browser.visit("codesignal.com");
    browser.visit("learn.codesignal.com");
    browser.visit("learn.codesignal.com/course-paths");
    
    std::cout << browser.back(2) << std::endl;
    std::cout << browser.forward(1) << std::endl;
    
    return 0;
}