Skip to content

Instantly share code, notes, and snippets.

@lukebarton
Created March 20, 2018 17:47
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save lukebarton/8bb6e6014f92e00637fa9ad48076b678 to your computer and use it in GitHub Desktop.
Save lukebarton/8bb6e6014f92e00637fa9ad48076b678 to your computer and use it in GitHub Desktop.
If I were to make improvements, I'd sort out the interface and return values around the resolve and getConflicts functions - they could probably use new names too.
module.exports = {
makeRelationshipSet: () => ({
required: {},
conflicting: {}
}),
dependsOn: (package, requiredDependency, ruleSet) => {
initPackage(package, ruleSet);
initPackage(requiredDependency, ruleSet);
ruleSet.required[package].push(requiredDependency);
return ruleSet;
},
areExclusive: (package, conflictingDependency, ruleSet) => {
initPackage(package, ruleSet);
initPackage(conflictingDependency, ruleSet);
ruleSet.conflicting[package].push(conflictingDependency);
ruleSet.conflicting[conflictingDependency].push(package);
return ruleSet;
},
checkRelationships: (ruleSet) => {
return !getConflicts(Object.keys(ruleSet.required), ruleSet).some((conflicts) => conflicts.length > 0);
},
toggle: (set, package, ruleSet) => {
if (set[package]) {
} else {
const newSet = Object.keys(set).concat(resolve(package, ruleSet.required)).reduce((prev, curr) => {
prev[curr] = true;
return prev;
}, {});
// const newConflicts = getConflicts(Object.keys(set), ruleSet);
return newSet;
}
return set;
}
}
function getConflicts(set, ruleSet) {
const flatTrees = set.map((package) => resolve(package, ruleSet.required));
const conflicts = flatTrees.map((flatTree) => {
const conflictsOfTreeMembers = flatTree.reduce((prev, curr) => prev.concat(ruleSet.conflicting[curr]), []);
return flatTree.filter(function(n) {
return conflictsOfTreeMembers.indexOf(n) !== -1;
});
});
return conflicts;
}
function resolve(package, packageMap, visited = {}) {
var packages = [package];
packageMap[package].forEach((dependency) => {
if (!visited[dependency]) {
visited[dependency] = true;
packages = packages.concat(resolve(dependency, packageMap, visited));
}
});
return packages;
}
function initPackage(package, ruleSet) {
if (ruleSet.required[package] === undefined) {
ruleSet.required[package] = [];
ruleSet.conflicting[package] = [];
}
return ruleSet;
};
const { makeRelationshipSet, dependsOn, areExclusive, checkRelationships, toggle } = require('./dependencyChecker');
var s, selected;
s = makeRelationshipSet();
s = dependsOn('a', 'a', s);
console.assert(checkRelationships(s));
s = makeRelationshipSet();
s = dependsOn('a', 'b', s);
s = dependsOn('b', 'a', s);
console.assert(checkRelationships(s));
s = makeRelationshipSet();
s = dependsOn('a', 'b', s);
s = areExclusive('a', 'b', s);
console.assert(!checkRelationships(s));
s = makeRelationshipSet();
s = dependsOn('a', 'b', s);
s = dependsOn('b', 'c', s);
s = areExclusive('a', 'c', s);
console.assert(!checkRelationships(s));
s = makeRelationshipSet();
s = dependsOn('a', 'b', s);
s = dependsOn('b', 'c', s);
s = dependsOn('c', 'a', s);
s = dependsOn('d', 'e', s);
s = areExclusive('c', 'e', s);
console.assert(checkRelationships(s));
// This function takes some arguments and returns a set of selected options.
// If needed, you should replace it with your own data structure.
function set() {
var l = {};
for (var i in arguments) {
l[arguments[i]] = true;
}
return l;
}
// This function returns whether two sets of selected options have the same options selected.
// If needed, you should reimplement it for your own data structure.
function setsEqual(a, b) {
var ka = Object.keys(a).sort();
var kb = Object.keys(b).sort();
if (ka.length != kb.length) {
return false;
}
for (var i in ka) {
if (kb[i] != ka[i]) {
return false;
}
}
return true;
}
selected = set(); // Or list, array, etc.
selected = toggle(selected, 'a', s);
console.assert(setsEqual(selected, set('a', 'c', 'b')));
s = dependsOn('f', 'f', s);
selected = toggle(selected, 'f', s);
console.assert(setsEqual(selected, set('a', 'c', 'b', 'f')));
selected = toggle(selected, 'e', s);
console.assert(setsEqual(selected, set('e', 'f')));
selected = toggle(selected, 'b', s);
console.assert(setsEqual(selected, set('a', 'c', 'b', 'f')));
s = dependsOn('b', 'g', s);
selected = toggle(selected, 'g', s);
selected = toggle(selected, 'b', s);
console.assert(setsEqual(selected, set('g', 'f')));
s = makeRelationshipSet();
s = dependsOn('a', 'b', s);
s = dependsOn('b', 'c', s);
selected = set();
selected = toggle(selected, 'c', s);
console.assert(setsEqual(selected, set('c')));
// Deep dependencies
s = makeRelationshipSet();
s = dependsOn('a', 'b', s);
s = dependsOn('b', 'c', s);
s = dependsOn('c', 'd', s);
s = dependsOn('d', 'e', s);
s = dependsOn('a', 'f', s);
s = areExclusive('e', 'f', s);
console.assert(!checkRelationships(s));
// Multiple dependencies and exclusions.
s = makeRelationshipSet();
s = dependsOn('a', 'b', s);
s = dependsOn('a', 'c', s);
s = areExclusive('b', 'd', s);
s = areExclusive('b', 'e', s);
console.assert(checkRelationships(s));
selected = set();
selected = toggle(selected, 'd', s);
selected = toggle(selected, 'e', s);
selected = toggle(selected, 'a', s);
console.assert(setsEqual(selected, set('a', 'c', 'b')));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment