Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
<html>
<head></head>
<body>
<script>
function isObject(o) {
return Object.prototype.toString.call(o) === "[object Object]";
}
function isArray(a) {
return Object.prototype.toString.call(a) === "[object Array]";
}
function isEmptyObject(o) {
return !Object.keys(o).length;
}
function getObjectIdValue(identify, target) {
let id = "";
if (isArray(identify)) {
id = findObjectValueByPath(target, identify);
} else {
// TODO: Check isString
id = target[identify];
}
return id;
}
function normalize(identify, data) {
const id2Value = {};
data.forEach(item => {
const idValue = getObjectIdValue(identify, item);
id2Value[idValue] = item;
});
return id2Value;
}
function traverseArray(
root,
excludedKeys,
target,
identify,
belongingId
) {
let id = belongingId ? belongingId : "";
if (!id) {
target.forEach(item => {
id = getObjectIdValue(identify, item);
traverseObject(root, id, excludedKeys, item);
});
}
}
function traverseObject(root, belongingId, excludedKeys, target) {
Object.keys(target).forEach(itemKey => {
if (
excludedKeys &&
excludedKeys.length &&
excludedKeys.includes(itemKey)
) {
return;
}
const itemValue = target[itemKey];
if (isObject(itemValue)) {
traverseObject(root, belongingId, (excludedKeys = []), itemValue);
} else if (isArray(itemValue)) {
traverseArray(
root,
(excludedKeys = []),
itemValue,
"",
belongingId
);
} else {
// debugger;
// 注意这里会把 Number 和 Boolean 类型也字符串化
const stringifiedValue = String(itemValue);
let tempRoot = root;
const arraiedAtringifiedValue = Array.from(stringifiedValue);
arraiedAtringifiedValue.forEach((character, characterIndex) => {
const reachEnd =
characterIndex === arraiedAtringifiedValue.length - 1;
if (!tempRoot.children[character]) {
tempRoot.children[character] = new Leaf(
reachEnd ? belongingId : "",
character
);
tempRoot = tempRoot.children[character];
} else {
if (reachEnd) {
tempRoot.children[character].share(belongingId);
}
tempRoot = tempRoot.children[character];
}
});
}
});
return root;
}
function findObjectValueByPath(target, paths) {
let value = target;
for (const path in paths) {
value = value[path];
}
return value;
}
class SearchTrieTree {
constructor({ identify = "id", excludedKeys = [], data = [] }) {
this.root = new Leaf();
this.id2value = normalize(identify, data);
traverseArray(this.root, excludedKeys, data, identify);
}
show() {
console.log(this.root);
}
search(keyword) {
const keywordArr = Array.from(String(keyword));
let point = this.root;
let result = [];
for (let i = 0; i < keywordArr.length; i++) {
const character = keywordArr[i];
if (!point.children[character]) {
break;
} else {
point = point.children[character];
}
if (keywordArr.length - 1 === i) {
result = point.ids;
}
}
return result.map(id => {
return this.id2value[id];
});
}
}
class Leaf {
constructor(id = "", value = "") {
this.ids = id ? [id] : [];
this.value = value;
this.children = {};
}
share(id) {
this.ids.push(id);
}
}
// const identify = ["login", "uuid"];
const identify = "id";
const excludedKeys = [];
const root = new Leaf();
let tree = null;
fetch("https://randomuser.me/api/")
// fetch("https://randomuser.me/api/?results=1000")
.then(response => {
return response.json();
})
.then(formattedResponse => {
// const { results } = formattedResponse;
results = [
{
id: "id1",
name: "liguangyi",
common: "common"
},
{
id: "id2",
name: "suna",
common: "common",
alias: "lig"
}
];
tree = new SearchTrieTree({
identify: "id",
data: results
});
tree.show();
// traverseArray(root, excludedKeys, results);
// console.log(root);
})
.catch(error => {
console.log(error);
});
</script>
</body>
</html>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.