Mudder.js

Generate lexicographically-spaced strings between two strings from pre-defined alphabets.

The name came to me while I was writing an early version that called the central function “midder” (i.e., the mid-point between strings), which I took to calling “mudder” from the memorable episode of Firefly called “Jaynestown”.

Quickstart

Node.js npm install --save mudder, then var mudder = require('mudder').

Browser Download mudder.min.js, then include it in your HTML: <script src="mudder.min.js"></script>. This loads the mudder object into the browser’s global namespace.

TypeScript The community maintains type definitions for this JavaScript library on DefinitelyTyped. To get them, run npm install --save-dev @types/mudder (after first installing the JavaScript package, with npm install --save mudder), then import as usual—for example, import {SymbolTable, base62} from 'mudder';.

Example usage Three symbol tables are pre-generated for your convenience:

• base62: 0-9A-Za-z,
• base36: 0-9a-z (lower- and upper-case accepted, to match Number.toString),
• alphabet: a-z (lower- and upper-case accepted).

Or you may create a new symbol table with the list of characters you want to use. In this example, we consider lowercase hexadecimal strings, and then ask for three strings between ffff and fe0f:

var mudder = require('mudder'); // only in Node
var hex = new mudder.SymbolTable('0123456789abcdef');
var hexstrings = hex.mudder('ffff', 'fe0f', 3);
console.log(hexstrings);
// [ 'ff8', 'ff', 'fe8' ]

The three strings are guaranteed to be the shortest and as-close-to-evenly-spaced between the two original strings (ffff and fe0f, in this case) as possible.

You may also omit the start and/or end strings, and provide only the number of strings to subdivide the entire string space. (Even this number may also be omitted if you just want one string in the middle of the string space.)

var mudder = require('mudder'); // only in Node
var strings = mudder.base62.mudder(1000);
console.log(strings);
// [ '03', '07', '0B', ... 'zo', 'zs', 'zw' ]

Ports See mudder_dart for Dart/Flutter, contributed by @tiagocpeixoto.

Try right now My blog post lets you interactively experiment with this library.

API

Constructor

var m = new mudder.SymbolTable(string) creates a new symbol table using the individual characters of string.

var m = new mudder.SymbolTable(symbolsArr) uses the stringy elements of symbolsArr as allowed symbols. This way you can get fancy, i.e., Roman numerals, Emoji, Chinese phrases, etc.

var m = new mudder.SymbolTable(symbolsArr, symbolsMap) allows the most flexibility in creating symbol tables. The stringy elements of symbolsArr are again the allowed symbols, while symbolsMap is a JavaScript object or Map, whose keys must include all the strings in symbolsArr while the corresponding values must be JavaScript numbers, running from 0 up without skips. symbolsMap can contain keys not found in symbolsArr: this allows you to let multiple strings represent the same value, i.e., lower- and upper-case hexadecimal values. Mudder.js outputs will contain only the strings found in symbolsArr but it can consume strings containing anything found among the keys of symbolsMap.

There are very few restrictions on what symbols the SymbolTable constructor accepts. The symbols are permitted to be non-prefix-free. In fact the library won’t object if you have repeated symbols in the table, though this makes very little sense. But in either of these cases, the mudder function (below) can only be invoked with arrays, not strings—i.e., you’ve parsed strings into symbols somehow yourself.

Generate strings

m.mudder(start = '', end = '' [, numStrings[, base[, numDivisions[, placesToKeep]]]]) for strings, or array-of-strings, start and end, returns a numStrings-length (default one) array of strings.

base is an integer defaulting to the size of the symbol table m, but can be less than it if you, for some reason, wish to use only a subset of the symbol table.

start can be lexicographically less than or greater than end, but in either case, the returned array will be lexicographically sorted between them.

If start or end are non-truthy, the first is replaced by the first symbol, and the second is replaced by repeating the final symbol several times—e.g., for a numeric symbol table, start would default to 0 and end to 999999 or similar. This is done so that the strings returned cover 99.99...% of the available string space.

numDivisions defaults to numStrings + 1 and must be greater than numStrings. It represents the number of pieces to subdivide the lexical space between start and end into—then the returned array will contain the first numStrings steps along that grid from start to end. You can customize numDivisions to be (much) larger than numStrings in cases where you know you are going to insert many strings between two endpoints, but only one (or a few) at a time.

placesToKeep defaults to 0 and tells Mudder, instead of returning the shortest string(s) possible, to allow them to be up to (or greater than) this length.

For example, if you call start = m.mudder(start, end, 1)[0] over and over (overwriting start each iteration), you halve the space between the endpoints each call, eventually making the new string very long. If you knew you were going to do this, you can call start = m.mudder(start, end, 1, undefined, 100)[0], i.e., set numDivisons=100, to subdivide the space between the endpoints a hundred times (instead of just two times), and return just the first 1/100th step from start to end. This makes your string length grow much more sedately, and you can always reverse start and end to get the same behavior going in the other direction. See #7 for numerous examples, and a caveat if you’re using non-truthy start.

placesTokeep is useful when you want just one string back but also want to use a high numDivisions. For example, base62.mudder('a', '0', 1, undefined, numDivisions) is the same (Z) whether numDivisions is 100, 1000, or 10,000. By using a high numDivisions you probably don’t want this behavior: you probably want more dynamic range the more divisions you use. By passing in placesToKeep, you can ask Mudder to not aggressively truncate the strings it generates. With placesToKeep=4, the previous call returns Zdg, Zxm, and ZzmA.

If the symbol table was not prefix-free, the function will refuse to operate on strings start/end because, without the prefix-free criterion, a string can’t be parsed unambiguously: you have to split the string into an array of stringy symbols yourself. Invalid or unrecognized symbols are silently ignored.

m.mudder(number = 1) is equivalent to m.mudder('', '', number). See above.

Recipes

In this section we attempt to highlight when the library's default behavior is fine and when you might need to use which specific arguments described in the API above.

Abeni: “I am just starting my database and need ten keys for the first set of data; I expect future keys to be interspersed among this set.” This is the most benign case. With a new dataset, you probably want compact keys, so I recommend base62:

var mudder = require('mudder'); // only in Node
var keys = mudder.base62.mudder(10);
console.log(keys);
/*
[
  '5', 'B', 'G', 'M',
  'S', 'X', 'd', 'j',
  'o', 'u'
]
*/

Now I have my eleventh data point and need a key between the 4th and 5th.

var newKey = mudder.base62.mudder(keys[3], keys[4]);
console.log(newKey)
// [ 'P' ]

I need two keys between the first and the second.

var newKeys = mudder.base62.mudder(keys[0], keys[1], 2);
console.log(newKeys)
// [ '7', '9' ]

In general, as Abeni’s database grows, a data point may come before the first:

console.log(mudder.base62.mudder(undefined, keys[0]))
// [ '2' ]

or after the last:

console.log(mudder.base62.mudder(keys[keys.length-1]))
// [ 'w' ]

but assuming random ordering, the keys will grow in length as needed.

Bolanle: I’m also starting my database and also need ten keys for my initial data, but I am confident all future data will come after the initial data. Bolanle does not want her first ten keys to span the entire base62 gamut from 0 to z because she is confident most of her future keys will need to go after the tenth key, and Abeni’s approach would squander the bulk of lexicographic space.

A simple approach would be, generate 99 keys covering the whole base62 key space and keep only the first ten needed:

var mudder = require('mudder'); // only in Node
var keys = mudder.base62.mudder(99).slice(0, 10);
console.log(keys);
/*
[
  '0c', '1',  '1r',
  '2',  '3',  '3i',
  '4',  '4x', '5',
  '6'
]
*/

or equivalently, use numDivisions = 100 which does the same thing, just a more efficiently: split up the base62 gamut into a hundred pieces and gets the first ten:

var numDivisions = 100;
var keys = mudder.base62.mudder('', '', 10, undefined, numDivisions);
console.log(keys);
/* Same as above:
[
  '0c', '1',  '1r',
  '2',  '3',  '3i',
  '4',  '4x', '5',
  '6'
]
*/

(Note how we can use '' (the empty string) instead of undefined for the start and end.)

*And what if all my future data is likely to come before my initial data? Can I use numDivisions to gene