Stacks Binary Trees

Design Browser History

Stacks
JavaScript

Problem:

You have a browser of one tab where you start on the homepage and you can visit another url, get back in the history number of steps or move forward in the history number of steps. So these operations can be performed on the browser history:

  • visit(url): Visits a URL given as string
  • forward(steps): Forward the given number of steps
  • backward(steps): Backward the given number of steps

When a set of operations is given, find the active page the user is on at the end of these operations.

Example:

Home Pate: wp.com

Input Array (Browser operations):

[
    'visit(x.com)'
    'visit(fb.com)'
    'visit(ytb.in)'
    'back(1)'
    'back(1)'
    'forward(1)'
    'visit(one.com)'
    'forward(1)'
    'back(2)'
]

Output (The current page user is on): ‘x.com’

Algorithm:

We can solve this using two stacks. When the user performs visit operations we can keep track of the active urls in stack 1. And when the user performs the back operation then we need to pop the urls from stack 1 and push them onto stack 2. The urls in the stack 2 will be used to perform the forward opearion. Finally the url at the top of the stack 1 is the current active url.

Steps:

  1. Loop through the operations and perform these steps:
    1. For visit operation push the url to the stack 1.
    2. For backward operation pop the url from stack 1 and push to stack 2.
    3. For forward operation pop the url from stack 2 and push to stack 1.
  2. Finally the url at the top of the stack 1 is the current active url.

Solution & Visualize:

The animation/visualization below demonstrates how the algorithm to reverse a string works. Feel free to experiment by changing the input strings.

Result
Code

Input:

Homepage: wp.com
[
    'visit(x.com)',
    'visit(fb.com)',
    'visit(ytb.in)',
    'back(1)',
    'back(1)',
    'forward(1)',
    'visit(one.com)',
    'forward(1)',
    'back(2)'
]

Output:

   
solution.js
stack.js
stack-displayer.js
animator-module.js
function stackSolution(args) {
    let browserOps = [
        'visit(x.com)',
        'visit(fb.com)',
        'visit(ytb.in)',
        'back(1)',
        'back(1)',
        'forward(1)',
        'visit(one.com)',
        'forward(1)',
        'back(2)'
    ];

    const stack = new Stack(
        ['wp.com'],
        {
            name: 'Stack',
            description: 'This stack holds the browser history.'
        }
    );

    const forwardStack = new Stack(
        [],
        {
            name: 'Forward Stack',
            description: 'This stack holds the urls for forward operation.'
        }
    );

    let browserOp, value;
    for (var i = 0; i < browserOps.length; i++) {
        browserOp = browserOps[i].substr(0, browserOps[i].indexOf('('));
        value = browserOps[i].replace(browserOp, '').replaceAll(/[\(\)]/g, '');

        if (browserOp == 'visit') {
            animatorModule.displayComment(
                'Loop through the browser operations. <br><br><strong class="sv-comment-highlight-char">'+ browserOps[i] +'</strong><br><br>'
                + 'For visit operation push url to the stack and clear the forward stack.',
                500
            );
            stack.push(value);

            while (! forwardStack.isEmpty()) {
                forwardStack.pop();
            }
        }

        if (browserOp == 'back') {
            animatorModule.displayComment(
                'Loop through the browser operations. <br><br><strong class="sv-comment-highlight-char">'+ browserOps[i] +'</strong><br><br>'
                + 'For back operation move the urls from input Stack to Forward Stack.',
                500
            );

            value = parseInt(value);
            while (value > 0) {
                if (stack.isEmpty()) {
                    break;
                }
                forwardStack.push(stack.pop());
                value--;
            }

            if (value > 0 && ! stack.isEmpty()) {
                stack.push(forwardStack.pop());
            }
        }

        if (browserOp == 'forward') {
            animatorModule.displayComment(
                'Loop through the browser operations. <br><br><strong class="sv-comment-highlight-char">'+ browserOps[i] +'</strong><br><br>'
                + 'For forward operation move the urls from Forward Stack to input Stack.',
                500
            );

            value = parseInt(value);
            while (value > 0) {
                if (forwardStack.isEmpty()) {
                    animatorModule.displayComment(
                        'Loop through the browser operations. <br><br><strong class="sv-comment-highlight-char">'+ browserOps[i] +'</strong><br><br>'
                        + 'For forward operation move the urls from Forward Stack to input Stack. <br>'
                        + 'No URLs to forward.',
                        1000
                    );
                    break;
                }
                stack.push(forwardStack.pop());
                value--;
            }
        }
    }

    animatorModule.displayComment(
        'The current active page: ' + stack.top(),
        500
    );
    animatorModule.displayOutput(stack.top());
    return stack.top();
}
                                        
class Stack {
    metaData = {
        'name': 'Stack',
        'description': '',
        'animation_duration': 1500,
    }

    constructor(initialData, metaData) {
        this.initialData = [...initialData];
        this.metaData = Object.assign({}, this.metaData, metaData);

        this.stackDisplayer = new StackDisplayer(initialData, this.metaData);
        this.stackId = this.stackDisplayer.display();
    }

    getStackData() {
        return this.initialData;
    }

    push(value) {
        this.initialData.push(value);

        // Perform the animation
        animatorModule.performPushAnimation(this.stackId, value);
    }

    pop() {
        if (this.initialData.length == 0) return;

        const value = this.initialData.pop();

        // Perform the animation
        animatorModule.performPopAnimation(this.stackId, value);

        return value;
    }

    top() {
        if (this.initialData.length == 0) return;

        const value = this.initialData[this.initialData.length - 1];

        return value;
    }

    isEmpty() {
        return this.initialData.length === 0;
    }
}
                                        
class StackDisplayer {
    constructor(initialData, metaData) {
        this.initialData = initialData;
        this.metaData = metaData;
    }

    display() {
        // Display stack on the screen
        const stackTemplate = document.getElementById('stack-template');
        const clone = stackTemplate.content.cloneNode(true);
        const stackCount = document.getElementsByClassName('stack-wrapper').length + 1;

        // Add an unique ID to the clone
        const stackWrapperId = 'stack-' + stackCount;
        const stackWrapper = clone.querySelector('.stack-wrapper');
        stackWrapper.id = stackWrapperId;

        // Add initial stack items
        const stackElement = clone.querySelector('.stack');
        while(this.initialData.length) {
            stackElement.insertAdjacentHTML(
                'beforeend',
                '<div class="stack-item">'+ this.initialData.pop() +'</div>'
            )
        }

        clone.querySelector('.stack-description h4')
             .textContent = this.metaData.name;
        clone.querySelector('.stack-description p')
             .textContent = this.metaData.description;

        document.getElementById('stack-visualizer')
                .appendChild(clone);

        return stackWrapperId;
    }
}
                                        
class AnimationList {
    animations = [];

    length() {
        return this.animations.length;
    }

    push(animation) {
        this.animations.push(animation);
    }

    shift() {
        return this.animations.shift();
    }
}

let animatorModule = (function() {
    let animations = new AnimationList();
    let animationsRunning = false;
    let animationSpeed = 1200;

    function getMoveDownAnimation(animation) {
        let topElement = animation.stackElement.children[0];

        let distance = animation.stackElement.offsetHeight;
        if (topElement) {
            distance = topElement.getBoundingClientRect().y
                        - animation.pushElement.getBoundingClientRect().y
                        - animation.pushElement.getBoundingClientRect().height
                        - 2; // Margin bottom
        }

        let moveDownAnimation = [
            '0',
            '0',
            '0',
            '0',
            '0',
            '0',
            '0',
            '0',
            '0',
            '0',
            '0',
            '0',
            (0.2 * distance) +  'px',
            (0.37 * distance) +  'px',
            (0.55 * distance) +  'px',
            (0.7 * distance) +  'px',
            (0.87 * distance) +  'px',
            distance  + 'px',
            distance  + 'px'
        ];

        return moveDownAnimation;
    }

    function getMoveUpAnimation(animation) {
        let topElement = animation.stackElement.children[0];
        let distance = topElement.getBoundingClientRect().y
                        - animation.pushElement.getBoundingClientRect().y;

        let moveUpAnimation = [
            (distance - 0.95 * distance) +  'px',
            (distance - 0.87 * distance) +  'px',
            (distance - 0.7 * distance) +  'px',
            (distance - 0.55 * distance) +  'px',
            (distance - 0.37 * distance) +  'px',
            (distance - 0.2 * distance) +  'px',
            distance + 'px',
            distance + 'px',
            distance + 'px',
            distance + 'px',
            distance + 'px',
            distance + 'px',
            distance + 'px'
        ];

        return moveUpAnimation;
    }

    function pushAnimate(animation) {
        animation.pushElement.textContent = animation.value;

        let pushAnimationKeyFrames = {
            // 25% - Show element
            opacity: ['0', '0.3', '0.7', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1'],
            left: ['0', '0', '0', '0', '7px', '20px', '35px', '60px', '75px', '90px', '100px', '100px', '100px', '100px', '100px', '100px', '100px', '100px', '100px'],
            top: getMoveDownAnimation(animation),
            offset: [0, 0.08, 0.16, 0.25, 0.25, 0.31, 0.37, 0.43, 0.5, 0.56, 0.62, 0.68, 0.73, 0.78, 0.83, 0.88, 0.93, 0.98, 1]
        };

        let duplicateElement = animation.pushElement.cloneNode(true);
        duplicateElement.classList.remove('hidden');

        // TODO: Increase the height of the stack before pushing

        let pushAnimation = animation.pushElement.animate(pushAnimationKeyFrames, animationSpeed);

        return new Promise((resolve) => {
            return pushAnimation.finished.then(() => {
                animation.stackElement.prepend(duplicateElement);
                resolve(`Push Animation completed!`);
            });
        })
    }

    function popAnimate(animation) {
        let popAnimationKeyFrames = {
            bottom: getMoveUpAnimation(animation),
            left: ['0', '0', '0', '0', '0', '0', '7px', '20px', '35px', '60px', '75px', '90px', '100px'],
            offset: [0, 0.07, 0.15, 0.22, 0.3, 0.37, 0.45, 0.52, 0.6, 0.67, 0.75, 0.82, 0.9, 1]
        };

        let topElement = animation.stackElement.children[0];

        let popAnimation = topElement.animate(popAnimationKeyFrames, animationSpeed);
        // The animation is not smooth
        // So remove the item before animation is completed
        setTimeout(() => {
            topElement.remove();
            animation.popElement.textContent = topElement.textContent;
        }, animationSpeed - 200);

        return new Promise((resolve) => {
            return popAnimation.finished.then(() => {
                // topElement.remove();
                // animation.popElement.textContent = topElement.textContent;
                resolve(`Pop Animation completed!`);
            });
        })
    }

    function displayCommentAnimate(animation) {
        return new Promise((resolve) => {
            document.getElementsByClassName('sv-comment')[0]
                    .innerHTML = animation.value;

            setTimeout(() => {
                resolve('Comment displayed!');
            }, animation.timeout);
        })
    }

    function displayOutputAnimate(animation) {
        return new Promise((resolve) => {
            let outputELement = document.getElementById('final-output');
            outputELement.innerHTML = animation.value;
            resolve('Output displayed!');
        })
    }

    function runSingleAnimation(animation) {
        switch (animation.type) {
            case 'push':
                return pushAnimate(animation);
                break;
            case 'pop':
                return popAnimate(animation);
                break;
            case 'display-comment':
                return displayCommentAnimate(animation);
                break;
            case 'display-output':
                return displayOutputAnimate(animation);
                break;
        }
    }

    function runAnimations() {
        if (animationsRunning) return;

        animationsRunning = true;
        // Perform the animations one after the other
        let animation = animations.shift();
        runSingleAnimation(animation)
            .then(() => {
                animationsRunning = false;
                if (animations.length()) {
                    runAnimations();
                }
            });
    }

    function getStackElements(stackId) {
        let stackWrapper = document.getElementById(stackId);
        return {
            stackElement: stackWrapper.getElementsByClassName('stack')[0],
            pushElement: stackWrapper.getElementsByClassName('push-element')[0],
            popElement: stackWrapper.getElementsByClassName('pop-element')[0]
        }
    }

    let performPushAnimation = function (stackId, value) {
        let animationObject = Object.assign(
                                {type: 'push', value: value},
                                getStackElements(stackId)
                            );
        animations.push(animationObject);

        runAnimations();
    }

    let performPopAnimation = function (stackId, value) {
        let animationObject = Object.assign(
                                {type: 'pop', value: value},
                                getStackElements(stackId)
                            );
        animations.push(animationObject);

        runAnimations();
    }

    /**
     * Set the animation duration.
     *
     * @param flot speed Duration in seconds (1, 2.5...)
     */
    let setAnimationSpeed = function (speed) {
        animationSpeed = speed * 1000;
    }

    let displayComment = function (comment, timeout = 0) {
        let animationObject = {
            type: 'display-comment',
            value: comment,
            timeout: timeout
        };

        animations.push(animationObject);
        runAnimations();
    }

    let displayOutput = function (output) {
        let animationObject = {
            type: 'display-output',
            value: output
        };

        animations.push(animationObject);
        runAnimations();
    }

    let clearAnimations = function () {
        animations = new AnimationList();
        animationsRunning = false;
    }

    return {
        performPushAnimation: performPushAnimation,
        performPopAnimation: performPopAnimation,
        setAnimationSpeed: setAnimationSpeed,
        displayComment: displayComment,
        displayOutput: displayOutput,
        clearAnimations: clearAnimations
    }
})();