Stacks Binary Trees

Simplify Absolute UNIX Path

Stacks
JavaScript

Problem:

You are given an absolute path for a Unix-style file system, which always begins with a slash ‘/’. Your task is to transform this absolute path into its simplified canonical path.

The Unix-style file system has following rules:

  • A single period ‘.’ represents the current directory.
  • A double period ‘..’ represents the previous/parent directory.
  • Multiple consecutive slashes such as ‘//’ and ‘///’ are treated as a single slash ‘/’.
  • Any sequence of periods that does not match the rules above should be treated as a valid directory or file name. For example, ‘…’ and ‘….’ are valid directory or file names.

The simplified canonical path should follow these rules:

  • The path must start with a single slash ‘/’.
  • Directories within the path must be separated by exactly one slash ‘/’.
  • The path must not end with a slash ‘/’, unless it is the root directory.
  • The path must not have any single or double periods (‘.’ and ‘..’) used to denote current or parent directories.

Example:

Input Path: ‘/home/’

Output (Simplified Path): ‘/home’

Input Path: ‘/home/user//Documents/../Pictures’

Output (Simplified Path): ‘/home/user/Pictures’

Input Path: ‘/…/a/../b/c/../d/./’

Output (Simplified Path): ‘/…/b/d’

Algorithm:

To solve this, we need to split the string at each forward slash (‘/’) and process each path segment individually. If we encounter ‘.’ or ‘..’, we skip the corresponding path segments.

Steps:

  1. Split the string at each forward slash (‘/’) and push each segment onto the stack.
  2. When processing the segments, if ‘.’ is encountered, skip it. If ‘..’ is encountered, pop the top element from the stack to move one level up in the path.
  3. After processing all segments, reconstruct the path by popping from the stack and joining the valid segments.

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:

Output:

   
solution.js
stack.js
stack-displayer.js
animator-module.js
function stackSolution(args) {
    let string = args[0];
    let paths = string.split('/');

    const stack = new Stack(
        [],
        {
            name: 'Stack',
            description: 'This stack holds the path segments.'
        }
    );

    animatorModule.displayComment('Push the individual path segments to the stack.');
    for (var i = 0; i < paths.length; i++) {
        if (paths[i] !== '') {
            stack.push(paths[i]);
        }
    }

    let simplifiedPath = '';
    let skipNextPath = false;
    while (! stack.isEmpty()) {
        if (skipNextPath) {
            animatorModule.displayComment('If ".." is encountered skip the next path.', 500);
        } else {
            animatorModule.displayComment(
                'Pop individual path segments and prepend them. <br><div class="sv-comment-highlight">'+ simplifiedPath +'</div>'
            );
        }
        path = stack.pop();

        if (path == '..') {
            skipNextPath = true;
        } else {
            if (path == '.') {
                animatorModule.displayComment('If "." is encountered ignore it.', 1500);
            }

            if (path !== '.' && ! skipNextPath) {
                // The first letter in simplifiedPath is '/'
                simplifiedPath = '/' + path + simplifiedPath;
            }

            animatorModule.displayOutput(simplifiedPath);
            skipNextPath = false;
        }
    }

    simplifiedPath = (simplifiedPath == '') ? '/' : simplifiedPath;

    animatorModule.displayComment('Final path: <br><div class="sv-comment-highlight">' + simplifiedPath + '<div>', 1000);
    animatorModule.displayOutput(simplifiedPath);
    animatorModule.displayComment('');
    return simplifiedPath;
}
                                        
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
    }
})();