// 字典
function Dict(elements) {
// 允許選擇性的初始對映表
this.elements = elements || {};
}
Dict.prototype.has = function (key) {
// 只有自有特性 (own property)
return {}.hasOwnProperty.call(this.elements, key);
};
Dict.prototype.get = function (key) {
// 只有自有特性
return this.has(key) ? this.elements[key] : undefined;
};
Dict.prototype.set = function (key, val) {
return this.elements[key] = val;
};
Dict.prototype.remove = function (key) {
delete this.elements[key];
};
// 任意挑選集合元素
Dict.prototype.pick = function () {
for (var key in this.elements) { // 這裡的elements是Member實體
if (this.has(key)) {
return key;
}
}
throw new Error("空的字典");
};
// 為了避免字典被汙染, 所以建立一個工作集, 把字典放在這個類別中, 用來追蹤目前集合中的元素項目
function WorkSet() {
this.entries = new Dict();
this.count = 0;
}
WorkSet.prototype.isEmpty = function () {
return this.count === 0;
};
WorkSet.prototype.add = function (key, val) {
if (this.entries.has(key)) {
return;
}
this.entries.set(key, val);
this.count++;
};
WorkSet.prototype.get = function (key) {
return this.entries.get(key);
};
WorkSet.prototype.remove = function (key) {
if (!this.entries.has(key)) {
return;
}
this.entries.remove(key);
this.count--;
};
WorkSet.prototype.pick = function () {
return this.entries.pick();
};
// 社交網路成員
function Member(name) {
this.name = name;
this.friends = [];
}
// 關聯朋友 方法1:用一個while迴圈來實作, 每次從集合中挑選出一個任意的元素, 並從work-set中移除
Member.prototype.inNetworkSet =
function (other) {
var visited = {};
var workset = new WorkSet();
workset.add(this.name, this); // 呼叫者的名子當 key, 用來先查找該呼叫者的朋友
while (!workset.isEmpty()) {
var name = workset.pick(); // 取出 key
var member = workset.get(name);
workset.remove(name);
if (name in visited) { // 不要重新訪問成員
continue;
}
visited[name] = member;
if (member === other) { // 找到成員
return true;
}
member.friends.forEach(function (friend) {
workset.add(friend.name, friend);
});
}
return false;
};
// 關聯朋友 方法2:將工作項目存到陣列中而非一個集合(set)中, 以完全相同的順序來巡訪社交網路路線
Member.prototype.inNetworkList
= function (other) {
var visited = {};
var worklist = [this];
while (worklist.length > 0) {
var member = worklist.pop();
if (member.name in visited) {// 不要重新訪問成員
continue;
}
visited[member.name] = member;
if (member === other) {
return true;
}
member.friends.forEach(function (friend) {
worklist.push(friend); // 加入工作清單
});
}
return false;
};
var a = new Member("Adm"),
b = new Member("Bob"),
c = new Member("Chris"),
d = new Member("David"),
e = new Member("Eason"),
f = new Member("Fiona");
a.friends.push(b);
b.friends.push(c);
c.friends.push(e);
d.friends.push(b);
e.friends.push(d, f); // a 和 f 關聯
console.log(a.inNetworkList(f));
