JavaScript - Sets(LinkedList)

Data Structures and Algorithms With Javascript
(O'Reilly Media)
Michael McMillan(著)

開発環境

• OS X Yosemite - Apple (OS)
• Emacs (Text Editor)
• JavaScript (プログラミング言語)
• SpiderMonkey, Node.js(V8) (JavaScript engine)

Data Structures and Algorithms With Javascript (Michael McMillan(著)、O'Reilly Media)のChapter 9(Sets)、Exercises 2.(No. 5683)を解いてみる。

Exercises 2.(No. 5683)

JavaScript(Emacs)

/*jslint         browser : true, continue : true,
  devel  : true, indent  : 4,    maxerr   : 50,
  newcap : true, nomen   : true, plusplus : false,
  regexp : true, sloppy  : true, vars     : false,
  white  : true
*/

/*global print */
var Set,
    Node,
    LinkedList,
    set;

Node = function (element) {
    this.element = element;
    this.next = null;
};
LinkedList = function () {
    this.head = new Node('head');
    this.size = 0;
};
LinkedList.prototype = {
    constructor: LinkedList,
    find: function (item) {
        var curr_node = this.head;
        
        while (curr_node !== null && curr_node.element !== item) {
            curr_node = curr_node.next;
        }
        return curr_node;
    },
    insert: function (new_element, item) {
        var new_node = new Node(new_element),
            current = this.find(item);

        new_node.next = current.next;
        current.next = new_node;
    },
    display: function () {
        var curr_node = this.head;
        while (curr_node.next !== null) {
            print(curr_node.next.element);
            curr_node = curr_node.next;
        }
    },
    findPrevious : function (item) {
        var curr_node = this.head;
        while (curr_node !== null && curr_node.next.element !== item) {
            curr_node = curr_node.next;
        }
        return curr_node;
    },
    remove : function (item) {
        var prev_node = this.findPrevious(item);
        
        if (prev_node.next !== null) {
            prev_node.next = prev_node.next.next;
        }
    }
};

Set = function () {
    this.data_store = new LinkedList();
};
Set.prototype = {
    constructor : Set,
    add : function (data) {
        if (this.data_store.find(data) === null) {
            this.data_store.insert(data, "head");
            this.data_store.size += 1;
            return true;
        }
        return false;
    },
    remove : function (data) {
        var pos = this.data_store.find(data);
        if (pos !== null) {
            this.data_store.remove(data);
            this.data_store.size -= 1;
            return true;
        }
        return false;
    },
    size : function () {
        return this.data_store.size;
    },
    contains: function (data) {
        return this.data_store.ifind(data) !== null ? true : false;
    },
    union : function (set) {
        var temp_set = new Set(),
            elem = this.data_store.head.next,
            elem1;

        while (elem !== null) {
            temp_set.add(elem);
            elem = elem.next;
        }
        elem1 = set.data_store.head.next;
        while (elem1 !== null) {
            if (!temp_set.contains(elem1)) {
                temp_set.add(elem1);
            }
            elem1 = elem1.next;
        }
        return temp_set;
    },
    intersect: function (set) {
        var temp_set = new Set(),
            elem = this.data_store.head.next;

        while (elem !== null) {
            if (set.contains(elem)) {
                temp_set.add(elem);
            }
            elem = elem.next;
        }
        return temp_set;
    },
    subset: function (set) {
        var elem;
        if (this.size() > set.size()) {
            return false;
        }
        elem = this.data_store.head.next;
        while (elem !== null) {
            if (!set.contains(elem)) {
                return false;
            }
        }
        return true;
    },
    difference: function (set) {
        var temp_set = new Set(),
            elem = this.data_store.head.next;

        while (elem !== null) {
            if (!set.contains(elem)) {
                temp_set.add(elem);
            }
            elem = elem.next;
        }
        return temp_set;            
    },
    show: function () {
        return this.data_store.display();
    }
};

set = new Set();
set.add("Clayton");
set.add("Jennifer");
set.add("Danny");
set.add("Bryan");
set.add("Clayton");

set.show();

出力結果(Terminal, shell, SpiderMonkey)

$ jslint sample2.js

sample2.js is OK.
$ js sample2.js
Bryan
Danny
Jennifer
Clayton
$