Skip to content

Instantly share code, notes, and snippets.

@pvdz

pvdz/build.js

Last active December 9, 2016 11:08
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 pvdz/7307e414c5414b26b4f72b2b77b1ee30 to your computer and use it in GitHub Desktop.
Save pvdz/7307e414c5414b26b4f72b2b77b1ee30 to your computer and use it in GitHub Desktop.
Download ZIP
failing babili on this finitedomain build at bbc7aeecd2b1fee7409d8ddd46e8f78091bcaaaf (grunt distq, ./node_modules/.bin/babili build/finitedomain.es6.concat.js -o foo.js)
Raw
build.js
let Solver = (function(){
// from: src/config.js
/**
* @returns {$config}
*/
function config_create() {
let config = {
_class: '$config',
// names of all vars in this search tree
allVarNames: [],
// doing `indexOf` for 5000+ names is _not_ fast. so use a trie
_varNamesTrie: trie_create(),
varStratConfig: config_createVarStratConfig(),
valueStratName: 'min',
targetedVars: 'all',
varDistOptions: {},
timeoutCallback: undefined,
// this is for the rng stuff in this library. in due time all calls
// should happen through this function. and it should be initialized
// with the rngCode string for exportability. this would be required
// for webworkers and DSL imports which can't have functions. tests
// can initialize it to something static, prod can use a seeded rng.
rngCode: '', // string. Function(rngCode) should return a callable rng
_defaultRng: undefined, // Function. if not exist at init time it'll be `rngCode ? Function(rngCode) : Math.random`
// the propagators are generated from the constraints when a space
// is created from this config. constraints are more higher level.
allConstraints: [],
constantCache: {}, // <value:varIndex>, generally anonymous vars but pretty much first come first serve
initialDomains: [], // $nordom[] : initial domains for each var, maps 1:1 to allVarNames
_propagators: [], // initialized later
_varToPropagators: [], // initialized later
_constrainedAway: [], // list of var names that were constrained but whose constraint was optimized away. they will still be "targeted" if target is all. TODO: fix all tests that depend on this and eliminate this. it is a hack.
_constraintHash: {}, // every constraint is logged here (note: for results only the actual constraints are stored). if it has a result, the value is the result var _name_. otherwise just `true` if it exists and `false` if it was optimized away.
};
return config;
}
function config_clone(config, newDomains) {
let {
varStratConfig,
valueStratName,
targetedVars,
varDistOptions,
timeoutCallback,
constantCache,
allVarNames,
allConstraints,
initialDomains,
_propagators,
_varToPropagators,
_constrainedAway,
} = config;
let clone = {
_class: '$config',
_varNamesTrie: trie_create(allVarNames), // just create a new trie with (should be) the same names
varStratConfig,
valueStratName,
targetedVars: targetedVars instanceof Array ? targetedVars.slice(0) : targetedVars,
varDistOptions: JSON.parse(JSON.stringify(varDistOptions)), // TOFIX: clone this more efficiently
timeoutCallback, // by reference because it's a function if passed on...
rngCode: config.rngCode,
_defaultRng: config.rngCode ? undefined : config._defaultRng,
constantCache, // is by reference ok?
allVarNames: allVarNames.slice(0),
allConstraints: allConstraints.slice(0),
initialDomains: newDomains ? newDomains.map(domain_toSmallest) : initialDomains, // <varName:domain>
_propagators: _propagators && _propagators.slice(0), // in case it is initialized
_varToPropagators: _varToPropagators && _varToPropagators.slice(0), // inited elsewhere
_constrainedAway: _constrainedAway && _constrainedAway.slice(0), // list of var names that were constrained but whose constraint was optimized away. they will still be "targeted" if target is all. TODO: fix all tests that depend on this and eliminate this. it is a hack.
// not sure what to do with this in the clone...
_constraintHash: {},
};
return clone;
}
/**
* Add an anonymous var with max allowed range
*
* @param {$config} config
* @returns {number} varIndex
*/
function config_addVarAnonNothing(config) {
return config_addVarNothing(config, true);
}
/**
* @param {$config} config
* @param {string|boolean} varName (If true, is anonymous)
* @returns {number} varIndex
*/
function config_addVarNothing(config, varName) {
return _config_addVar(config, varName, domain_createRange(SUB, SUP));
}
/**
* @param {$config} config
* @param {number} lo
* @param {number} hi
* @returns {number} varIndex
*/
function config_addVarAnonRange(config, lo, hi) {
if (lo === hi) return config_addVarAnonConstant(config, lo);
return config_addVarRange(config, true, lo, hi);
}
/**
* @param {$config} config
* @param {string|boolean} varName (If true, is anonymous)
* @param {number} lo
* @param {number} hi
* @returns {number} varIndex
*/
function config_addVarRange(config, varName, lo, hi) {
let domain = domain_createRange(lo, hi);
return _config_addVar(config, varName, domain);
}
/**
* @param {$config} config
* @param {string|boolean} varName (If true, anon)
* @param {$arrdom} domain Small domain format not allowed here. this func is intended to be called from Solver, which only accepts arrdoms
* @returns {number} varIndex
*/
function config_addVarDomain(config, varName, domain, _allowEmpty) {
return _config_addVar(config, varName, domain_anyToSmallest(domain), _allowEmpty);
}
/**
* @param {$config} config
* @param {number} value
* @returns {number} varIndex
*/
function config_addVarAnonConstant(config, value) {
if (config.constantCache[value] !== undefined) {
return config.constantCache[value];
}
return config_addVarConstant(config, true, value);
}
/**
* @param {$config} config
* @param {string|boolean} varName (True means anon)
* @param {number} value
* @returns {number} varIndex
*/
function config_addVarConstant(config, varName, value) {
let domain = domain_createRange(value, value);
return _config_addVar(config, varName, domain);
}
/**
* @param {$config} config
* @param {string|true} varName If true, the varname will be the same as the index it gets on allVarNames
* @param {$nordom} domain
* @returns {number} varIndex
*/
function _config_addVar(config, varName, domain, _allowEmpty) {
let allVarNames = config.allVarNames;
let varIndex = allVarNames.length;
if (varName === true) {
varName = '__' + String(varIndex) + '__';
} else {
if (typeof varName !== 'string') THROW('Var names should be a string or anonymous, was: ' + JSON.stringify(varName));
if (!varName) THROW('Var name cannot be empty string');
if (String(parseInt(varName, 10)) === varName) THROW('Don\'t use numbers as var names (' + varName + ')');
}
// note: 100 is an arbitrary number but since large sets are probably
// automated it's very unlikely we'll need this check in those cases
if (varIndex < 100) {
if (trie_has(config._varNamesTrie, varName)) THROW('Var name already part of this config. Probably a bug?', varName);
}
let solvedTo = domain_getValue(domain);
if (solvedTo !== NOT_FOUND && !config.constantCache[solvedTo]) config.constantCache[solvedTo] = varIndex;
config.initialDomains[varIndex] = domain;
config.allVarNames.push(varName);
trie_add(config._varNamesTrie, varName, varIndex);
return varIndex;
}
/**
* Initialize the config of this space according to certain presets
*
* @param {$config} config
* @param {string} varName
*/
function config_setDefaults(config, varName) {
let defs = distribution_getDefaults(varName);
for (let key in defs) config_setOption(config, key, defs[key]);
}
/**
* Create a config object for the var distribution
*
* @param {Object} obj
* @property {string} [obj.type] Map to the internal names for var distribution strategies
* @property {string} [obj.priorityList] An ordered list of var names to prioritize. Names not in the list go implicitly and unordered last.
* @property {boolean} [obj.inverted] Should the list be interpreted inverted? Unmentioned names still go last, regardless.
* @property {Object} [obj.fallback] Same struct as obj. If current strategy is inconclusive it can fallback to another strategy.
* @returns {$var_strat_config}
*/
function config_createVarStratConfig(obj) {
/**
* @typedef {$var_strat_config}
*/
return {
_class: '$var_strat_config',
type: (obj && obj.type) || 'naive',
priorityByName: obj && obj.priorityList,
_priorityByIndex: undefined,
inverted: !!(obj && obj.inverted),
fallback: obj && obj.fallback,
};
}
/**
* Configure an option for the solver
*
* @param {$config} config
* @param {string} optionName
* @param {*} optionValue
* @param {string} [optionTarget] For certain options, this is the target var name
*/
function config_setOption(config, optionName, optionValue, optionTarget) {
if (optionName === 'varStratOverride') {
THROW('deprecated, should be wiped internally');
}
switch (optionName) {
case 'varStrategy':
if (typeof optionValue === 'function') THROW('functions no longer supported', optionValue);
if (typeof optionValue === 'string') THROW('strings should be passed on as {type:value}', optionValue);
if (typeof optionValue !== 'object') THROW('varStrategy should be object', optionValue);
if (optionValue.name) THROW('name should be type');
if (optionValue.dist_name) THROW('dist_name should be type');
let vsc = config_createVarStratConfig(optionValue);
config.varStratConfig = vsc;
while (vsc.fallback) {
vsc.fallback = config_createVarStratConfig(vsc.fallback);
vsc = vsc.fallback;
}
break;
case 'valueStrategy':
// determine how the next value of a variable is picked when creating a new space
config.valueStratName = optionValue;
break;
case 'targeted_var_names':
if (!optionValue || !optionValue.length) THROW('ONLY_USE_WITH_SOME_TARGET_VARS'); // omit otherwise to target all
// which vars must be solved for this space to be solved
// string: 'all'
// string[]: list of vars that must be solved
// function: callback to return list of names to be solved
config.targetedVars = optionValue;
break;
case 'varStratOverrides':
// An object which defines a value distributor per variable
// which overrides the globally set value distributor.
// See Bvar#distributeOptions (in multiverse)
for (let key in optionValue) {
config_setOption(config, 'varValueStrat', optionValue[key], key);
}
break;
case 'varValueStrat':
// override all the specific strategy parameters for one variable
if (!config.varDistOptions) config.varDistOptions = {};
config.varDistOptions[optionTarget] = optionValue;
if (optionValue.valtype === 'markov') {
let matrix = optionValue.matrix;
if (!matrix) {
if (optionValue.expandVectorsWith) {
matrix = optionValue.matrix = [{vector: []}];
} else {
THROW('Solver: markov var missing distribution (needs matrix or expandVectorsWith)');
}
}
for (let i = 0, n = matrix.length; i < n; ++i) {
let row = matrix[i];
if (row.boolean) THROW('row.boolean was deprecated in favor of row.boolVarName');
if (row.booleanId !== undefined) THROW('row.booleanId is no longer used, please use row.boolVarName');
let boolFuncOrName = row.boolVarName;
if (typeof boolFuncOrName === 'function') {
boolFuncOrName = boolFuncOrName(optionValue);
}
if (boolFuncOrName) {
if (typeof boolFuncOrName !== 'string') {
THROW('row.boolVarName, if it exists, should be the name of a var or a func that returns that name, was/got: ' + boolFuncOrName + ' (' + typeof boolFuncOrName + ')');
}
// store the var index
row._boolVarIndex = trie_get(config._varNamesTrie, boolFuncOrName);
}
}
}
break;
case 'timeoutCallback':
// A function that returns true if the current search should stop
// Can be called multiple times after the search is stopped, should
// keep returning false (or assume an uncertain outcome).
// The function is called after the first batch of propagators is
// called so it won't immediately stop. But it stops quickly.
config.timeoutCallback = optionValue;
break;
case 'var': return THROW('REMOVED. Replace `var` with `varStrategy`');
case 'val': return THROW('REMOVED. Replace `var` with `valueStrategy`');
case 'rng':
// sets the default rng for this solve. a string should be raw js
// code, number will be a static return value, a function is used
// as is. the resulting function should return a value `0<=v<1`
if (typeof optionValue === 'string') {
config.rngCode = optionValue;
} else if (typeof optionValue === 'number') {
config.rngCode = 'return ' + optionValue + ';'; // dont use arrow function. i dont think this passes through babel.
} else {
config._defaultRng = optionValue;
}
break;
default: THROW('unknown option');
}
}
/**
* This function should be removed once we can update mv
*
* @deprecated in favor of config_setOption
* @param {$config} config
* @param {Object} options
* @property {Object} [options.varStrategy]
* @property {string} [options.varStrategy.name]
* @property {string[]} [options.varStrategy.list] Only if name=list
* @property {string[]} [options.varStrategy.priorityList] Only if name=list
* @property {boolean} [options.varStrategy.inverted] Only if name=list
* @property {Object} [options.varStrategy.fallback] Same struct as options.varStrategy (recursive)
*/
function config_setOptions(config, options) {
if (!options) return;
if (options.varStrategy) config_setOption(config, 'varStrategy', options.varStrategy);
if (options.valueStrategy) config_setOption(config, 'valueStrategy', options.valueStrategy);
if (options.targeted_var_names) config_setOption(config, 'targeted_var_names', options.targeted_var_names);
if (options.varStratOverrides) config_setOption(config, 'varStratOverrides', options.varStratOverrides);
if (options.varStratOverride) {
console.warn('deprecated "varStratOverride" in favor of "varValueStrat"');
config_setOption(config, 'varValueStrat', options.varStratOverride, options.varStratOverrideName);
}
if (options.varValueStrat) config_setOption(config, 'varValueStrat', options.varValueStrat, options.varStratOverrideName);
if (options.timeoutCallback) config_setOption(config, 'timeoutCallback', options.timeoutCallback);
}
/**
* @param {$config} config
* @param {$propagator} propagator
*/
function config_addPropagator(config, propagator) {
config._propagators.push(propagator);
}
/**
* Creates a mapping from a varIndex to a set of propagatorIndexes
* These propagators are the ones that use the varIndex
* This is useful for quickly determining which propagators
* need to be stepped while propagating them.
*
* @param {$config} config
*/
function config_populateVarPropHash(config) {
let hash = new Array(config.allVarNames.length);
let propagators = config._propagators;
let initialDomains = config.initialDomains;
for (let propagatorIndex = 0, plen = propagators.length; propagatorIndex < plen; ++propagatorIndex) {
let propagator = propagators[propagatorIndex];
_config_addVarConditionally(propagator.index1, initialDomains, hash, propagatorIndex);
if (propagator.index2 >= 0) _config_addVarConditionally(propagator.index2, initialDomains, hash, propagatorIndex);
if (propagator.index3 >= 0) _config_addVarConditionally(propagator.index3, initialDomains, hash, propagatorIndex);
}
config._varToPropagators = hash;
}
function _config_addVarConditionally(varIndex, initialDomains, hash, propagatorIndex) {
// (at some point this could be a strings, or array, or whatever)
// dont bother adding props on unsolved vars because they can't affect
// anything anymore. seems to prevent about 10% in our case so worth it.
let domain = initialDomains[varIndex];
if (!domain_isSolved(domain)) {
if (!hash[varIndex]) hash[varIndex] = [propagatorIndex];
else if (hash[varIndex].indexOf(propagatorIndex) < 0) hash[varIndex].push(propagatorIndex);
}
}
/**
* Create a constraint. If the constraint has a result var it
* will return (only) the variable name that ends up being
* used (anonymous or not).
*
* In some edge cases the constraint can be resolved immediately.
* There are two ways a constraint can resolve: solved or reject.
* A solved constraint is omitted and if there is a result var it
* will become a constant that is set to the outcome of the
* constraint. If rejected the constraint will still be added and
* will immediately reject the search once it starts.
*
* Due to constant optimization and mapping the result var name
* may differ from the input var name. In that case both names
* should map to the same var index internally. Only constraints
* with a result var have a return value here.
*
* @param {$config} config
* @param {string} name Type of constraint (hardcoded values)
* @param {string[]} varNames All the argument var names for target constraint
* @param {string} [param] The result var name for certain. With reifiers param is the actual constraint to reflect.
* @returns {string|undefined} Actual result vars only, undefined otherwise. See desc above.
*/
function config_addConstraint(config, name, varNames, param) {
// should return a new var name for most props
let inputConstraintKeyOp = name;
let resultVarName;
let forceBool = false;
switch (name) { /* eslint no-fallthrough: "off" */
case 'reifier':
forceBool = true;
inputConstraintKeyOp = param;
// fall-through
case 'plus':
case 'min':
case 'ring-mul':
case 'ring-div':
case 'mul':
// fall-through
case 'sum':
case 'product': {
let sumOrProduct = name === 'product' || name === 'sum';
if (sumOrProduct && varNames.length === 0) {
// no variables means the sum/product is zero. not sure about the product though. nothing times nothing = 0?
return config.allVarNames[config_addVarAnonConstant(config, 0)];
}
resultVarName = sumOrProduct ? param : varNames[2];
let resultVarIndex;
if (resultVarName === undefined) {
if (forceBool) resultVarIndex = config_addVarAnonRange(config, 0, 1);
else resultVarIndex = config_addVarAnonNothing(config);
resultVarName = config.allVarNames[resultVarIndex];
} else if (typeof resultVarName === 'number') {
resultVarIndex = config_addVarAnonConstant(config, resultVarName);
resultVarName = config.allVarNames[resultVarIndex];
} else if (typeof resultVarName !== 'string') {
THROW(`expecting result var name to be absent or a number or string: \`${resultVarName}\``);
} else {
resultVarIndex = trie_get(config._varNamesTrie, resultVarName);
if (resultVarIndex < 0) THROW('Vars must be defined before using them (' + resultVarName + ')');
}
if (sumOrProduct) param = resultVarIndex;
else varNames[2] = resultVarName;
break;
}
case 'distinct':
case 'eq':
case 'neq':
case 'lt':
case 'lte':
case 'gt':
case 'gte':
break;
default:
THROW(`UNKNOWN_PROPAGATOR ${name}`);
}
// note: if param is a var constant then that case is already resolved above
config_compileConstants(config, varNames);
if (config_dedupeConstraint(config, inputConstraintKeyOp + '|' + varNames.join(','), resultVarName)) return resultVarName;
let varIndexes = config_varNamesToIndexes(config, varNames);
if (!config_solvedAtCompileTime(config, name, varIndexes, param)) {
let constraint = constraint_create(name, varIndexes, param);
config.allConstraints.push(constraint);
}
return resultVarName;
}
/**
* Go through the list of var names and create an anonymous var for
* each value that is actually a number rather than a string.
* Replaces the values inline.
*
* @param {$config} config
* @param {string|number} varNames
*/
function config_compileConstants(config, varNames) {
for (let i = 0, n = varNames.length; i < n; ++i) {
if (typeof varNames[i] === 'number') {
let varIndex = config_addVarAnonConstant(config, varNames[i]);
varNames[i] = config.allVarNames[varIndex];
}
}
}
/**
* Convert a list of var names to a list of their indexes
*
* @param {$config} config
* @param {string[]} varNames
* @returns {number[]}
*/
function config_varNamesToIndexes(config, varNames) {
let varIndexes = [];
for (let i = 0, n = varNames.length; i < n; ++i) {
let varName = varNames[i];
let varIndex = trie_get(config._varNamesTrie, varName);
varIndexes[i] = varIndex;
}
return varIndexes;
}
/**
* Check whether we already know a given constraint (represented by a unique string).
* If we don't, add the string to the cache with the expected result name, if any.
*
* @param config
* @param constraintUI
* @param resultVarName
* @returns {boolean}
*/
function config_dedupeConstraint(config, constraintUI, resultVarName) {
if (!config._constraintHash) config._constraintHash = {}; // can happen for imported configs that are extended or smt
let haveConstraint = config._constraintHash[constraintUI];
if (haveConstraint === true) {
if (resultVarName !== undefined) {
throw new Error('How is this possible?'); // either a constraint-with-value gets a result var, or it's a constraint-sans-value
}
return true;
}
if (haveConstraint !== undefined) {
// the constraint exists and had a result. map that result to this result for equivalent results.
config_addConstraint(config, 'eq', [resultVarName, haveConstraint]); // _could_ also be optimized away ;)
return true;
}
config._constraintHash[constraintUI] = resultVarName || true;
return false;
}
/**
* If either side of certain constraints are solved at compile time, which
* is right now, then the constraint should not be recorded at all because
* it will never "unsolve". This can cause vars to become rejected before
* the search even begins and that is okay.
*
* @param {$config} config
* @param {string} constraintName
* @param {number[]} varIndexes
* @param {*} [param] The extra parameter for constraints
* @returns {boolean}
*/
function config_solvedAtCompileTime(config, constraintName, varIndexes, param) {
if (constraintName === 'lte' || constraintName === 'lt') {
return _config_solvedAtCompileTimeLtLte(config, constraintName, varIndexes);
} else if (constraintName === 'gte' || constraintName === 'gt') {
return _config_solvedAtCompileTimeGtGte(config, constraintName, varIndexes);
} else if (constraintName === 'eq') {
return _config_solvedAtCompileTimeEq(config, constraintName, varIndexes);
} else if (constraintName === 'neq') {
return _config_solvedAtCompileTimeNeq(config, constraintName, varIndexes);
} else if (constraintName === 'reifier') {
return _config_solvedAtCompileTimeReifier(config, constraintName, varIndexes, param);
} else if (constraintName === 'sum') {
if (!varIndexes.length) return true;
return _config_solvedAtCompileTimeSumProduct(config, constraintName, varIndexes, param);
} else if (constraintName === 'product') {
return _config_solvedAtCompileTimeSumProduct(config, constraintName, varIndexes, param);
}
return false;
}
function _config_solvedAtCompileTimeLtLte(config, constraintName, varIndexes) {
let initialDomains = config.initialDomains;
let varIndexLeft = varIndexes[0];
let varIndexRight = varIndexes[1];
let domainLeft = initialDomains[varIndexLeft];
let domainRight = initialDomains[varIndexRight];
let v = domain_getValue(domainLeft);
if (v !== NO_SUCH_VALUE) {
let targetValue = v - (constraintName === 'lt' ? 0 : 1);
initialDomains[varIndexRight] = domain_removeLte(domainRight, targetValue);
// do not add constraint; this constraint is already solved
config._constrainedAway.push(varIndexLeft, varIndexRight);
return true;
}
v = domain_getValue(domainRight);
if (v !== NO_SUCH_VALUE) {
let targetValue = v + (constraintName === 'lt' ? 0 : 1);
initialDomains[varIndexLeft] = domain_removeGte(domainLeft, targetValue);
// do not add constraint; this constraint is already solved
config._constrainedAway.push(varIndexLeft, varIndexRight);
return true;
}
let targetGte = domain_max(domainRight) + (constraintName === 'lt' ? 0 : 1);
let newLeft = initialDomains[varIndexLeft] = domain_removeGte(domainLeft, targetGte);
let targetLte = domain_min(domainLeft) - (constraintName === 'lt' ? 0 : 1);
let newRight = initialDomains[varIndexRight] = domain_removeLte(domainRight, targetLte);
if (domainLeft !== newLeft || domainRight !== newRight) return _config_solvedAtCompileTimeLtLte(config, constraintName, varIndexes);
return false;
}
function _config_solvedAtCompileTimeGtGte(config, constraintName, varIndexes) {
let initialDomains = config.initialDomains;
let varIndexLeft = varIndexes[0];
let varIndexRight = varIndexes[1];
let domainLeft = initialDomains[varIndexLeft];
let domainRight = initialDomains[varIndexRight];
let v = domain_getValue(domainLeft);
if (v !== NO_SUCH_VALUE) {
let targetValue = v + (constraintName === 'gt' ? 0 : 1);
initialDomains[varIndexRight] = domain_removeGte(domainRight, targetValue, true);
// do not add constraint; this constraint is already solved
config._constrainedAway.push(varIndexLeft, varIndexRight);
return true;
}
v = domain_getValue(domainRight);
if (v !== NO_SUCH_VALUE) {
let targetValue = v - (constraintName === 'gt' ? 0 : 1);
initialDomains[varIndexLeft] = domain_removeLte(domainLeft, targetValue);
// do not add constraint; this constraint is already solved
config._constrainedAway.push(varIndexLeft, varIndexRight);
return true;
}
// A > B or A >= B. smallest number in A must be larger than the smallest number in B. largest number in B must be smaller than smallest number in A
let targetLte = domain_min(domainRight) - (constraintName === 'gt' ? 0 : 1);
let newLeft = initialDomains[varIndexLeft] = domain_removeLte(domainLeft, targetLte);
let targetGte = domain_max(domainLeft) + (constraintName === 'gt' ? 0 : 1);
let newRight = initialDomains[varIndexRight] = domain_removeGte(domainRight, targetGte);
// if the domains changed there's a chance this propagator is now removable
if (domainLeft !== newLeft || domainRight !== newRight) return _config_solvedAtCompileTimeGtGte(config, constraintName, varIndexes);
return false;
}
function _config_solvedAtCompileTimeEq(config, constraintName, varIndexes) {
let initialDomains = config.initialDomains;
let varIndexLeft = varIndexes[0];
let varIndexRight = varIndexes[1];
let a = initialDomains[varIndexLeft];
let b = initialDomains[varIndexRight];
let v = domain_getValue(a);
if (v === NO_SUCH_VALUE) v = domain_getValue(b);
if (v !== NO_SUCH_VALUE) {
let r = domain_intersection(a, b);
initialDomains[varIndexLeft] = r;
initialDomains[varIndexRight] = r;
config._constrainedAway.push(varIndexLeft, varIndexRight);
return true;
}
return false;
}
function _config_solvedAtCompileTimeNeq(config, constraintName, varIndexes) {
let initialDomains = config.initialDomains;
let varIndexLeft = varIndexes[0];
let varIndexRight = varIndexes[1];
let v = domain_getValue(initialDomains[varIndexLeft]);
if (v !== NO_SUCH_VALUE) {
initialDomains[varIndexRight] = domain_removeValue(initialDomains[varIndexRight], v);
config._constrainedAway.push(varIndexLeft, varIndexRight);
return true;
}
v = domain_getValue(initialDomains[varIndexRight]);
if (v !== NO_SUCH_VALUE) {
initialDomains[varIndexLeft] = domain_removeValue(initialDomains[varIndexLeft], v);
config._constrainedAway.push(varIndexLeft, varIndexRight);
return true;
}
return false;
}
function _config_solvedAtCompileTimeReifier(config, constraintName, varIndexes, opName) {
let initialDomains = config.initialDomains;
let varIndexLeft = varIndexes[0];
let varIndexRight = varIndexes[1];
let varIndexResult = varIndexes[2];
let domain1 = initialDomains[varIndexLeft];
let domain2 = initialDomains[varIndexRight];
let domain3 = initialDomains[varIndexResult];
domain3 = initialDomains[varIndexResult] = domain_removeGte(domain3, 2); // result domains are bool. just cut away the rest.
let v1 = domain_getValue(initialDomains[varIndexLeft]);
let v2 = domain_getValue(initialDomains[varIndexRight]);
let hasLeft = v1 !== NO_SUCH_VALUE;
let hasRight = v2 !== NO_SUCH_VALUE;
if (hasLeft && hasRight) { // just left or right would not force anything. but both does.
return _config_solvedAtCompileTimeReifierBoth(config, varIndexes, opName, v1, v2);
}
let v3 = domain_getValue(domain3);
let hasResult = v3 !== NO_SUCH_VALUE;
if (hasResult) {
if (hasLeft) {
// resolve right and eliminate reifier
return _config_solvedAtCompileTimeReifierLeft(config, opName, varIndexRight, v1, v3, domain1, domain2);
} else if (hasRight) {
// resolve right and eliminate reifier
return _config_solvedAtCompileTimeReifierRight(config, opName, varIndexLeft, v2, v3, domain1, domain2);
}
}
if (opName !== 'eq' && opName !== 'neq') {
// must be lt lte gt gte. these are solved completely when either param is solved
const REMOVE_FAIL = 0;
const REMOVE_PASS = 1;
if (opName === 'lt') {
// A < B. solved if max(A) < min(B). rejected if min(A) >= max(B)
if (domain_max(domain1) < domain_min(domain2)) return _config_eliminate(config, varIndexLeft, varIndexRight, varIndexResult, domain3, REMOVE_FAIL);
if (domain_min(domain1) >= domain_max(domain2)) return _config_eliminate(config, varIndexLeft, varIndexRight, varIndexResult, domain3, REMOVE_PASS);
} else if (opName === 'lte') {
// A <= B. solved if max(A) <= min(B). rejected if min(A) > max(B)
if (domain_max(domain1) <= domain_min(domain2)) return _config_eliminate(config, varIndexLeft, varIndexRight, varIndexResult, domain3, REMOVE_FAIL);
if (domain_min(domain1) > domain_max(domain2)) return _config_eliminate(config, varIndexLeft, varIndexRight, varIndexResult, domain3, REMOVE_PASS);
} else if (opName === 'gt') {
// A > B. solved if min(A) > max(B). rejected if max(A) <= min(B)
if (domain_min(domain1) > domain_max(domain2)) return _config_eliminate(config, varIndexLeft, varIndexRight, varIndexResult, domain3, REMOVE_FAIL);
if (domain_max(domain1) <= domain_min(domain2)) return _config_eliminate(config, varIndexLeft, varIndexRight, varIndexResult, domain3, REMOVE_PASS);
} else if (opName === 'gte') {
// A > B. solved if min(A) >= max(B). rejected if max(A) < min(B)
if (domain_min(domain1) >= domain_max(domain2)) return _config_eliminate(config, varIndexLeft, varIndexRight, varIndexResult, domain3, REMOVE_FAIL);
if (domain_max(domain1) < domain_min(domain2)) return _config_eliminate(config, varIndexLeft, varIndexRight, varIndexResult, domain3, REMOVE_PASS);
} else {
THROW('UNKNOWN_OP');
}
}
return false;
}
function _config_eliminate(config, leftVarIndex, rightVarIndex, resultVarIndex, resultDomain, value) {
config.initialDomains[resultVarIndex] = domain_removeValue(resultDomain, value);
config._constrainedAway.push(leftVarIndex, rightVarIndex, resultVarIndex);
return true;
}
function _config_solvedAtCompileTimeReifierBoth(config, varIndexes, opName, v1, v2) {
let initialDomains = config.initialDomains;
let varIndexResult = varIndexes[2];
let bool = false;
switch (opName) {
case 'lt':
bool = v1 < v2;
break;
case 'lte':
bool = v1 <= v2;
break;
case 'gt':
bool = v1 > v2;
break;
case 'gte':
bool = v1 >= v2;
break;
case 'eq':
bool = v1 === v2;
break;
case 'neq':
bool = v1 !== v2;
break;
default:
return false;
}
initialDomains[varIndexResult] = domain_removeValue(initialDomains[varIndexResult], bool ? 0 : 1);
config._constrainedAway.push(varIndexResult); // note: left and right have been solved already so no need to push those here
return true;
}
function _config_solvedAtCompileTimeReifierLeft(config, opName, varIndex, value, result, domain1, domain2) {
let initialDomains = config.initialDomains;
let domain = initialDomains[varIndex];
switch (opName) {
case 'lt':
if (result) domain = domain_removeLte(domain, value);
else domain = domain_removeGte(domain, value + 1);
break;
case 'lte':
if (result) domain = domain_removeLte(domain, value - 1);
else domain = domain_removeGte(domain, value);
break;
case 'gt':
if (result) domain = domain_removeGte(domain, value);
else domain = domain_removeLte(domain, value - 1);
break;
case 'gte':
if (result) domain = domain_removeGte(domain, value + 1);
else domain = domain_removeLte(domain, value);
break;
case 'eq':
if (result) domain = domain_intersection(domain1, domain2);
else domain = domain_removeValue(domain, value);
break;
case 'neq':
if (result) domain = domain_removeValue(domain, value);
else domain = domain_intersection(domain1, domain2);
break;
default:
return false;
}
initialDomains[varIndex] = domain;
config._constrainedAway.push(varIndex); // note: left and result have been solved already so no need to push those here
return true;
}
function _config_solvedAtCompileTimeReifierRight(config, opName, varIndex, value, result, domain1, domain2) {
let initialDomains = config.initialDomains;
let domain = initialDomains[varIndex];
switch (opName) {
case 'lt':
if (result) domain = domain_removeGte(domain, value);
else domain = domain_removeLte(domain, value - 1);
break;
case 'lte':
if (result) domain = domain_removeGte(domain, value + 1);
else domain = domain_removeLte(domain, value);
break;
case 'gt':
if (result) domain = domain_removeLte(domain, value);
else domain = domain_removeGte(domain, value + 1);
break;
case 'gte':
if (result) domain = domain_removeLte(domain, value - 1);
else domain = domain_removeGte(domain, value);
break;
case 'eq':
if (result) domain = domain_intersection(domain1, domain2);
else domain = domain_removeValue(domain, value);
break;
case 'neq':
if (result) domain = domain_removeValue(domain, value);
else domain = domain_intersection(domain1, domain2);
break;
default:
return false;
}
initialDomains[varIndex] = domain;
config._constrainedAway.push(varIndex); // note: right and result have been solved already so no need to push those here
return true;
}
function _config_solvedAtCompileTimeSumProduct(config, constraintName, varIndexes, resultIndex) {
let initialDomains = config.initialDomains;
// if there are no vars then the next step would fail. could happen as an artifact.
if (initialDomains.length) {
// limit result var to the min/max possible sum
let maxDomain = initialDomains[varIndexes[0]]; // dont start with EMPTY or [0,0]!
for (let i = 1, n = varIndexes.length; i < n; ++i) {
let varIndex = varIndexes[i];
let domain = initialDomains[varIndex];
if (constraintName === 'sum') maxDomain = domain_plus(maxDomain, domain);
else maxDomain = domain_mul(maxDomain, domain);
}
initialDomains[resultIndex] = domain_intersection(maxDomain, initialDomains[resultIndex]);
}
// eliminate multiple constants
if (varIndexes.length > 1) {
let newVarIndexes = [];
let total = constraintName === 'product' ? 1 : 0;
for (let i = 0, n = varIndexes.length; i < n; ++i) {
let varIndex = varIndexes[i];
let domain = initialDomains[varIndex];
let value = domain_getValue(domain);
if (value === NO_SUCH_VALUE) {
newVarIndexes.push(varIndex);
} else if (constraintName === 'sum') {
total += value;
} else if (constraintName === 'product') {
total *= value;
}
}
// note for product, multiply by 1 to get identity. for sum it's add 0 for identity.
if (!newVarIndexes.length || (constraintName === 'sum' && total !== 0) || (constraintName === 'product' && total !== 1)) {
let varIndex = config_addVarAnonConstant(config, total);
newVarIndexes.push(varIndex);
}
// copy new list inline
for (let i = 0, n = newVarIndexes.length; i < n; ++i) {
varIndexes[i] = newVarIndexes[i];
}
varIndexes.length = newVarIndexes.length;
}
// shouldnt be zero here unless it was declared empty
if (varIndexes.length === 1) {
// both in the case of sum and product, if there is only one value in the set, the result must be that value
// so here we do an intersect that one value with the result because that's what must happen anyways
let domain = domain_intersection(config.initialDomains[resultIndex], config.initialDomains[varIndexes[0]]);
config.initialDomains[resultIndex] = domain;
config.initialDomains[varIndexes[0]] = domain;
if (domain_isSolved(domain)) {
config._constrainedAway.push(varIndexes[0], resultIndex);
return true;
}
// cant eliminate constraint; sum will compile an `eq` for it.
}
return false;
}
/**
* Generate all propagators from the constraints in given config
* Puts these back into the same config.
*
* @param {$config} config
*/
function config_generatePropagators(config) {
let constraints = config.allConstraints;
config._propagators = [];
for (let i = 0, n = constraints.length; i < n; ++i) {
let constraint = constraints[i];
if (constraint.varNames) {
console.warn('saw constraint.varNames, converting to varIndexes, log out result and update test accordingly');
constraint.varIndexes = constraint.varNames.map(name => trie_get(config._varNamesTrie, name));
let p = constraint.param;
delete constraint.param;
delete constraint.varNames;
constraint.param = p;
}
config_generatePropagator(config, constraint.name, constraint.varIndexes, constraint.param, constraint);
}
}
/**
* @param {$config} config
* @param {string} name
* @param {number[]} varIndexes
* @param {string|undefined} param Depends on the prop; reifier=op name, product/sum=result var
*/
function config_generatePropagator(config, name, varIndexes, param, _constraint) {
switch (name) {
case 'plus':
return propagator_addPlus(config, varIndexes[0], varIndexes[1], varIndexes[2]);
case 'min':
return propagator_addMin(config, varIndexes[0], varIndexes[1], varIndexes[2]);
case 'ring-mul':
return propagator_addRingMul(config, varIndexes[0], varIndexes[1], varIndexes[2]);
case 'ring-div':
return propagator_addDiv(config, varIndexes[0], varIndexes[1], varIndexes[2]);
case 'mul':
return propagator_addMul(config, varIndexes[0], varIndexes[1], varIndexes[2]);
case 'sum':
return propagator_addSum(config, varIndexes.slice(0), param);
case 'product':
return propagator_addProduct(config, varIndexes.slice(0), param);
case 'distinct':
return propagator_addDistinct(config, varIndexes.slice(0));
case 'reifier':
return propagator_addReified(config, param, varIndexes[0], varIndexes[1], varIndexes[2]);
case 'neq':
return propagator_addNeq(config, varIndexes[0], varIndexes[1]);
case 'eq':
return propagator_addEq(config, varIndexes[0], varIndexes[1]);
case 'gte':
return propagator_addGte(config, varIndexes[0], varIndexes[1]);
case 'lte':
return propagator_addLte(config, varIndexes[0], varIndexes[1]);
case 'gt':
return propagator_addGt(config, varIndexes[0], varIndexes[1]);
case 'lt':
return propagator_addLt(config, varIndexes[0], varIndexes[1]);
default:
THROW('UNEXPECTED_NAME: ' + name);
}
}
function config_generateMarkovs(config) {
let varDistOptions = config.varDistOptions;
for (let varName in varDistOptions) {
let varIndex = trie_get(config._varNamesTrie, varName);
if (varIndex < 0) THROW('Found markov var options for an unknown var name (' + varName + ')');
let options = varDistOptions[varName];
if (options && options.valtype === 'markov') {
return propagator_addMarkov(config, varIndex);
}
}
}
function config_populateVarStrategyListHash(config) {
let vsc = config.varStratConfig;
while (vsc) {
if (vsc.priorityByName) {
let obj = {};
let list = vsc.priorityByName;
for (let i = 0, len = list.length; i < len; ++i) {
let varIndex = trie_get(config._varNamesTrie, list[i]);
obj[varIndex] = len - i; // never 0, offset at 1. higher value is higher prio
}
vsc._priorityByIndex = obj;
}
vsc = vsc.fallback;
}
}
/**
* At the start of a search, populate this config with the dynamic data
*
* @param {$config} config
*/
function config_init(config) {
if (!config._varNamesTrie) {
config._varNamesTrie = trie_create(config.allVarNames);
}
// Generate the default rng ("Random Number Generator") to use in stuff like markov
// We prefer the rngCode because that way we can serialize the config (required for stuff like webworkers)
if (!config._defaultRng) config._defaultRng = config.rngCode ? Function(config.rngCode) : Math.random; /* eslint no-new-func: "off" */
config_generatePropagators(config);
config_generateMarkovs(config);
config_populateVarPropHash(config);
config_populateVarStrategyListHash(config);
}
// end of src/config.js
// from: src/constraint.js
function constraint_create(name, varIndexes, param) {
return {
_class: '$constraint',
name,
varIndexes,
param,
};
}
// end of src/constraint.js
// from: src/distribution/defaults.js
const PRESETS = {
defaults: {
varStrategy: {type: 'naive'},
valueStrategy: 'min',
},
// The native distribution strategy simply steps through all
// undetermined variables.
naive: {
varStrategy: {type: 'naive'},
valueStrategy: 'min',
},
// The "fail first" strategy branches on the variable with the
// smallest domain size.
fail_first: {
varStrategy: {type: 'size'},
valueStrategy: 'min',
},
// The "domain splitting" strategy where each domain is roughly
// halved in each step. The 'varname' argument can be either a
// single var name or an array of names or an object whose
// values are var names.
split: {
varStrategy: {type: 'size'},
valueStrategy: 'splitMin',
},
};
function distribution_getDefaults(name) {
if (PRESETS[name]) return PRESETS[name];
THROW(`distribution.get_defaults: Unknown preset: ${name}`);
}
// end of src/distribution/defaults.js
// from: src/distribution/markov.js
/**
* Given a domain, probability vector, value legend, and rng
* function; return one of the values in the value legend
* according to the outcome of the rng and considering the
* prob weight of each value in the legend.
* The rng should be normalized (returning values from 0 including
* up to but not including 1), unless the argument says otherwise
* (that is used for testing only, to get around rounding errors).
*
* @param {$domain} domain A regular domain. It's values only determine whether a legend value can be used, it may have values that can never be picked. It's only a filter mask.
* @param {number[]} probVector List of probabilities, maps 1:1 to val_legend.
* @param {number[]} valLegend List of values eligible for picking. Maps 1:1 to prob_vector. Only values in the current domain are actually eligible.
* @param {Function} randomFunc
* @param {boolean} [rngIsNormalized=true] Is 0<=rng()<1 or 0<=rng()<total_prob ? The latter is only used for testing to avoid rounding errors.
* @return {number | undefined}
*/
function distribution_markovSampleNextFromDomain(domain, probVector, valLegend, randomFunc, rngIsNormalized = true) {
// make vector & legend for available values only
let filteredLegend = [];
let cumulativeFilteredProbVector = [];
let totalProb = 0;
for (let index = 0; index < probVector.length; index++) {
let prob = probVector[index];
if (prob > 0) {
let value = valLegend[index];
if (domain_containsValue(domain, value)) {
totalProb += prob;
cumulativeFilteredProbVector.push(totalProb);
filteredLegend.push(value);
}
}
}
// no more values left to search
if (cumulativeFilteredProbVector.length === 0) {
return;
}
// only one value left
if (cumulativeFilteredProbVector.length === 1) {
return filteredLegend[0];
}
// TOFIX: could set `cumulativeFilteredProbVector[cumulativeFilteredProbVector.length-1] = 1` here...
return _distribution_markovRoll(randomFunc, totalProb, cumulativeFilteredProbVector, filteredLegend, rngIsNormalized);
}
/**
* @private
* @param {Function} rng A function ("random number generator"), which is usually normalized, but in tests may not be
* @param {number} totalProb
* @param {number[]} cumulativeProbVector Maps 1:1 to the value legend. `[prob0, prob0+prob1, prob0+prob1+prob2, etc]`
* @param {number[]} valueLegend
* @param {boolean} rngIsNormalized
* @returns {number}
*/
function _distribution_markovRoll(rng, totalProb, cumulativeProbVector, valueLegend, rngIsNormalized) {
let rngRoll = rng();
let probVal = rngRoll;
if (rngIsNormalized) { // 0 <= rng < 1
// roll should yield; 0<=value<1
probVal = rngRoll * totalProb;
}
// else 0 <= rng < totalProb (mostly to avoid precision problems in tests)
for (var index = 0; index < cumulativeProbVector.length; index++) {
// note: if first element is 0.1 and roll is 0.1 this will pick the
// SECOND item. by design. so prob domains are `[x, y)`
let prob = cumulativeProbVector[index];
if (prob > probVal) {
break;
}
}
return valueLegend[index];
}
// end of src/distribution/markov.js
// from: src/distribution/value.js
const FIRST_CHOICE = 0;
const SECOND_CHOICE = 1;
const THIRD_CHOICE = 2;
const NO_CHOICE = undefined;
function distribute_getNextDomainForVar(space, config, varIndex, choiceIndex) {
let valueStrategy = config.valueStratName;
// each var can override the value distributor
let configVarDistOptions = config.varDistOptions;
let varName = config.allVarNames[varIndex];
let valueDistributorName = configVarDistOptions[varName] && configVarDistOptions[varName].valtype;
if (valueDistributorName) valueStrategy = valueDistributorName;
if (typeof valueStrategy === 'function') return valueStrategy(space, varIndex, choiceIndex);
return _distribute_getNextDomainForVar(valueStrategy, space, config, varIndex, choiceIndex);
}
function _distribute_getNextDomainForVar(stratName, space, config, varIndex, choiceIndex) {
switch (stratName) {
case 'max':
return distribution_valueByMax(space, varIndex, choiceIndex);
case 'markov':
return distribution_valueByMarkov(space, config, varIndex, choiceIndex);
case 'mid':
return distribution_valueByMid(space, varIndex, choiceIndex);
case 'min':
return distribution_valueByMin(space, varIndex, choiceIndex);
case 'minMaxCycle':
return distribution_valueByMinMaxCycle(space, varIndex, choiceIndex);
case 'list':
return distribution_valueByList(space, config, varIndex, choiceIndex);
case 'naive':
return domain_createValue(domain_min(space.vardoms[varIndex]));
case 'splitMax':
return distribution_valueBySplitMax(space, varIndex, choiceIndex);
case 'splitMin':
return distribution_valueBySplitMin(space, varIndex, choiceIndex);
case 'throw':
return ASSERT(false, 'not expecting to pick this distributor');
}
THROW('unknown next var func', stratName);
}
/**
* Attempt to solve by setting var domain to values in the order
* given as a list. This may also be a function which should
* return a new domain given the space, var index, and choice index.
*
* @param {$space} space
* @param {$config} config
* @param {number} varIndex
* @param {number} choiceIndex
* @returns {$domain|undefined} The new domain for this var index in the next space TOFIX: support small domains
*/
function distribution_valueByList(space, config, varIndex, choiceIndex) {
let domain = space.vardoms[varIndex];
let varName = config.allVarNames[varIndex];
let configVarDistOptions = config.varDistOptions;
let varDistOptions = configVarDistOptions[varName];
let listSource = varDistOptions.list;
let fallbackName = '';
if (varDistOptions.fallback) {
fallbackName = varDistOptions.fallback.valtype;
}
let list = listSource;
if (typeof listSource === 'function') {
// Note: callback should return the actual list
list = listSource(space, varName, choiceIndex);
}
switch (choiceIndex) {
case FIRST_CHOICE:
let nextValue = domain_getFirstIntersectingValue(domain, list);
if (nextValue === NO_SUCH_VALUE) {
if (fallbackName) {
return _distribute_getNextDomainForVar(fallbackName, space, config, varIndex, choiceIndex);
}
return NO_CHOICE;
} else {
space._lastChosenValue = nextValue;
}
return domain_createValue(nextValue);
case SECOND_CHOICE:
if (space._lastChosenValue >= 0) {
return domain_removeValue(domain, space._lastChosenValue);
}
if (fallbackName) {
return _distribute_getNextDomainForVar(fallbackName, space, config, varIndex, choiceIndex);
}
return NO_CHOICE;
}
return NO_CHOICE;
}
/**
* Searches through a var's values from min to max.
* For each value in the domain it first attempts just
* that value, then attempts the domain without this value.
*
* @param {$space} space
* @param {number} varIndex
* @param {number} choiceIndex
* @returns {$domain|undefined} The new domain this var index should get in the next space
*/
function distribution_valueByMin(space, varIndex, choiceIndex) {
let domain = space.vardoms[varIndex];
switch (choiceIndex) {
case FIRST_CHOICE:
let minValue = domain_min(domain);
space._lastChosenValue = minValue;
return domain_createValue(minValue);
case SECOND_CHOICE:
// Cannot lead to empty domain because lo can only be SUP if
// domain was solved and we assert it wasn't.
return domain_removeValue(domain, space._lastChosenValue);
}
return NO_CHOICE;
}
/**
* Searches through a var's values from max to min.
* For each value in the domain it first attempts just
* that value, then attempts the domain without this value.
*
* @param {$space} space
* @param {number} varIndex
* @param {number} choiceIndex
* @returns {$domain|undefined} The new domain this var index should get in the next space
*/
function distribution_valueByMax(space, varIndex, choiceIndex) {
let domain = space.vardoms[varIndex];
switch (choiceIndex) {
case FIRST_CHOICE:
let maxValue = domain_max(domain);
space._lastChosenValue = maxValue;
return domain_createValue(maxValue);
case SECOND_CHOICE:
// Cannot lead to empty domain because hi can only be SUB if
// domain was solved and we assert it wasn't.
return domain_removeValue(domain, space._lastChosenValue);
}
return NO_CHOICE;
}
/**
* Searches through a var's values by taking the middle value.
* This version targets the value closest to `(max-min)/2`
* For each value in the domain it first attempts just
* that value, then attempts the domain without this value.
*
* @param {$space} space
* @param {number} varIndex
* @param {number} choiceIndex
* @returns {$domain|undefined} The new domain this var index should get in the next space
*/
function distribution_valueByMid(space, varIndex, choiceIndex) {
let domain = space.vardoms[varIndex];
switch (choiceIndex) {
case FIRST_CHOICE:
let middle = domain_middleElement(domain);
space._lastChosenValue = middle;
return domain_createValue(middle);
case SECOND_CHOICE:
return domain_removeValue(domain, space._lastChosenValue);
}
return NO_CHOICE;
}
/**
* Search a domain by splitting it up through the (max-min)/2 middle.
* First simply tries the lower half, then tries the upper half.
*
* @param {$space} space
* @param {number} varIndex
* @param {number} choiceIndex
* @returns {$domain|undefined} The new domain this var index should get in the next space
*/
function distribution_valueBySplitMin(space, varIndex, choiceIndex) {
let domain = space.vardoms[varIndex];
let max = domain_max(domain);
switch (choiceIndex) {
case FIRST_CHOICE: {
// TOFIX: can do this more optimal if coding it out explicitly
let min = domain_min(domain);
let mmhalf = min + Math.floor((max - min) / 2);
space._lastChosenValue = mmhalf;
// Note: domain is not determined so the operation cannot fail
// Note: this must do some form of intersect, though maybe not constrain
return domain_intersection(domain, domain_createRange(min, mmhalf));
}
case SECOND_CHOICE: {
// Note: domain is not determined so the operation cannot fail
// Note: this must do some form of intersect, though maybe not constrain
return domain_intersection(domain, domain_createRange(space._lastChosenValue + 1, max));
}
}
return NO_CHOICE;
}
/**
* Search a domain by splitting it up through the (max-min)/2 middle.
* First simply tries the upper half, then tries the lower half.
*
* @param {$space} space
* @param {number} varIndex
* @param {number} choiceIndex
* @returns {$domain|undefined} The new domain this var index should get in the next space
*/
function distribution_valueBySplitMax(space, varIndex, choiceIndex) {
let domain = space.vardoms[varIndex];
let min = domain_min(domain);
switch (choiceIndex) {
case FIRST_CHOICE: {
// TOFIX: can do this more optimal if coding it out explicitly
let max = domain_max(domain);
let mmhalf = min + Math.floor((max - min) / 2);
space._lastChosenValue = mmhalf;
// Note: domain is not determined so the operation cannot fail
// Note: this must do some form of intersect, though maybe not constrain
return domain_intersection(domain, domain_createRange(mmhalf + 1, max));
}
case SECOND_CHOICE: {
// Note: domain is not determined so the operation cannot fail
// Note: this must do some form of intersect, though maybe not constrain
return domain_intersection(domain, domain_createRange(min, space._lastChosenValue));
}
}
return NO_CHOICE;
}
/**
* Applies distribution_valueByMin and distribution_valueByMax alternatingly
* depending on the position of the given var in the list of vars.
*
* @param {$space} space
* @param {number} varIndex
* @param {number} choiceIndex
* @returns {$domain|undefined} The new domain this var index should get in the next space
*/
function distribution_valueByMinMaxCycle(space, varIndex, choiceIndex) {
if (_isEven(varIndex)) {
return distribution_valueByMin(space, varIndex, choiceIndex);
} else {
return distribution_valueByMax(space, varIndex, choiceIndex);
}
}
/**
* @param {number} n
* @returns {boolean}
*/
function _isEven(n) { return n % 2 === 0; }
/**
* Search a domain by applying a markov chain to determine an optimal value
* checking path.
*
* @param {$space} space
* @param {$config} config
* @param {number} varIndex
* @param {number} choiceIndex
* @returns {$domain|undefined} The new domain this var index should get in the next space
*/
function distribution_valueByMarkov(space, config, varIndex, choiceIndex) {
let domain = space.vardoms[varIndex];
switch (choiceIndex) {
case FIRST_CHOICE: {
// THIS IS AN EXPENSIVE STEP!
let varName = config.allVarNames[varIndex];
let configVarDistOptions = config.varDistOptions;
let distOptions = configVarDistOptions[varName];
let expandVectorsWith = distOptions.expandVectorsWith;
let random = distOptions.random || config._defaultRng;
// note: expandVectorsWith can be 0, so check with null
let values = markov_createLegend(typeof expandVectorsWith === 'number', distOptions.legend, domain);
let valueCount = values.length;
if (!valueCount) {
return NO_CHOICE;
}
let probabilities = markov_createProbVector(space, distOptions.matrix, expandVectorsWith, valueCount);
let value = distribution_markovSampleNextFromDomain(domain, probabilities, values, random);
if (value == null) {
return NO_CHOICE;
}
space._lastChosenValue = value;
return domain_createValue(value);
}
case SECOND_CHOICE: {
let lastValue = space._lastChosenValue;
let newDomain = domain_removeValue(domain, lastValue);
return newDomain;
}
}
return NO_CHOICE;
}
// end of src/distribution/value.js
// from: src/distribution/var.js
const BETTER = 1;
const SAME = 2;
const WORSE = 3;
/**
* Given a list of variables return the next var to consider based on the
* current var distribution configuration and an optional filter condition.
*
* @param {$space} space
* @param {$config} config
* @returns {number}
*/
function distribution_getNextVarIndex(space, config) {
let varStratConfig = config.varStratConfig;
let isBetterVarFunc = distribution_getFunc(varStratConfig.type);
let varIndex = _distribution_varFindBest(space, config, isBetterVarFunc, varStratConfig);
return varIndex;
}
/**
* @param {string} distName
* @returns {Function|undefined}
*/
function distribution_getFunc(distName) {
switch (distName) {
case 'naive':
return null;
case 'size':
return distribution_varByMinSize;
case 'min':
return distribution_varByMin;
case 'max':
return distribution_varByMax;
case 'markov':
return distribution_varByMarkov;
case 'list':
return distribution_varByList;
case 'throw':
return THROW('not expecting to pick this distributor');
}
return THROW('unknown next var func', distName);
}
/**
* Return the best varIndex according to a fitness function
*
* @param {$space} space
* @param {$config} config
* @param {Function($space, currentIndex, bestIndex, Function)} [fitnessFunc] Given two var indexes returns true iif the first var is better than the second var
* @param {Object} varStratConfig
* @returns {number} The varIndex of the next var or NO_SUCH_VALUE
*/
function _distribution_varFindBest(space, config, fitnessFunc, varStratConfig) {
let i = 0;
let unsolvedVarIndexes = space._unsolved;
let bestVarIndex = unsolvedVarIndexes[i++];
if (fitnessFunc) {
for (let len = unsolvedVarIndexes.length; i < len; i++) {
let varIndex = unsolvedVarIndexes[i];
if (BETTER === fitnessFunc(space, config, varIndex, bestVarIndex, varStratConfig)) {
bestVarIndex = varIndex;
}
}
}
return bestVarIndex;
}
//#####
// preset fitness functions
//#####
function distribution_varByMinSize(space, config, varIndex1, varIndex2) {
let n = domain_size(space.vardoms[varIndex1]) - domain_size(space.vardoms[varIndex2]);
if (n < 0) return BETTER;
if (n > 0) return WORSE;
return SAME;
}
function distribution_varByMin(space, config, varIndex1, varIndex2) {
let n = domain_min(space.vardoms[varIndex1]) - domain_min(space.vardoms[varIndex2]);
if (n < 0) return BETTER;
if (n > 0) return WORSE;
return SAME;
}
function distribution_varByMax(space, config, varIndex1, varIndex2) {
let n = domain_max(space.vardoms[varIndex1]) - domain_max(space.vardoms[varIndex2]);
if (n > 0) return BETTER;
if (n < 0) return WORSE;
return SAME;
}
function distribution_varByMarkov(space, config, varIndex1, varIndex2, varStratConfig) {
let distOptions = config.varDistOptions;
// v1 is only, but if so always, better than v2 if v1 is a markov var
let varName1 = config.allVarNames[varIndex1];
if (distOptions[varName1] && distOptions[varName1].valtype === 'markov') {
return BETTER;
}
let varName2 = config.allVarNames[varIndex2];
if (distOptions[varName2] && distOptions[varName2].valtype === 'markov') {
return WORSE;
}
return distribution_varFallback(space, config, varIndex1, varIndex2, varStratConfig.fallback);
}
function distribution_varByList(space, config, varIndex1, varIndex2, varStratConfig) {
// note: config._priorityByIndex is compiled by Solver#prepare from given priorityByName
// if in the list, lowest prio can be 1. if not in the list, prio will be undefined
let hash = varStratConfig._priorityByIndex;
// if v1 or v2 is not in the list they will end up as undefined
let p1 = hash[varIndex1];
let p2 = hash[varIndex2];
if (!p1 && !p2) { // neither has a priority
return distribution_varFallback(space, config, varIndex1, varIndex2, varStratConfig.fallback);
}
// invert this operation? ("deprioritizing").
let inverted = varStratConfig.inverted;
// if inverted being on the list makes it worse than not.
if (!p2) {
if (inverted) return WORSE;
return BETTER;
}
if (!p1) {
if (inverted) return BETTER;
return WORSE;
}
// the higher the p, the higher the prio. (the input array is compiled that way)
// if inverted then low p is higher prio
if (p1 > p2) {
if (inverted) return WORSE;
return BETTER;
}
if (inverted) return BETTER;
return WORSE;
}
function distribution_varFallback(space, config, varIndex1, varIndex2, fallbackConfig) {
if (!fallbackConfig) {
return SAME;
}
let distName = fallbackConfig.type;
switch (distName) {
case 'size':
return distribution_varByMinSize(space, config, varIndex1, varIndex2);
case 'min':
return distribution_varByMin(space, config, varIndex1, varIndex2);
case 'max':
return distribution_varByMax(space, config, varIndex1, varIndex2);
case 'markov':
return distribution_varByMarkov(space, config, varIndex1, varIndex2, fallbackConfig);
case 'list':
return distribution_varByList(space, config, varIndex1, varIndex2, fallbackConfig);
case 'throw':
return THROW('nope');
}
return THROW(`Unknown var dist fallback name: ${distName}`);
}
// end of src/distribution/var.js
// from: src/domain.js
// CSIS form = Canonical Sorted Interval Sequeunce form.
// Basically means the ranges in the domain are ordered
// ascending and no ranges overlap. We call this "simplified"
//let FIRST_RANGE = 0;
let STR_FIRST_RANGE_LO = 0; // first and second char of a string
let STR_FIRST_RANGE_HI = 2; // third and fourth char of a string
let ARR_FIRST_RANGE_LO = 0;
let ARR_FIRST_RANGE_HI = 1;
// Cache static Math functions
let MIN = Math.min;
let MAX = Math.max;
let FLOOR = Math.floor;
let CEIL = Math.ceil;
// size of values and ranges in a string domain
const STR_VALUE_SIZE = 2;
const STR_RANGE_SIZE = 4;
const EMPTY = 0;
const EMPTY_STR = '';
/**
* Append given range to the end of given domain. Does not
* check if the range belongs there! Dumbly appends.
*
* @param {$nordom} domain
* @param {number} lo
* @param {number} hi
* @returns {$domain}
*/
//function domain_appendRange(domain, lo, hi) {
// ASSERT_NORDOM(domain);
//
// if (typeof domain === 'number') {
// // note: this function should not receive numdoms with a SOLVED_FLAG set
// // it is only used in temporary array cases, the flag must be set afterwards
// ASSERT(domain < SOLVED_FLAG, 'not expecting solved numdoms');
// if (hi <= SMALL_MAX_NUM) return domain_bit_addRange(domain, lo, hi);
// domain = domain_numToStr(domain);
// }
// return domain_str_addRange(domain, lo, hi);
//}
function domain_bit_addRange(domain, lo, hi) {
// what we do is:
// - create a 1
// - move the 1 to the left, `1+to-from` times
// - subtract 1 to get a series of `to-from` ones
// - shift those ones `from` times to the left
// - OR that result with the domain and return it
let range = (((1 << (1 + (hi | 0) - (lo | 0))) - 1) << lo);
return domain | range;
}
//function domain_str_addRange(domain, lo, hi) {
// ASSERT_STRDOM(domain);
// ASSERT(lo >= 0);
// ASSERT(hi <= SUP);
// ASSERT(lo <= hi);
//
// return domain + domain_str_encodeRange(lo, hi);
//}
/**
* returns whether domain covers given value
*
* @param {$nordom} domain
* @param {number} value
* @returns {boolean}
*/
function domain_containsValue(domain, value) {
if (typeof domain === 'number') return domain_num_containsValue(domain, value);
return domain_str_containsValue(domain, value);
}
function domain_num_containsValue(domain, value) {
if (domain >= SOLVED_FLAG) return domain_sol_containsValue(domain, value);
return domain_bit_containsValue(domain, value);
}
function domain_sol_containsValue(domain, value) {
return (domain ^ SOLVED_FLAG) === value;
}
function domain_bit_containsValue(domain, value) {
return (domain & (1 << value)) !== 0;
}
function domain_str_containsValue(domain, value) {
return domain_str_rangeIndexOf(domain, value) !== NOT_FOUND;
}
/**
* return the range index in given domain that covers given
* value, or if the domain does not cover it at all
*
* @param {$strdom} domain
* @param {number} value
* @returns {number} >=0 actual index on strdom or NOT_FOUND
*/
function domain_str_rangeIndexOf(domain, value) {
let len = domain.length;
for (let index = 0; index < len; index += STR_RANGE_SIZE) {
let lo = domain_str_decodeValue(domain, index);
if (lo <= value) {
let hi = domain_str_decodeValue(domain, index + STR_VALUE_SIZE);
if (hi >= value) {
// value is lo<=value<=hi
return index;
}
} else {
// value is between previous range and this one, aka: not found.
break;
}
}
return NOT_FOUND;
}
/**
* Check if given domain is solved. If so, return the value
* to which it was solved. Otherwise return NO_SUCH_VALUE.
*
* @param {$nordom} domain
* @returns {number}
*/
function domain_getValue(domain) {
// TODO: in a sound system we'd only have to check for soldoms...
if (typeof domain === 'number') return domain_num_getValue(domain);
return domain_str_getValue(domain);
}
function domain_num_getValue(domain) {
if (domain >= SOLVED_FLAG) return domain_sol_getValue(domain);
return domain_bit_getValue(domain);
}
function domain_sol_getValue(domain) {
return domain ^ SOLVED_FLAG;
}
function domain_bit_getValue(domain) {
var lo = domain_bit_min(domain);
return (domain === (1 << lo)) ? lo : NO_SUCH_VALUE;
}
function domain_str_getValue(domain) {
if (domain.length !== STR_RANGE_SIZE) return NO_SUCH_VALUE;
let lo = domain_str_decodeValue(domain, STR_FIRST_RANGE_LO);
let hi = domain_str_decodeValue(domain, STR_FIRST_RANGE_HI);
if (lo === hi) return lo;
return NO_SUCH_VALUE;
}
/**
* @param {$strdom} domain
* @param {number} index
* @returns {number}
*/
function domain_str_decodeValue(domain, index) {
return (domain.charCodeAt(index) << 16) | domain.charCodeAt(index + 1);
}
/**
* @param {number} value
* @returns {string} not a $strdom but half of one
*/
function domain_str_encodeValue(value) {
return String.fromCharCode((value >>> 16) & 0xffff, value & 0xffff);
}
/**
* @param {number} lo
* @param {number} hi
* @returns {$strdom} One range is still a valid domain
*/
function domain_str_encodeRange(lo, hi) {
return String.fromCharCode((lo >>> 16) & 0xffff, lo & 0xffff, (hi >>> 16) & 0xffff, hi & 0xffff);
}
/**
* External API only. Always returns an arrdom.
*
* @param {number[]} list
* @returns {$arrdom}
*/
function domain_fromListToArrdom(list) {
if (!list.length) return [];
list = list.slice(0);
list.sort((a, b) => a - b); // note: default sort is lexicographic!
let arrdom = [];
let hi;
let lo;
for (let index = 0; index < list.length; index++) {
let value = list[index];
if (index === 0) {
lo = value;
hi = value;
} else {
if (value > hi + 1) {
arrdom.push(lo, hi);
lo = value;
}
hi = value;
}
}
arrdom.push(lo, hi);
return arrdom;
}
/**
* domain to list of possible values
*
* @param {$nordom} domain
* @returns {number[]}
*/
function domain_toList(domain) {
if (typeof domain === 'number') return domain_num_toList(domain);
return domain_str_toList(domain);
}
function domain_num_toList(domain) {
if (domain >= SOLVED_FLAG) return domain_sol_toList(domain);
return domain_bit_toList(domain);
}
function domain_sol_toList(domain) {
return [domain ^ SOLVED_FLAG];
}
function domain_bit_toList(domain) {
let list = [];
for (let i = 0; i < SMALL_MAX_NUM; ++i) {
if ((domain & ((1 << i) >>> 0)) > 0) list.push(i);
}
return list;
}
function domain_str_toList(domain) {
let list = [];
for (let i = 0, len = domain.length; i < len; i += STR_RANGE_SIZE) {
for (let n = domain_str_decodeValue(domain, i), m = domain_str_decodeValue(domain, i + STR_VALUE_SIZE); n <= m; ++n) {
list.push(n);
}
}
return list;
}
/**
* @param {$nordom} domain
* @param {number[]} list
* @returns {number} Can return NO_SUCH_VALUE
*/
function domain_getFirstIntersectingValue(domain, list) {
if (typeof domain === 'number') return domain_num_getFirstIntersectingValue(domain, list);
return domain_str_getFirstIntersectingValue(domain, list);
}
function domain_num_getFirstIntersectingValue(domain, list) {
if (domain >= SOLVED_FLAG) return domain_sol_getFirstIntersectingValue(domain, list);
return domain_bit_getFirstIntersectingValue(domain, list);
}
function domain_sol_getFirstIntersectingValue(domain, list) {
let solvedValue = domain ^ SOLVED_FLAG;
if (list.indexOf(solvedValue) >= 0) return solvedValue;
return NO_SUCH_VALUE;
}
function domain_bit_getFirstIntersectingValue(domain, list) {
for (let i = 0; i < list.length; ++i) {
let value = list[i];
// 1<<100 = 16 and large numbers are valid here so do check
if (value <= SMALL_MAX_NUM && (domain & (1 << value)) > 0) return value;
}
return NO_SUCH_VALUE;
}
function domain_str_getFirstIntersectingValue(domain, list) {
for (let i = 0; i < list.length; i++) {
let value = list[i];
if (domain_str_containsValue(domain, value)) {
return value;
}
}
return NO_SUCH_VALUE;
}
/**
* All ranges will be ordered ascending and overlapping ranges are merged
* This function first checks whether simplification is needed at all
* Should normalize all return values.
*
* @param {$strdom|string} domain
* @returns {$strdom} ironically, not optimized to a number if possible
*/
function domain_str_simplify(domain) {
if (!domain) return EMPTY; // keep return type consistent, dont return EMPTY
if (domain.length === STR_RANGE_SIZE) return domain_toSmallest(domain);
// order ranges, then merge overlapping ranges (TODO: can we squash this step together?)
domain = _domain_str_quickSortRanges(domain);
domain = _domain_str_mergeOverlappingRanges(domain);
return domain_toSmallest(domain);
}
/**
* Sort all ranges in this pseudo-strdom from lo to hi. Domain
* may already be csis but we're not sure. This function call
* is part of the process of ensuring that.
*
* @param {$strdom|string} domain MAY not be CSIS yet (that's probably why this function is called in the first place)
* @returns {$strdom|string} ranges in this string will be ordered but may still overlap
*/
function _domain_str_quickSortRanges(domain) {
if (!domain) return EMPTY_STR; // keep return type consistent, dont return EMPTY
let len = domain.length;
if (len <= STR_RANGE_SIZE) return domain;
// TODO: right now we convert to actual values and concat with "direct" string access. would it be faster to use slices? and would it be faster to do string comparisons with the slices and no decoding?
let pivotIndex = 0; // TODO: i think we'd be better off with a different pivot? middle probably performs better
let pivotLo = domain_str_decodeValue(domain, pivotIndex);
let pivotHi = domain_str_decodeValue(domain, pivotIndex + STR_VALUE_SIZE);
let left = EMPTY_STR;
let right = EMPTY_STR;
for (let i = STR_RANGE_SIZE; i < len; i += STR_RANGE_SIZE) {
let lo = domain_str_decodeValue(domain, i);
// TODO: if we change assumptions elsewhere we could drop the `hi` stuff from this function altogether
if (lo < pivotLo || (lo === pivotLo && domain_str_decodeValue(domain, i + STR_VALUE_SIZE) < pivotHi)) {
left += domain[i] + domain[i + 1] + domain[i + 2] + domain[i + 3];
} else {
right += domain[i] + domain[i + 1] + domain[i + 2] + domain[i + 3];
}
}
return ('' +
_domain_str_quickSortRanges(left) + // sort left part, without pivot
domain[pivotIndex] + // include pivot (4 chars)
domain[pivotIndex + 1] +
domain[pivotIndex + STR_VALUE_SIZE] +
domain[pivotIndex + STR_VALUE_SIZE + 1] +
_domain_str_quickSortRanges(right) // sort right part, without pivot
);
}
/**
* @param {$strdom|string} domain May already be csis but at least all ranges should be ordered and are lo<=hi
* @returns {$strdom}
*/
function _domain_str_mergeOverlappingRanges(domain) {
if (!domain) return EMPTY_STR; // prefer strings for return type consistency
// assumes domain is sorted
// assumes all ranges are "sound" (lo<=hi)
let len = domain.length;
if (len === STR_RANGE_SIZE) return domain;
let newDomain = domain[STR_FIRST_RANGE_LO] + domain[STR_FIRST_RANGE_LO + 1]; // just copy the first two characters...
let lasthi = domain_str_decodeValue(domain, STR_FIRST_RANGE_HI);
let lasthindex = STR_FIRST_RANGE_HI;
for (let i = STR_RANGE_SIZE; i < len; i += STR_RANGE_SIZE) {
let lo = domain_str_decodeValue(domain, i);
let hi = domain_str_decodeValue(domain, i + STR_VALUE_SIZE);
// either:
// - lo <= lasthi, hi <= lasthi: last range consumes current range (drop it)
// - lo <= lasthi+1: replace lasthi, last range is extended by current range
// - lo >= lasthi+2: flush lasthi, replace lastlo and lasthi, current range becomes last range
//if (lo <= lasthi && hi <= lasthi) {}
//else
if (lo <= lasthi + 1) {
if (hi > lasthi) {
lasthi = hi;
lasthindex = i + STR_VALUE_SIZE;
}
} else {
newDomain += domain[lasthindex] + domain[lasthindex + 1] + domain[i] + domain[i + 1];
lasthi = hi;
lasthindex = i + STR_VALUE_SIZE;
}
}
return newDomain + domain[lasthindex] + domain[lasthindex + 1];
}
/**
* Intersect two $domains.
* Intersection means the result only contains the values
* that are contained in BOTH domains.
*
* @param {$nordom} domain1
* @param {$nordom} domain2
* @returns {$nordom}
*/
function domain_intersection(domain1, domain2) {
if (domain1 === domain2) return domain1;
let isNum1 = typeof domain1 === 'number';
let isNum2 = typeof domain2 === 'number';
if (isNum1 && isNum2) return domain_numnum_intersection(domain1, domain2);
if (isNum1) return domain_numstr_intersection(domain1, domain2);
if (isNum2) return domain_numstr_intersection(domain2, domain1); // swapped!
return domain_strstr_intersection(domain1, domain2);
}
function domain_numnum_intersection(domain1, domain2) {
let sol1 = domain1 >= SOLVED_FLAG;
let sol2 = domain2 >= SOLVED_FLAG;
if (sol1) {
if (sol2) return domain_solsol_intersect(domain1, domain2);
return domain_solbit_intersect(domain1, domain2);
}
if (sol2) return domain_solbit_intersect(domain2, domain1);
return domain_bitbit_intersect(domain1, domain2);
}
function domain_solbit_intersect(soldom, bitdom) {
let solvedValue = soldom ^ SOLVED_FLAG;
if (solvedValue <= SMALL_MAX_NUM && (bitdom & (1 << solvedValue))) return soldom;
return EMPTY;
}
function domain_solsol_intersect(domain1, domain2) {
if (domain1 === domain2) return domain1;
return EMPTY;
}
function domain_bitbit_intersect(domain1, domain2) {
return domain_bitToSmallest(domain1 & domain2);
}
function domain_numstr_intersection(numdom, strdom) {
if (numdom >= SOLVED_FLAG) return domain_solstr_intersect(numdom, strdom);
return domain_bitstr_intersect(numdom, strdom);
}
function domain_solstr_intersect(soldom, strdom) {
let solvedValue = soldom ^ SOLVED_FLAG;
for (let i = 0, len = strdom.length; i < len; i += STR_RANGE_SIZE) {
let lo = domain_str_decodeValue(strdom, i);
let hi = domain_str_decodeValue(strdom, i + STR_VALUE_SIZE);
// once a range is found beyond the solved value we can never find solved value in domain_str
if (solvedValue < lo) break;
// when lo<=value<=hi the intersection is non-empty. return the solved domain.
if (solvedValue <= hi) return soldom;
}
return EMPTY;
}
function domain_bitstr_intersect(bitdom, strdom) {
// TODO: intersect in a "zipper" O(max(n,m)) algorithm instead of O(n*m). see _domain_strstr_intersection
let domain = EMPTY;
for (let i = 0, len = strdom.length; i < len; i += STR_RANGE_SIZE) {
let lo = domain_str_decodeValue(strdom, i);
if (lo > SMALL_MAX_NUM) break;
let hi = domain_str_decodeValue(strdom, i + STR_VALUE_SIZE);
for (let j = lo, m = MIN(SMALL_MAX_NUM, hi); j <= m; ++j) {
let flag = 1 << j;
if (bitdom & flag) domain |= flag; // could be: domain |= domain1 & NUMBER[j]; but this reads better?
}
}
return domain_bitToSmallest(domain);
}
function domain_strstr_intersection(domain1, domain2) {
let len1 = domain1.length;
let len2 = domain2.length;
if ((len1 | len2) === 0) return EMPTY;
let newDomain = EMPTY_STR;
let index1 = 0;
let index2 = 0;
let lo1 = domain_str_decodeValue(domain1, STR_FIRST_RANGE_LO);
let hi1 = domain_str_decodeValue(domain1, STR_FIRST_RANGE_HI);
let lo2 = domain_str_decodeValue(domain2, STR_FIRST_RANGE_LO);
let hi2 = domain_str_decodeValue(domain2, STR_FIRST_RANGE_HI);
while (true) {
if (hi1 < lo2) {
index1 += STR_RANGE_SIZE;
if (index1 >= len1) break;
lo1 = domain_str_decodeValue(domain1, index1);
hi1 = domain_str_decodeValue(domain1, index1 + STR_VALUE_SIZE);
} else if (hi2 < lo1) {
index2 += STR_RANGE_SIZE;
if (index2 >= len2) break;
lo2 = domain_str_decodeValue(domain2, index2);
hi2 = domain_str_decodeValue(domain2, index2 + STR_VALUE_SIZE);
} else {
let mh = MIN(hi1, hi2);
newDomain += domain_str_encodeRange(MAX(lo1, lo2), mh);
// put all ranges after the one we just added...
mh += 2; // last added range + 1 position gap
lo1 = lo2 = mh;
if (hi1 < mh) {
index1 += STR_RANGE_SIZE;
if (index1 >= len1) break;
lo1 = domain_str_decodeValue(domain1, index1);
hi1 = domain_str_decodeValue(domain1, index1 + STR_VALUE_SIZE);
}
if (hi2 < mh) {
index2 += STR_RANGE_SIZE;
if (index2 >= len2) break;
lo2 = domain_str_decodeValue(domain2, index2);
hi2 = domain_str_decodeValue(domain2, index2 + STR_VALUE_SIZE);
}
}
}
if (newDomain === EMPTY_STR) return EMPTY;
return domain_toSmallest(newDomain);
}
/**
* Return a simple string showing the given domain in array
* form and the representation type that was passed on.
*
* @param {$domain} domain
* @returns {string}
*/
function domain__debug(domain) {
if (typeof domain === 'number') {
if (domain >= SOLVED_FLAG) return 'soldom([' + (domain ^ SOLVED_FLAG) + ',' + (domain ^ SOLVED_FLAG) + '])';
return 'numdom([' + domain_numToArr(domain) + '])';
}
if (typeof domain === 'string') return 'strdom([' + domain_strToArr(domain) + '])';
if (domain instanceof Array) return 'arrdom([' + domain + '])';
return '???dom(' + domain + ')';
}
/**
* The idea behind this function - which is primarily
* intended for domain_plus and domain_minus and probably applies
* to nothing else - is that when adding two intervals,
* both intervals expand by the other's amount. This means
* that when given two segmented domains, each continuous
* range expands by at least the interval of the smallest
* range of the other segmented domain. When such an expansion
* occurs, any gaps between subdomains that are <= the smallest
* range's interval width get filled up, which we can exploit
* to reduce the number of segments in a domain. Reducing the
* number of domain segments helps reduce the N^2 complexity of
* the subsequent domain consistent interval addition method.
*
* @param {$strdom} domain1
* @param {$strdom} domain2
* @returns {$strdom[]} NOT smallest! call sites depend on strdom, and they will take care of normalization
*/
function domain_str_closeGaps(domain1, domain2) {
if (domain1 && domain2) {
let change;
do {
change = 0;
if (domain1.length > STR_RANGE_SIZE) {
let smallestRangeSize = domain_str_smallestRangeSize(domain2);
let domain = _domain_str_closeGaps(domain1, smallestRangeSize);
change += domain1.length - domain.length;
domain1 = domain;
}
if (domain2.length > STR_RANGE_SIZE) {
let smallestRangeSize = domain_str_smallestRangeSize(domain1);
let domain = _domain_str_closeGaps(domain2, smallestRangeSize);
change += domain2.length - domain.length;
domain2 = domain;
}
} while (change !== 0);
}
// TODO: we could return a concatted string and prefix the split, instead of this temporary array...
return [
domain1,
domain2,
];
}
/**
* Closes all the gaps between the intervals according to
* the given gap value. All gaps less than this gap are closed.
* Domain is not harmed
*
* @param {$strdom} domain
* @param {number} gap
* @returns {$strdom} (min/max won't be eliminated and input should be a "large" domain)
*/
function _domain_str_closeGaps(domain, gap) {
let newDomain = domain[STR_FIRST_RANGE_LO] + domain[STR_FIRST_RANGE_LO + 1];
let lasthi = domain_str_decodeValue(domain, STR_FIRST_RANGE_HI);
let lasthindex = STR_FIRST_RANGE_HI;
for (let i = STR_RANGE_SIZE, len = domain.length; i < len; i += STR_RANGE_SIZE) {
let lo = domain_str_decodeValue(domain, i);
let hi = domain_str_decodeValue(domain, i + STR_VALUE_SIZE);
if ((lo - lasthi) > gap) {
newDomain += domain[lasthindex] + domain[lasthindex + 1] + domain[i] + domain[i + 1];
}
lasthi = hi;
lasthindex = i + STR_VALUE_SIZE;
}
newDomain += domain[lasthindex] + domain[lasthindex + 1];
return newDomain;
}
/**
* @param {$strdom} domain
* @returns {number}
*/
function domain_str_smallestRangeSize(domain) {
let min_width = SUP;
for (let i = 0, len = domain.length; i < len; i += STR_RANGE_SIZE) {
let lo = domain_str_decodeValue(domain, i);
let hi = domain_str_decodeValue(domain, i + STR_VALUE_SIZE);
let width = 1 + hi - lo;
if (width < min_width) {
min_width = width;
}
}
return min_width;
}
/**
* Note that this one isn't domain consistent.
*
* @param {$nordom} domain1
* @param {$nordom} domain2
* @returns {$domain}
*/
function domain_mul(domain1, domain2) {
// TOFIX: quick shortcut for solved domains
// for simplicity sake, convert them back to arrays
if (typeof domain1 === 'number') domain1 = domain_numToStr(domain1);
if (typeof domain2 === 'number') domain2 = domain_numToStr(domain2);
// TODO domain_mulNum
return domain_strstr_mul(domain1, domain2);
}
function domain_strstr_mul(domain1, domain2) {
let result = EMPTY_STR;
for (let i = 0, leni = domain1.length; i < leni; i += STR_RANGE_SIZE) {
let lo = domain_str_decodeValue(domain1, i);
let hi = domain_str_decodeValue(domain1, i + STR_VALUE_SIZE);
result += _domain_str_mulByRange(domain2, lo, hi);
}
// TODO: is it worth doing this step immediately?
return domain_str_simplify(result);
}
/**
* Multiply a domain by given range
*
* @param {$strdom} strdom
* @param {number} lo
* @param {number} hi
* @returns {$strdom} NOT normalized
*/
function _domain_str_mulByRange(strdom, lo, hi) {
let result = EMPTY_STR;
for (let j = 0, len = strdom.length; j < len; j += STR_RANGE_SIZE) {
let loj = domain_str_decodeValue(strdom, j);
let hij = domain_str_decodeValue(strdom, j + STR_VALUE_SIZE);
result += domain_str_encodeRange(MIN(SUP, lo * loj), MIN(SUP, hi * hij));
}
return result;
}
/**
* Multiply given domain by a single value
* [1, 10] * 5 = [5, 50]
*
* @param {$nordom} domain
* @param {number} value
* @returns {$nordom}
*/
function domain_mulByValue(domain, value) {
if (typeof domain === 'number') domain = domain_numToStr(domain);
domain = _domain_str_mulByRange(domain, value, value);
return domain_str_simplify(domain);
}
/**
* Divide one range by another
* Result has any integer values that are equal or between
* the real results. This means fractions are floored/ceiled.
* This is an expensive operation.
* Zero is a special case.
*
* Does not harm input domains
*
* @param {$nordom} domain1
* @param {$nordom} domain2
* @param {boolean} [floorFractions=true] Include the floored lo of the resulting ranges?
* For example, <5,5>/<2,2> is <2.5,2.5>. If this flag is true, it will include
* <2,2>, otherwise it will not include anything for that division.
* @returns {$nordom}
*/
function domain_divby(domain1, domain2, floorFractions = true) {
// TOFIX: add quick shortcut for solved domains
// for simplicity sake, convert them back to arrays
if (typeof domain1 === 'number') domain1 = domain_numToStr(domain1);
if (typeof domain2 === 'number') domain2 = domain_numToStr(domain2);
// TODO: domain_divByNum
return domain_strstr_divby(domain1, domain2, floorFractions);
}
function domain_strstr_divby(domain1, domain2, floorFractions = true) {
let result = EMPTY_STR;
for (let i = 0, leni = domain2.length; i < leni; i += STR_RANGE_SIZE) {
let lo = domain_str_decodeValue(domain2, i);
let hi = domain_str_decodeValue(domain2, i + STR_VALUE_SIZE);
result += _domain_str_divbyRange(domain1, lo, hi, floorFractions);
}
return domain_str_simplify(result);
}
function _domain_str_divbyRange(strdom, divisorLo, divisorHi, floorFractions) {
// Division: Dividend / Divisor = Quotient
let result = EMPTY_STR;
for (let j = 0, lenj = strdom.length; j < lenj; j += STR_RANGE_SIZE) {
let dividendLo = domain_str_decodeValue(strdom, j);
let dividendHi = domain_str_decodeValue(strdom, j + STR_VALUE_SIZE);
// cannot /0
// we ignore it right now. should we...
// - add a 0 or SUB or SUP for it
// - throw an error / issue a warning for it
if (divisorHi > 0) {
let quotientLo = dividendLo / divisorHi;
let quotientHi = divisorLo > 0 ? dividendHi / divisorLo : SUP;
// we cant use fractions, so we'll only include any values in the
// resulting domains that are _above_ the lo and _below_ the hi.
let left = CEIL(quotientLo);
let right = FLOOR(quotientHi);
// if the fraction is within the same integer this could result in
// lo>hi so we must prevent this case
if (left <= right) {
result += domain_str_encodeRange(left, right);
} else {
if (floorFractions) {
// only use the floored value
// note: this is a choice. not both floor/ceil because then 5/2=2.5 becomes [2,3]. should be [2,2] or [3,3]
result += domain_str_encodeRange(right, right);
}
}
}
}
return result;
}
function domain_divByValue(domain, value) {
if (typeof domain === 'number') domain = domain_numToStr(domain);
let domain2 = _domain_str_divbyRange(domain, value, value);
return domain_str_simplify(domain2);
}
/**
* Do the opposite of a mul. This is _like_ a div but there
* are special cases for zeroes and fractions:
* - x * y = 0
* - x / 0 = y (not infinity)
* - y / 0 = x (not infinity)
* - 2 * x = [2, 3]
* - 2 / [1, 3] = x (integer division so x=1)
* - x / [1, 3] = 2
*
* @param {$nordom} domain1
* @param {$nordom} domain2
* @returns {$nordom}
*/
function domain_invMul(domain1, domain2) {
// TOFIX: add quick shortcut for solved domains
// for simplicity sake, convert them back to arrays
if (typeof domain1 === 'number') domain1 = domain_numToStr(domain1);
if (typeof domain2 === 'number') domain2 = domain_numToStr(domain2);
// TODO: domain_divByNum
return domain_strstr_invMul(domain1, domain2);
}
function domain_strstr_invMul(domain1, domain2) {
let result = EMPTY_STR;
for (let i = 0, len = domain2.length; i < len; i += STR_RANGE_SIZE) {
let lo = domain_str_decodeValue(domain2, i);
let hi = domain_str_decodeValue(domain2, i + STR_VALUE_SIZE);
result += _domain_str_invMulRange(domain1, lo, hi);
}
return domain_str_simplify(result);
}
function _domain_str_invMulRange(domain, divisorLo, divisorHi) {
// note: act like div but do exact opposite of mul regardless
// all we worry about is the zero since input is >=0 and finite
let result = EMPTY_STR;
for (let i = 0, len = domain.length; i < len; i += STR_RANGE_SIZE) {
let dividendLo = domain_str_decodeValue(domain, i);
let dividendHi = domain_str_decodeValue(domain, i + STR_VALUE_SIZE);
let quotientLo = divisorHi ? (dividendLo / divisorHi) : SUB; // use SUB if /0
let quotientHi = divisorLo ? (dividendHi / divisorLo) : SUP; // use SUP if /0
// only care about the integers within the division range
let lo = CEIL(quotientLo);
let hi = FLOOR(quotientHi);
// if the lo hi quotients are inside the same integer, the result is empty
if (lo <= hi) {
result += domain_str_encodeRange(lo, hi);
}
}
return result;
}
function domain_invMulValue(domain, value) {
if (typeof domain === 'number') domain = domain_numToStr(domain);
let domain2 = _domain_str_invMulRange(domain, value, value);
return domain_str_simplify(domain2);
}
/**
* Return the number of elements this domain covers
*
* @param {$nordom} domain
* @returns {number}
*/
function domain_size(domain) {
if (typeof domain === 'number') return domain_num_size(domain);
return domain_str_size(domain);
}
function domain_num_size(domain) {
if (domain >= SOLVED_FLAG) return 1;
return domain_bit_size(domain);
}
function domain_bit_size(domain) {
// need to work on this one because it requires 64bits. should be doable, to revisit later
// domain = (domain - (((domain >>> 1) & 0x55555555))) | 0;
// domain = ((domain & 0x33333333) + ((domain >>> 2) & 0x33333333)) | 0;
// domain = ((+((domain + (domain >>> 4)) & 0x0F0F0F0F) * +0x01010101)|0) >>> 24;
// return domain;
// hot paths; binary
// the empty domain is "free"
switch (domain) {
case 0: return 0; // empty domain
case 1: return 1;
case 2: return 1;
case 3: return 2;
}
return (
(domain & 1) +
((domain >> 1) & 1) +
((domain >> 2) & 1) +
((domain >> 3) & 1) +
((domain >> 4) & 1) +
((domain >> 5) & 1) +
((domain >> 6) & 1) +
((domain >> 7) & 1) +
((domain >> 8) & 1) +
((domain >> 9) & 1) +
((domain >> 10) & 1) +
((domain >> 11) & 1) +
((domain >> 12) & 1) +
((domain >> 13) & 1) +
((domain >> 14) & 1) +
((domain >> 15) & 1) +
((domain >> 16) & 1) +
((domain >> 17) & 1) +
((domain >> 18) & 1) +
((domain >> 19) & 1) +
((domain >> 20) & 1) +
((domain >> 21) & 1) +
((domain >> 22) & 1) +
((domain >> 23) & 1) +
((domain >> 24) & 1) +
((domain >> 25) & 1) +
((domain >> 26) & 1) +
((domain >> 27) & 1) +
((domain >> 28) & 1) +
((domain >> 29) & 1) +
((domain >> 30) & 1) +
((domain >> 31) & 1)
) | 0;
}
function domain_str_size(domain) {
let count = 0;
for (let i = 0, len = domain.length; i < len; i += STR_RANGE_SIZE) {
// TODO: add test to confirm this still works fine if SUB is negative
count += 1 + domain_str_decodeValue(domain, i + STR_VALUE_SIZE) - domain_str_decodeValue(domain, i);
}
return count;
}
/**
* Get the middle element of all elements in domain.
* Not hi-lo/2 but the (size/2)th element.
* For domains with an even number of elements it
* will take the first value _above_ the middle,
* in other words; index=ceil(count/2).
*
* @param {$nordom} domain
* @returns {number} can return
*/
function domain_middleElement(domain) {
if (typeof domain === 'number') {
if (domain >= SOLVED_FLAG) return domain ^ SOLVED_FLAG;
// for simplicity sake, convert them back to arrays
domain = domain_numToStr(domain);
}
// TODO: domain_middleElementNum(domain);
return domain_str_middleElement(domain);
}
function domain_str_middleElement(domain) {
if (!domain) return NO_SUCH_VALUE;
let size = domain_str_size(domain);
let targetValue = FLOOR(size / 2);
let lo;
let hi;
for (let i = 0, len = domain.length; i < len; i += STR_RANGE_SIZE) {
lo = domain_str_decodeValue(domain, i);
hi = domain_str_decodeValue(domain, i + STR_VALUE_SIZE);
let count = 1 + hi - lo;
if (targetValue < count) {
break;
}
targetValue -= count;
}
// `targetValue` should be the `nth` element in the current range (`lo-hi`)
// so we can use `lo` and add the remainder of `targetValue` to get the mid value
return lo + targetValue;
}
/**
* Get lowest value in the domain
* Only use if callsite doesn't need to cache first range (because array access)
*
* @param {$nordom} domain
* @returns {number}
*/
function domain_min(domain) {
if (typeof domain === 'number') return domain_num_min(domain);
return domain_str_min(domain);
}
function domain_num_min(domain) {
if (domain >= SOLVED_FLAG) return domain_sol_min(domain);
return domain_bit_min(domain);
}
function domain_sol_min(domain) {
return domain ^ SOLVED_FLAG;
}
function domain_bit_min(domain) {
// This is also called a "bitscan" or "bitscan forward" because
// in a small domain we want to know the index of the least
// significant bit that is set. A different way of looking at
// this is that we'd want to know the number of leading zeroes
// ("clz") in the number because we would just need to +1 that
// to get our desired value. There are various solutiosn to
// this problem but some are not feasible to implement in JS
// because we can't rely on low level optimizations. And
// certainly we can't use the cpu machine instruction.
//
// Be aware that there are about a million ways to do this,
// even to do this efficiently. Mileage under JS varies hto.
//
// ES6 _does_ expose `Math.clz32()` so if we can be certain
// it is natively supported we should go with that and hope
// it becomes a single instruction. Don't rely on a polyfill.
// fast paths: these are by far the most used case in our situation
if ((domain | 0) === 1) return 0;
if ((domain | 0) === 2) return 1;
if ((domain | 0) === 3) return 0;
// from https://graphics.stanford.edu/~seander/bithacks.html#ZerosOnRightModLookup
// the table lookup is unfortunate. the mod is probably slow for us but hard to tell
// the difference so let's not care for now.
switch (((domain & -domain) % 37) | 0) {
case 0:
//return 32;
return -1; // note: we dont use bits 31 and 32 so we can check for empty domain here "for free"
case 1: // does not exist within 32bits
return 0;
case 2:
return 1;
case 3:
return 26;
case 4:
return 2;
case 5:
return 23;
case 6:
return 27;
case 7: // does not exist within 32bits
return 0;
case 8:
return 3;
case 9:
return 16;
case 10:
return 24;
case 11:
return 30; // should not be possible. implies soldom (to 30).
case 12:
return 28;
case 13:
return 11;
case 14: // does not exist within 32bits
return 0;
case 15:
return 13;
case 16:
return 4;
case 17:
return 7;
case 18:
return 17;
case 19: // does not exist within 32bits
return 0;
case 20:
return 25;
case 21:
return 22;
case 22:
//return 31;
return -1; // we dont use the last bit
case 23:
return 15;
case 24:
return 29;
case 25:
return 10;
case 26:
return 12;
case 27:
return 6;
case 28: // does not exist within 32bits
return 0;
case 29:
return 21;
case 30:
return 14;
case 31:
return 9;
case 32:
return 5;
case 33:
return 20;
case 34:
return 8;
case 35:
return 19;
}
// case 36:
return 18;
}
function domain_str_min(domain) {
if (!domain) return NO_SUCH_VALUE;
return domain_str_decodeValue(domain, STR_FIRST_RANGE_LO);
}
/**
* Only use if callsite doesn't use last range again
*
* @param {$nordom} domain
* @returns {number} can be NO_SUCH_VALUE
*/
function domain_max(domain) {
if (typeof domain === 'number') return domain_num_max(domain);
return domain_str_max(domain);
}
function domain_num_max(domain) {
if (domain >= SOLVED_FLAG) return domain_sol_max(domain);
return domain_bit_max(domain);
}
function domain_sol_max(domain) {
return domain ^ SOLVED_FLAG;
}
function domain_bit_max(domain) {
// Relatively expensive because there's no easy trick.
var i = 30;
// fast paths: these are by far the most used case in our situation
// (the empty domain check is "free" here)
switch (domain | 0) {
case 0:
return -1; // empty domain
case 1:
return 0; // should not be possible. implies a soldom
case 2:
return 1;
case 3:
return 1;
}
// there's no pretty way to do this
do {
if (domain & (1 << i)) break;
i = (i - 1) | 0;
} while ((i | 0) >= 0);
return i | 0; // note: the 31 case is unused in our system and assumed impossible here
}
function domain_str_max(domain) {
if (!domain) return NO_SUCH_VALUE;
// last encoded value in the string should be the hi of the last range. so max is last value
return domain_str_decodeValue(domain, domain.length - STR_VALUE_SIZE);
}
function domain_arr_max(domain) {
let len = domain.length;
if (len === 0) return NO_SUCH_VALUE;
return domain[len - 1];
}
/**
* A domain is "solved" if it covers exactly one value. It is not solved if it is empty.
*
* @param {$nordom} domain
* @returns {boolean}
*/
function domain_isSolved(domain) {
return typeof domain === 'number' && domain >= SOLVED_FLAG;
}
/**
* Is given domain empty?
* Assuming a nordom, the only value that returns true is EMPTY.
* Minifier or browser should eliminate this function.
*
* @param {$nordom} domain
* @returns {boolean}
*/
function domain_isEmpty(domain) {
return domain === EMPTY;
}
/**
* Remove all values from domain that are greater
* than or equal to given value
*
* @param {$domain} domain
* @param {number} value
* @returns {$domain}
*/
function domain_removeGte(domain, value) {
if (typeof domain === 'number') return domain_num_removeGte(domain, value);
return domain_str_removeGte(domain, value);
}
function domain_num_removeGte(domain, value) {
if (domain >= SOLVED_FLAG) return domain_sol_removeGte(domain, value);
return domain_bitToSmallest(domain_bit_removeGte(domain, value));
}
function domain_sol_removeGte(domain, value) {
// (could we just do `return (domain >= (value|SOLVED_FLAG)) ? EMPTY : domain` ?)
let solvedValue = domain ^ SOLVED_FLAG;
if (solvedValue >= value) return EMPTY;
return domain; // no change
}
/**
* Remove all values from domain that are greater
* than or equal to given value
*
* @param {$numdom} domain
* @param {number} value NOT a flag
* @returns {$numdom}
*/
function domain_bit_removeGte(domain, value) {
switch (value) {
case 0:
return 0;
case 1:
return domain & 0x00000001;
case 2:
return domain & 0x00000003;
case 3:
return domain & 0x00000007;
case 4:
return domain & 0x0000000f;
case 5:
return domain & 0x0000001f;
case 6:
return domain & 0x0000003f;
case 7:
return domain & 0x0000007f;
case 8:
return domain & 0x000000ff;
case 9:
return domain & 0x000001ff;
case 10:
return domain & 0x000003ff;
case 11:
return domain & 0x000007ff;
case 12:
return domain & 0x00000fff;
case 13:
return domain & 0x00001fff;
case 14:
return domain & 0x00003fff;
case 15:
return domain & 0x00007fff;
case 16:
return domain & 0x0000ffff;
case 17:
return domain & 0x0001ffff;
case 18:
return domain & 0x0003ffff;
case 19:
return domain & 0x0007ffff;
case 20:
return domain & 0x000fffff;
case 21:
return domain & 0x001fffff;
case 22:
return domain & 0x003fffff;
case 23:
return domain & 0x007fffff;
case 24:
return domain & 0x00ffffff;
case 25:
return domain & 0x01ffffff;
case 26:
return domain & 0x03ffffff;
case 27:
return domain & 0x07ffffff;
case 28:
return domain & 0x0fffffff;
case 30:
return domain; // assuming domain is "valid" we can just return it now.
}
return domain; // when value > 30
}
/**
* Remove any value from domain that is bigger than or equal to given value.
* Since domains are assumed to be in CSIS form, we can start from the back and
* search for the first range that is smaller or contains given value. Prune
* any range that follows it and trim the found range if it contains the value.
* Returns whether the domain was changed somehow.
*
* @param {$strdom} strdom
* @param {number} value
* @returns {$strdom}
*/
function domain_str_removeGte(strdom, value) {
for (let i = 0, len = strdom.length; i < len; i += STR_RANGE_SIZE) {
let lo = domain_str_decodeValue(strdom, i);
let hi = domain_str_decodeValue(strdom, i + STR_VALUE_SIZE);
// case: v=5
// 012 456 // => 012 4
// 012 45 // => 012 4
// 012 567 // => 012
// 012 5 // => 012
// 012 678 // => 012
// 012 // => NONE
// 678 // => empty
// TODO: if we know the returned domain is a small domain we should prevent the slice at all.
if (lo >= value) {
// >
// 67 9 -> empty
// 012 789 -> 012
// ==
// 567 9 -> empty
// 012 567 -> 012
// 012 5 -> 012
// 5 ->
if (!i) return EMPTY;
return domain_toSmallest(strdom.slice(0, i));
}
if (value <= hi) {
if (i === 0 && value === lo + 1) {
// domain_createValue(lo);
let slo = strdom.slice(0, STR_VALUE_SIZE);
return domain_toSmallest(slo + slo);
}
// 012 456 -> 012 4
// 012 45 -> 012 4
let newDomain = strdom.slice(0, i + STR_VALUE_SIZE) + domain_str_encodeValue(value - 1);
//if (value - 1 <= SMALL_MAX_NUM) return newDomain;
return domain_toSmallest(newDomain);
}
}
return strdom; // 012 -> 012
}
/**
* Remove all values from domain that are lower
* than or equal to given value
*
* @param {$domain} domain
* @param {number} value
* @returns {$domain}
*/
function domain_removeLte(domain, value) {
if (typeof domain === 'number') return domain_num_removeLte(domain, value);
return domain_str_removeLte(domain, value);
}
function domain_num_removeLte(domain, value) {
if (domain >= SOLVED_FLAG) return domain_sol_removeLte(domain, value);
return domain_toSmallest(domain_bit_removeLte(domain, value));
}
function domain_sol_removeLte(domain, value) {
// (could we just do `return (domain <= (value|SOLVED_FLAG)) ? EMPTY : domain` ?)
let solvedValue = domain ^ SOLVED_FLAG;
if (solvedValue <= value) return EMPTY;
return domain; // no change
}
/**
* Remove all values from domain that are lower
* than or equal to given value
*
* @param {$numdom} domain
* @param {number} value NOT a flag
* @returns {$numdom}
*/
function domain_bit_removeLte(domain, value) {
switch (value) {
case 0:
return domain & 0x7ffffffe;
case 1:
return domain & 0x7ffffffc;
case 2:
return domain & 0x7ffffff8;
case 3:
return domain & 0x7ffffff0;
case 4:
return domain & 0x7fffffe0;
case 5:
return domain & 0x7fffffc0;
case 6:
return domain & 0x7fffff80;
case 7:
return domain & 0x7fffff00;
case 8:
return domain & 0x7ffffe00;
case 9:
return domain & 0x7ffffc00;
case 10:
return domain & 0x7ffff800;
case 11:
return domain & 0x7ffff000;
case 12:
return domain & 0x7fffe000;
case 13:
return domain & 0x7fffc000;
case 14:
return domain & 0x7fff8000;
case 15:
return domain & 0x7fff0000;
case 16:
return domain & 0x7ffe0000;
case 17:
return domain & 0x7ffc0000;
case 18:
return domain & 0x7ff80000;
case 19:
return domain & 0x7ff00000;
case 20:
return domain & 0x7fe00000;
case 21:
return domain & 0x7fc00000;
case 22:
return domain & 0x7f800000;
case 23:
return domain & 0x7f000000;
case 24:
return domain & 0x7e000000;
case 25:
return domain & 0x7c000000;
case 26:
return domain & 0x78000000;
case 27:
return domain & 0x70000000;
case 28:
return domain & 0x60000000;
case 29:
return domain & 0x40000000;
case 30:
return 0; // assuming domain is "valid" this should remove all elements
}
if (value < 0) return domain;
return 0;
}
/**
* Remove any value from domain that is lesser than or equal to given value.
* Since domains are assumed to be in CSIS form, we can start from the front and
* search for the first range that is smaller or contains given value. Prune
* any range that preceeds it and trim the found range if it contains the value.
* Returns whether the domain was changed somehow
* Does not harm domain
*
* @param {$strdom} strdom
* @param {number} value
* @returns {$nordom}
*/
function domain_str_removeLte(strdom, value) {
for (let i = 0, len = strdom.length; i < len; i += STR_RANGE_SIZE) {
let lo = domain_str_decodeValue(strdom, i);
let hi = domain_str_decodeValue(strdom, i + STR_VALUE_SIZE);
// case: v=5
// 456 89 => 6 89
// 45 89 => 89
// 56 89 => 6 89
// 5 89 => 5 89
// 6788 => 67 9
// 789 => NONE
// 012 => empty
if (lo > value) {
// 678 -> 678
if (!i) return domain_toSmallest(strdom);
// 234 678 -> 678
return domain_toSmallest(strdom.slice(i));
}
if (hi === value) {
// 45 89 => 89
// 5 89 => 5 89
// 15 =>
if (i >= len - STR_RANGE_SIZE) return EMPTY;
return domain_toSmallest(strdom.slice(i + STR_RANGE_SIZE));
}
if (value <= hi) {
// 456 89 => 6 89
// 56 89 => 6 89
return domain_toSmallest(domain_str_encodeValue(value + 1) + strdom.slice(i + STR_VALUE_SIZE));
}
}
return EMPTY; // 012 -> empty
}
/**
* Remove given value from given domain and return
* the new domain that doesn't contain it.
*
* @param {$domain} domain
* @param {number} value
* @returns {$domain}
*/
function domain_removeValue(domain, value) {
if (typeof domain === 'number') return domain_num_removeValue(domain, value);
return domain_toSmallest(domain_str_removeValue(domain, value));
}
/**
* @param {$numdom} domain
* @param {number} value
* @returns {$domain}
*/
function domain_num_removeValue(domain, value) {
if (domain >= SOLVED_FLAG) return domain_sol_removeValue(domain, value);
return domain_bit_removeValue(domain, value);
}
function domain_sol_removeValue(domain, value) {
if (value === (domain ^ SOLVED_FLAG)) return EMPTY;
return domain;
}
/**
* @param {$bitdom} domain
* @param {number} value NOT a flag
* @returns {$bitdom}
*/
function domain_bit_removeValue(domain, value) {
if (value > 30) return domain_toSmallest(domain); // though probably already fine, we dont know what `domain` is here
let flag = 1 << value;
return domain_bitToSmallest((domain | flag) ^ flag);
}
/**
* @param {$strdom} domain
* @param {number} value
* @returns {$domain} should be smallest
*/
function domain_str_removeValue(domain, value) {
let lastLo = -1;
let lastHi = -1;
for (let i = 0, len = domain.length; i < len; i += STR_RANGE_SIZE) {
let lo = domain_str_decodeValue(domain, i);
// domain is CSIS so once a range was found beyond value, no further ranges can possibly wrap value. return now.
if (value < lo) break;
let hi = domain_str_decodeValue(domain, i + STR_VALUE_SIZE);
if (value <= hi) {
return _domain_str_removeValue(domain, len, i, lo, hi, value, lastLo, lastHi);
}
lastLo = lo;
lastHi = hi;
}
// "no change" because domain was not found.
return domain;
}
function _domain_str_removeValue(domain, len, index, lo, hi, value, lastLo, lastHi) {
// normalize to (solved) numdom if the result is solved:
// - one range and it contains two values: solved numdom
// - oen range and it contains one value: EMPTY
// - two ranges and both have one value: solved numdom
// - removed value is >MAX_NUMDOM_VALUE and new highest value <=MAX_NUMDOM_VALUE: numdom
// - must remove highest value of dom. either
// - from a range of >=2 values (check hi-1)
// - from range with one value (check lastHi)
if (len === STR_RANGE_SIZE) {
if (hi - lo === 1) return ((lo === value ? hi : lo) | SOLVED_FLAG) >>> 0;
if (lo === hi) return EMPTY;
} else if (index && len === 2 * STR_RANGE_SIZE && lo === hi && lastLo === lastHi) {
return (lastLo | SOLVED_FLAG) >>> 0;
}
if (index === len - STR_RANGE_SIZE && value === hi) {
// to numdom checks
if (lo === hi && lastHi <= SMALL_MAX_NUM) {
// numdom excluding the last range
let newLen = len - STR_RANGE_SIZE;
return domain_strToBit(domain.slice(0, newLen), newLen);
} else if (hi - 1 <= SMALL_MAX_NUM) {
// numdom excluding last value of last range
// (the encodeValue step is unfortunate but let's KISS)
return domain_strToBit(domain.slice(0, -STR_VALUE_SIZE) + domain_str_encodeValue(hi - 1), len);
}
}
// from this point onward we'll return a strdom
let before = domain.slice(0, index);
let after = domain.slice(index + STR_RANGE_SIZE);
if (hi === value) {
if (lo === value) {
// lo=hi=value; drop this range completely
return before + after;
}
return before + domain_str_encodeRange(lo, hi - 1) + after;
} else if (lo === value) {
return before + domain_str_encodeRange(lo + 1, hi) + after;
} else {
// we get new two ranges...
return before + domain_str_encodeRange(lo, value - 1) + domain_str_encodeRange(value + 1, hi) + after;
}
}
/**
* Check if every element in one domain not
* occur in the other domain and vice versa
*
* @param {$domain} domain1
* @param {$domain} domain2
* @returns {boolean}
*/
function domain_sharesNoElements(domain1, domain2) {
let isNum1 = typeof domain1 === 'number';
let isNum2 = typeof domain2 === 'number';
if (isNum1 && isNum2) return domain_numnum_sharesNoElements(domain1, domain2);
if (isNum1) return domain_numstr_sharesNoElements(domain1, domain2);
if (isNum2) return domain_numstr_sharesNoElements(domain2, domain1);
return domain_strstr_sharesNoElements(domain1, domain2);
}
function domain_numnum_sharesNoElements(domain1, domain2) {
if (domain1 >= SOLVED_FLAG) {
if (domain2 >= SOLVED_FLAG) return domain_solsol_sharesNoElements(domain1, domain2);
return domain_solbit_sharesNoElements(domain1, domain2);
}
if (domain2 >= SOLVED_FLAG) return domain_solbit_sharesNoElements(domain2, domain1);
return domain_bitbit_sharesNoElements(domain1, domain2);
}
function domain_solsol_sharesNoElements(domain1, domain2) {
return domain1 !== domain2;
}
function domain_solbit_sharesNoElements(soldom, bitsol) {
let solvedValue = soldom ^ SOLVED_FLAG;
if (solvedValue > SMALL_MAX_NUM) return true;
return (bitsol & (1 << solvedValue)) === 0;
}
/**
* Check if every element in one domain does not
* occur in the other domain and vice versa
*
* @param {$numdom} domain1
* @param {$numdom} domain2
* @returns {boolean}
*/
function domain_bitbit_sharesNoElements(domain1, domain2) {
// checks whether not a single bit in set in _both_ domains
return (domain1 & domain2) === 0;
}
/**
* Check if every element in one domain not
* occur in the other domain and vice versa
*
* @param {$numdom} numdom
* @param {$strdom} strdom
* @returns {boolean}
*/
function domain_numstr_sharesNoElements(numdom, strdom) {
if (numdom >= SOLVED_FLAG) return domain_solstr_sharesNoElements(numdom, strdom);
return domain_bitstr_sharesNoElements(numdom, strdom);
}
function domain_solstr_sharesNoElements(soldom, strdom) {
let solvedValue = soldom ^ SOLVED_FLAG;
for (let strIndex = 0, strlen = strdom.length; strIndex < strlen; strIndex += STR_RANGE_SIZE) {
let lo = domain_str_decodeValue(strdom, strIndex);
let hi = domain_str_decodeValue(strdom, strIndex + STR_VALUE_SIZE);
if (solvedValue < lo) return true; // solved value not found so element not shared
if (solvedValue <= hi) return false; // solved value is in current range so element shared
}
// did not find a range that contained value so no element shared
return true;
}
function domain_bitstr_sharesNoElements(bitdom, strdom) {
let strIndex = 0;
let strlen = strdom.length;
for (let numIndex = 0; numIndex <= SMALL_MAX_NUM; ++numIndex) {
if (bitdom & (1 << numIndex)) {
// find numIndex (as value) in domain_str. return true when
// found. return false if number above small_max_num is found
while (strIndex < strlen) {
let lo = domain_str_decodeValue(strdom, strIndex);
let hi = domain_str_decodeValue(strdom, strIndex + STR_VALUE_SIZE);
// there is overlap if numIndex is within current range so return false
if (numIndex >= lo && numIndex <= hi) return false;
// the next value in domain_num can not be smaller and the previous
// domain_str range was below that value and the next range is beyond
// the small domain max so there can be no more matching values
if (lo > SMALL_MAX_NUM) return true;
// this range is bigger than target value so the value doesnt
// exist; skip to next value
if (lo > numIndex) break;
strIndex += STR_RANGE_SIZE;
}
if (strIndex >= strlen) return true;
}
}
return true; // dead code?
}
/**
* Check if every element in one domain not
* occur in the other domain and vice versa
*
* @param {$strdom} domain1
* @param {$strdom} domain2
* @returns {boolean}
*/
function domain_strstr_sharesNoElements(domain1, domain2) {
let len1 = domain1.length;
let len2 = domain2.length;
let index1 = 0;
let index2 = 0;
let lo1 = domain_str_decodeValue(domain1, STR_FIRST_RANGE_LO);
let hi1 = domain_str_decodeValue(domain1, STR_FIRST_RANGE_HI);
let lo2 = domain_str_decodeValue(domain2, STR_FIRST_RANGE_LO);
let hi2 = domain_str_decodeValue(domain2, STR_FIRST_RANGE_HI);
while (true) {
if (hi1 < lo2) {
index1 += STR_RANGE_SIZE;
if (index1 >= len1) break;
lo1 = domain_str_decodeValue(domain1, index1);
hi1 = domain_str_decodeValue(domain1, index1 + STR_VALUE_SIZE);
} else if (hi2 < lo1) {
index2 += STR_RANGE_SIZE;
if (index2 >= len2) break;
lo2 = domain_str_decodeValue(domain2, index2);
hi2 = domain_str_decodeValue(domain2, index2 + STR_VALUE_SIZE);
} else {
return false;
}
}
// no overlaps found
return true;
}
/**
* @param {number} value
* @returns {$domain} will be a soldom
*/
function domain_createValue(value) {
return (value | SOLVED_FLAG) >>> 0;
}
/**
* @param {number} lo
* @param {number} hi
* @returns {$domain}
*/
function domain_createRange(lo, hi) {
if (lo === hi) return domain_createValue(lo);
if (hi <= SMALL_MAX_NUM) return domain_num_createRange(lo, hi);
return domain_str_encodeRange(lo, hi);
}
/**
* @param {number} lo
* @param {number} hi
* @returns {$bitdom}
*/
function domain_num_createRange(lo, hi) {
return (((1 << (1 + hi - lo)) - 1) << lo);
}
/**
* This function mainly prevents leaking EMPTY outside of domain.js
* Browsers should optimize this away, if the minifier didn't already.
*
* @returns {$numdom}
*/
function domain_createEmpty() {
return EMPTY;
}
/**
* Return a domain containing all numbers from zero to the highest
* number in given domain. In binary this means we'll set all the
* bits of lower value than the most-significant set bit.
*
* @param {$numdom} domain_num Must be > ZERO
* @returns {$domain} never solved since that requires ZERO to be a valid input, which it isnt
*/
function domain_numnum_createRangeZeroToMax(domain_num) {
//if (domain_num === (1 << 0)) return SOLVED_FLAG; // note: SOLVED_FLAG|0 === SOLVED_FLAG.
domain_num = domain_num | (domain_num >> 1);
domain_num = domain_num | (domain_num >> 2);
domain_num = domain_num | (domain_num >> 4);
domain_num = domain_num | (domain_num >> 8);
domain_num = domain_num | (domain_num >> 16);
return domain_num;
}
/**
* Get a domain representation in array form
*
* @param {$domain} domain
* @param {boolean} [clone] If input is array, slice the array? (other cases will always return a fresh array)
* @returns {$arrdom} (small domains will also be arrays)
*/
function domain_toArr(domain, clone) {
if (typeof domain === 'number') return domain_numToArr(domain);
if (typeof domain === 'string') return domain_strToArr(domain);
if (clone) return domain.slice(0);
return domain;
}
function domain_numToArr(domain) {
if (domain >= SOLVED_FLAG) return domain_solToArr(domain);
return domain_bitToArr(domain);
}
function domain_solToArr(domain) {
let solvedValue = domain ^ SOLVED_FLAG;
return [solvedValue, solvedValue];
}
function domain_bitToArr(domain) {
if (domain === EMPTY) return [];
let arr = [];
let lo = -1;
let hi = -1;
if ((1 << 0) & domain) {
lo = 0;
hi = 0;
}
if ((1 << 1) & domain) {
if (lo !== 0) { // lo is either 0 or nothing
lo = 1;
}
hi = 1; // there cannot be a gap yet
}
if ((1 << 2) & domain) {
if (hi === 0) {
arr.push(0, 0);
lo = 2;
} else if (hi !== 1) {
// if hi isnt 0 and hi isnt 1 then hi isnt set and so lo isnt set
lo = 2;
}
hi = 2;
}
if ((1 << 3) & domain) {
if (hi < 0) { // this is the LSB that is set
lo = 3;
} else if (hi !== 2) { // there's a gap so push prev range now
arr.push(lo, hi);
lo = 3;
}
hi = 3;
}
// is the fifth bit or higher even set at all? for ~85% that is not the case at this point
if (domain >= (1 << 4)) {
for (let i = 4; i <= SMALL_MAX_NUM; ++i) {
if (domain & (1 << i)) {
if (hi < 0) { // this is the LSB that is set
lo = i;
} else if (hi !== i - 1) { // there's a gap so push prev range now
arr.push(lo, hi);
lo = i;
}
hi = i;
}
}
}
// since the domain wasn't empty (checked at start) there
// must now be an unpushed lo/hi pair left to push...
arr.push(lo, hi);
return arr;
}
function domain_strToArr(domain) {
if (domain === EMPTY) return [];
let arr = [];
for (let i = 0, len = domain.length; i < len; i += STR_RANGE_SIZE) {
let lo = domain_str_decodeValue(domain, i);
let hi = domain_str_decodeValue(domain, i + STR_VALUE_SIZE);
arr.push(lo, hi);
}
return arr;
}
/**
* Get a domain representation in string form
*
* @param {$domain} domain
* @returns {$strdom} (small domains will also be strings)
*/
function domain_toStr(domain) {
if (typeof domain === 'number') return domain_numToStr(domain);
if (typeof domain === 'string') return domain;
return domain_arrToStr(domain);
}
function domain_numToStr(domain) {
if (domain >= SOLVED_FLAG) return domain_solToStr(domain);
return domain_bitToStr(domain);
}
function domain_solToStr(domain) {
let solvedValue = domain ^ SOLVED_FLAG;
return domain_str_encodeRange(solvedValue, solvedValue);
}
function domain_bitToStr(domain) {
if (domain === EMPTY) return EMPTY_STR;
let str = EMPTY_STR;
let lo = -1;
let hi = -1;
if ((1 << 0) & domain) {
lo = 0;
hi = 0;
}
if ((1 << 1) & domain) {
if (lo !== 0) { // lo is either 0 or nothing
lo = 1;
}
hi = 1; // there cannot be a gap yet
}
if ((1 << 2) & domain) {
if (hi === 0) {
str = domain_str_encodeRange(0, 0);
lo = 2;
} else if (hi !== 1) {
// if hi isnt 0 and hi isnt 1 then hi isnt set and so lo isnt set
lo = 2;
}
hi = 2;
}
if ((1 << 3) & domain) {
if (hi < 0) { // this is the LSB that is set
lo = 3;
} else if (hi !== 2) { // there's a gap so push prev range now
str += domain_str_encodeRange(lo, hi);
lo = 3;
}
hi = 3;
}
// is the fifth bit or higher even set at all? for ~85% that is not the case at this point
if (domain >= (1 << 4)) {
for (let i = 4; i <= SMALL_MAX_NUM; ++i) {
if (domain & (1 << i)) {
if (hi < 0) { // this is the LSB that is set
lo = i;
} else if (hi !== i - 1) { // there's a gap so push prev range now
str += domain_str_encodeRange(lo, hi);
lo = i;
}
hi = i;
}
}
}
// since the domain wasn't empty (checked at start) there
// must now be an unpushed lo/hi pair left to push...
str += domain_str_encodeRange(lo, hi);
return str;
}
function domain_arrToStr(arrdom) {
let str = EMPTY_STR;
for (let i = 0, len = arrdom.length; i < len; i += ARR_RANGE_SIZE) {
let lo = arrdom[i];
let hi = arrdom[i + 1];
str += domain_str_encodeRange(lo, hi);
}
return str;
}
/**
* Returns the smallest representation of given domain. The order is:
* soldom < numdom < strdom
* Won't return arrdoms.
*
* @param {$domain} domain
* @returns {$domain}
*/
function domain_toSmallest(domain) {
if (typeof domain === 'number') return domain_numToSmallest(domain);
return domain_strToSmallest(domain);
}
function domain_anyToSmallest(domain) {
// for tests and config import
if (domain instanceof Array) domain = domain_arrToStr(domain);
return domain_toSmallest(domain);
}
function domain_numToSmallest(domain) {
if (domain >= SOLVED_FLAG) return domain;
return domain_bitToSmallest(domain);
}
function domain_bitToSmallest(domain) {
let value = domain_getValue(domain);
if (value === NO_SUCH_VALUE) return domain;
return domain_createValue(value);
}
function domain_strToSmallest(domain) {
let len = domain.length;
if (!len) return EMPTY;
let min = domain_str_decodeValue(domain, 0);
let max = domain_str_decodeValue(domain, len - STR_VALUE_SIZE);
if (len === STR_RANGE_SIZE) {
if (min === max) return domain_createValue(min);
}
if (max <= SMALL_MAX_NUM) return domain_strToBit(domain, len);
return domain;
}
/**
* Convert string domain to number domain. Assumes domain
* is eligible to be a small domain.
*
* @param {$strdom} strdom
* @param {number} len Cache of domain.length (string length... not value count)
* @returns {$strdom}
*/
function domain_strToBit(strdom, len) {
if (len === 0) return EMPTY;
let lo = domain_str_decodeValue(strdom, 0);
let hi = domain_str_decodeValue(strdom, 0 + STR_VALUE_SIZE);
//if (len === STR_RANGE_SIZE && lo === hi) {
// return (lo | SOLVED_FLAG) >>> 0; // >>>0 forces unsigned.
//}
let out = domain_bit_addRange(EMPTY, lo, hi);
for (let i = STR_RANGE_SIZE; i < len; i += STR_RANGE_SIZE) {
let lo = domain_str_decodeValue(strdom, i);
let hi = domain_str_decodeValue(strdom, i + STR_VALUE_SIZE);
out = domain_bit_addRange(out, lo, hi);
}
return out;
}
function domain_arrToSmallest(arrdom) {
let len = arrdom.length;
if (len === 0) return EMPTY;
if (len === ARR_RANGE_SIZE && arrdom[0] === arrdom[1]) return domain_createValue(arrdom[0]);
let max = domain_arr_max(arrdom);
if (max <= SMALL_MAX_NUM) return _domain_arrToBit(arrdom, len);
return domain_arrToStr(arrdom);
}
function _domain_arrToBit(domain, len) {
// TODO
// if (domain.length === 2 && domain[0] === domain[1]) return (domain[0] | SOLVED_FLAG) >>> 0;
let out = 0;
for (let i = 0; i < len; i += ARR_RANGE_SIZE) {
out = domain_bit_addRange(out, domain[i], domain[i + 1]);
}
return out;
}
// end of src/domain.js
// from: src/doms/domain_minus.js
/**
* Subtract one domain from the other
*
* @param {$domain} domain1
* @param {$domain} domain2
* @returns {$domain}
*/
function domain_minus(domain1, domain2) {
// note: this is not x-0=x. this is nothing-something=nothing because the domains contain no value
if (!domain1) return EMPTY;
if (!domain2) return EMPTY;
// optimize an easy path: if both domains contain zero the
// result will always be [0, max(domain1)], because:
// d1-d2 = [lo1-hi2, hi1-lo2] -> [0-hi2, hi1-0] -> [0, hi1]
if (domain_min(domain1) === 0 && domain_min(domain2) === 0) {
return domain_createRange(0, domain_max(domain1));
}
let isNum1 = typeof domain1 === 'number';
let isNum2 = typeof domain2 === 'number';
if (isNum1) {
// note: if domain1 is a small domain the result is always a small domain
if (isNum2) return _domain_minusNumNum(domain1, domain2);
return _domain_minusNumStr(domain1, domain2);
}
let result;
if (isNum2) result = _domain_minusStrNumStr(domain1, domain2); // cannot swap minus args!
else result = _domain_minusStrStrStr(domain1, domain2);
return domain_toSmallest(domain_str_simplify(result));
}
function _domain_minusStrStrStr(domain1, domain2) {
// Simplify the domains by closing gaps since when we add
// the domains, the gaps will close according to the
// smallest interval width in the other domain.
let domains = domain_str_closeGaps(domain1, domain2);
domain1 = domains[0];
domain2 = domains[1];
let newDomain = EMPTY_STR;
for (let index = 0, len = domain1.length; index < len; index += STR_RANGE_SIZE) {
let lo = domain_str_decodeValue(domain1, index);
let hi = domain_str_decodeValue(domain1, index + STR_VALUE_SIZE);
newDomain += _domain_minusRangeStrStr(lo, hi, domain2);
}
return newDomain;
}
function _domain_minusNumNum(domain1, domain2) {
if (domain1 >= SOLVED_FLAG) {
let solvedValue = domain1 ^ SOLVED_FLAG;
if (domain2 >= SOLVED_FLAG) {
let result = solvedValue - (domain2 ^ SOLVED_FLAG);
if (result < 0) return EMPTY;
return domain_createValue(result);
}
if (solvedValue <= SMALL_MAX_NUM) return _domain_minusRangeNumNum(solvedValue, solvedValue, domain2);
else return _domain_minusRangeNumStr(solvedValue, solvedValue, domain2);
}
return _domain_minusNumNumNum(domain1, domain2);
}
function _domain_minusNumNumNum(domain1, domain2) {
if (domain_num_containsValue(domain1, 0) && domain_num_containsValue(domain2, 0)) return domain_numnum_createRangeZeroToMax(domain1);
let flagIndex = 0;
// find the first set bit. must find something because small domain and not empty
while ((domain1 & (1 << flagIndex)) === 0) ++flagIndex;
let lo = flagIndex;
let hi = flagIndex;
let flagValue = 1 << ++flagIndex;
let newDomain = EMPTY;
while (flagValue <= domain1 && flagIndex <= SMALL_MAX_NUM) {
if ((flagValue & domain1) > 0) {
if (hi !== flagIndex - 1) { // there's a gap so push prev range now
newDomain |= _domain_minusRangeNumNum(lo, hi, domain2);
lo = flagIndex;
}
hi = flagIndex;
}
flagValue = 1 << ++flagIndex;
}
return newDomain | _domain_minusRangeNumNum(lo, hi, domain2);
}
function _domain_minusNumStr(domain_num, domain_str) {
if (domain_num >= SOLVED_FLAG) {
let solvedValue = domain_num ^ SOLVED_FLAG;
if (solvedValue <= SMALL_MAX_NUM) return _domain_minusRangeStrNum(solvedValue, solvedValue, domain_str);
else return _domain_minusRangeStrStr(solvedValue, solvedValue, domain_str);
}
return _domain_minusNumStrNum(domain_num, domain_str);
}
function _domain_minusNumStrNum(domain_num, domain_str) {
if (domain_num >= SOLVED_FLAG) {
let solvedValue = domain_num ^ SOLVED_FLAG;
return _domain_minusRangeStrNum(solvedValue, solvedValue, domain_str);
}
// since any number above the small domain max ends up with negative, which is truncated, use the max of domain1
if (domain_num_containsValue(domain_num, 0) && domain_min(domain_str) === 0) return domain_numnum_createRangeZeroToMax(domain_num);
let flagIndex = 0;
// find the first set bit. must find something because small domain and not empty
while ((domain_num & (1 << flagIndex)) === 0) ++flagIndex;
let lo = flagIndex;
let hi = flagIndex;
let flagValue = 1 << ++flagIndex;
let newDomain = EMPTY;
while (flagValue <= domain_num && flagIndex <= SMALL_MAX_NUM) {
if ((flagValue & domain_num) > 0) {
if (hi !== flagIndex - 1) { // there's a gap so push prev range now
newDomain |= _domain_minusRangeStrNum(lo, hi, domain_str);
lo = flagIndex;
}
hi = flagIndex;
}
flagValue = 1 << ++flagIndex;
}
return newDomain | _domain_minusRangeStrNum(lo, hi, domain_str);
}
function _domain_minusRangeNumNum(loi, hii, domain_num) {
if (domain_num >= SOLVED_FLAG) {
let solvedValue = domain_num ^ SOLVED_FLAG;
return _domain_minusRangeRangeNum(loi, hii, solvedValue, solvedValue);
}
let flagIndex = 0;
// find the first set bit. must find something because small domain and not empty
while ((domain_num & (1 << flagIndex)) === 0) ++flagIndex;
let lo = flagIndex;
let hi = flagIndex;
let flagValue = 1 << ++flagIndex;
let newDomain = EMPTY;
while (flagValue <= domain_num && flagIndex <= SMALL_MAX_NUM) {
if ((flagValue & domain_num) > 0) {
if (hi !== flagIndex - 1) { // there's a gap so push prev range now
newDomain |= _domain_minusRangeRangeNum(loi, hii, lo, hi);
lo = flagIndex;
}
hi = flagIndex;
}
flagValue = 1 << ++flagIndex;
}
return newDomain | _domain_minusRangeRangeNum(loi, hii, lo, hi);
}
function _domain_minusStrNumStr(domain_str, domain_num) {
// optimize an easy path: if both domains contain zero the
// result will always be [0, max(domain1)], because:
// d1-d2 = [lo1-hi2, hi1-lo2] -> [0-hi2, hi1-0] -> [0, hi1]
if (domain_min(domain_str) === 0 && domain_min(domain_num) === 0) {
return domain_createRange(0, domain_max(domain_str));
}
let newDomain = EMPTY_STR;
for (let index = 0, len = domain_str.length; index < len; index += STR_RANGE_SIZE) {
let lo = domain_str_decodeValue(domain_str, index);
let hi = domain_str_decodeValue(domain_str, index + STR_VALUE_SIZE);
newDomain += _domain_minusRangeNumStr(lo, hi, domain_num);
}
return newDomain;
}
function _domain_minusRangeNumStr(loi, hii, domain_num) {
if (domain_num === EMPTY) return EMPTY;
if (domain_num >= SOLVED_FLAG) {
let solvedValue = domain_num ^ SOLVED_FLAG;
return _domain_minusRangeRangeStr(loi, hii, solvedValue, solvedValue);
}
let flagIndex = 0;
// find the first set bit. must find something because small domain and not empty
while ((domain_num & (1 << flagIndex)) === 0) ++flagIndex;
let lo = flagIndex;
let hi = flagIndex;
let flagValue = 1 << ++flagIndex;
let newDomain = EMPTY_STR;
while (flagValue <= domain_num && flagIndex <= SMALL_MAX_NUM) {
if ((flagValue & domain_num) > 0) {
if (hi !== flagIndex - 1) { // there's a gap so push prev range now
newDomain += _domain_minusRangeRangeStr(loi, hii, lo, hi);
lo = flagIndex;
}
hi = flagIndex;
}
flagValue = 1 << ++flagIndex;
}
return newDomain + _domain_minusRangeRangeStr(loi, hii, lo, hi);
}
function _domain_minusRangeStrStr(loi, hii, domain_str) {
let newDomain = EMPTY_STR;
for (let index = 0, len = domain_str.length; index < len; index += STR_RANGE_SIZE) {
let lo = domain_str_decodeValue(domain_str, index);
let hi = domain_str_decodeValue(domain_str, index + STR_VALUE_SIZE);
newDomain += _domain_minusRangeRangeStr(loi, hii, lo, hi);
}
return newDomain;
}
function _domain_minusRangeStrNum(loi, hii, domain_str) {
let newDomain = EMPTY;
for (let index = 0, len = domain_str.length; index < len; index += STR_RANGE_SIZE) {
let lo = domain_str_decodeValue(domain_str, index);
let hi = domain_str_decodeValue(domain_str, index + STR_VALUE_SIZE);
newDomain |= _domain_minusRangeRangeNum(loi, hii, lo, hi);
}
return newDomain;
}
function _domain_minusRangeRangeStr(loi, hii, loj, hij) {
let hi = hii - loj;
if (hi >= SUB) { // silently ignore results that are OOB
let lo = MAX(SUB, loi - hij);
return domain_str_encodeRange(lo, hi);
}
return EMPTY_STR;
}
function _domain_minusRangeRangeNum(loi, hii, loj, hij) {
let hi = hii - loj;
if (hi >= SUB) { // silently ignore results that are OOB
let lo = MAX(SUB, loi - hij);
let domain = domain_num_createRange(lo, hi);
return domain;
}
return EMPTY;
}
// end of src/doms/domain_minus.js
// from: src/doms/domain_plus.js
/**
* Does not harm input domains
*
* @param {$domain} domain1
* @param {$domain} domain2
* @returns {$domain}
*/
function domain_plus(domain1, domain2) {
// note: this is not 0+x=x. this is nothing+something=nothing because the domains contain no value
if (!domain1) return EMPTY;
if (!domain2) return EMPTY;
let isNum1 = typeof domain1 === 'number';
let isNum2 = typeof domain2 === 'number';
let result;
if (isNum1 && isNum2) {
// if the highest number in the result is below the max of a small
// domain we can take a fast path for it. this case happens often.
if (_domain_plusWillBeSmall(domain1, domain2)) {
return _domain_plusNumNumNum(domain1, domain2);
}
result = _domain_plusNumNumStr(domain1, domain2);
} else {
if (isNum1) result = _domain_plusNumStrStr(domain1, domain2);
else if (isNum2) result = _domain_plusNumStrStr(domain2, domain1); // swapped domains!
else result = _domain_plusStrStrStr(domain1, domain2);
}
return domain_toSmallest(domain_str_simplify(result));
}
function _domain_plusStrStrStr(domain1, domain2) {
// Simplify the domains by closing gaps since when we add
// the domains, the gaps will close according to the
// smallest interval width in the other domain.
let domains = domain_str_closeGaps(domain1, domain2);
domain1 = domains[0];
domain2 = domains[1];
let newDomain = EMPTY_STR;
for (let index = 0, len = domain1.length; index < len; index += STR_RANGE_SIZE) {
let lo = domain_str_decodeValue(domain1, index);
let hi = domain_str_decodeValue(domain1, index + STR_VALUE_SIZE);
newDomain += _domain_plusRangeStrStr(lo, hi, domain2);
}
return newDomain;
}
function _domain_plusWillBeSmall(domain1, domain2) {
// if both domains are small enough they cannot add to a domain beyond the max
//if (((domain1 | domain2) >>> 0) < (1 << 15)) return true; // could catch some cases
//if (domain1 < (1<<15) && domain2 < (1<<15)) return true; // alternative of above
return domain_max(domain1) + domain_max(domain2) <= SMALL_MAX_NUM; // if max changes, update above too!
}
function _domain_plusNumNumStr(domain1, domain2) {
if (domain1 >= SOLVED_FLAG) {
let solvedValue = domain1 ^ SOLVED_FLAG;
return _domain_plusRangeNumStr(solvedValue, solvedValue, domain2);
}
let flagIndex = 0;
// find the first set bit. must find something because small domain and not empty
while ((domain1 & (1 << flagIndex)) === 0) ++flagIndex;
let lo = flagIndex;
let hi = flagIndex;
let flagValue = 1 << ++flagIndex;
let newDomain = EMPTY_STR;
while (flagValue <= domain1 && flagIndex <= SMALL_MAX_NUM) {
if ((flagValue & domain1) > 0) {
if (hi !== flagIndex - 1) { // there's a gap so push prev range now
newDomain += _domain_plusRangeNumStr(lo, hi, domain2);
lo = flagIndex;
}
hi = flagIndex;
}
flagValue = 1 << ++flagIndex;
}
return newDomain + _domain_plusRangeNumStr(lo, hi, domain2);
}
function _domain_plusNumNumNum(domain1, domain2) {
if (domain1 >= SOLVED_FLAG) {
let solvedValue = domain1 ^ SOLVED_FLAG;
return _domain_plusRangeNumNum(solvedValue, solvedValue, domain2);
}
let flagIndex = 0;
// find the first set bit. must find something because small domain and not empty
while ((domain1 & (1 << flagIndex)) === 0) ++flagIndex;
let lo = flagIndex;
let hi = flagIndex;
let flagValue = 1 << ++flagIndex;
let newDomain = EMPTY;
while (flagValue <= domain1 && flagIndex <= SMALL_MAX_NUM) {
if ((flagValue & domain1) > 0) {
if (hi !== flagIndex - 1) { // there's a gap so push prev range now
newDomain |= _domain_plusRangeNumNum(lo, hi, domain2);
lo = flagIndex;
}
hi = flagIndex;
}
flagValue = 1 << ++flagIndex;
}
return newDomain | _domain_plusRangeNumNum(lo, hi, domain2);
}
function _domain_plusRangeNumNum(loi, hii, domain_num) {
if (domain_num >= SOLVED_FLAG) {
let solvedValue = domain_num ^ SOLVED_FLAG;
return _domain_plusRangeRangeNum(loi, hii, solvedValue, solvedValue);
}
let flagIndex = 0;
// find the first set bit. must find something because small domain and not empty
while ((domain_num & (1 << flagIndex)) === 0) ++flagIndex;
let lo = flagIndex;
let hi = flagIndex;
let flagValue = 1 << ++flagIndex;
let newDomain = EMPTY;
while (flagValue <= domain_num && flagIndex <= SMALL_MAX_NUM) {
if ((flagValue & domain_num) > 0) {
if (hi !== flagIndex - 1) { // there's a gap so push prev range now
newDomain |= _domain_plusRangeRangeNum(loi, hii, lo, hi);
lo = flagIndex;
}
hi = flagIndex;
}
flagValue = 1 << ++flagIndex;
}
return newDomain | _domain_plusRangeRangeNum(loi, hii, lo, hi);
}
function _domain_plusNumStrStr(domain_num, domain_str) {
if (domain_num >= SOLVED_FLAG) {
let solvedValue = domain_num ^ SOLVED_FLAG;
return _domain_plusRangeStrStr(solvedValue, solvedValue, domain_str);
}
let flagIndex = 0;
// find the first set bit. must find something because small domain and not empty
while ((domain_num & (1 << flagIndex)) === 0) ++flagIndex;
let lo = flagIndex;
let hi = flagIndex;
let flagValue = 1 << ++flagIndex;
let newDomain = EMPTY_STR;
while (flagValue <= domain_num && flagIndex <= SMALL_MAX_NUM) {
if ((flagValue & domain_num) > 0) {
if (hi !== flagIndex - 1) { // there's a gap so push prev range now
newDomain += _domain_plusRangeStrStr(lo, hi, domain_str);
lo = flagIndex;
}
hi = flagIndex;
}
flagValue = 1 << ++flagIndex;
}
return newDomain + _domain_plusRangeStrStr(lo, hi, domain_str);
}
function _domain_plusRangeNumStr(loi, hii, domain_num) {
if (domain_num >= SOLVED_FLAG) {
let solvedValue = domain_num ^ SOLVED_FLAG;
return _domain_plusRangeRangeStr(loi, hii, solvedValue, solvedValue);
}
let flagIndex = 0;
// find the first set bit. must find something because small domain and not empty
while ((domain_num & (1 << flagIndex)) === 0) ++flagIndex;
let lo = flagIndex;
let hi = flagIndex;
let flagValue = 1 << ++flagIndex;
let newDomain = EMPTY_STR;
while (flagValue <= domain_num && flagIndex <= SMALL_MAX_NUM) {
if ((flagValue & domain_num) > 0) {
if (hi !== flagIndex - 1) { // there's a gap so push prev range now
newDomain += _domain_plusRangeRangeStr(loi, hii, lo, hi);
lo = flagIndex;
}
hi = flagIndex;
}
flagValue = 1 << ++flagIndex;
}
return newDomain + _domain_plusRangeRangeStr(loi, hii, lo, hi);
}
function _domain_plusRangeStrStr(loi, hii, domain_str) {
let newDomain = EMPTY_STR;
for (let index = 0, len = domain_str.length; index < len; index += STR_RANGE_SIZE) {
let lo = domain_str_decodeValue(domain_str, index);
let hi = domain_str_decodeValue(domain_str, index + STR_VALUE_SIZE);
newDomain += _domain_plusRangeRangeStr(loi, hii, lo, hi);
}
return newDomain;
}
function _domain_plusRangeRangeStr(loi, hii, loj, hij) {
let lo = loi + loj;
if (lo <= SUP) { // if lo exceeds SUP the resulting range is completely OOB and we ignore it.
let hi = MIN(SUP, hii + hij);
return domain_str_encodeRange(lo, hi);
}
return EMPTY_STR;
}
function _domain_plusRangeRangeNum(loi, hii, loj, hij) {
let domain = domain_num_createRange(loi + loj, hii + hij);
return domain;
}
// end of src/doms/domain_plus.js
// from: src/exporter.js
/**
* Export a given config with optional target domains
* (initial domains otherwise) to special DSL string.
* The resulting string should be usable with the
* importer to create a new solver with same state.
* This function only omits constraints when they only
* consist of constants. Optimization should occur elsewhere.
*
* @param {$config} config
* @param {$domain[]} [vardoms] If not given then config.initialDomains are used
* @param {boolean} [usePropagators] Output the low-level propagators instead of the higher level constraints
* @param {boolean} [minimal] Omit comments, use short var names, reduce whitespace where possible. etc
* @param {boolean} [withDomainComments] Put the input domains behind each constraint even if minimal=true
* @returns {string}
*/
function exporter_main(config, vardoms, usePropagators, minimal, withDomainComments) {
// TODO: dont export contants that are not bound to constraints and not targeted explicitly
// TODO: deal export->import better wrt anonymous vars
let indexToString = minimal ? exporter_varstrShort : exporter_varstrNum;
let var_dist_options = config.varDistOptions;
let domains = vardoms || config.initialDomains;
let vars = config.allVarNames.map((varName, varIndex) => {
let domain = exporter_domstr(domains[varIndex]);
let s = ': ' + indexToString(varIndex) + ' = ' + domain;
if (varName !== String(varIndex)) s += ' alias(' + exporter_encodeVarName(varName) + ')';
let overrides = var_dist_options[varName];
if (overrides && (overrides.valtype !== 'list' || (overrides.list && overrides.list.length))) {
s += ' @' + overrides.valtype;
switch (overrides.valtype) {
case 'markov':
if ('expandVectorsWith' in overrides) s += 'expand(' + (overrides.expandVectorsWith || 0) + ')';
if ('legend' in overrides) s += ' legend(' + overrides.legend.join(' ') + ')';
if ('matrix' in overrides) s += ' matrix(' + JSON.stringify(overrides.matrix).replace(/"/g, '') + ')';
break;
case 'list':
if (typeof overrides.list === 'function') s += ' prio(???func???)';
else s += ' prio(' + overrides.list.join(' ') + ')';
break;
case 'max':
case 'mid':
case 'min':
case 'minMaxCycle':
case 'naive':
case 'splitMax':
case 'splitMin':
break;
default:
console.warn('Unknown value strategy override: ' + overrides.valtype);
s += ' @? ' + JSON.stringify(overrides);
}
}
return s;
});
let constraints = usePropagators ? [] : config.allConstraints.map(constraint => {
let indexes = constraint.varIndexes;
// create var names for each index, unless solved, in that case use solved value as literal
let aliases = indexes.map(indexToString);
indexes.forEach((varIndex, i) => {
let v = domain_getValue(domains[varIndex]);
if (v >= 0) aliases[i] = v;
});
// do same for param if it's an index
let paramName = '';
if (typeof constraint.param === 'number') {
let paramV = domain_getValue(domains[constraint.param]);
if (paramV >= 0) paramName = paramV;
else paramName = indexToString(constraint.param);
}
let s = '';
let comment = '';
switch (constraint.name) {
case 'reifier':
let op;
switch (constraint.param) {
case 'eq': op = '=='; break;
case 'neq': op = '!='; break;
case 'lt': op = '<'; break;
case 'lte': op = '<='; break;
case 'gt': op = '>'; break;
case 'gte': op = '>='; break;
default: THROW('what dis param: ' + op);
}
s += aliases[2] + ' = ' + aliases[0] + ' ' + op + '? ' + aliases[1];
break;
case 'plus':
s += aliases[2] + ' = ' + aliases[0] + ' + ' + aliases[1];
break;
case 'min':
s += aliases[2] + ' = ' + aliases[0] + ' - ' + aliases[1];
break;
case 'ring-mul':
s += aliases[2] + ' = ' + aliases[0] + ' * ' + aliases[1];
break;
case 'ring-div':
s += aliases[2] + ' = ' + aliases[0] + ' / ' + aliases[1];
break;
case 'mul':
s += aliases[2] + ' = ' + aliases[0] + ' * ' + aliases[1];
break;
case 'sum':
s += paramName + ' = sum(' + aliases.join(' ') + ')';
break;
case 'product':
s += paramName + ' = product(' + aliases.join(' ') + ')';
break;
case 'markov':
s += '# markov(' + aliases + ')';
break;
case 'distinct':
s += 'distinct(' + aliases + ')';
break;
case 'eq':
s += aliases[0] + ' == ' + aliases[1];
break;
case 'neq':
s += aliases[0] + ' != ' + aliases[1];
break;
case 'lt':
s += aliases[0] + ' < ' + aliases[1];
break;
case 'lte':
s += aliases[0] + ' <= ' + aliases[1];
break;
case 'gt':
s += aliases[0] + ' > ' + aliases[1];
break;
case 'gte':
s += aliases[0] + ' >= ' + aliases[1];
break;
default:
console.warn('unknown constraint: ' + constraint.name);
s += 'unknown = ' + JSON.stringify(constraint);
}
let t = s;
// if a constraint has no vars, ignore it.
// note: this assumes those constraints are not contradictions
if (s.indexOf('$') < 0 || (constraint.name === 'distinct' && aliases.length <= 1) || (((constraint.name === 'product' || constraint.name === 'sum') && aliases.length === 0))) {
if (!minimal) {
comment += (comment ? ', ' : ' # ') + 'dropped; constraint already solved (' + s + ') (' + indexes.map(indexToString) + ', ' + indexToString(constraint.param) + ')';
}
s = '';
}
if (!minimal || withDomainComments) {
// this is more for easier debugging...
aliases.forEach((alias, i) => { if (typeof alias === 'string') t = t.replace(alias, exporter_domstr(domains[indexes[i]])); });
if (typeof constraint.param === 'number' && typeof paramName === 'string') t = t.replace(paramName, exporter_domstr(domains[constraint.param]));
if (s || !minimal) {
// s += ' '.repeat(Math.max(0, 30 - s.length))
for (let i = Math.max(0, 30 - s.length); i >= 0; --i) s += ' ';
s += ' # ' + t;
}
s += comment;
}
return s;
}).filter(s => !!s);
let propagators = !usePropagators ? [] : config._propagators.map(propagator => {
let varIndex1 = propagator.index1;
let varIndex2 = propagator.index2;
let varIndex3 = propagator.index3;
let v1 = varIndex1 >= 0 ? domain_getValue(domains[varIndex1]) : -1;
let name1 = v1 >= 0 ? v1 : varIndex1 < 0 ? undefined : indexToString(varIndex1);
let v2 = varIndex2 >= 0 ? domain_getValue(domains[varIndex2]) : -1;
let name2 = v2 >= 0 ? v2 : varIndex2 < 0 ? undefined : indexToString(varIndex2);
let v3 = varIndex3 >= 0 ? domain_getValue(domains[varIndex3]) : -1;
let name3 = v3 >= 0 ? v3 : varIndex3 < 0 ? undefined : indexToString(varIndex3);
let s = '';
let comment = '';
switch (propagator.name) {
case 'reified':
let op;
switch (propagator.arg3) {
case 'eq': op = '=='; break;
case 'neq': op = '!='; break;
case 'lt': op = '<'; break;
case 'lte': op = '<='; break;
case 'gt': op = '>'; break;
case 'gte': op = '>='; break;
default: THROW('what dis param: ' + op);
}
s += name3 + ' = ' + name1 + ' ' + op + '? ' + name2;
break;
case 'eq':
s += name1 + ' == ' + name2;
break;
case 'lt':
s += name1 + ' < ' + name2;
break;
case 'lte':
s += name1 + ' <= ' + name2;
break;
case 'mul':
s += name3 + ' = ' + name1 + ' * ' + name2;
break;
case 'div':
s += name3 + ' = ' + name1 + ' / ' + name2;
break;
case 'neq':
s += name1 + ' != ' + name2;
break;
case 'min':
s += name3 + ' = ' + name1 + ' - ' + name2;
break;
case 'ring':
switch (propagator.arg1) {
case 'plus':
s += name3 + ' = ' + name1 + ' + ' + name2;
break;
case 'min':
s += name3 + ' = ' + name1 + ' - ' + name2;
break;
case 'ring-mul':
s += name3 + ' = ' + name1 + ' * ' + name2;
break;
case 'ring-div':
s += name3 + ' = ' + name1 + ' / ' + name2;
break;
default:
throw new Error('Unexpected ring op:' + propagator.arg1);
}
break;
case 'markov':
// ignore. the var @markov modifier should cause this. it's not a real constraint.
return '';
default:
console.warn('unknown propagator: ' + propagator.name);
s += 'unknown = ' + JSON.stringify(propagator);
}
let t = s;
// if a propagator has no vars, ignore it.
// note: this assumes those constraints are not contradictions
if (s.indexOf('$') < 0) {
if (!minimal) comment += (comment ? ', ' : ' # ') + 'dropped; constraint already solved (' + s + ')';
s = '';
}
if (!minimal) {
// this is more for easier debugging...
if (typeof name1 === 'string') t = t.replace(name1, exporter_domstr(domains[varIndex1]));
if (typeof name2 === 'string') t = t.replace(name2, exporter_domstr(domains[varIndex2]));
if (typeof name3 === 'string') t = t.replace(name3, exporter_domstr(domains[varIndex3]));
s += ' '.repeat(Math.max(0, 30 - s.length)) + ' # initial: ' + t;
s += comment;
}
return s;
}).filter(s => !!s);
return [
'## constraint problem export',
'@custom var-strat = ' + JSON.stringify(config.varStratConfig), // TODO
'@custom val-strat = ' + config.valueStratName,
vars.join('\n') || '# no vars',
constraints.join('\n') || propagators.join('\n') || '# no constraints',
'@targets = ' + (config.targetedVars === 'all' ? 'all' : '[' + config.targetedVars.map(varName => indexToString(trie_get(config._varNamesTrie, varName))).join(' ') + ']'),
'## end of export',
].join('\n\n');
}
function exporter_encodeVarName(varName) {
if (typeof varName === 'number') return varName; // constant
return varName.replace(/^(\d)/, '___$1').replace(/[\(\)\[\]\*@\=\<\>\!, ]/g, '_');
}
function exporter_varstrNum(varIndex) {
// note: we put a `$` behind it so that we can search-n-replace for `$1` without matching `$100`
return '$' + varIndex + '$';
}
function exporter_varstrShort(varIndex) {
// take care not to start the name with a number
// note: .toString(36) uses a special (standard) base 36 encoding; 0-9a-z to represent 0-35
let name = varIndex.toString(36);
if (name[0] < 'a') name = '$' + name; // this is a little lazy but whatever
return name;
}
function exporter_domstr(domain) {
// represent domains as pairs, a single pair as [lo hi] and multiple as [[lo hi] [lo hi]]
let arrdom = domain_toArr(domain);
if (arrdom.length === 2 && arrdom[0] === arrdom[1]) return String(arrdom[0]);
if (arrdom.length > 2) {
let dom = [];
for (let i = 0, n = arrdom.length; i < n; i += 2) {
dom.push('[' + arrdom[i] + ' ' + arrdom[i + 1] + ']');
}
arrdom = dom;
}
return '[' + arrdom.join(' ') + ']';
}
// end of src/exporter.js
// from: src/helpers.js
let SUB = 0; // WARNING: adjusting SUB to something negative means adjusting all tests. probably required for any change actually.
let SUP = 100000000;
let SOLVED = 1;
let UNDETERMINED = 0;
let NOT_FOUND = -1;
let LOG_NONE = 0;
let LOG_STATS = 1;
let LOG_SOLVES = 2;
let LOG_MIN = LOG_NONE;
let LOG_MAX = LOG_SOLVES;
// different from NOT_FOUND in that NOT_FOUND must be -1 because of the indexOf api
// while NO_SUCH_VALUE must be a value that cannot be a legal domain value (<SUB or >SUP)
let NO_SUCH_VALUE = Math.min(0, SUB) - 1; // make sure NO_SUCH_VALUE is a value that may be neither valid in a domain nor >=0
let ENABLED = true; // override for most tests (but not regular ASSERTs) like full domains and space validations
let ENABLE_DOMAIN_CHECK = false; // also causes unrelated errors because mocha sees the expandos
let ENABLE_EMPTY_CHECK = false; // also causes unrelated errors because mocha sees the expandos
let ARR_RANGE_SIZE = 2;
const SMALL_MAX_NUM = 30;
// there are SMALL_MAX_NUM flags. if they are all on, this is the number value
// (oh and; 1<<31 is negative. >>>0 makes it unsigned. this is why 30 is max.)
const SOLVED_FLAG = 1 << 31 >>> 0; // the >>> makes it unsigned, we dont really need it but it may help perf a little (unsigned vs signed)
// Abstraction for throwing because throw statements cause deoptimizations
// All explicit throws should use this function. Also helps with tooling
// later, catching and reporting explicits throws and what not.
function THROW(...msg) {
throw new Error(msg.join(': '));
}
// end of src/helpers.js
// from: src/importer.js
/**
* @param {string} str
* @param {Solver} [solver]
* @returns {Solver}
*/
function importer_main(str, solver, _debug) {
if (!solver) solver = new Solver();
let pointer = 0;
let len = str.length;
while (!isEof()) parseStatement();
return solver;
function read() {
return str[pointer];
}
function skip() {
++pointer;
}
function is(c, desc) {
if (read() !== c) THROW('Expected ' + (desc + ' ' || '') + '`' + c + '`, found `' + read() + '`');
skip();
}
function skipWhitespaces() {
while (pointer < len && isWhitespace(read())) skip();
}
function skipWhites() {
while (!isEof()) {
let c = read();
if (isWhite(c)) {
skip();
} else if (isComment(c)) {
skipComment();
} else {
break;
}
}
}
function isWhitespace(s) {
return s === ' ' || s === '\t';
}
function isNewline(s) {
// no, I don't feel bad for also flaggin a comment as eol :)
return s === '\n' || s === '\r';
}
function isComment(s) {
return s === '#';
}
function isWhite(s) {
return isWhitespace(s) || isNewline(s);
}
function expectEol() {
skipWhitespaces();
if (pointer < len) {
let c = read();
if (c === '#') {
skipComment();
} else if (isNewline(c)) {
skip();
} else {
THROW('Expected EOL but got `' + read() + '`');
}
}
}
function isEof() {
return pointer >= len;
}
function parseStatement() {
// either:
// - start with colon: var decl
// - start with hash: line comment
// - empty: empty
// - otherwise: constraint
skipWhites();
switch (read()) {
case ':': return parseVar();
case '#': return skipComment();
case '@': return parseAtRule();
default:
if (!isEof()) return parseUndefConstraint();
}
}
function parseVar() {
skip(); // is(':')
skipWhitespaces();
let name = parseIdentifier();
skipWhitespaces();
let domain = parseDomain();
skipWhitespaces();
let alts;
while (str.slice(pointer, pointer + 6) === 'alias(') {
if (!alts) alts = [];
alts.push(parseAlias(pointer += 6));
skipWhitespaces();
}
let mod = parseModifier();
expectEol();
solver.decl(name, domain, mod, true);
// TODO: properly map the alts to the same var index...
if (alts) alts.map(name => solver.decl(name, domain, mod, true));
}
function parseIdentifier() {
if (read() === '\'') return parseQuotedIdentifier();
else return parseUnquotedIdentifier();
}
function parseQuotedIdentifier() {
is('\'');
let start = pointer;
while (!isEof() && read() !== '\'') skip();
if (isEof()) THROW('Quoted identifier must be closed');
if (start === pointer) THROW('Expected to parse identifier, found none');
skip(); // quote
return str.slice(start, pointer - 1); // return unquoted ident
}
function parseUnquotedIdentifier() {
// anything terminated by whitespace
let start = pointer;
if (read() >= '0' && read() <= '9') THROW('Unquoted ident cant start with number');
while (!isEof() && isValidUnquotedIdentChar(read())) skip();
if (isEof()) THROW('Quoted identifier must be closed');
if (start === pointer) THROW('Expected to parse identifier, found none');
return str.slice(start, pointer);
}
function isValidUnquotedIdentChar(c) {
switch (c) {
case '(':
case ')':
case ',':
case '[':
case ']':
case '\'':
case '#':
return false;
}
if (isWhite(c)) return false;
return true;
}
function parseAlias() {
skipWhitespaces();
let start = pointer;
while (true) {
let c = read();
if (c === ')') break;
if (isNewline(c)) THROW('Alias must be closed with a `)` but wasnt (eol)');
if (isEof()) THROW('Alias must be closed with a `)` but wasnt (eof)');
skip();
}
let alias = str.slice(start, pointer);
if (!alias) THROW('The alias() can not be empty but was');
skipWhitespaces();
is(')', '`alias` to be closed by `)`');
return alias;
}
function parseDomain() {
// []
// [lo hi]
// [[lo hi] [lo hi] ..]
// *
// 25
// (comma's optional and ignored)
let c = read();
if (c === '=') {
skip();
skipWhitespaces();
c = read();
}
let domain;
switch (c) {
case '[':
is('[', 'domain start');
skipWhitespaces();
domain = [];
if (read() === '[') {
do {
skip();
skipWhitespaces();
let lo = parseNumber();
skipWhitespaces();
if (read() === ',') {
skip();
skipWhitespaces();
}
let hi = parseNumber();
skipWhitespaces();
is(']', 'range-end');
skipWhitespaces();
domain.push(lo, hi);
if (read() === ',') {
skip();
skipWhitespaces();
}
} while (read() === '[');
} else if (read() !== ']') {
do {
skipWhitespaces();
let lo = parseNumber();
skipWhitespaces();
if (read() === ',') {
skip();
skipWhitespaces();
}
let hi = parseNumber();
skipWhitespaces();
domain.push(lo, hi);
if (read() === ',') {
skip();
skipWhitespaces();
}
} while (read() !== ']');
}
is(']', 'domain-end');
return domain;
case '*':
skip();
return [SUB, SUP];
case '0':
case '1':
case '2':
case '3':
case '4':
case '5':
case '6':
case '7':
case '8':
case '9':
let v = parseNumber();
skipWhitespaces();
return [v, v];
}
THROW('Expecting valid domain start, found `' + c + '`');
}
function parseModifier() {
if (read() !== '@') return;
skip();
let mod = {};
let start = pointer;
while (read() >= 'a' && read() <= 'z') skip();
let stratName = str.slice(start, pointer);
switch (stratName) {
case 'list':
parseList(mod);
break;
case 'markov':
parseMarkov(mod);
break;
case 'max':
case 'mid':
case 'min':
case 'minMaxCycle':
case 'naive':
case 'splitMax':
case 'splitMin':
break;
default:
THROW('Expecting a strategy name after the `@` modifier (`' + stratName + '`)');
}
mod.valtype = stratName;
return mod;
}
function parseList(mod) {
skipWhitespaces();
if (str.slice(pointer, pointer + 5) !== 'prio(') THROW('Expecting the priorities to follow the `@list`');
pointer += 5;
mod.list = parseNumList();
is(')', 'list end');
}
function parseMarkov(mod) {
while (true) {
skipWhitespaces();
if (str.slice(pointer, pointer + 7) === 'matrix(') {
// TOFIX: there is no validation here. apply stricter and safe matrix parsing
let matrix = str.slice(pointer + 7, pointer = str.indexOf(')', pointer));
let code = 'return ' + matrix;
let func = Function(code); /* eslint no-new-func: "off" */
mod.matrix = func();
if (pointer === -1) THROW('The matrix must be closed by a `)` but did not find any');
} else if (str.slice(pointer, pointer + 7) === 'legend(') {
pointer += 7;
mod.legend = parseNumList();
skipWhitespaces();
is(')', 'legend closer');
} else if (str.slice(pointer, pointer + 7) === 'expand(') {
pointer += 7;
mod.expandVectorsWith = parseNumber();
skipWhitespaces();
is(')', 'expand closer');
} else {
break;
}
skip();
}
}
function skipComment() {
is('#', 'comment start'); //is('#', 'comment hash');
while (!isEof() && !isNewline(read())) skip();
if (!isEof()) skip();
}
function parseUndefConstraint() {
// parse a constraint that does not return a value itself
// first try to parse single value constraints without value like markov() and distinct()
if (parseUexpr()) return;
// so the first value must be a value returning expr
let A = parseVexpr(); // returns a var name or a constant value
skipWhitespaces();
let cop = parseCop();
skipWhitespaces();
switch (cop) {
case '=':
parseAssignment(A);
break;
case '==':
solver.eq(A, parseVexpr());
break;
case '!=':
solver.neq(A, parseVexpr());
break;
case '<':
solver.lt(A, parseVexpr());
break;
case '<=':
solver.lte(A, parseVexpr());
break;
case '>':
solver.gt(A, parseVexpr());
break;
case '>=':
solver.gte(A, parseVexpr());
break;
default:
if (cop) THROW('Unknown constraint op: [' + cop + ']');
}
expectEol();
}
function parseAssignment(C) {
// note: if Solver api changes this may return the wrong value...
// it should always return the "result var" var name or constant
// (that would be C, but C may be undefined here and created by Solver)
if (typeof C === 'string' && !solver.hasVar(C)) C = solver.decl(C);
let A = parseVexpr(C);
skipWhitespaces();
let c = read();
if (isEof() || isNewline(c) || isComment(c)) return A; // any group without "top-level" op (`A=(B+C)`), or sum() etc
return parseAssignRest(A, C);
}
function parseAssignRest(A, C) {
let rop = parseRop();
skipWhitespaces();
switch (rop) {
case '==?':
return solver.isEq(A, parseVexpr(), C);
case '!=?':
return solver.isNeq(A, parseVexpr(), C);
case '<?':
return solver.isLt(A, parseVexpr(), C);
case '<=?':
return solver.isLte(A, parseVexpr(), C);
case '>?':
return solver.isGt(A, parseVexpr(), C);
case '>=?':
return solver.isGte(A, parseVexpr(), C);
case '+':
return solver.plus(A, parseVexpr(), C);
case '-':
return solver.minus(A, parseVexpr(), C);
case '*':
return solver.times(A, parseVexpr(), C);
case '/':
return solver.div(A, parseVexpr(), C);
default:
if (rop !== undefined) THROW('Unknown rop: `' + rop + '`');
return A;
}
}
function parseCop() {
let c = read();
switch (c) {
case '=':
skip();
if (read() === '=') {
skip();
return '==';
}
return '=';
case '!':
skip();
if (read() === '=') {
skip();
return '!=';
}
return '!';
case '<':
skip();
if (read() === '=') {
skip();
return '<=';
}
return '<';
case '>':
skip();
if (read() === '=') {
skip();
return '>=';
}
return '>';
case '#':
THROW('Expected to parse a cop but found a comment instead');
break;
default:
if (isEof()) THROW('Expected to parse a cop but reached eof instead');
THROW('Unknown cop char: `' + c + '`');
}
}
function parseRop() {
let a = read();
switch (a) {
case '=':
skip();
let b = read();
if (b === '=') {
skip();
is('?', 'reifier suffix');
return '==?';
} else {
return '=';
}
case '!':
skip();
is('=', 'middle part of !=? op');
is('?', 'reifier suffix');
return '!=?';
case '<':
skip();
if (read() === '=') {
skip();
is('?', 'reifier suffix');
return '<=?';
} else {
is('?', 'reifier suffix');
return '<?';
}
case '>':
skip();
if (read() === '=') {
skip();
is('?', 'reifier suffix');
return '>=?';
} else {
is('?', 'reifier suffix');
return '>?';
}
case '+':
case '-':
case '*':
case '/':
skip();
return a;
default:
THROW('Wanted to parse a rop but next char is `' + a + '`');
}
}
function parseUexpr() {
// it's not very efficient (we could parse an ident before and check that result here) but it'll work for now
if (str.slice(pointer, pointer + 9) === 'distinct(') parseDistinct();
else return false;
return true;
}
function parseDistinct() {
pointer += 9;
skipWhitespaces();
let vals = parseVexpList();
solver.distinct(vals);
skipWhitespaces();
is(')', 'distinct call closer');
expectEol();
}
function parseVexpList() {
let list = [];
skipWhitespaces();
while (!isEof() && read() !== ')') {
let v = parseVexpr();
list.push(v);
skipWhitespaces();
if (read() === ',') {
skip();
skipWhitespaces();
}
}
return list;
}
function parseVexpr(resultVar) {
// valcall, ident, number, group
let c = read();
let v;
if (c === '(') v = parseGrouping();
else if (c === '[') {
let d = parseDomain();
if (d[0] === d[1] && d.length === 2) v = d[0];
else v = solver.decl(undefined, d);
} else if (c >= '0' && c <= '9') {
v = parseNumber();
} else {
let ident = parseIdentifier();
if (read() === '(') {
if (ident === 'sum') v = parseSum(resultVar);
else if (ident === 'product') v = parseProduct(resultVar);
else THROW('Unknown constraint func: ' + ident);
} else {
v = ident;
}
}
return v;
}
function parseGrouping() {
is('(', 'group open');
skipWhitespaces();
let A = parseVexpr();
skipWhitespaces();
if (read() === '=') {
if (read() !== '=') {
parseAssignment(A);
skipWhitespaces();
is(')', 'group closer');
return A;
}
}
if (read() === ')') {
// just wrapping a vexpr is okay
skip();
return A;
}
let C = parseAssignRest(A);
skipWhitespaces();
is(')', 'group closer');
return C;
}
function parseNumber() {
let start = pointer;
while (read() >= '0' && read() <= '9') skip();
if (start === pointer) {
THROW('Expecting to parse a number but did not find any digits [' + start + ',' + pointer + '][' + read() + ']');
}
return parseInt(str.slice(start, pointer), 10);
}
function parseSum(result) {
is('(', 'sum call opener');
skipWhitespaces();
let refs = parseVexpList();
let r = solver.sum(refs, result);
skipWhitespaces();
is(')', 'sum closer');
return r;
}
function parseProduct(result) {
is('(', 'product call opener');
skipWhitespaces();
let refs = parseVexpList();
let r = solver.product(refs, result);
skipWhitespaces();
is(')', 'product closer');
return r;
}
function parseNumstr() {
let start = pointer;
while (read() >= '0' && read() <= '9') skip();
return str.slice(start, pointer);
}
function parseNumList() {
let nums = [];
skipWhitespaces();
let numstr = parseNumstr();
while (numstr) {
nums.push(parseInt(numstr, 10));
skipWhitespaces();
if (read() === ',') {
++pointer;
skipWhitespaces();
}
numstr = parseNumstr();
}
if (!nums.length) THROW('Expected to parse a list of at least some numbers but found none');
return nums;
}
function parseIdentList() {
let idents = [];
while (true) {
skipWhitespaces();
if (read() === ')') break;
if (read() === ',') {
skip();
skipWhitespaces();
}
let ident = parseIdentifier();
idents.push(ident);
}
if (!idents.length) THROW('Expected to parse a list of at least some identifiers but found none');
return idents;
}
function readLine() {
let line = '';
while (!isEof() && !isNewline(read())) {
line += read();
skip();
}
return line;
}
function parseAtRule() {
is('@');
// mostly temporary hacks while the dsl stabilizes...
if (str.slice(pointer, pointer + 6) === 'custom') {
pointer += 6;
skipWhitespaces();
let ident = parseIdentifier();
skipWhitespaces();
if (read() === '=') {
skip();
skipWhitespaces();
}
switch (ident) {
case 'var-strat':
parseVarStrat();
break;
case 'val-strat':
parseValStrat();
break;
case 'set-valdist':
skipWhitespaces();
let target = parseIdentifier();
let config = parseRestCustom();
solver.setValueDistributionFor(target, JSON.parse(config));
break;
default:
THROW('Unsupported custom rule: ' + ident);
}
} else if (str.slice(pointer, pointer + 7) === 'targets') {
pointer += 7;
parseTargets();
} else if (str.slice(pointer, pointer + 4) === 'mode') {
pointer += 4;
parseMode();
} else {
THROW('Unknown atrule');
}
expectEol();
}
function parseVarStrat() {
let json = readLine();
expectEol();
solver.varStratConfig = JSON.parse(json);
}
function parseValStrat() {
let name = parseIdentifier();
expectEol();
solver.valueStratName = name;
}
function parseRestCustom() {
skipWhitespaces();
if (read() === '=') {
skip();
skipWhitespaces();
}
return readLine();
}
function parseTargets() {
skipWhitespaces();
if (read() === '=') {
skip();
skipWhitespaces();
}
if (str.slice(pointer, pointer + 3) === 'all') {
pointer += 3;
solver.config.targetedVars = 'all';
} else {
is('(');
let idents = parseIdentList();
if (idents.length) solver.config.targetedVars = idents;
is(')');
}
expectEol();
}
function parseMode() {
skipWhitespaces();
if (read() === '=') {
skip();
skipWhitespaces();
}
if (str.slice(pointer, pointer + 'constraints'.length) === 'constraints') {
// input consists of high level constraints. generate low level optimizations.
pointer += 'constraints'.length;
} else if (str.slice(pointer, pointer + 'propagators'.length) === 'propagators') {
// input consists of low level constraints. try not to generate more.
pointer += 'propagators'.length;
}
}
function THROW(msg) {
if (_debug) {
console.log(str.slice(0, pointer) + '##|PARSER_IS_HERE[' + msg + ']|##' + str.slice(pointer));
}
msg += ', source at #|#: `' + str.slice(Math.max(0, pointer - 20), pointer) + '#|#' + str.slice(pointer, Math.min(str.length, pointer + 20)) + '`';
throw new Error(msg);
}
}
// end of src/importer.js
// from: src/markov.js
/**
* If a row has no boolean condition, return it.
* If the boolean condition of a row is 1, return it.
* If no row meets these conditions, return the last row.
*
* @param {$space} space
* @param {?} matrix
* @returns {*}
*/
function markov_getNextRowToSolve(space, matrix) {
let vardoms = space.vardoms;
for (let i = 0; i < matrix.length; i++) {
var row = matrix[i];
let boolDomain = vardoms[row._boolVarIndex];
if (boolDomain === undefined || domain_getValue(boolDomain) === 1) {
break;
}
}
return row;
}
function markov_createLegend(merge, inputLegend, domain) {
if (merge) {
return markov_mergeDomainAndLegend(inputLegend, domain);
}
return inputLegend;
}
function markov_mergeDomainAndLegend(inputLegend, domain) {
let legend;
if (inputLegend) {
legend = inputLegend.slice(0);
} else {
legend = [];
}
let listed = domain_toList(domain);
for (let i = 0; i < listed.length; ++i) {
let val = listed[i];
if (legend.indexOf(val) < 0) {
legend.push(val);
}
}
return legend;
}
function markov_createProbVector(space, matrix, expandVectorsWith, valueCount) {
let row = markov_getNextRowToSolve(space, matrix);
let probVector = row.vector;
if (expandVectorsWith != null) { // could be 0
probVector = probVector ? probVector.slice(0) : [];
let delta = valueCount - probVector.length;
if (delta > 0) {
for (let i = 0; i < delta; ++i) {
probVector.push(expandVectorsWith);
}
}
return probVector;
}
if (!probVector || probVector.length !== valueCount) {
THROW('E_EACH_MARKOV_VAR_MUST_HAVE_PROB_VECTOR_OR_ENABLE_EXPAND_VECTORS');
}
return probVector;
}
// end of src/markov.js
// from: src/propagator.js
/**
* @param {string} name
* @param {Function} stepFunc
* @param {number} index1
* @param {number} [index2=-1]
* @param {number} [index3=-1]
* @param {string} [arg1='']
* @param {string} [arg2='']
* @param {string} [arg3='']
* @param {string} [arg4='']
* @param {string} [arg5='']
* @param {string} [arg6='']
* @returns {$propagator}
*/
function propagator_create(name, stepFunc, index1, index2, index3, arg1, arg2, arg3, arg4, arg5, arg6) {
return {
_class: '$propagator',
name: name,
stepper: stepFunc,
index1: index1 === undefined ? -1 : index1,
index2: index2 === undefined ? -1 : index2,
index3: index3 === undefined ? -1 : index3,
arg1: arg1 === undefined ? '' : arg1,
arg2: arg2 === undefined ? '' : arg2,
arg3: arg3 === undefined ? '' : arg3,
arg4: arg4 === undefined ? '' : arg4,
arg5: arg5 === undefined ? '' : arg5,
arg6: arg6 === undefined ? '' : arg6,
};
}
/**
* Adds propagators which reify the given operator application
* to the given boolean variable.
*
* `opname` is a string giving the name of the comparison
* operator to reify. Currently, 'eq', 'neq', 'lt', 'lte', 'gt' and 'gte'
* are supported.
*
* `leftVarIndex` and `rightVarIndex` are the arguments accepted
* by the comparison operator.
*
* `resultVarIndex` is the name of the boolean variable to which to
* reify the comparison operator. Note that this boolean
* variable must already have been declared. If this argument
* is omitted from the call, then the `reified` function can
* be used in "functional style" and will return the name of
* the reified boolean variable which you can pass to other
* propagator creator functions.
*
* @param {$config} config
* @param {string} opname
* @param {number} leftVarIndex
* @param {number} rightVarIndex
* @param {number} resultVarIndex
*/
function propagator_addReified(config, opname, leftVarIndex, rightVarIndex, resultVarIndex) {
let initialDomains = config.initialDomains;
let A = initialDomains[leftVarIndex];
let B = initialDomains[rightVarIndex];
let C = initialDomains[resultVarIndex] = domain_removeGte(initialDomains[resultVarIndex], 2);
let valueA = domain_getValue(A);
let valueB = domain_getValue(B);
let valueC = domain_getValue(C);
// the reifier is solved if all three vars are solved
let solved = 0;
if (valueA >= 0) ++solved;
if (valueB >= 0) ++solved;
if (valueC >= 0) ++solved;
if (solved === 3) return;
let minA = domain_min(A);
let maxA = domain_max(A);
let minB = domain_min(B);
let maxB = domain_max(B);
// the reifier can be rewritten if any two of the three vars are solved
// the reifier might be rewritable if one var is solved
// in some cases certain constraints can be decided without being solved ([0,4]<[5,10] always holds)
// the actual rewrites depends on the op, though
let nopName;
let opFunc;
let nopFunc;
let opRejectChecker;
let nopRejectChecker;
switch (opname) {
case 'eq': {
// R = A ==? B
// 1 = A ==? B -> A == B
// 0 = A ==? B -> A != B
// R = x ==? B -> check if B contains value x, solve accordingly
// if B is boolean we can apply even more special rules (we know R is boolean)
// R = 0 ==? B[0 1] -> R != B
// R = 1 ==? B[0 1] -> R == B
if (valueC >= 0) { // result solved
if (valueA >= 0) {
if (valueC) initialDomains[rightVarIndex] = A;
else initialDomains[rightVarIndex] = domain_removeValue(B, valueA);
} else if (valueB >= 0) {
if (valueC) initialDomains[leftVarIndex] = B;
else initialDomains[leftVarIndex] = domain_removeValue(A, valueB);
} else {
// neither A nor B is solved; simplify
if (valueC) propagator_addEq(config, leftVarIndex, rightVarIndex);
else propagator_addNeq(config, leftVarIndex, rightVarIndex);
}
return;
}
if (valueA >= 0 && valueB >= 0) {
initialDomains[resultVarIndex] = domain_createValue(valueA === valueB ? 1 : 0);
return;
}
// C isnt solved, and A and B arent both solved
// check the cases of one side solved and other side bool
if (maxA <= 1 && maxB === 1) {
if (valueA === 0) return propagator_addNeq(config, rightVarIndex, resultVarIndex);
else if (valueA === 1) return propagator_addEq(config, rightVarIndex, resultVarIndex);
}
if (maxB <= 1 && maxA === 1) {
if (valueB === 0) return propagator_addNeq(config, leftVarIndex, resultVarIndex);
else if (valueB === 1) return propagator_addEq(config, leftVarIndex, resultVarIndex);
}
nopName = 'neq';
opFunc = propagator_eqStepBare;
nopFunc = propagator_neqStepBare;
opRejectChecker = propagator_eqStepWouldReject;
nopRejectChecker = propagator_neqStepWouldReject;
break;
}
case 'neq': {
// similar optimizations to eq. just inversed.
if (valueC >= 0) { // result solved
if (valueA >= 0) {
if (valueC) initialDomains[rightVarIndex] = domain_removeValue(B, valueA);
else initialDomains[rightVarIndex] = A;
} else if (valueB >= 0) {
if (valueC) initialDomains[leftVarIndex] = domain_removeValue(A, valueB);
else initialDomains[leftVarIndex] = B;
} else {
// neither A nor B is solved; simplify
if (valueC) propagator_addNeq(config, leftVarIndex, rightVarIndex);
else propagator_addEq(config, leftVarIndex, rightVarIndex);
}
return;
}
if (valueA >= 0 && valueB >= 0) {
initialDomains[resultVarIndex] = domain_createValue(valueA === valueB ? 0 : 1);
return;
}
// C isnt solved, and A and B arent both solved
// check the cases of one side solved and other side bool
if (maxA <= 1 && maxB === 1) {
if (valueA === 0) return propagator_addEq(config, rightVarIndex, resultVarIndex);
else if (valueA === 1) return propagator_addNeq(config, rightVarIndex, resultVarIndex);
}
if (maxB <= 1 && maxA === 1) {
if (valueB === 0) return propagator_addEq(config, leftVarIndex, resultVarIndex);
else if (valueB === 1) return propagator_addNeq(config, leftVarIndex, resultVarIndex);
}
nopName = 'eq';
opFunc = propagator_neqStepBare;
nopFunc = propagator_eqStepBare;
opRejectChecker = propagator_neqStepWouldReject;
nopRejectChecker = propagator_eqStepWouldReject;
break;
}
case 'lt':
// R = A <? B
// x = A <? B -> reduce A and B regardless, drop constraint
// R = x <? B -> check if B >= x, solve accordingly
// R = 0 <? B[0 1] -> R == B
if (valueC >= 0) { // result solved
// either this resolves the constraint or we compile a non-reifier for the remainder
if (valueC) {
if (maxA < minB) return;
return propagator_addLt(config, leftVarIndex, rightVarIndex);
}
// C=0 so solve if all A >= all B
if (minA >= maxB) return;
return propagator_addGte(config, leftVarIndex, rightVarIndex);
}
// regardless of being solved, check if the domains are already solving < as is
if (maxA < minB) return initialDomains[resultVarIndex] = domain_createValue(1);
if (minA >= maxB) return initialDomains[resultVarIndex] = domain_createValue(0);
if (valueA === 0 && maxB <= 1) return propagator_addEq(config, rightVarIndex, resultVarIndex);
if (valueB === 0 && maxA <= 1) return propagator_addEq(config, leftVarIndex, resultVarIndex);
opFunc = propagator_neqStepBare;
opRejectChecker = propagator_ltStepWouldReject;
nopName = 'gte';
nopFunc = propagator_gteStepBare;
nopRejectChecker = propagator_gteStepWouldReject;
break;
case 'lte':
// R = A <=? B
// x = A <=? B -> reduce A and B regardless, drop constraint
// R = x <=? B -> check if B > x, solve accordingly
// R = 1 <=? B[0,1] -> eq(R, B)
if (valueC >= 0) { // result solved
// either this resolves the constraint or we compile a non-reifier for the remainder
if (valueC) {
if (maxA <= minB) return;
return propagator_addLte(config, leftVarIndex, rightVarIndex);
}
// C=0 so solve if all A > all B
if (minA > maxB) return;
return propagator_addGt(config, leftVarIndex, rightVarIndex);
}
// regardless of being solved, check if the domains are already solving < as is
if (maxA <= minB) return initialDomains[resultVarIndex] = domain_createValue(1);
if (minA > maxB) return initialDomains[resultVarIndex] = domain_createValue(0);
if (valueA === 1 && maxB <= 1) return propagator_addEq(config, rightVarIndex, resultVarIndex);
if (valueB === 1 && maxA <= 1) return propagator_addEq(config, leftVarIndex, resultVarIndex);
opFunc = propagator_lteStepBare;
opRejectChecker = propagator_lteStepWouldReject;
nopName = 'gt';
nopFunc = propagator_gtStepBare;
nopRejectChecker = propagator_gtStepWouldReject;
break;
case 'gt':
return propagator_addReified(config, 'lt', rightVarIndex, leftVarIndex, resultVarIndex);
case 'gte':
return propagator_addReified(config, 'lte', rightVarIndex, leftVarIndex, resultVarIndex);
default:
THROW('UNKNOWN_REIFIED_OP');
}
config_addPropagator(config, propagator_create('reified', propagator_reifiedStepBare, leftVarIndex, rightVarIndex, resultVarIndex, opFunc, nopFunc, opname, nopName, opRejectChecker, nopRejectChecker));
}
/**
* Domain equality propagator. Creates the propagator
* in given config.
* Can pass in vars or numbers that become anonymous
* vars. Must at least pass in one var because the
* propagator would be useless otherwise.
*
* @param {$config} config
* @param {number} leftVarIndex
* @param {number} rightVarIndex
*/
function propagator_addEq(config, leftVarIndex, rightVarIndex) {
let initialDomains = config.initialDomains;
let A = initialDomains[leftVarIndex];
if (domain_getValue(A) >= 0) return initialDomains[rightVarIndex] = A;
let B = initialDomains[rightVarIndex];
if (domain_getValue(B) >= 0) return initialDomains[leftVarIndex] = B;
initialDomains[leftVarIndex] = initialDomains[rightVarIndex] = domain_intersection(A, B);
config_addPropagator(config, propagator_create('eq', propagator_eqStepBare, leftVarIndex, rightVarIndex));
}
/**
* Less than propagator. See general propagator nores
* for fdeq which also apply to this one.
*
* @param {$config} config
* @param {number} leftVarIndex
* @param {number} rightVarIndex
*/
function propagator_addLt(config, leftVarIndex, rightVarIndex) {
let initialDomains = config.initialDomains;
let A = initialDomains[leftVarIndex];
let B = initialDomains[rightVarIndex];
let maxA = domain_max(A);
let minB = domain_min(B);
// A |----|
// B |--|
if (maxA < minB) return; // solved
let minA = domain_min(A);
let maxB = domain_max(B);
// A |----|
// B |--|
if (minA >= maxB) return initialDomains[leftVarIndex] = initialDomains[rightVarIndex] = domain_createEmpty();
// not solved nor rejected. prune invalid values
// A |-------| -> |---|
// B |----| |----|
if (maxA >= maxB) initialDomains[leftVarIndex] = domain_removeGte(A, maxB);
// A |-----| -> |----|
// B |-------| |---|
if (minB <= minA) initialDomains[rightVarIndex] = domain_removeLte(B, minA);
config_addPropagator(config, propagator_create('lt', propagator_ltStepBare, leftVarIndex, rightVarIndex));
}
/**
* Greater than propagator.
*
* @param {$config} config
* @param {number} leftVarIndex
* @param {number} rightVarIndex
*/
function propagator_addGt(config, leftVarIndex, rightVarIndex) {
// _swap_ v1 and v2 because: a>b is b<a
propagator_addLt(config, rightVarIndex, leftVarIndex);
}
/**
* Less than or equal to propagator.
*
* @param {$config} config
* @param {number} leftVarIndex
* @param {number} rightVarIndex
*/
function propagator_addLte(config, leftVarIndex, rightVarIndex) {
let initialDomains = config.initialDomains;
let A = initialDomains[leftVarIndex];
let B = initialDomains[rightVarIndex];
let maxA = domain_max(A);
let minB = domain_min(B);
// A |----|
// B |--|
if (maxA < minB) return; // solved
let minA = domain_min(A);
let maxB = domain_max(B);
// A |----|
// B |--|
if (minA > maxB) return initialDomains[leftVarIndex] = initialDomains[rightVarIndex] = domain_createEmpty();
// not solved nor rejected. prune invalid values
// A |-------| -> |----|
// B |----| |----|
if (maxA >= maxB) initialDomains[leftVarIndex] = domain_removeGte(A, maxB + 1);
// A |-----| -> |----|
// B |-------| |----|
if (minB <= minA) initialDomains[rightVarIndex] = domain_removeLte(B, minA - 1);
config_addPropagator(config, propagator_create('lte', propagator_lteStepBare, leftVarIndex, rightVarIndex));
}
/**
* @param {$config} config
* @param {number} leftVarIndex
* @param {number} rightVarIndex
* @param {number} resultVarIndex
*/
function propagator_addMul(config, leftVarIndex, rightVarIndex, resultVarIndex) {
if (propagator_mulConstraintResolved(config, leftVarIndex, rightVarIndex, resultVarIndex)) return;
config_addPropagator(config, propagator_create('mul', propagator_mulStep, leftVarIndex, rightVarIndex, resultVarIndex));
}
/**
* Would a mul for given vars need a constraint?
*
* @param {$config} config
* @param {number} varIndexA
* @param {number} varIndexB
* @param {number} varIndexC
* @returns {boolean}
*/
function propagator_mulConstraintResolved(config, varIndexA, varIndexB, varIndexC) {
let initialDomains = config.initialDomains;
let A = initialDomains[varIndexA];
let B = initialDomains[varIndexB];
let C = initialDomains[varIndexC];
let maxA = domain_max(A);
let maxB = domain_max(B);
// if A and B is unsolved just do a bounds check on result for [lo*lo, hi*hi]
let vA = domain_getValue(A);
let vB = domain_getValue(B);
let vC = domain_getValue(C);
if (vA >= 0) {
if (vB >= 0) {
initialDomains[varIndexC] = domain_intersection(C, domain_createValue(vA * vB));
return true;
}
if (vA === 0) {
// C must be 0 and B can be anything
initialDomains[varIndexC] = domain_intersection(C, domain_createValue(0));
return true;
}
if (vC >= 0) {
if (vC === 0) {
// if a is zero, b can be anything. otherwise, b must be zero (or the result couldn't be zero)
if (vA !== 0) initialDomains[varIndexB] = domain_intersection(B, domain_createValue(0));
} else {
let b = (vA % vC) ? domain_createEmpty() : domain_createValue(vA / vC);
initialDomains[varIndexB] = domain_intersection(B, b);
}
return true;
}
// C can only contain values that equals b*vA for any b in B
// TODO: this could be dangerous if B _and_ C are very large ranges... should we guard against that?
initialDomains[varIndexC] = domain_intersection(C, domain_mulByValue(B, vA));
initialDomains[varIndexB] = (maxB === 0 || vA === 0) ? B : domain_intersection(B, domain_invMulValue(initialDomains[varIndexC], vA));
} else if (vB >= 0) {
if (vB === 0) {
// C must be 0 and A can be anything
initialDomains[varIndexC] = domain_intersection(C, domain_createValue(0));
return true;
}
if (vC >= 0) {
if (vC === 0) {
// if b is zero, a can be anything. otherwise, a must be zero (or the result couldn't be zero)
if (vB !== 0) initialDomains[varIndexA] = domain_intersection(A, domain_createValue(0));
} else {
let a = (vB % vC) ? domain_createEmpty() : domain_createValue(vB / vC);
initialDomains[varIndexA] = domain_intersection(A, a);
}
return true;
}
// C can only contain values that equals a*vB for any a in A
// TODO: this could be dangerous if A _and_ C are very large ranges... should we guard against that?
initialDomains[varIndexC] = domain_intersection(C, domain_mulByValue(A, vB));
initialDomains[varIndexA] = (maxA === 0 || vB === 0) ? A : domain_intersection(A, domain_invMulValue(initialDomains[varIndexC], vB));
} else {
// simple bounds enforcement
initialDomains[varIndexA] = domain_intersection(A, domain_invMul(C, B));
initialDomains[varIndexB] = domain_intersection(B, domain_invMul(C, A));
initialDomains[varIndexC] = domain_intersection(C, domain_mul(A, B));
}
return false;
}
/**
* @param {$config} config
* @param {number} leftVarIndex
* @param {number} rightVarIndex
* @param {number} resultVarIndex
*/
function propagator_addDiv(config, leftVarIndex, rightVarIndex, resultVarIndex) {
config_addPropagator(config, propagator_create('div', propagator_divStep, leftVarIndex, rightVarIndex, resultVarIndex));
}
/**
* Greater than or equal to.
*
* @param {$config} config
* @param {number} leftVarIndex
* @param {number} rightVarIndex
*/
function propagator_addGte(config, leftVarIndex, rightVarIndex) {
// _swap_ v1 and v2 because: a>=b is b<=a
propagator_addLte(config, rightVarIndex, leftVarIndex);
}
/**
* Ensures that the two variables take on different values.
*
* @param {$config} config
* @param {number} leftVarIndex
* @param {number} rightVarIndex
*/
function propagator_addNeq(config, leftVarIndex, rightVarIndex) {
let initialDomains = config.initialDomains;
let A = initialDomains[leftVarIndex];
let B = initialDomains[rightVarIndex];
let vA = domain_getValue(A);
if (vA >= 0) return initialDomains[rightVarIndex] = domain_removeValue(B, vA);
let vB = domain_getValue(A);
if (vB >= 0) return initialDomains[leftVarIndex] = domain_removeValue(A, vB);
if (domain_isEmpty(domain_intersection(A, B))) return; // no overlapping elements so constraint is redundant
config_addPropagator(config, propagator_create('neq', propagator_neqStepBare, leftVarIndex, rightVarIndex));
}
/**
* Takes an arbitrary number of FD variables and adds propagators that
* ensure that they are pairwise distinct.
*
* @param {$config} config
* @param {number[]} varIndexes
*/
function propagator_addDistinct(config, varIndexes) {
for (let i = 0; i < varIndexes.length; i++) {
let varIndex = varIndexes[i];
for (let j = 0; j < i; ++j) {
propagator_addNeq(config, varIndex, varIndexes[j]);
}
}
}
/**
* @param {$config} config
* @param {string} targetOpName
* @param {string} invOpName
* @param {Function} opFunc
* @param {Function} nopFunc
* @param {number} leftVarIndex
* @param {number} rightVarIndex
* @param {number} resultVarIndex
*/
function propagator_addRingPlusOrMul(config, targetOpName, invOpName, opFunc, nopFunc, leftVarIndex, rightVarIndex, resultVarIndex) {
propagator_addRing(config, leftVarIndex, rightVarIndex, resultVarIndex, targetOpName, opFunc);
propagator_addRing(config, resultVarIndex, rightVarIndex, leftVarIndex, invOpName, nopFunc);
propagator_addRing(config, resultVarIndex, leftVarIndex, rightVarIndex, invOpName, nopFunc);
}
/**
* @param {$config} config
* @param {string} A
* @param {string} B
* @param {string} C
* @param {string} opName
* @param {Function} opFunc
*/
function propagator_addRing(config, A, B, C, opName, opFunc) {
config_addPropagator(config, propagator_create('ring', propagator_ringStepBare, A, B, C, opName, opFunc));
}
/**
* Bidirectional addition propagator.
*
* @param {$config} config
* @param {number} leftVarIndex
* @param {number} rightVarIndex
* @param {number} resultVarIndex
*/
function propagator_addPlus(config, leftVarIndex, rightVarIndex, resultVarIndex) {
propagator_addRingPlusOrMul(config, 'plus', 'min', domain_plus, domain_minus, leftVarIndex, rightVarIndex, resultVarIndex);
}
/**
* @param {$config} config
* @param {number} leftVarIndex
* @param {number} rightVarIndex
* @param {number} resultVarIndex
*/
function propagator_addMin(config, leftVarIndex, rightVarIndex, resultVarIndex) {
config_addPropagator(config, propagator_create('min', propagator_minStep, leftVarIndex, rightVarIndex, resultVarIndex));
}
/**
* Bidirectional multiplication propagator.
*
* @param {$config} config
* @param {number} leftVarIndex
* @param {number} rightVarIndex
* @param {number} resultVarIndex
*/
function propagator_addRingMul(config, leftVarIndex, rightVarIndex, resultVarIndex) {
if (propagator_mulConstraintResolved(config, leftVarIndex, rightVarIndex, resultVarIndex)) return;
propagator_addRingPlusOrMul(config, 'mul', 'div', domain_mul, domain_invMul, leftVarIndex, rightVarIndex, resultVarIndex);
}
/**
* Sum of N domains = resultVar
* Creates as many anonymous varIndexes as necessary.
*
* @param {$config} config
* @param {number[]} varIndexes
* @param {number} resultVarIndex
*/
function propagator_addSum(config, varIndexes, resultVarIndex) {
let len = varIndexes.length;
switch (len) {
case 0:
THROW('SUM_REQUIRES_VARS');
return undefined;
case 1:
propagator_addEq(config, resultVarIndex, varIndexes[0]);
return undefined;
case 2:
propagator_addPlus(config, varIndexes[0], varIndexes[1], resultVarIndex);
return undefined;
}
// "divide and conquer" ugh. feels like there is a better way to do this
let t1;
let n = Math.floor(varIndexes.length / 2);
if (n > 1) {
t1 = config_addVarAnonNothing(config);
propagator_addSum(config, varIndexes.slice(0, n), t1);
} else {
t1 = varIndexes[0];
}
let t2 = config_addVarAnonNothing(config);
propagator_addSum(config, varIndexes.slice(n), t2);
propagator_addPlus(config, t1, t2, resultVarIndex);
}
/**
* Product of N varIndexes = resultVar.
* Create as many anonymous varIndexes as necessary.
*
* @param {$config} config
* @param {number[]} varIndexes
* @param {number} resultVarIndex
*/
function propagator_addProduct(config, varIndexes, resultVarIndex) {
switch (varIndexes.length) {
case 0:
THROW('PRODUCT_REQUIRES_VARS');
return undefined;
case 1:
// note: by putting the result var first we get
// the var name back for it in case it's a number
propagator_addEq(config, resultVarIndex, varIndexes[0]);
return undefined;
case 2:
propagator_addRingMul(config, varIndexes[0], varIndexes[1], resultVarIndex);
return undefined;
}
let n = Math.floor(varIndexes.length / 2);
let t1;
if (n > 1) {
t1 = config_addVarAnonNothing(config);
propagator_addProduct(config, varIndexes.slice(0, n), t1);
} else {
t1 = varIndexes[0];
}
let t2 = config_addVarAnonNothing(config);
propagator_addProduct(config, varIndexes.slice(n), t2);
propagator_addRingMul(config, t1, t2, resultVarIndex);
}
/**
* @param {$config} config
* @param {number} varIndex
*/
function propagator_addMarkov(config, varIndex) {
config_addPropagator(config, propagator_create('markov', propagator_markovStepBare, varIndex));
}
// end of src/propagator.js
// from: src/propagators/div.js
/**
* @param {$space} space
* @param {$config} config
* @param {number} varIndex1
* @param {number} varIndex2
* @param {number} varIndex3
* @returns {$fd_changeState}
*/
function propagator_divStep(space, config, varIndex1, varIndex2, varIndex3) {
let domain1 = space.vardoms[varIndex1];
let domain2 = space.vardoms[varIndex2];
let domain3 = space.vardoms[varIndex3];
space.vardoms[varIndex3] = _propagator_divStep(domain1, domain2, domain3);
}
/**
* @param {$domain} domain1
* @param {$domain} domain2
* @param {$domain} domResult
* @returns {$domain}
*/
function _propagator_divStep(domain1, domain2, domResult) {
let domain = domain_divby(domain1, domain2);
return domain_intersection(domResult, domain);
}
// end of src/propagators/div.js
// from: src/propagators/eq.js
/**
* This eq propagator looks a lot different from neq because in
* eq we can prune early all values that are not covered by both.
* Any value that is not covered by both can not be a valid solution
* that holds this constraint. In neq that's different and we can
* only start pruning once at least one var has a solution.
* Basically eq is much more efficient compared to neq because we
* can potentially skip a lot of values early.
*
* @param {$space} space
* @param {$config} config
* @param {number} varIndex1
* @param {number} varIndex2
* @returns {$fd_changeState}
*/
function propagator_eqStepBare(space, config, varIndex1, varIndex2) {
let vardoms = space.vardoms;
let domain1 = vardoms[varIndex1];
let domain2 = vardoms[varIndex2];
let result = domain_intersection(domain1, domain2);
vardoms[varIndex1] = result;
vardoms[varIndex2] = result;
}
/**
* The eq step would reject if there all elements in one domain
* do not occur in the other domain. Because then there's no
* valid option to make sure A=B holds. So search for such value
* or return false.
* Read only check
*
* @param {$domain} domain1
* @param {$domain} domain2
* @returns {boolean}
*/
function propagator_eqStepWouldReject(domain1, domain2) {
let result = domain_sharesNoElements(domain1, domain2);
return result;
}
// end of src/propagators/eq.js
// from: src/propagators/lt.js
/**
* @param {$space} space
* @param {$config} config
* @param {number} varIndex1
* @param {number} varIndex2
*/
function propagator_ltStepBare(space, config, varIndex1, varIndex2) {
let domain1 = space.vardoms[varIndex1];
let domain2 = space.vardoms[varIndex2];
let lo1 = domain_min(domain1);
let hi2 = domain_max(domain2);
space.vardoms[varIndex1] = domain_removeGte(domain1, hi2);
space.vardoms[varIndex2] = domain_removeLte(domain2, lo1);
}
function propagator_gtStepBare(space, config, varIndex1, varIndex2) {
return propagator_ltStepBare(space, config, varIndex2, varIndex1);
}
/**
* lt would reject if all elements in the left var are bigger or equal to
* the right var. And since everything is CSIS, we only have to check the
* lo bound of left to the high bound of right for that answer.
* Read-only check
*
* @param {$domain} domain1
* @param {$domain} domain2
* @returns {boolean}
*/
function propagator_ltStepWouldReject(domain1, domain2) {
let result = domain_min(domain1) >= domain_max(domain2);
return result;
}
/**
* Reverse of propagator_ltStepWouldReject
*
* @param {$domain} domain1
* @param {$domain} domain2
* @returns {boolean}
*/
function propagator_gtStepWouldReject(domain1, domain2) {
let result = propagator_ltStepWouldReject(domain2, domain1);
return result;
}
// end of src/propagators/lt.js
// from: src/propagators/lte.js
/**
* @param {$space} space
* @param {$config} config
* @param {number} varIndex1
* @param {number} varIndex2
* @returns {$fd_changeState}
*/
function propagator_lteStepBare(space, config, varIndex1, varIndex2) {
let domain1 = space.vardoms[varIndex1];
let domain2 = space.vardoms[varIndex2];
let lo1 = domain_min(domain1);
let hi2 = domain_max(domain2);
space.vardoms[varIndex1] = domain_removeGte(domain1, hi2 + 1);
space.vardoms[varIndex2] = domain_removeLte(domain2, lo1 - 1);
}
function propagator_gteStepBare(space, config, varIndex1, varIndex2) {
return propagator_lteStepBare(space, config, varIndex2, varIndex1);
}
/**
* lte would reject if all elements in the left var are bigger than the
* right var. And since everything is CSIS, we only have to check the
* lo bound of left to the high bound of right for that answer.
*
* @param {$domain} domain1
* @param {$domain} domain2
* @returns {boolean}
*/
function propagator_lteStepWouldReject(domain1, domain2) {
let result = domain_min(domain1) > domain_max(domain2);
return result;
}
/**
* Reverse of propagator_lteStepWouldReject
*
* @param {$domain} domain1
* @param {$domain} domain2
* @returns {boolean}
*/
function propagator_gteStepWouldReject(domain1, domain2) {
let result = propagator_lteStepWouldReject(domain2, domain1);
return result;
}
// end of src/propagators/lte.js
// from: src/propagators/markov.js
/**
* Markov uses a special system for trying values. The domain doesn't
* govern the list of possible values, only acts as a mask for the
* current node in the search tree (-> space). But since FD will work
* based on this domain anyways we will need this extra step to verify
* whether a solved var is solved to a valid value in current context.
*
* Every markov variable should have a propagator. Perhaps later
* there can be one markov propagator that checks all markov vars.
*
* @param {$space} space
* @param {$config} config
* @param {number} varIndex
*/
function propagator_markovStepBare(space, config, varIndex) {
// THIS IS VERY EXPENSIVE IF expandVectorsWith IS ENABLED
let domain = space.vardoms[varIndex];
if (!domain_isSolved(domain)) {
return;
}
let value = domain_min(domain); // note: solved so lo=hi=value
let configVarDistOptions = config.varDistOptions;
let distributeOptions = configVarDistOptions[config.allVarNames[varIndex]];
let expandVectorsWith = distributeOptions.expandVectorsWith;
// note: expandVectorsWith can be 0, so check with null
let values = markov_createLegend(expandVectorsWith != null, distributeOptions.legend, domain); // TODO: domain is a value, can this be optimized? is that worth the effort? (profile this)
let probabilities = markov_createProbVector(space, distributeOptions.matrix, expandVectorsWith, values.length);
let pos = values.indexOf(value);
if (pos < 0 || pos >= probabilities.length || probabilities[pos] === 0) {
space.vardoms[varIndex] = domain_createEmpty();
}
}
// end of src/propagators/markov.js
// from: src/propagators/min.js
/**
* Min as in minus. Only updates the result domain.
*
* @param {$space} space
* @param {$config} config
* @param {number} varIndex1
* @param {number} varIndex2
* @param {number} varIndex3
*/
function propagator_minStep(space, config, varIndex1, varIndex2, varIndex3) {
let domain1 = space.vardoms[varIndex1];
let domain2 = space.vardoms[varIndex2];
let domain3 = space.vardoms[varIndex3];
// TODO: prune domain1 and domain2 like ring does, but here
space.vardoms[varIndex3] = _propagator_minStep(domain1, domain2, domain3);
}
/**
* @param {$domain} domain1
* @param {$domain} domain2
* @param {$domain} domResult
* @returns {$domain}
*/
function _propagator_minStep(domain1, domain2, domResult) {
let domain = domain_minus(domain1, domain2);
return domain_intersection(domResult, domain);
}
// end of src/propagators/min.js
// from: src/propagators/mul.js
/**
* @param {$space} space
* @param {$config} config
* @param {number} varIndex1
* @param {number} varIndex2
* @param {number} varIndex3
*/
function propagator_mulStep(space, config, varIndex1, varIndex2, varIndex3) {
let vardoms = space.vardoms;
let domain1 = vardoms[varIndex1];
let domain2 = vardoms[varIndex2];
let domain3 = vardoms[varIndex3];
space.vardoms[varIndex3] = _propagator_mulStep(domain1, domain2, domain3);
}
/**
* @param {$domain} domain1
* @param {$domain} domain2
* @param {$domain} domResult
* @returns {$domain}
*/
function _propagator_mulStep(domain1, domain2, domResult) {
let domain = domain_mul(domain1, domain2);
return domain_intersection(domResult, domain);
}
// end of src/propagators/mul.js
// from: src/propagators/neq.js
/**
* @param {$space} space
* @param {$config} config
* @param {number} varIndex1
* @param {number} varIndex2
*/
function propagator_neqStepBare(space, config, varIndex1, varIndex2) {
let vardoms = space.vardoms;
let domain1 = vardoms[varIndex1];
let domain2 = vardoms[varIndex2];
// remove solved value from the other domain. confirm neither rejects over it.
let value = domain_getValue(domain1);
if (value !== NO_SUCH_VALUE) {
if (domain1 === domain2) {
vardoms[varIndex1] = domain_createEmpty();
vardoms[varIndex2] = domain_createEmpty();
} else {
vardoms[varIndex2] = domain_removeValue(domain2, value);
}
} else {
// domain1 is not solved, remove domain2 from domain1 if domain2 is solved
value = domain_getValue(domain2);
if (value !== NO_SUCH_VALUE) {
vardoms[varIndex1] = domain_removeValue(domain1, value);
}
}
}
/**
* neq will only reject if both domains are solved and equal.
* This is a read-only check.
*
* @param {$domain} domain1
* @param {$domain} domain2
* @returns {boolean}
*/
function propagator_neqStepWouldReject(domain1, domain2) {
let value = domain_getValue(domain1);
let result = value !== NO_SUCH_VALUE && value === domain_getValue(domain2);
return result;
}
// end of src/propagators/neq.js
// from: src/propagators/reified.js
let REIFIER_FAIL = 0;
let REIFIER_PASS = 1;
/**
* A boolean variable that represents whether a comparison
* condition between two variables currently holds or not.
*
* @param {$space} space
* @param {$config} config
* @param {number} leftVarIndex
* @param {number} rightVarIndex
* @param {number} resultVarIndex
* @param {Function} opFunc like propagator_ltStepBare
* @param {Function} nopFunc opposite of opFunc like propagator_gtStepBare
* @param {string} opName
* @param {string} invOpName
* @param {Function} opRejectChecker
* @param {Function} nopRejectChecker
*/
function propagator_reifiedStepBare(space, config, leftVarIndex, rightVarIndex, resultVarIndex, opFunc, nopFunc, opName, invOpName, opRejectChecker, nopRejectChecker) {
let vardoms = space.vardoms;
let domResult = vardoms[resultVarIndex];
let value = domain_getValue(domResult);
if (value === REIFIER_FAIL) {
nopFunc(space, config, leftVarIndex, rightVarIndex);
} else if (value === REIFIER_PASS) {
opFunc(space, config, leftVarIndex, rightVarIndex);
} else {
let domain1 = vardoms[leftVarIndex];
let domain2 = vardoms[rightVarIndex];
if (nopRejectChecker(domain1, domain2)) {
vardoms[resultVarIndex] = domain_createValue(REIFIER_PASS);
opFunc(space, config, leftVarIndex, rightVarIndex);
} else if (opRejectChecker(domain1, domain2)) {
vardoms[resultVarIndex] = domain_createValue(REIFIER_FAIL);
nopFunc(space, config, leftVarIndex, rightVarIndex);
}
}
}
// end of src/propagators/reified.js
// from: src/propagators/ring.js
/**
* @param {$space} space
* @param {$config} config
* @param {number} varIndex1
* @param {number} varIndex2
* @param {number} varIndex3
* @param {string} opName
* @param {Function} opFunc
*/
function propagator_ringStepBare(space, config, varIndex1, varIndex2, varIndex3, opName, opFunc) {
let vardoms = space.vardoms;
let domain1 = vardoms[varIndex1];
let domain2 = vardoms[varIndex2];
let domain3 = vardoms[varIndex3];
space.vardoms[varIndex3] = _propagator_ringStepBare(domain1, domain2, domain3, opFunc, opName);
}
/**
* @param {$domain} domain1
* @param {$domain} domain2
* @param {$domain} domainResult
* @param {Function} opFunc
* @param {string} opName For debugging only, the canonical name of opFunc
* @returns {$domain}
*/
function _propagator_ringStepBare(domain1, domain2, domainResult, opFunc, opName) {
let domain = opFunc(domain1, domain2);
return domain_intersection(domainResult, domain);
}
// end of src/propagators/ring.js
// from: src/search.js
/**
* Depth first search.
*
* Traverse the search space in DFS order and return the first (next) solution
*
* state.space must be the starting space. The object is used to store and
* track continuation information from that point onwards.
*
* On return, state.status contains either 'solved' or 'end' to indicate
* the status of the returned solution. Also state.more will be true if
* the search can continue and there may be more solutions.
*
* @param {Object} state
* @property {$space} state.space Root space if this is the start of searching
* @property {boolean} [state.more] Are there spaces left to investigate after the last solve?
* @property {$space[]} [state.stack]=[state,space] The search stack as initialized by this class
* @property {string} [state.status] Set to 'solved' or 'end'
* @param {$config} config
* @param {Function} [dbgCallback] Call after each epoch until it returns false, then stop calling it.
*/
function search_depthFirst(state, config, dbgCallback) {
let stack = state.stack;
let epochs = 0;
// the stack only contains stable spaces. the first space is not
// stable so we propagate it first and before putting it on the stack.
let isStart = !stack || stack.length === 0;
if (isStart) {
if (!stack) stack = state.stack = [];
let solved = search_depthFirstLoop(state.space, config, stack, state);
if (dbgCallback && dbgCallback(++epochs)) dbgCallback = undefined;
if (solved) return;
}
while (stack.length > 0) {
// take the top space and generate the next offspring, if any
let childSpace = search_createNextSpace(stack[stack.length - 1], config);
if (childSpace) {
// stabilize the offspring and put it on the stack
let solved = search_depthFirstLoop(childSpace, config, stack, state);
if (dbgCallback && dbgCallback(++epochs)) dbgCallback = undefined;
if (solved) return;
} else {
// remove the space, it has no more children. this is a dead end.
stack.pop();
}
}
// there are no more spaces to explore and therefor no further solutions to be found.
state.status = 'end';
state.more = false;
}
/**
* One search step of the given space
*
* @param {$space} space
* @param {$config} config
* @param {$space[]} stack
* @param {Object} state See search_depthFirst
* @returns {boolean}
*/
function search_depthFirstLoop(space, config, stack, state) {
let rejected = space_propagate(space, config);
return search_afterPropagation(rejected, space, config, stack, state);
}
/**
* Process a propagated space and the result. If it rejects, discard the
* space. If it passed, act accordingly. Otherwise determine whether the
* space has children. If so queue them. Otherwise discard the space.
*
* @param {boolean} rejected Did the propagation end due to a rejection?
* @param {$space} space
* @param {$config} config
* @param {$space[]} stack
* @param {Object} state See search_depthFirst
* @returns {boolean|undefined}
*/
function search_afterPropagation(rejected, space, config, stack, state) {
if (rejected) {
_search_onReject(state, space, stack);
return false;
}
let solved = space_updateUnsolvedVarList(space, config);
if (solved) {
_search_onSolve(state, space, stack);
return true;
}
// put on the stack so the next loop can branch off it
stack.push(space);
return undefined; // neither solved nor rejected
}
/**
* Create a new Space based on given Space which basically
* serves as a child node in a search graph. The space is
* cloned and in the clone one variable is restricted
* slightly further. This clone is then returned.
* This takes various search and distribution strategies
* into account.
*
* @param {$space} space
* @param {$config} config
* @returns {$space|undefined} a clone with small modification or nothing if this is an unsolved leaf node
*/
function search_createNextSpace(space, config) {
let varIndex = distribution_getNextVarIndex(space, config);
if (varIndex !== NO_SUCH_VALUE) {
let domain = space.vardoms[varIndex];
if (!domain_isSolved(domain)) {
let choice = space.next_distribution_choice++;
let nextDomain = distribute_getNextDomainForVar(space, config, varIndex, choice);
if (nextDomain) {
let clone = space_createClone(space);
clone.updatedVarIndex = varIndex;
clone.vardoms[varIndex] = nextDomain;
return clone;
}
}
}
// space is an unsolved leaf node, return undefined
}
/**
* When search fails this function is called
*
*
* @param {Object} state The search state data
* @param {$space} space The search node to fail
* @param {$space[]} stack See state.stack
*/
function _search_onReject(state, space, stack) {
// Some propagators failed so this is now a failed space and we need
// to pop the stack and continue from above. This is a failed space.
space.failed = true;
}
/**
* When search finds a solution this function is called
*
* @param {Object} state The search state data
* @param {Space} space The search node to fail
* @param {Space[]} stack See state.stack
*/
function _search_onSolve(state, space, stack) {
state.status = 'solved';
state.space = space; // is this so the solution can be read from it?
state.more = stack.length > 0;
}
// end of src/search.js
// from: src/solver.js
let GENERATE_BARE_DSL = false;
//
// It is extended by path_solver
/**
* This is a super class.
* It is extended by PathSolver in a private project
*
* @type {Solver}
*/
class Solver {
/**
* @param {Object} options = {}
* @property {string} [options.distribute='naive']
* @property {Object} [options.searchDefaults]
* @property {$config} [options.config=config_create()]
* @property {boolean} [options.exportBare]
* @property {number} [options.logging=LOG_NONE]
*/
constructor(options = {}) {
this._class = 'solver';
this.logging = options.log || LOG_NONE;
this.distribute = options.distribute || 'naive';
if (options.config) {
let config = this.config = options.config;
if (config.initialDomains) {
let initialDomains = config.initialDomains;
for (let i = 0, len = initialDomains.length; i < len; ++i) {
let domain = initialDomains[i];
if (domain.length === 0) domain = domain_createEmpty();
initialDomains[i] = domain_anyToSmallest(domain);
}
}
if (config._propagators) config._propagators = undefined; // will be regenerated
if (config._varToPropagators) config._varToPropagators = undefined; // will be regenerated
} else {
this.config = config_create();
}
this.solutions = [];
this.state = {
space: null,
more: false,
};
this._prepared = false;
}
/**
* Returns an anonymous var with given value as lo/hi for the domain
*
* @param {number} num
* @returns {string}
*/
num(num) {
if (typeof num !== 'number') {
THROW(`Solver#num: expecting a number, got ${num} (a ${typeof num})`);
}
if (isNaN(num)) {
THROW('Solver#num: expecting a number, got NaN');
}
let varIndex = config_addVarAnonConstant(this.config, num);
return this.config.allVarNames[varIndex];
}
/**
* Declare a var with optional given domain or constant value and distribution options.
*
* @param {string} [varName] Optional, Note that you can use this.num() to declare a constant.
* @param {$arrdom|number} [domainOrValue] Note: if number, it is a constant (so [domain,domain]) not a $numdom! If omitted it becomes [SUB, SUP]
* @param {Object} [distributionOptions] Var distribution options. A defined non-object here will throw an error to prevent doing declRange
* @param {boolean} [_allowEmpty=false] Temp (i hope) override for importer
* @returns {string}
*/
decl(varName, domainOrValue, distributionOptions, _allowEmpty) {
if (varName === '') THROW('Var name can not be the empty string');
let arrdom;
if (typeof domainOrValue === 'number') arrdom = [domainOrValue, domainOrValue]; // just normalize it here.
else if (!domainOrValue) arrdom = [SUB, SUP];
else arrdom = domainOrValue;
if (!arrdom.length && !_allowEmpty) THROW('EMPTY_DOMAIN_NOT_ALLOWED');
let varIndex = config_addVarDomain(this.config, varName || true, arrdom, _allowEmpty);
varName = this.config.allVarNames[varIndex];
if (distributionOptions) {
if (distributionOptions.distribute) THROW('Use `valtype` to set the value distribution strategy');
config_setOption(this.config, 'varValueStrat', distributionOptions, varName);
}
return varName;
}
/**
* Declare multiple variables with the same domain/options
*
* @param {string[]} varNames
* @param {$arrdom|number} [domainOrValue] Note: if number, it is a constant (so [domain,domain]) not a $numdom! If omitted it becomes [SUB, SUP]
* @param {Object} [options] Var distribution options. A number here will throw an error to prevent doing declRange
*/
decls(varNames, domainOrValue, options) {
for (let i = 0, n = varNames.length; i < n; ++i) {
this.decl(varNames[i], domainOrValue, options);
}
}
/**
* Declare a var with given range
*
* @param {string} varName
* @param {number} lo Ensure SUB<=lo<=hi<=SUP
* @param {number} hi Ensure SUB<=lo<=hi<=SUP
* @param {Object} [options] Var distribution options
*/
declRange(varName, lo, hi, options) {
return this.decl(varName, [lo, hi], options);
}
// Arithmetic Propagators
plus(A, B, C) {
let R = config_addConstraint(this.config, 'plus', [A, B, C]);
return R;
}
minus(A, B, C) {
let R = config_addConstraint(this.config, 'min', [A, B, C]);
return R;
}
mul(A, B, C) {
let R = config_addConstraint(this.config, 'ring-mul', [A, B, C]);
return R;
}
div(A, B, C) {
let R = config_addConstraint(this.config, 'ring-div', [A, B, C]);
return R;
}
sum(A, C) {
let R = config_addConstraint(this.config, 'sum', A, C);
return R;
}
product(A, C) {
let R = config_addConstraint(this.config, 'product', A, C);
return R;
}
// TODO
// times_plus k1*v1 + k2*v2
// wsum ∑ k*v
// scale k*v
// (In)equality Propagators
// only first expression can be array
distinct(A) {
config_addConstraint(this.config, 'distinct', A);
}
eq(e1, e2) {
if (e1 instanceof Array) {
for (let i = 0, n = e1.length; i < n; ++i) {
this.eq(e1[i], e2);
}
} else if (e2 instanceof Array) {
for (let i = 0, n = e2.length; i < n; ++i) {
this.eq(e1, e2[i]);
}
} else {
config_addConstraint(this.config, 'eq', [e1, e2]);
}
}
neq(e1, e2) {
if (e1 instanceof Array) {
for (let i = 0, n = e1.length; i < n; ++i) {
this.neq(e1[i], e2);
}
} else if (e2 instanceof Array) {
for (let i = 0, n = e2.length; i < n; ++i) {
this.neq(e1, e2[i]);
}
} else {
config_addConstraint(this.config, 'neq', [e1, e2]);
}
}
gte(A, B) {
config_addConstraint(this.config, 'gte', [A, B]);
}
lte(A, B) {
config_addConstraint(this.config, 'lte', [A, B]);
}
gt(A, B) {
config_addConstraint(this.config, 'gt', [A, B]);
}
lt(A, B) {
config_addConstraint(this.config, 'lt', [A, B]);
}
isNeq(A, B, C) {
let R = config_addConstraint(this.config, 'reifier', [A, B, C], 'neq');
return R;
}
isEq(A, B, C) {
let R = config_addConstraint(this.config, 'reifier', [A, B, C], 'eq');
return R;
}
isGte(A, B, C) {
let R = config_addConstraint(this.config, 'reifier', [A, B, C], 'gte');
return R;
}
isLte(A, B, C) {
let R = config_addConstraint(this.config, 'reifier', [A, B, C], 'lte');
return R;
}
isGt(A, B, C) {
let R = config_addConstraint(this.config, 'reifier', [A, B, C], 'gt');
return R;
}
isLt(A, B, C) {
let R = config_addConstraint(this.config, 'reifier', [A, B, C], 'lt');
return R;
}
// Various rest
/**
* Solve this solver. It should be setup with all the constraints.
*
* @param {Object} options
* @property {number} [options.max=1000]
* @property {number} [options.log=this.logging] Logging level; one of: 0, 1 or 2 (see LOG_* constants)
* @property {string|Array.<string|Bvar>} options.vars Target branch vars or var names to force solve. Defaults to all.
* @property {string|Object} [options.distribute='naive'] Maps to FD.distribution.value, see config_setOptions
* @property {boolean} [_debug] A more human readable print of the configuration for this solver
* @property {boolean} [_debugConfig] Log out solver.config after prepare() but before run()
* @property {boolean} [_debugSpace] Log out solver._space after prepare() but before run(). Only works in dev code (stripped from dist)
* @property {boolean} [_debugSolver] Call solver._debugSolver() after prepare() but before run()
* @property {boolean} [_tostring] Serialize the config into a DSL
* @property {boolean} [_nosolve] Dont actually solve. Used for debugging when printing something but not interested in actually running.
* @property {number} [_debugDelay=0] When debugging, how many propagate steps should the debugging wait? (0 is only preprocessing)
* @return {Object[]}
*/
solve(options = {}) {
let log = this.logging = options.log === undefined ? this.logging : options.log;
let max = options.max || 1000;
this._prepare(options, log);
let dbgCallback;
if (options._tostring || options._debug || options._debugConfig || options._debugSpace || options._debugSolver) {
dbgCallback = epoch => {
if (options._debugDelay >= epoch) {
if (options._debug) this._debugLegible();
if (options._debugConfig) this._debugConfig();
if (options._debugSolver) this._debugSolver();
return true;
}
return false;
};
if (dbgCallback(0)) dbgCallback = undefined;
}
if (options._nosolve) return;
this._run(max, log, dbgCallback);
return this.solutions;
}
/**
* Generate the next child from given space. Or none if there isn't any.
*
* @param {$space} space
* @returns {$space|undefined}
*/
offspring(space) {
return search_createNextSpace(space, this.config);
}
/**
* Propagate the given space to stability.
* Returns whether this ended in a reject.
*
* @param {$space} space
* @returns {boolean}
*/
propagate(space) {
return space_propagate(space, this.config);
}
/**
* Checks the state of a space (search node).
* Basically one depth first search loop step
* without the propagation. Returns true if
* the space was solved, false if the space
* was rejected, and undefined otherwise.
*
* @param {$space} space
* @returns {boolean|undefined} true=solved, false=rejected, undefined=neither
*/
checkStableSpace(space) {
return search_afterPropagation(false, space, this.config, this.state.stack, this.state);
}
/**
* Prepare internal configuration before actually solving
* Collects one-time config data and sets up defaults
*
* @param {Object} [options={}] See @solve
* @param {number} log One of the LOG_* constants
*/
_prepare(options, log) {
if (log >= LOG_STATS) {
console.log(' - FD Preparing...');
console.time(' - FD Prepare Time');
}
this._prepareConfig(options, log);
// create the root node of the search tree (each node is a Space)
let rootSpace = this.createSpace();
this.state.space = rootSpace;
this.state.more = true;
this.state.stack = [];
this._prepared = true;
if (log >= LOG_STATS) console.timeEnd(' - FD Prepare Time');
}
/**
* Create the root space using the config of this solver as its base.
*
* @returns {$space}
*/
createSpace() {
return space_createFromConfig(this.config);
}
/**
* Prepare the config side of things for a solve.
* No space is created in this function (that's the point).
*
* @param {Object} options See _prepare
* @param {number} log
*/
_prepareConfig(options, log) {
let config = this.config;
if (options.vars && options.vars !== 'all') {
config_setOption(config, 'targeted_var_names', options.vars);
}
// TODO: eliminate?
let distributionSettings = options.distribute || this.distribute;
if (typeof distributionSettings === 'string') config_setDefaults(config, distributionSettings);
else config_setOptions(config, distributionSettings); // TOFIX: get rid of this in mv
config_init(config);
}
/**
* Run the solver. You should call @_prepare before calling this function.
*
* @param {number} max Hard stop the solver when this many solutions have been found
* @param {number} log One of the LOG_* constants
* @param {Function} [dbgCallback] Call after each epoch until it returns false, then stop calling it.
*/
_run(max, log, dbgCallback) {
this._prepared = false;
let state = this.state;
if (log >= LOG_STATS) {
console.log(` - FD Var Count: ${this.config.allVarNames.length}`);
console.log(` - FD Constraint Count: ${this.config.allConstraints.length}`);
console.log(` - FD Propagator Count: ${this.config._propagators.length}`);
console.log(' - FD Solving...');
console.time(' - FD Solving Time');
}
let alreadyRejected = false;
let vardoms = state.space.vardoms;
for (let i = 0, n = vardoms.length; i < n; ++i) {
if (domain_isEmpty(vardoms[i])) {
alreadyRejected = true;
if (log >= LOG_STATS) {
console.log(' - FD: rejected without propagation');
}
break;
}
}
let solvedSpaces;
if (alreadyRejected) {
if (log >= LOG_STATS) {
console.log(' - FD Input Problem Rejected Immediately');
}
solvedSpaces = [];
} else {
solvedSpaces = solver_runLoop(state, this.config, max, dbgCallback);
}
if (log >= LOG_STATS) {
console.timeEnd(' - FD Solving Time');
console.log(` - FD Solutions: ${solvedSpaces.length}`);
}
solver_getSolutions(solvedSpaces, this.config, this.solutions, log);
}
generateSolutions(solvedSpaces, config, targetObject, log) {
solver_getSolutions(solvedSpaces, config, targetObject, log);
}
/**
* Expose a method to normalize the internal representation
* of a domain to always return an array representation
*
* @param {$space} space
* @param {number} varIndex
* @returns {$arrdom}
*/
getDomain(space, varIndex) {
return domain_toArr(space.vardoms[varIndex]);
}
hasVar(varName) {
return trie_get(this.config._varNamesTrie, varName) >= 0;
}
/**
* Get the current domains for all targeted vars (only)
* Heavy operation.
*
* @param {$space} space
* @returns {Object.<string,$arrdom>}
*/
getTargetState(space) {
let result = {};
let targets = this.config.targetedVars;
if (targets === 'all') {
targets = this.config.allVarNames;
}
let varNamesTrie = this.config._varNamesTrie;
for (let i = 0, n = targets.length; i < n; ++i) {
let varName = targets[i];
let varIndex = trie_get(varNamesTrie, varName);
result[varName] = domain_toArr(space.vardoms[varIndex]);
}
return result;
}
/**
* Exposed for multiverse as a legacy api.
* Sets the value distribution options for a var after declaring it.
*
* @param {string} varName
* @param {Object} options
*/
setValueDistributionFor(varName, options) {
config_setOption(this.config, 'varValueStrat', options, varName);
}
/**
* @returns {Solver}
*/
branch_from_current_solution() {
// get the _solved_ space, convert to config,
// use new config as base for new solver
let solvedConfig = space_toConfig(this.state.space, this.config);
return new Solver({config: solvedConfig});
}
_debugLegible() {
let WITH_INDEX = true;
let clone = JSON.parse(JSON.stringify(this.config)); // prefer this over config_clone, just in case.
let names = clone.allVarNames;
let targeted = clone.targetedVars;
let constraints = clone.allConstraints;
let domains = clone.initialDomains;
let propagators = clone._propagators;
for (let key in clone) {
// underscored prefixed objects are generally auto-generated structs
// we don't want to debug a 5mb buffer, one byte per line.
if (key[0] === '_' && typeof clone[key] === 'object') {
clone[key] = '<removed>';
}
}
clone.allVarNames = '<removed>';
clone.allConstraints = '<removed>';
clone.initialDomains = '<removed>';
clone.varDistOptions = '<removed>';
if (targeted !== 'all') clone.targetedVars = '<removed>';
console.log('\n## _debug:\n');
console.log('- config:');
console.log(getInspector()(clone));
console.log('- vars (' + names.length + '):');
console.log(names.map((name, index) => `${WITH_INDEX ? index : ''}: ${domain__debug(domains[index])} ${name === String(index) ? '' : ' // ' + name}`).join('\n'));
if (targeted !== 'all') {
console.log('- targeted vars (' + targeted.length + '): ' + targeted.join(', '));
}
console.log('- constraints (' + constraints.length + ' -> ' + propagators.length + '):');
console.log(constraints.map((c, index) => {
if (c.param === undefined) {
return `${WITH_INDEX ? index : ''}: ${c.name}(${c.varIndexes}) ---> ${c.varIndexes.map(index => domain__debug(domains[index])).join(', ')}`;
} else if (c.name === 'reifier') {
return `${WITH_INDEX ? index : ''}: ${c.name}[${c.param}](${c.varIndexes}) ---> ${domain__debug(domains[c.varIndexes[0]])} ${c.param} ${domain__debug(domains[c.varIndexes[1]])} = ${domain__debug(domains[c.varIndexes[2]])}`;
} else {
return `${WITH_INDEX ? index : ''}: ${c.name}(${c.varIndexes}) = ${c.param} ---> ${c.varIndexes.map(index => domain__debug(domains[index])).join(', ')} -> ${domain__debug(domains[c.param])}`;
}
}).join('\n'));
console.log('##/\n');
}
_debugSolver() {
console.log('## _debugSolver:\n');
//let inspect = getInspector();
let config = this.config;
//console.log('# Config:');
//console.log(inspect(_clone(config)));
let names = config.allVarNames;
console.log('# Variables (' + names.length + 'x):');
console.log(' index name domain toArr');
for (let varIndex = 0; varIndex < names.length; ++varIndex) {
console.log(' ', varIndex, ':', names[varIndex], ':', domain__debug(config.initialDomains[varIndex]));
}
let constraints = config.allConstraints;
console.log('# Constraints (' + constraints.length + 'x):');
console.log(' index name vars param');
for (let i = 0; i < constraints.length; ++i) {
console.log(' ', i, ':', constraints[i].name, ':', constraints[i].varIndexes.join(','), ':', constraints[i].param);
}
let propagators = config._propagators;
console.log('# Propagators (' + propagators.length + 'x):');
console.log(' index name vars args');
for (let i = 0; i < propagators.length; ++i) {
console.log(
' ', i, ':', propagators[i].name + (propagators[i].name === 'reified' ? '(' + propagators[i].arg3 + ')' : ''),
':',
propagators[i].index1, propagators[i].index2, propagators[i].index3,
'->',
domain__debug(config.initialDomains[propagators[i].index1]),
domain__debug(config.initialDomains[propagators[i].index2]),
domain__debug(config.initialDomains[propagators[i].index3])
);
}
console.log('##');
}
_debugConfig() {
let config = _clone(this.config);
config.initialDomains = config.initialDomains.map(domain__debug);
console.log('## _debugConfig:\n', getInspector()(config));
}
/**
* Exposes internal method domain_fromList for subclass
* (Used by PathSolver in a private project)
* It will always create an array, never a "small domain"
* (number that is bit-wise flags) because that should be
* kept an internal finitedomain artifact.
*
* @param {number[]} list
* @returns {$arrdom[]}
*/
static domainFromList(list) {
return domain_fromListToArrdom(list);
}
}
/**
* Deep clone given object for debugging purposes (only)
* Revise if used for anything concrete
*
* @param {*} value
* @returns {*}
*/
function _clone(value) {
switch (typeof value) {
case 'object':
if (!value) return null;
if (value instanceof Array) {
return value.map(v => _clone(v));
}
let obj = {};
for (let key in value) {
obj[key] = _clone(value[key]);
}
return obj;
case 'function':
let fobj = {
__THIS_IS_A_FUNCTION: 1,
__source: value.toString(),
};
for (let key in value) {
fobj[key] = _clone(value[key]);
}
return fobj;
case 'string':
case 'number':
case 'boolean':
case 'undefined':
return value;
}
THROW('config value what?', value);
}
let inspectorCache;
function getInspector() {
if (!inspectorCache) {
inspectorCache = typeof require === 'function' ? function(arg) { return require('util').inspect(arg, false, null); } : function(o) { return o; };
}
return inspectorCache;
}
/**
* This is the core search loop. Supports multiple solves although you
* probably only need one solution. Won't return more solutions than max.
*
* @param {Object} state
* @param {$config} config
* @param {number} max Stop after finding this many solutions
* @param {Function} [dbgCallback] Call after each epoch until it returns false, then stop calling it.
* @returns {$space[]} All solved spaces that were found (until max or end was reached)
*/
function solver_runLoop(state, config, max, dbgCallback) {
let list = [];
while (state.more && list.length < max) {
search_depthFirst(state, config, dbgCallback);
if (state.status !== 'end') {
list.push(state.space);
}
}
return list;
}
function solver_getSolutions(solvedSpaces, config, solutions, log) {
if (log >= LOG_STATS) {
console.time(' - FD Solution Construction Time');
}
for (let i = 0; i < solvedSpaces.length; ++i) {
let solution = space_solution(solvedSpaces[i], config);
solutions.push(solution);
if (log >= LOG_SOLVES) {
console.log(' - FD solution() ::::::::::::::::::::::::::::');
console.log(JSON.stringify(solution));
console.log(' ::::::::::::::::::::::::::::');
}
}
if (log >= LOG_STATS) {
console.timeEnd(' - FD Solution Construction Time');
}
}
// end of src/solver.js
// from: src/space.js
let space_uid = 0;
/**
* @returns {$space}
*/
function space_createRoot() {
// only for debugging
let _depth = 0;
let _child = 0;
let _path = '';
return space_createNew([], undefined, _depth, _child, _path);
}
/**
* @param {$config} config
* @returns {$space}
*/
function space_createFromConfig(config) {
let space = space_createRoot();
space_initFromConfig(space, config);
return space;
}
/**
* Create a space node that is a child of given space node
*
* @param {$space} space
* @returns {$space}
*/
function space_createClone(space) {
let vardomsCopy = space.vardoms.slice(0);
let unsolvedVarIndexes = space._unsolved.slice(0);
// only for debugging
let _depth;
let _child;
let _path;
// do it inside ASSERTs so they are eliminated in the dist
return space_createNew(vardomsCopy, unsolvedVarIndexes, _depth, _child, _path);
}
/**
* Create a new config with the configuration of the given Space
* Basically clones its config but updates the `initialDomains` with fresh state
*
* @param {$space} space
* @param {$config} config
* @returns {$space}
*/
function space_toConfig(space, config) {
let vardoms = space.vardoms;
let newDomains = [];
let names = config.allVarNames;
for (let i = 0, n = names.length; i < n; i++) {
let domain = vardoms[i];
newDomains[i] = domain_toStr(domain);
}
return config_clone(config, undefined, newDomains);
}
/**
* Concept of a space that holds config, some named domains (referred to as "vars"), and some propagators
*
* @param {$domain[]} vardoms Maps 1:1 to config.allVarNames
* @param {number[]|undefined} unsolvedVarIndexes
* @param {number} _depth (Debugging only) How many parent nodes are there from this node?
* @param {number} _child (Debugging only) How manieth child is this of the parent?
* @param {string} _path (Debugging only) String of _child values from root to this node (should be unique per node and len=_depth+1)
* @returns {$space}
*/
function space_createNew(vardoms, unsolvedVarIndexes, _depth, _child, _path) {
let space = {
_class: '$space',
vardoms,
_unsolved: unsolvedVarIndexes,
next_distribution_choice: 0,
updatedVarIndex: -1, // the varIndex that was updated when creating this space (-1 for root)
_lastChosenValue: -1, // cache to prevent duplicate operations
};
// search graph metrics
// debug only. do it inside ASSERT so they are stripped in the dist
return space;
}
/**
* @param {$space} space
* @param {$config} config
*/
function space_initFromConfig(space, config) {
space_generateVars(space, config); // config must be initialized (generating propas may introduce fresh vars)
space_initializeUnsolvedVars(space, config);
}
/**
* Return the current number of unsolved vars for given space.
* This is only used for testing, prevents leaking internals into tests
*
* @param {$space} space
* @param {$config} config
* @returns {number}
*/
function space_getUnsolvedVarCount(space, config) {
return space._unsolved.length;
}
/**
* Only use this for testing or debugging as it creates a fresh array
* for the result. We don't use the names internally, anyways.
*
* @param {$space} space
* @param {$config} config
* @returns {string[]} var names of all unsolved vars of given space
*/
function _space_getUnsolvedVarNamesFresh(space, config) {
return space._unsolved.map(varIndex => config.allVarNames[varIndex]);
}
/**
* Initialized the list of unsolved variables. These are either the explicitly
* targeted variables, or any unsolved variables if none were explicitly targeted.
*
* @param {$space} space
* @param {$config} config
*/
function space_initializeUnsolvedVars(space, config) {
let targetVarNames = config.targetedVars;
let vardoms = space.vardoms;
let unsolvedVarIndexes = [];
space._unsolved = unsolvedVarIndexes;
if (targetVarNames === 'all') {
for (let varIndex = 0, n = vardoms.length; varIndex < n; ++varIndex) {
if (!domain_isSolved(vardoms[varIndex])) {
if (config._varToPropagators[varIndex] || (config._constrainedAway && config._constrainedAway.indexOf(varIndex) >= 0)) {
unsolvedVarIndexes.push(varIndex);
}
}
}
} else {
let varNamesTrie = config._varNamesTrie;
for (let i = 0, n = targetVarNames.length; i < n; ++i) {
let varName = targetVarNames[i];
let varIndex = trie_get(varNamesTrie, varName);
if (varIndex === TRIE_KEY_NOT_FOUND) THROW('E_TARGETED_VARS_SHOULD_EXIST_NOW');
if (!domain_isSolved(vardoms[varIndex])) {
unsolvedVarIndexes.push(varIndex);
}
}
}
}
/**
* Run all the propagators until stability point.
* Returns true if any propagator rejects.
*
* @param {$space} space
* @param {$config} config
* @returns {boolean} when true, a propagator rejects and the (current path to a) solution is invalid
*/
function space_propagate(space, config) {
let propagators = config._propagators;
// "cycle" is one step, "epoch" all steps until stable (but not solved per se)
// worst case all unsolved vars change. but in general it's about 30% so run with that
let cells = Math.ceil(space._unsolved.length * TRIE_NODE_SIZE * 0.3);
let changedTrie = trie_create(TRIE_EMPTY, cells); // track changed vars per cycle in this epoch
let cycles = 0;
let changedVars = []; // in one cycle
let minimal = 1;
if (space.updatedVarIndex >= 0) {
changedVars.push(space.updatedVarIndex);
} else {
// very first cycle of first epoch of the search. all propagators must be visited at least once now.
let rejected = space_propagateAll(space, config, propagators, changedVars, changedTrie, ++cycles);
if (rejected) {
return true;
}
}
if (space_abortSearch(space, config)) {
return true;
}
let returnValue = false;
while (changedVars.length) {
let newChangedVars = [];
let rejected = space_propagateChanges(space, config, propagators, minimal, changedVars, newChangedVars, changedTrie, ++cycles);
if (rejected) {
returnValue = true;
break;
}
if (space_abortSearch(space, config)) {
returnValue = true;
break;
}
changedVars = newChangedVars;
minimal = 2; // see space_propagateChanges
}
return returnValue;
}
function space_propagateAll(space, config, propagators, changedVars, changedTrie, cycleIndex) {
for (let i = 0, n = propagators.length; i < n; i++) {
let propagator = propagators[i];
let rejected = space_propagateStep(space, config, propagator, changedVars, changedTrie, cycleIndex);
if (rejected) return true;
}
return false;
}
function space_propagateByIndexes(space, config, propagators, propagatorIndexes, changedVars, changedTrie, cycleIndex) {
for (let i = 0, n = propagatorIndexes.length; i < n; i++) {
let propagatorIndex = propagatorIndexes[i];
let propagator = propagators[propagatorIndex];
let rejected = space_propagateStep(space, config, propagator, changedVars, changedTrie, cycleIndex);
if (rejected) return true;
}
return false;
}
function space_propagateStep(space, config, propagator, changedVars, changedTrie, cycleIndex) {
let vardoms = space.vardoms;
let index1 = propagator.index1;
let index2 = propagator.index2;
let index3 = propagator.index3;
let domain1 = vardoms[index1];
let domain2 = index2 !== undefined && vardoms[index2];
let domain3 = index3 !== undefined && vardoms[index3];
let stepper = propagator.stepper;
// TODO: if we can get a "solved" state here we can prevent an isSolved check later...
stepper(space, config, index1, index2, index3, propagator.arg1, propagator.arg2, propagator.arg3, propagator.arg4, propagator.arg5, propagator.arg6);
if (domain1 !== vardoms[index1]) {
if (domain_isEmpty(vardoms[index1])) {
return true; // fail
}
space_recordChange(index1, changedTrie, changedVars, cycleIndex);
}
if (index2 !== undefined && domain2 !== vardoms[index2]) {
if (domain_isEmpty(vardoms[index2])) {
return true; // fail
}
space_recordChange(index2, changedTrie, changedVars, cycleIndex);
}
if (index3 !== undefined && domain3 !== vardoms[index3]) {
if (domain_isEmpty(vardoms[index3])) {
return true; // fail
}
space_recordChange(index3, changedTrie, changedVars, cycleIndex);
}
return false;
}
function space_recordChange(varIndex, changedTrie, changedVars, cycleIndex) {
if (typeof varIndex === 'number') {
let status = trie_getNum(changedTrie, varIndex);
if (status !== cycleIndex) {
changedVars.push(varIndex);
trie_addNum(changedTrie, varIndex, cycleIndex);
}
} else {
for (let i = 0, len = varIndex.length; i < len; ++i) {
space_recordChange(varIndex[i], changedTrie, changedVars, cycleIndex);
}
}
}
function space_propagateChanges(space, config, allPropagators, minimal, targetVars, changedVars, changedTrie, cycleIndex) {
let varToPropagators = config._varToPropagators;
for (let i = 0, vlen = targetVars.length; i < vlen; i++) {
let propagatorIndexes = varToPropagators[targetVars[i]];
// note: the first loop of propagate() should require all propagators affected, even if
// it is just one. after that, if a var was updated that only has one propagator it can
// only have been updated by that one propagator. however, this step is queueing up
// propagators to check, again, since one of its vars changed. a propagator that runs
// twice without other changes will change nothing. so we do it for the initial loop,
// where the var is updated externally, after that the change can only occur from within
// a propagator so we skip it.
// ultimately a list of propagators should perform better but the indexOf negates that perf
// (this doesn't affect a whole lot of vars... most of them touch multiple propas)
if (propagatorIndexes && propagatorIndexes.length >= minimal) {
let result = space_propagateByIndexes(space, config, allPropagators, propagatorIndexes, changedVars, changedTrie, cycleIndex);
if (result) return true; // rejected
}
}
return false;
}
/**
* @param {$space} space
* @param {$config} config
* @returns {boolean}
*/
function space_abortSearch(space, config) {
let callback = config.timeoutCallback;
if (callback) {
return callback(space);
}
return false;
}
/**
* Returns true if this space is solved - i.e. when
* all the vars in the space have a singleton domain.
*
* This is a *very* strong condition that might not need
* to be satisfied for a space to be considered to be
* solved. For example, the propagators may determine
* ranges for all variables under which all conditions
* are met and there would be no further need to enumerate
* those solutions.
*
* @param {$space} space
* @param {$config} config
* @returns {boolean}
*/
function space_updateUnsolvedVarList(space, config) {
let vardoms = space.vardoms;
let unsolvedVarIndexes = space._unsolved;
let m = 0;
for (let i = 0, len = unsolvedVarIndexes.length; i < len; ++i) {
let varIndex = unsolvedVarIndexes[i];
let domain = vardoms[varIndex];
if (!domain_isSolved(domain)) {
unsolvedVarIndexes[m++] = varIndex;
}
}
unsolvedVarIndexes.length = m;
return m === 0; // 0 unsolved means we've solved it :)
}
/**
* Returns an object whose field names are the var names
* and whose values are the solved values. The space *must*
* be already in a solved state for this to work.
*
* @param {$space} space
* @param {$config} config
* @returns {Object}
*/
function space_solution(space, config) {
let allVarNames = config.allVarNames;
let result = {};
for (let varIndex = 0, n = allVarNames.length; varIndex < n; varIndex++) {
let varName = allVarNames[varIndex];
result[varName] = space_getVarSolveState(space, varIndex);
}
return result;
}
/**
* Note: this is the (shared) second most called function of the library
* (by a third of most, but still significantly more than the rest)
*
* @param {$space} space
* @param {number} varIndex
* @returns {number|number[]|boolean} The solve state for given var index, also put into result
*/
function space_getVarSolveState(space, varIndex) {
let domain = space.vardoms[varIndex];
if (domain_isEmpty(domain)) {
return false;
}
let value = domain_getValue(domain);
if (value !== NO_SUCH_VALUE) return value;
return domain_toArr(domain);
}
function space_getDomainArr(space, varIndex) {
return domain_toArr(space.vardoms[varIndex]);
}
/**
* Initialize the vardoms array on the first space node.
*
* @param {$space} space
* @param {$config} config
*/
function space_generateVars(space, config) {
let vardoms = space.vardoms;
let initialDomains = config.initialDomains;
let allVarNames = config.allVarNames;
for (let varIndex = 0, len = allVarNames.length; varIndex < len; varIndex++) {
let domain = initialDomains[varIndex];
vardoms[varIndex] = domain_toSmallest(domain);
}
}
/**
* @param {$space} space
* @param {$config} [config]
* @param {boolean} [printPath]
*/
function _space_debug(space, config, printPath) {
console.log('\n## Space:');
console.log('# Domains:');
console.log(space.vardoms.map(domain_toArr).map((d, i) => (d + '').padEnd(15, ' ') + ((!config || config.allVarNames[i] === String(i)) ? '' : ' (' + config.allVarNames[i] + ')')).join('\n'));
console.log('##\n');
}
// end of src/space.js
// from: src/trie.js
const TRIE_ROOT_OFFSET = 0;
const TRIE_BUCKET_COUNT = 10; // 10 digits
const TRIE_NODE_SIZE = TRIE_BUCKET_COUNT + 1; // inc value
const TRIE_INITIAL_SIZE = 16 * 1024;
const TRIE_MINIMAL_GROWTH = 4 * 1024;
const TRIE_KEY_NOT_FOUND = -1;
const TRIE_EMPTY = undefined;
const TRIE_DEFAULT_SIZE = undefined;
const TRIE_8_BIT = 8;
const TRIE_16_BIT = 16;
const TRIE_32_BIT = 32;
const TRIE_64_BIT = 64;
const TRIE_DEFAULT_BITS = undefined;
// every trie node needs space for 10 jumps + 1 leaf value (must be capable of containing `size(Trie)-1`) so initially 11 bytes, later 12 bytes and then 22 bytes once the number of nodes exceeds 255
/**
* Create a new trie and, optionally, initialize it
* with given values as keys and their index as value.
* Check `trie_add` for assumed key composition restrictions
*
* @param {string[]} [valuesByIndex] If exists, adds all values in array as keys, index as values
* @param {number} [initialLength] Hint to help control memory consumption for large/small tries. This length is in cells, not bytes. (byteLength=length*(bitsize/8))
* @param {number} [initialBitsize] Hint to set bitsize explicitly. One of: 8 16 32 64
* @returns {$trie}
*/
function trie_create(valuesByIndex, initialLength, initialBitsize) {
let size = (initialLength | 0) || TRIE_INITIAL_SIZE;
if (!size) THROW('fixme'); // blabla it's possible the constant is not yet initialized due to minification. dont initialize a trie in module global space
let bits = Math.max(trie_getValueBitsize(size), (initialBitsize | 0)); // given bitsize might be lower than max address, ignore it in that case
let buf = trie_createBuffer(size, bits);
// have to use a wrapper because the buffer ref may change when it grows
// otherwise we could just store the meta data inside the buffer. but at
// least this is easier to read :)
let trie = {
_class: '$trie',
buffer: buf,
bits: bits, // 8 16 32 (64?)
lastNode: TRIE_ROOT_OFFSET, // pointer to last node in the buffer
count: 0, // number of keys in the Trie
};
if (valuesByIndex) {
for (let i = 0, n = valuesByIndex.length; i < n; ++i) {
trie_add(trie, valuesByIndex[i], i);
}
}
return trie;
}
/**
* Create a buffer
*
* @param {number} size Length of the buffer in cells, not bytes (!)
* @param {number} bits One of: 8 16 32 64
* @returns {TypedArray}
*/
function trie_createBuffer(size, bits) {
switch (bits) {
case TRIE_8_BIT:
return new Uint8Array(size);
case 16:
return new Uint16Array(size);
case TRIE_32_BIT:
return new Uint32Array(size);
case TRIE_64_BIT:
return new Float64Array(size); // let's hope not ;)
}
THROW('Unsupported bit size');
}
/**
* Reserve a part of the Trie memory to represent a node in the Trie.
*
* In this particular implementation nodes are of fixed width. It's
* a field of 10 address cells and one value cell.
*
* Address cells point to other nodes. If zero, there is none (because
* that would be the root node) and a search ends in not found.
*
* Value cells that are zero (default) are also "not found".
*
* @returns {Uint16Array}
*/
function trie_addNode(trie) {
let newNodePtr = trie.lastNode + TRIE_NODE_SIZE;
trie.lastNode = newNodePtr;
// technically the `while` is valid (instead of an `if`) but only
// if the buffer could grow by a smaller amount than the node size...
// note: buffer.length is cell size, buffer.byteLength is byte size. we want cells here.
while (newNodePtr + TRIE_NODE_SIZE >= trie.buffer.length) trie_grow(trie);
return newNodePtr;
}
/**
* Allocate more size for this Trie
*
* Basically creates a new buffer with a larger size and then copies
* the current buffer into it. If the new size exceeds the max size
* of the current type (16bit/32bit) then the buffer is converted to
* a bigger bit size automagically.
* The trie buffer reference will be updated with the new buffer
*
* @param {$trie} trie
*/
function trie_grow(trie) {
let len = trie.buffer.length; // cell size! not byte size.
let newSize = ~~(len * 1.1); // grow by 10% (an arbitrary number)
if (len + TRIE_MINIMAL_GROWTH > newSize) newSize = TRIE_MINIMAL_GROWTH + len;
trie_malloc(trie, newSize);
}
/**
* Allocate space for a Trie and copy given Trie to it.
* Will grow bitsize if required, but never shrink it.
* (Bitsize must grow if cell size exceeds certain threshholds
* because otherwise we can't address all bytes in the buffer)
*
* @param {$trie} trie
* @param {number} size Cell size, not byte size
*/
function trie_malloc(trie, size) {
// make sure addressing fits
let newBits = trie_getValueBitsize(size);
// dont shrink bit size even if length would allow it; "large" _values_ may require it
// (our tries dont need to shrink)
trie.bits = Math.max(trie.bits, newBits);
let nbuf = trie_createBuffer(size, trie.bits);
nbuf.set(trie.buffer, 0);
trie.buffer = nbuf;
}
/**
* Return the cell width in bits to fit given value.
* For example, numbers below 256 can be represented in
* 8 bits but numbers above it will need at least 16 bits.
* Max is 64 but you can't pass on larger numbers in JS, anyways :)
*
* @param {number} value
* @returns {number}
*/
function trie_getValueBitsize(value) {
if (value < 0x100) return TRIE_8_BIT;
else if (value < 0x10000) return TRIE_16_BIT;
else if (value < 0x100000000) return TRIE_32_BIT;
else return TRIE_64_BIT;
}
/**
* Add a key/value pair
*
* Note: keys and values are of limited structure
*
* The key must be a string of ascii in range of 32-131.
* This key is hashed by turning each character into its
* ascii ordinal value, stringifying it padded with zero,
* and hashing each of the two resulting digits. This way
* we can guarantee that each node in the Trie only
* requires 10 places (one for each digit) plus a value.
* That makes reads super fast.
*
* @param {$trie} trie
* @param {string} key
* @param {number} value Any unsigned 32bit-1 value
* @returns {number} previous value, or -1 if there wasn't any
*/
function trie_add(trie, key, value) {
trie_ensureValueFits(trie, value);
return _trie_add(trie, TRIE_ROOT_OFFSET, key, 0, key.length, value);
}
/**
* Recursively find the place to add the key. If
* the trail runs cold, pave it. Clobbers existing
* values (though in our implementation that current
* shouldn't really happen...)
*
* @param {$trie} trie
* @param {number} offset
* @param {string} key
* @param {number} index Current index of the key being walked
* @param {number} len Cache of key.length
* @param {number} value Any unsigned 32bit-1 value
* @returns {number} the old value, or not found
*/
function _trie_add(trie, offset, key, index, len, value) {
// dont create next path part if it would create a leaf node
if (index >= len) {
let buf = trie.buffer;
let valuePtr = offset + TRIE_BUCKET_COUNT;
let curValue = trie.buffer[valuePtr];
if (!curValue) ++trie.count;
buf[valuePtr] = value + 1; // 0 is reserved to mean "unused"
return curValue - 1;
}
let c = key.charCodeAt(index) - 32; // allow all asciis 31 < c < 130 encoded as stringified double digits
offset = _trie_pavePath(trie, offset, c % 10);
offset = _trie_pavePath(trie, offset, Math.floor(c / 10));
return _trie_add(trie, offset, key, index + 1, len, value);
}
/**
* Add a key/value pair
*
* This adds a value under a key that is a number. This
* way reads and writes take `ceil(log(n)/log(10))` steps.
* Eg. as many steps as digits in the decimal number.
*
* @param {$trie} trie
* @param {number} key Assumes an unsigned int
* @param {number} value Any unsigned 32bit-1 value
* @returns {number} previous value, or -1 if there wasn't any
*/
function trie_addNum(trie, key, value) {
trie_ensureValueFits(trie, value);
return _trie_addNum(trie, TRIE_ROOT_OFFSET, key + 1, value);
}
/**
* Recursively find the place to add the key. If
* the trail runs cold, pave it. Clobbers existing
* values (though in our implementation that current
* shouldn't really happen...)
*
* @param {$trie} trie
* @param {number} offset
* @param {number} key Assumes an unsigned int >0
* @param {number} value Any unsigned 32bit-1 value
* @returns {number} the old value, or not found
*/
function _trie_addNum(trie, offset, key, value) {
if (key === 0) {
let buf = trie.buffer;
let valuePtr = offset + TRIE_BUCKET_COUNT;
let curValue = trie.buffer[valuePtr];
if (!curValue) ++trie.count;
buf[valuePtr] = value + 1; // 0 is reserved to mean "unused"
return curValue - 1;
}
offset = _trie_pavePath(trie, offset, key % 10);
key = Math.floor(key / 10);
return _trie_addNum(trie, offset, key, value);
}
/**
* Make sure the Trie can hold a value of given manitude.
* If the current bitsize of the trie is too small it will
* grow the buffer to accomodate the larger size.
*
* @param {$trie} trie
* @param {number} value
*/
function trie_ensureValueFits(trie, value) {
let bitsNeeded = trie_getValueBitsize(value);
if (bitsNeeded > trie.bits) {
trie.bits = bitsNeeded;
trie_malloc(trie, trie.buffer.length); // note: length = cell size, byteLength = byte size. we mean cell here.
}
}
/**
* One step of writing a value. Offset should be a node, if
* the digit has no address yet create it. If a node needs
* to be created the buffer may be grown to fit the new node.
* It will return the pointer of the (possibly new) next
* node for given digit.
*
* @param {$trie} trie
* @param {number} offset Start of a node
* @param {number} digit Zero through nine
* @returns {number} new address
*/
function _trie_pavePath(trie, offset, digit) {
offset += digit;
let ptr = trie.buffer[offset];
if (!ptr) {
ptr = trie_addNode(trie);
trie.buffer[offset] = ptr;
}
return ptr;
}
/**
* Find the value for given key. See trie_add for more details.
*
* @param {$trie} trie
* @param {string} key
* @returns {number} -1 if not found, >= 0 otherwise
*/
function trie_get(trie, key) {
return _trie_get(trie, TRIE_ROOT_OFFSET, key, 0, key.length);
}
/**
* Recursive function to search for key
*
* @param {$trie} trie
* @param {number} offset Start of a node
* @param {string} key
* @param {number} index Current index of the key being walked
* @param {number} len Cache of key.length
* @returns {number} -1 if not found or >= 0 otherwise
*/
function _trie_get(trie, offset, key, index, len) {
let buf = trie.buffer;
if (index >= len) {
let valuePtr = offset + TRIE_BUCKET_COUNT;
return buf[valuePtr] - 1;
}
let c = key.charCodeAt(index) - 32; // allow all asciis 31 < c < 130 encoded as stringified double digits
offset = buf[offset + (c % 10)];
if (!offset) return TRIE_KEY_NOT_FOUND;
offset = buf[offset + Math.floor(c / 10)];
if (!offset) return TRIE_KEY_NOT_FOUND;
return _trie_get(trie, offset, key, index + 1, len);
}
/**
* See trie_get for more details
*
* @param {$trie} trie
* @param {string} key
* @returns {boolean}
*/
function trie_has(trie, key) {
return trie_get(trie, key) !== TRIE_KEY_NOT_FOUND;
}
/**
* Find the value for given number key.
* See trie_addNum for more details.
*
* @param {$trie} trie
* @param {number} key Assumed to be an unsigned int >=0
* @returns {number} -1 if not found, >= 0 otherwise
*/
function trie_getNum(trie, key) {
return _trie_getNum(trie, TRIE_ROOT_OFFSET, key + 1);
}
/**
* Recursive function to search for number key
*
* @param {$trie} trie
* @param {number} offset Start of a node
* @param {number} key Assumed to be an unsigned int >=0
* @returns {number} -1 if not found or >= 0 otherwise
*/
function _trie_getNum(trie, offset, key) {
let buf = trie.buffer;
if (key === 0) {
let valuePtr = offset + TRIE_BUCKET_COUNT;
return buf[valuePtr] - 1;
}
offset = buf[offset + (key % 10)];
if (!offset) return TRIE_KEY_NOT_FOUND;
key = Math.floor(key / 10);
return _trie_getNum(trie, offset, key);
}
/**
* See trie_getNum for more details
*
* @param {$trie} trie
* @param {number} key Assumed to be unsigned int >= 0
* @returns {boolean}
*/
function trie_hasNum(trie, key) {
return trie_getNum(trie, key) !== TRIE_KEY_NOT_FOUND;
}
/**
* Human readable yay. Does not log, only returns a debug string.
*
* @param {$trie} trie
* @param {boolean} [skipBuffer=false]
* @returns {string}
*/
function _trie_debug(trie, skipBuffer) {
/* eslint no-extend-native: "off" */
let buf = trie.buffer;
let lastNode = trie.lastNode;
// patch some es6 stuff for debugging. note: dont do this in prod, it may slow stuff down.
if (!String.prototype.padStart) {
String.prototype.padStart = function(n, c) {
let s = this;
if (this.length < n) for (let i = 0; i < n - this.length; ++i) s = c + s;
return s;
};
}
if (!String.prototype.padEnd) {
String.prototype.padEnd = function(n, c) {
let s = this;
if (this.length < n) for (let i = 0; i < n - this.length; ++i) s = s + c;
return s;
};
}
if (!Array.from) {
Array.from = function(a) {
return [].concat.call(a);
};
}
// if one doesnt support them, they probably all dont.
if (!Uint8Array.prototype.slice) {
Uint8Array.prototype.slice = Uint16Array.prototype.slice = Uint32Array.prototype.slice = Float64Array.prototype.slice = Array.prototype.slice;
}
function bytes(b) {
if (b < 1024) return b + ' b';
b /= 1024;
if (b < 1024) return ~~(b * 100) / 100 + ' kb';
b /= 1024;
if (b < 1024) return ~~(b * 100) / 100 + ' mb';
b /= 1024;
return ~~(b * 100) / 100 + ' gb';
}
let pad = 20;
let npad = 6;
let s = '' +
'\n' +
'###\n' +
'Key count:'.padEnd(pad, ' ') + trie.count + '\n' +
'Node count:'.padEnd(pad, ' ') + ((lastNode / TRIE_NODE_SIZE) + 1) + ' (' + (((lastNode / TRIE_NODE_SIZE) + 1) / trie.count) + ' nodes per key)\n' +
'Buffer cell length:'.padEnd(pad, ' ') + buf.length + '\n' +
'Buffer byte length:'.padEnd(pad, ' ') + buf.byteLength + '\n' +
'Bit size:'.padEnd(pad, ' ') + trie.bits + '\n' +
'Node len:'.padEnd(pad, ' ') + TRIE_NODE_SIZE + '\n' +
'Node size:'.padEnd(pad, ' ') + TRIE_NODE_SIZE + '\n' +
'Last Node:'.padEnd(pad, ' ') + lastNode + '\n' +
'Used space:'.padEnd(pad, ' ') + (lastNode + TRIE_NODE_SIZE) + ' cells, ' + bytes((lastNode + TRIE_NODE_SIZE) * (trie.bits >> 3)) + '\n' +
'Unused space:'.padEnd(pad, ' ') + (buf.length - (lastNode + TRIE_NODE_SIZE)) + ' cells, ' + bytes((buf.length - (lastNode + TRIE_NODE_SIZE)) * (trie.bits >> 3)) + '\n' +
'\n';
if (!skipBuffer) {
s += 'ptr \\ key= 0 1 2 3 4 5 6 7 8 9 -> value\n\n';
let ptr = TRIE_ROOT_OFFSET;
while (ptr <= lastNode) {
s += String(ptr).padStart(npad, ' ') + ': ' + Array.from(buf.slice(ptr, ptr + TRIE_NODE_SIZE - 1)).map(n => String(n).padStart(npad, ' ')).join(', ') + ' -> ' + String(buf[ptr + TRIE_NODE_SIZE - 1]).padStart(npad, ' ') + '\n';
ptr += TRIE_NODE_SIZE;
}
}
s += '###\n\n';
return s;
}
// end of src/trie.js
return Solver;
})();
export default Solver;
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment