http://git-wip-us.apache.org/repos/asf/cordova-windows/blob/3aca1d87/node_modules/ansi/README.md ---------------------------------------------------------------------- diff --git a/node_modules/ansi/README.md b/node_modules/ansi/README.md new file mode 100644 index 0000000..6ce1940 --- /dev/null +++ b/node_modules/ansi/README.md @@ -0,0 +1,98 @@ +ansi.js +========= +### Advanced ANSI formatting tool for Node.js + +`ansi.js` is a module for Node.js that provides an easy-to-use API for +writing ANSI escape codes to `Stream` instances. ANSI escape codes are used to do +fancy things in a terminal window, like render text in colors, delete characters, +lines, the entire window, or hide and show the cursor, and lots more! + +#### Features: + + * 256 color support for the terminal! + * Make a beep sound from your terminal! + * Works with *any* writable `Stream` instance. + * Allows you to move the cursor anywhere on the terminal window. + * Allows you to delete existing contents from the terminal window. + * Allows you to hide and show the cursor. + * Converts CSS color codes and RGB values into ANSI escape codes. + * Low-level; you are in control of when escape codes are used, it's not abstracted. + + +Installation +------------ + +Install with `npm`: + +``` bash +$ npm install ansi +``` + + +Example +------- + +``` js +var ansi = require('ansi') + , cursor = ansi(process.stdout) + +// You can chain your calls forever: +cursor + .red() // Set font color to red + .bg.grey() // Set background color to grey + .write('Hello World!') // Write 'Hello World!' to stdout + .bg.reset() // Reset the bgcolor before writing the trailing \n, + // to avoid Terminal glitches + .write('\n') // And a final \n to wrap things up + +// Rendering modes are persistent: +cursor.hex('#660000').bold().underline() + +// You can use the regular logging functions, text will be green: +console.log('This is blood red, bold text') + +// To reset just the foreground color: +cursor.fg.reset() + +console.log('This will still be bold') + +// to go to a location (x,y) on the console +// note: 1-indexed, not 0-indexed: +cursor.goto(10, 5).write('Five down, ten over') + +// to clear the current line: +cursor.horizontalAbsolute(0).eraseLine().write('Starting again') + +// to go to a different column on the current line: +cursor.horizontalAbsolute(5).write('column five') + +// Clean up after yourself! +cursor.reset() +``` + + +License +------- + +(The MIT License) + +Copyright (c) 2012 Nathan Rajlich <[email protected]> + +Permission is hereby granted, free of charge, to any person obtaining +a copy of this software and associated documentation files (the +'Software'), to deal in the Software without restriction, including +without limitation the rights to use, copy, modify, merge, publish, +distribute, sublicense, and/or sell copies of the Software, and to +permit persons to whom the Software is furnished to do so, subject to +the following conditions: + +The above copyright notice and this permission notice shall be +included in all copies or substantial portions of the Software. + +THE SOFTWARE IS PROVIDED 'AS IS', WITHOUT WARRANTY OF ANY KIND, +EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF +MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. +IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY +CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, +TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE +SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
http://git-wip-us.apache.org/repos/asf/cordova-windows/blob/3aca1d87/node_modules/ansi/examples/beep/index.js ---------------------------------------------------------------------- diff --git a/node_modules/ansi/examples/beep/index.js b/node_modules/ansi/examples/beep/index.js new file mode 100644 index 0000000..c1ec929 --- /dev/null +++ b/node_modules/ansi/examples/beep/index.js @@ -0,0 +1,16 @@ +#!/usr/bin/env node + +/** + * Invokes the terminal "beep" sound once per second on every exact second. + */ + +process.title = 'beep' + +var cursor = require('../../')(process.stdout) + +function beep () { + cursor.beep() + setTimeout(beep, 1000 - (new Date()).getMilliseconds()) +} + +setTimeout(beep, 1000 - (new Date()).getMilliseconds()) http://git-wip-us.apache.org/repos/asf/cordova-windows/blob/3aca1d87/node_modules/ansi/examples/clear/index.js ---------------------------------------------------------------------- diff --git a/node_modules/ansi/examples/clear/index.js b/node_modules/ansi/examples/clear/index.js new file mode 100644 index 0000000..6ac21ff --- /dev/null +++ b/node_modules/ansi/examples/clear/index.js @@ -0,0 +1,15 @@ +#!/usr/bin/env node + +/** + * Like GNU ncurses "clear" command. + * https://github.com/mscdex/node-ncurses/blob/master/deps/ncurses/progs/clear.c + */ + +process.title = 'clear' + +function lf () { return '\n' } + +require('../../')(process.stdout) + .write(Array.apply(null, Array(process.stdout.getWindowSize()[1])).map(lf).join('')) + .eraseData(2) + .goto(1, 1) http://git-wip-us.apache.org/repos/asf/cordova-windows/blob/3aca1d87/node_modules/ansi/examples/cursorPosition.js ---------------------------------------------------------------------- diff --git a/node_modules/ansi/examples/cursorPosition.js b/node_modules/ansi/examples/cursorPosition.js new file mode 100644 index 0000000..50f9644 --- /dev/null +++ b/node_modules/ansi/examples/cursorPosition.js @@ -0,0 +1,32 @@ +#!/usr/bin/env node + +var tty = require('tty') +var cursor = require('../')(process.stdout) + +// listen for the queryPosition report on stdin +process.stdin.resume() +raw(true) + +process.stdin.once('data', function (b) { + var match = /\[(\d+)\;(\d+)R$/.exec(b.toString()) + if (match) { + var xy = match.slice(1, 3).reverse().map(Number) + console.error(xy) + } + + // cleanup and close stdin + raw(false) + process.stdin.pause() +}) + + +// send the query position request code to stdout +cursor.queryPosition() + +function raw (mode) { + if (process.stdin.setRawMode) { + process.stdin.setRawMode(mode) + } else { + tty.setRawMode(mode) + } +} http://git-wip-us.apache.org/repos/asf/cordova-windows/blob/3aca1d87/node_modules/ansi/examples/progress/index.js ---------------------------------------------------------------------- diff --git a/node_modules/ansi/examples/progress/index.js b/node_modules/ansi/examples/progress/index.js new file mode 100644 index 0000000..d28dbda --- /dev/null +++ b/node_modules/ansi/examples/progress/index.js @@ -0,0 +1,87 @@ +#!/usr/bin/env node + +var assert = require('assert') + , ansi = require('../../') + +function Progress (stream, width) { + this.cursor = ansi(stream) + this.delta = this.cursor.newlines + this.width = width | 0 || 10 + this.open = '[' + this.close = ']' + this.complete = 'â' + this.incomplete = '_' + + // initial render + this.progress = 0 +} + +Object.defineProperty(Progress.prototype, 'progress', { + get: get + , set: set + , configurable: true + , enumerable: true +}) + +function get () { + return this._progress +} + +function set (v) { + this._progress = Math.max(0, Math.min(v, 100)) + + var w = this.width - this.complete.length - this.incomplete.length + , n = w * (this._progress / 100) | 0 + , i = w - n + , com = c(this.complete, n) + , inc = c(this.incomplete, i) + , delta = this.cursor.newlines - this.delta + + assert.equal(com.length + inc.length, w) + + if (delta > 0) { + this.cursor.up(delta) + this.delta = this.cursor.newlines + } + + this.cursor + .horizontalAbsolute(0) + .eraseLine(2) + .fg.white() + .write(this.open) + .fg.grey() + .bold() + .write(com) + .resetBold() + .write(inc) + .fg.white() + .write(this.close) + .fg.reset() + .write('\n') +} + +function c (char, length) { + return Array.apply(null, Array(length)).map(function () { + return char + }).join('') +} + + + + +// Usage +var width = parseInt(process.argv[2], 10) || process.stdout.getWindowSize()[0] / 2 + , p = new Progress(process.stdout, width) + +;(function tick () { + p.progress += Math.random() * 5 + p.cursor + .eraseLine(2) + .write('Progress: ') + .bold().write(p.progress.toFixed(2)) + .write('%') + .resetBold() + .write('\n') + if (p.progress < 100) + setTimeout(tick, 100) +})() http://git-wip-us.apache.org/repos/asf/cordova-windows/blob/3aca1d87/node_modules/ansi/lib/ansi.js ---------------------------------------------------------------------- diff --git a/node_modules/ansi/lib/ansi.js b/node_modules/ansi/lib/ansi.js new file mode 100644 index 0000000..b1714e3 --- /dev/null +++ b/node_modules/ansi/lib/ansi.js @@ -0,0 +1,405 @@ + +/** + * References: + * + * - http://en.wikipedia.org/wiki/ANSI_escape_code + * - http://www.termsys.demon.co.uk/vtansi.htm + * + */ + +/** + * Module dependencies. + */ + +var emitNewlineEvents = require('./newlines') + , prefix = '\x1b[' // For all escape codes + , suffix = 'm' // Only for color codes + +/** + * The ANSI escape sequences. + */ + +var codes = { + up: 'A' + , down: 'B' + , forward: 'C' + , back: 'D' + , nextLine: 'E' + , previousLine: 'F' + , horizontalAbsolute: 'G' + , eraseData: 'J' + , eraseLine: 'K' + , scrollUp: 'S' + , scrollDown: 'T' + , savePosition: 's' + , restorePosition: 'u' + , queryPosition: '6n' + , hide: '?25l' + , show: '?25h' +} + +/** + * Rendering ANSI codes. + */ + +var styles = { + bold: 1 + , italic: 3 + , underline: 4 + , inverse: 7 +} + +/** + * The negating ANSI code for the rendering modes. + */ + +var reset = { + bold: 22 + , italic: 23 + , underline: 24 + , inverse: 27 +} + +/** + * The standard, styleable ANSI colors. + */ + +var colors = { + white: 37 + , black: 30 + , blue: 34 + , cyan: 36 + , green: 32 + , magenta: 35 + , red: 31 + , yellow: 33 + , grey: 90 + , brightBlack: 90 + , brightRed: 91 + , brightGreen: 92 + , brightYellow: 93 + , brightBlue: 94 + , brightMagenta: 95 + , brightCyan: 96 + , brightWhite: 97 +} + + +/** + * Creates a Cursor instance based off the given `writable stream` instance. + */ + +function ansi (stream, options) { + if (stream._ansicursor) { + return stream._ansicursor + } else { + return stream._ansicursor = new Cursor(stream, options) + } +} +module.exports = exports = ansi + +/** + * The `Cursor` class. + */ + +function Cursor (stream, options) { + if (!(this instanceof Cursor)) { + return new Cursor(stream, options) + } + if (typeof stream != 'object' || typeof stream.write != 'function') { + throw new Error('a valid Stream instance must be passed in') + } + + // the stream to use + this.stream = stream + + // when 'enabled' is false then all the functions are no-ops except for write() + this.enabled = options && options.enabled + if (typeof this.enabled === 'undefined') { + this.enabled = stream.isTTY + } + this.enabled = !!this.enabled + + // then `buffering` is true, then `write()` calls are buffered in + // memory until `flush()` is invoked + this.buffering = !!(options && options.buffering) + this._buffer = [] + + // controls the foreground and background colors + this.fg = this.foreground = new Colorer(this, 0) + this.bg = this.background = new Colorer(this, 10) + + // defaults + this.Bold = false + this.Italic = false + this.Underline = false + this.Inverse = false + + // keep track of the number of "newlines" that get encountered + this.newlines = 0 + emitNewlineEvents(stream) + stream.on('newline', function () { + this.newlines++ + }.bind(this)) +} +exports.Cursor = Cursor + +/** + * Helper function that calls `write()` on the underlying Stream. + * Returns `this` instead of the write() return value to keep + * the chaining going. + */ + +Cursor.prototype.write = function (data) { + if (this.buffering) { + this._buffer.push(arguments) + } else { + this.stream.write.apply(this.stream, arguments) + } + return this +} + +/** + * Buffer `write()` calls into memory. + * + * @api public + */ + +Cursor.prototype.buffer = function () { + this.buffering = true + return this +} + +/** + * Write out the in-memory buffer. + * + * @api public + */ + +Cursor.prototype.flush = function () { + this.buffering = false + var str = this._buffer.map(function (args) { + if (args.length != 1) throw new Error('unexpected args length! ' + args.length); + return args[0]; + }).join(''); + this._buffer.splice(0); // empty + this.write(str); + return this +} + + +/** + * The `Colorer` class manages both the background and foreground colors. + */ + +function Colorer (cursor, base) { + this.current = null + this.cursor = cursor + this.base = base +} +exports.Colorer = Colorer + +/** + * Write an ANSI color code, ensuring that the same code doesn't get rewritten. + */ + +Colorer.prototype._setColorCode = function setColorCode (code) { + var c = String(code) + if (this.current === c) return + this.cursor.enabled && this.cursor.write(prefix + c + suffix) + this.current = c + return this +} + + +/** + * Set up the positional ANSI codes. + */ + +Object.keys(codes).forEach(function (name) { + var code = String(codes[name]) + Cursor.prototype[name] = function () { + var c = code + if (arguments.length > 0) { + c = toArray(arguments).map(Math.round).join(';') + code + } + this.enabled && this.write(prefix + c) + return this + } +}) + +/** + * Set up the functions for the rendering ANSI codes. + */ + +Object.keys(styles).forEach(function (style) { + var name = style[0].toUpperCase() + style.substring(1) + , c = styles[style] + , r = reset[style] + + Cursor.prototype[style] = function () { + if (this[name]) return this + this.enabled && this.write(prefix + c + suffix) + this[name] = true + return this + } + + Cursor.prototype['reset' + name] = function () { + if (!this[name]) return this + this.enabled && this.write(prefix + r + suffix) + this[name] = false + return this + } +}) + +/** + * Setup the functions for the standard colors. + */ + +Object.keys(colors).forEach(function (color) { + var code = colors[color] + + Colorer.prototype[color] = function () { + this._setColorCode(this.base + code) + return this.cursor + } + + Cursor.prototype[color] = function () { + return this.foreground[color]() + } +}) + +/** + * Makes a beep sound! + */ + +Cursor.prototype.beep = function () { + this.enabled && this.write('\x07') + return this +} + +/** + * Moves cursor to specific position + */ + +Cursor.prototype.goto = function (x, y) { + x = x | 0 + y = y | 0 + this.enabled && this.write(prefix + y + ';' + x + 'H') + return this +} + +/** + * Resets the color. + */ + +Colorer.prototype.reset = function () { + this._setColorCode(this.base + 39) + return this.cursor +} + +/** + * Resets all ANSI formatting on the stream. + */ + +Cursor.prototype.reset = function () { + this.enabled && this.write(prefix + '0' + suffix) + this.Bold = false + this.Italic = false + this.Underline = false + this.Inverse = false + this.foreground.current = null + this.background.current = null + return this +} + +/** + * Sets the foreground color with the given RGB values. + * The closest match out of the 216 colors is picked. + */ + +Colorer.prototype.rgb = function (r, g, b) { + var base = this.base + 38 + , code = rgb(r, g, b) + this._setColorCode(base + ';5;' + code) + return this.cursor +} + +/** + * Same as `cursor.fg.rgb(r, g, b)`. + */ + +Cursor.prototype.rgb = function (r, g, b) { + return this.foreground.rgb(r, g, b) +} + +/** + * Accepts CSS color codes for use with ANSI escape codes. + * For example: `#FF000` would be bright red. + */ + +Colorer.prototype.hex = function (color) { + return this.rgb.apply(this, hex(color)) +} + +/** + * Same as `cursor.fg.hex(color)`. + */ + +Cursor.prototype.hex = function (color) { + return this.foreground.hex(color) +} + + +// UTIL FUNCTIONS // + +/** + * Translates a 255 RGB value to a 0-5 ANSI RGV value, + * then returns the single ANSI color code to use. + */ + +function rgb (r, g, b) { + var red = r / 255 * 5 + , green = g / 255 * 5 + , blue = b / 255 * 5 + return rgb5(red, green, blue) +} + +/** + * Turns rgb 0-5 values into a single ANSI color code to use. + */ + +function rgb5 (r, g, b) { + var red = Math.round(r) + , green = Math.round(g) + , blue = Math.round(b) + return 16 + (red*36) + (green*6) + blue +} + +/** + * Accepts a hex CSS color code string (# is optional) and + * translates it into an Array of 3 RGB 0-255 values, which + * can then be used with rgb(). + */ + +function hex (color) { + var c = color[0] === '#' ? color.substring(1) : color + , r = c.substring(0, 2) + , g = c.substring(2, 4) + , b = c.substring(4, 6) + return [parseInt(r, 16), parseInt(g, 16), parseInt(b, 16)] +} + +/** + * Turns an array-like object into a real array. + */ + +function toArray (a) { + var i = 0 + , l = a.length + , rtn = [] + for (; i<l; i++) { + rtn.push(a[i]) + } + return rtn +} http://git-wip-us.apache.org/repos/asf/cordova-windows/blob/3aca1d87/node_modules/ansi/lib/newlines.js ---------------------------------------------------------------------- diff --git a/node_modules/ansi/lib/newlines.js b/node_modules/ansi/lib/newlines.js new file mode 100644 index 0000000..4e37a0a --- /dev/null +++ b/node_modules/ansi/lib/newlines.js @@ -0,0 +1,71 @@ + +/** + * Accepts any node Stream instance and hijacks its "write()" function, + * so that it can count any newlines that get written to the output. + * + * When a '\n' byte is encountered, then a "newline" event will be emitted + * on the stream, with no arguments. It is up to the listeners to determine + * any necessary deltas required for their use-case. + * + * Ex: + * + * var cursor = ansi(process.stdout) + * , ln = 0 + * process.stdout.on('newline', function () { + * ln++ + * }) + */ + +/** + * Module dependencies. + */ + +var assert = require('assert') +var NEWLINE = '\n'.charCodeAt(0) + +function emitNewlineEvents (stream) { + if (stream._emittingNewlines) { + // already emitting newline events + return + } + + var write = stream.write + + stream.write = function (data) { + // first write the data + var rtn = write.apply(stream, arguments) + + if (stream.listeners('newline').length > 0) { + var len = data.length + , i = 0 + // now try to calculate any deltas + if (typeof data == 'string') { + for (; i<len; i++) { + processByte(stream, data.charCodeAt(i)) + } + } else { + // buffer + for (; i<len; i++) { + processByte(stream, data[i]) + } + } + } + + return rtn + } + + stream._emittingNewlines = true +} +module.exports = emitNewlineEvents + + +/** + * Processes an individual byte being written to a stream + */ + +function processByte (stream, b) { + assert.equal(typeof b, 'number') + if (b === NEWLINE) { + stream.emit('newline') + } +} http://git-wip-us.apache.org/repos/asf/cordova-windows/blob/3aca1d87/node_modules/ansi/package.json ---------------------------------------------------------------------- diff --git a/node_modules/ansi/package.json b/node_modules/ansi/package.json new file mode 100644 index 0000000..0585f8c --- /dev/null +++ b/node_modules/ansi/package.json @@ -0,0 +1,94 @@ +{ + "_args": [ + [ + { + "raw": "ansi@^0.3.1", + "scope": null, + "escapedName": "ansi", + "name": "ansi", + "rawSpec": "^0.3.1", + "spec": ">=0.3.1 <0.4.0", + "type": "range" + }, + "d:\\cordova\\cordova-windows\\node_modules\\cordova-common" + ] + ], + "_from": "ansi@>=0.3.1 <0.4.0", + "_id": "[email protected]", + "_inCache": true, + "_installable": true, + "_location": "/ansi", + "_nodeVersion": "5.3.0", + "_npmUser": { + "name": "tootallnate", + "email": "[email protected]" + }, + "_npmVersion": "3.3.12", + "_phantomChildren": {}, + "_requested": { + "raw": "ansi@^0.3.1", + "scope": null, + "escapedName": "ansi", + "name": "ansi", + "rawSpec": "^0.3.1", + "spec": ">=0.3.1 <0.4.0", + "type": "range" + }, + "_requiredBy": [ + "/cordova-common" + ], + "_resolved": "https://registry.npmjs.org/ansi/-/ansi-0.3.1.tgz";, + "_shasum": "0c42d4fb17160d5a9af1e484bace1c66922c1b21", + "_shrinkwrap": null, + "_spec": "ansi@^0.3.1", + "_where": "d:\\cordova\\cordova-windows\\node_modules\\cordova-common", + "author": { + "name": "Nathan Rajlich", + "email": "[email protected]", + "url": "http://tootallnate.net"; + }, + "bugs": { + "url": "https://github.com/TooTallNate/ansi.js/issues"; + }, + "dependencies": {}, + "description": "Advanced ANSI formatting tool for Node.js", + "devDependencies": {}, + "directories": {}, + "dist": { + "shasum": "0c42d4fb17160d5a9af1e484bace1c66922c1b21", + "tarball": "https://registry.npmjs.org/ansi/-/ansi-0.3.1.tgz"; + }, + "gitHead": "4d0d4af94e0bdaa648bd7262acd3bde4b98d5246", + "homepage": "https://github.com/TooTallNate/ansi.js#readme";, + "keywords": [ + "ansi", + "formatting", + "cursor", + "color", + "terminal", + "rgb", + "256", + "stream" + ], + "license": "MIT", + "main": "./lib/ansi.js", + "maintainers": [ + { + "name": "TooTallNate", + "email": "[email protected]" + }, + { + "name": "tootallnate", + "email": "[email protected]" + } + ], + "name": "ansi", + "optionalDependencies": {}, + "readme": "ERROR: No README data found!", + "repository": { + "type": "git", + "url": "git://github.com/TooTallNate/ansi.js.git" + }, + "scripts": {}, + "version": "0.3.1" +} http://git-wip-us.apache.org/repos/asf/cordova-windows/blob/3aca1d87/node_modules/balanced-match/.npmignore ---------------------------------------------------------------------- diff --git a/node_modules/balanced-match/.npmignore b/node_modules/balanced-match/.npmignore new file mode 100644 index 0000000..ae5d8c3 --- /dev/null +++ b/node_modules/balanced-match/.npmignore @@ -0,0 +1,5 @@ +test +.gitignore +.travis.yml +Makefile +example.js http://git-wip-us.apache.org/repos/asf/cordova-windows/blob/3aca1d87/node_modules/balanced-match/LICENSE.md ---------------------------------------------------------------------- diff --git a/node_modules/balanced-match/LICENSE.md b/node_modules/balanced-match/LICENSE.md new file mode 100644 index 0000000..2cdc8e4 --- /dev/null +++ b/node_modules/balanced-match/LICENSE.md @@ -0,0 +1,21 @@ +(MIT) + +Copyright (c) 2013 Julian Gruber <[email protected]> + +Permission is hereby granted, free of charge, to any person obtaining a copy of +this software and associated documentation files (the "Software"), to deal in +the Software without restriction, including without limitation the rights to +use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies +of the Software, and to permit persons to whom the Software is furnished to do +so, subject to the following conditions: + +The above copyright notice and this permission notice shall be included in all +copies or substantial portions of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, +OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE +SOFTWARE. http://git-wip-us.apache.org/repos/asf/cordova-windows/blob/3aca1d87/node_modules/balanced-match/README.md ---------------------------------------------------------------------- diff --git a/node_modules/balanced-match/README.md b/node_modules/balanced-match/README.md new file mode 100644 index 0000000..d6880b2 --- /dev/null +++ b/node_modules/balanced-match/README.md @@ -0,0 +1,91 @@ +# balanced-match + +Match balanced string pairs, like `{` and `}` or `<b>` and `</b>`. Supports regular expressions as well! + +[](http://travis-ci.org/juliangruber/balanced-match) +[](https://www.npmjs.org/package/balanced-match) + +[](https://ci.testling.com/juliangruber/balanced-match) + +## Example + +Get the first matching pair of braces: + +```js +var balanced = require('balanced-match'); + +console.log(balanced('{', '}', 'pre{in{nested}}post')); +console.log(balanced('{', '}', 'pre{first}between{second}post')); +console.log(balanced(/\s+\{\s+/, /\s+\}\s+/, 'pre { in{nest} } post')); +``` + +The matches are: + +```bash +$ node example.js +{ start: 3, end: 14, pre: 'pre', body: 'in{nested}', post: 'post' } +{ start: 3, + end: 9, + pre: 'pre', + body: 'first', + post: 'between{second}post' } +{ start: 3, end: 17, pre: 'pre', body: 'in{nest}', post: 'post' } +``` + +## API + +### var m = balanced(a, b, str) + +For the first non-nested matching pair of `a` and `b` in `str`, return an +object with those keys: + +* **start** the index of the first match of `a` +* **end** the index of the matching `b` +* **pre** the preamble, `a` and `b` not included +* **body** the match, `a` and `b` not included +* **post** the postscript, `a` and `b` not included + +If there's no match, `undefined` will be returned. + +If the `str` contains more `a` than `b` / there are unmatched pairs, the first match that was closed will be used. For example, `{{a}` will match `['{', 'a', '']`. + +### var r = balanced.range(a, b, str) + +For the first non-nested matching pair of `a` and `b` in `str`, return an +array with indexes: `[ <a index>, <b index> ]`. + +If there's no match, `undefined` will be returned. + +If the `str` contains more `a` than `b` / there are unmatched pairs, the first match that was closed will be used. For example, `{{a}` will match `[ 1, 3 ]`. + +## Installation + +With [npm](https://npmjs.org) do: + +```bash +npm install balanced-match +``` + +## License + +(MIT) + +Copyright (c) 2013 Julian Gruber <[email protected]> + +Permission is hereby granted, free of charge, to any person obtaining a copy of +this software and associated documentation files (the "Software"), to deal in +the Software without restriction, including without limitation the rights to +use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies +of the Software, and to permit persons to whom the Software is furnished to do +so, subject to the following conditions: + +The above copyright notice and this permission notice shall be included in all +copies or substantial portions of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, +OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE +SOFTWARE. http://git-wip-us.apache.org/repos/asf/cordova-windows/blob/3aca1d87/node_modules/balanced-match/index.js ---------------------------------------------------------------------- diff --git a/node_modules/balanced-match/index.js b/node_modules/balanced-match/index.js new file mode 100644 index 0000000..4670f7f --- /dev/null +++ b/node_modules/balanced-match/index.js @@ -0,0 +1,58 @@ +module.exports = balanced; +function balanced(a, b, str) { + if (a instanceof RegExp) a = maybeMatch(a, str); + if (b instanceof RegExp) b = maybeMatch(b, str); + + var r = range(a, b, str); + + return r && { + start: r[0], + end: r[1], + pre: str.slice(0, r[0]), + body: str.slice(r[0] + a.length, r[1]), + post: str.slice(r[1] + b.length) + }; +} + +function maybeMatch(reg, str) { + var m = str.match(reg); + return m ? m[0] : null; +} + +balanced.range = range; +function range(a, b, str) { + var begs, beg, left, right, result; + var ai = str.indexOf(a); + var bi = str.indexOf(b, ai + 1); + var i = ai; + + if (ai >= 0 && bi > 0) { + begs = []; + left = str.length; + + while (i < str.length && i >= 0 && ! result) { + if (i == ai) { + begs.push(i); + ai = str.indexOf(a, i + 1); + } else if (begs.length == 1) { + result = [ begs.pop(), bi ]; + } else { + beg = begs.pop(); + if (beg < left) { + left = beg; + right = bi; + } + + bi = str.indexOf(b, i + 1); + } + + i = ai < bi && ai >= 0 ? ai : bi; + } + + if (begs.length) { + result = [ left, right ]; + } + } + + return result; +} http://git-wip-us.apache.org/repos/asf/cordova-windows/blob/3aca1d87/node_modules/balanced-match/package.json ---------------------------------------------------------------------- diff --git a/node_modules/balanced-match/package.json b/node_modules/balanced-match/package.json new file mode 100644 index 0000000..5a6a85d --- /dev/null +++ b/node_modules/balanced-match/package.json @@ -0,0 +1,111 @@ +{ + "_args": [ + [ + { + "raw": "balanced-match@^0.4.1", + "scope": null, + "escapedName": "balanced-match", + "name": "balanced-match", + "rawSpec": "^0.4.1", + "spec": ">=0.4.1 <0.5.0", + "type": "range" + }, + "d:\\cordova\\cordova-windows\\node_modules\\brace-expansion" + ] + ], + "_from": "balanced-match@>=0.4.1 <0.5.0", + "_id": "[email protected]", + "_inCache": true, + "_installable": true, + "_location": "/balanced-match", + "_nodeVersion": "6.0.0", + "_npmOperationalInternal": { + "host": "packages-12-west.internal.npmjs.com", + "tmp": "tmp/balanced-match-0.4.1.tgz_1462129663650_0.39764496590942144" + }, + "_npmUser": { + "name": "juliangruber", + "email": "[email protected]" + }, + "_npmVersion": "3.8.6", + "_phantomChildren": {}, + "_requested": { + "raw": "balanced-match@^0.4.1", + "scope": null, + "escapedName": "balanced-match", + "name": "balanced-match", + "rawSpec": "^0.4.1", + "spec": ">=0.4.1 <0.5.0", + "type": "range" + }, + "_requiredBy": [ + "/brace-expansion" + ], + "_resolved": "https://registry.npmjs.org/balanced-match/-/balanced-match-0.4.1.tgz";, + "_shasum": "19053e2e0748eadb379da6c09d455cf5e1039335", + "_shrinkwrap": null, + "_spec": "balanced-match@^0.4.1", + "_where": "d:\\cordova\\cordova-windows\\node_modules\\brace-expansion", + "author": { + "name": "Julian Gruber", + "email": "[email protected]", + "url": "http://juliangruber.com"; + }, + "bugs": { + "url": "https://github.com/juliangruber/balanced-match/issues"; + }, + "dependencies": {}, + "description": "Match balanced character pairs, like \"{\" and \"}\"", + "devDependencies": { + "tape": "~4.5.0" + }, + "directories": {}, + "dist": { + "shasum": "19053e2e0748eadb379da6c09d455cf5e1039335", + "tarball": "https://registry.npmjs.org/balanced-match/-/balanced-match-0.4.1.tgz"; + }, + "gitHead": "7004b289baaaab6a832f4901735e29d37cc2a863", + "homepage": "https://github.com/juliangruber/balanced-match";, + "keywords": [ + "match", + "regexp", + "test", + "balanced", + "parse" + ], + "license": "MIT", + "main": "index.js", + "maintainers": [ + { + "name": "juliangruber", + "email": "[email protected]" + } + ], + "name": "balanced-match", + "optionalDependencies": {}, + "readme": "ERROR: No README data found!", + "repository": { + "type": "git", + "url": "git://github.com/juliangruber/balanced-match.git" + }, + "scripts": { + "test": "make test" + }, + "testling": { + "files": "test/*.js", + "browsers": [ + "ie/8..latest", + "firefox/20..latest", + "firefox/nightly", + "chrome/25..latest", + "chrome/canary", + "opera/12..latest", + "opera/next", + "safari/5.1..latest", + "ipad/6.0..latest", + "iphone/6.0..latest", + "android-browser/4.2..latest" + ] + }, + "version": "0.4.1" +} http://git-wip-us.apache.org/repos/asf/cordova-windows/blob/3aca1d87/node_modules/base64-js/.travis.yml ---------------------------------------------------------------------- diff --git a/node_modules/base64-js/.travis.yml b/node_modules/base64-js/.travis.yml new file mode 100644 index 0000000..939cb51 --- /dev/null +++ b/node_modules/base64-js/.travis.yml @@ -0,0 +1,5 @@ +language: node_js +node_js: + - "0.8" + - "0.10" + - "0.11" \ No newline at end of file http://git-wip-us.apache.org/repos/asf/cordova-windows/blob/3aca1d87/node_modules/base64-js/LICENSE.MIT ---------------------------------------------------------------------- diff --git a/node_modules/base64-js/LICENSE.MIT b/node_modules/base64-js/LICENSE.MIT new file mode 100644 index 0000000..96d3f68 --- /dev/null +++ b/node_modules/base64-js/LICENSE.MIT @@ -0,0 +1,21 @@ +The MIT License (MIT) + +Copyright (c) 2014 + +Permission is hereby granted, free of charge, to any person obtaining a copy +of this software and associated documentation files (the "Software"), to deal +in the Software without restriction, including without limitation the rights +to use, copy, modify, merge, publish, distribute, sublicense, and/or sell +copies of the Software, and to permit persons to whom the Software is +furnished to do so, subject to the following conditions: + +The above copyright notice and this permission notice shall be included in +all copies or substantial portions of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, +OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN +THE SOFTWARE. http://git-wip-us.apache.org/repos/asf/cordova-windows/blob/3aca1d87/node_modules/base64-js/README.md ---------------------------------------------------------------------- diff --git a/node_modules/base64-js/README.md b/node_modules/base64-js/README.md new file mode 100644 index 0000000..ed31d1a --- /dev/null +++ b/node_modules/base64-js/README.md @@ -0,0 +1,31 @@ +base64-js +========= + +`base64-js` does basic base64 encoding/decoding in pure JS. + +[](http://travis-ci.org/beatgammit/base64-js) + +[](https://ci.testling.com/beatgammit/base64-js) + +Many browsers already have base64 encoding/decoding functionality, but it is for text data, not all-purpose binary data. + +Sometimes encoding/decoding binary data in the browser is useful, and that is what this module does. + +## install + +With [npm](https://npmjs.org) do: + +`npm install base64-js` + +## methods + +`var base64 = require('base64-js')` + +`base64` has two exposed functions, `toByteArray` and `fromByteArray`, which both take a single argument. + +* `toByteArray` - Takes a base64 string and returns a byte array +* `fromByteArray` - Takes a byte array and returns a base64 string + +## license + +MIT \ No newline at end of file http://git-wip-us.apache.org/repos/asf/cordova-windows/blob/3aca1d87/node_modules/base64-js/bench/bench.js ---------------------------------------------------------------------- diff --git a/node_modules/base64-js/bench/bench.js b/node_modules/base64-js/bench/bench.js new file mode 100644 index 0000000..0689e08 --- /dev/null +++ b/node_modules/base64-js/bench/bench.js @@ -0,0 +1,19 @@ +var random = require('crypto').pseudoRandomBytes + +var b64 = require('../') +var fs = require('fs') +var path = require('path') +var data = random(1e6).toString('base64') +//fs.readFileSync(path.join(__dirname, 'example.b64'), 'ascii').split('\n').join('') +var start = Date.now() +var raw = b64.toByteArray(data) +var middle = Date.now() +var data = b64.fromByteArray(raw) +var end = Date.now() + +console.log('decode ms, decode ops/ms, encode ms, encode ops/ms') +console.log( + middle - start, data.length / (middle - start), + end - middle, data.length / (end - middle)) +//console.log(data) + http://git-wip-us.apache.org/repos/asf/cordova-windows/blob/3aca1d87/node_modules/base64-js/lib/b64.js ---------------------------------------------------------------------- diff --git a/node_modules/base64-js/lib/b64.js b/node_modules/base64-js/lib/b64.js new file mode 100644 index 0000000..46001d2 --- /dev/null +++ b/node_modules/base64-js/lib/b64.js @@ -0,0 +1,124 @@ +var lookup = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/'; + +;(function (exports) { + 'use strict'; + + var Arr = (typeof Uint8Array !== 'undefined') + ? Uint8Array + : Array + + var PLUS = '+'.charCodeAt(0) + var SLASH = '/'.charCodeAt(0) + var NUMBER = '0'.charCodeAt(0) + var LOWER = 'a'.charCodeAt(0) + var UPPER = 'A'.charCodeAt(0) + var PLUS_URL_SAFE = '-'.charCodeAt(0) + var SLASH_URL_SAFE = '_'.charCodeAt(0) + + function decode (elt) { + var code = elt.charCodeAt(0) + if (code === PLUS || + code === PLUS_URL_SAFE) + return 62 // '+' + if (code === SLASH || + code === SLASH_URL_SAFE) + return 63 // '/' + if (code < NUMBER) + return -1 //no match + if (code < NUMBER + 10) + return code - NUMBER + 26 + 26 + if (code < UPPER + 26) + return code - UPPER + if (code < LOWER + 26) + return code - LOWER + 26 + } + + function b64ToByteArray (b64) { + var i, j, l, tmp, placeHolders, arr + + if (b64.length % 4 > 0) { + throw new Error('Invalid string. Length must be a multiple of 4') + } + + // the number of equal signs (place holders) + // if there are two placeholders, than the two characters before it + // represent one byte + // if there is only one, then the three characters before it represent 2 bytes + // this is just a cheap hack to not do indexOf twice + var len = b64.length + placeHolders = '=' === b64.charAt(len - 2) ? 2 : '=' === b64.charAt(len - 1) ? 1 : 0 + + // base64 is 4/3 + up to two characters of the original data + arr = new Arr(b64.length * 3 / 4 - placeHolders) + + // if there are placeholders, only get up to the last complete 4 chars + l = placeHolders > 0 ? b64.length - 4 : b64.length + + var L = 0 + + function push (v) { + arr[L++] = v + } + + for (i = 0, j = 0; i < l; i += 4, j += 3) { + tmp = (decode(b64.charAt(i)) << 18) | (decode(b64.charAt(i + 1)) << 12) | (decode(b64.charAt(i + 2)) << 6) | decode(b64.charAt(i + 3)) + push((tmp & 0xFF0000) >> 16) + push((tmp & 0xFF00) >> 8) + push(tmp & 0xFF) + } + + if (placeHolders === 2) { + tmp = (decode(b64.charAt(i)) << 2) | (decode(b64.charAt(i + 1)) >> 4) + push(tmp & 0xFF) + } else if (placeHolders === 1) { + tmp = (decode(b64.charAt(i)) << 10) | (decode(b64.charAt(i + 1)) << 4) | (decode(b64.charAt(i + 2)) >> 2) + push((tmp >> 8) & 0xFF) + push(tmp & 0xFF) + } + + return arr + } + + function uint8ToBase64 (uint8) { + var i, + extraBytes = uint8.length % 3, // if we have 1 byte left, pad 2 bytes + output = "", + temp, length + + function encode (num) { + return lookup.charAt(num) + } + + function tripletToBase64 (num) { + return encode(num >> 18 & 0x3F) + encode(num >> 12 & 0x3F) + encode(num >> 6 & 0x3F) + encode(num & 0x3F) + } + + // go through the array every three bytes, we'll deal with trailing stuff later + for (i = 0, length = uint8.length - extraBytes; i < length; i += 3) { + temp = (uint8[i] << 16) + (uint8[i + 1] << 8) + (uint8[i + 2]) + output += tripletToBase64(temp) + } + + // pad the end with zeros, but make sure to not forget the extra bytes + switch (extraBytes) { + case 1: + temp = uint8[uint8.length - 1] + output += encode(temp >> 2) + output += encode((temp << 4) & 0x3F) + output += '==' + break + case 2: + temp = (uint8[uint8.length - 2] << 8) + (uint8[uint8.length - 1]) + output += encode(temp >> 10) + output += encode((temp >> 4) & 0x3F) + output += encode((temp << 2) & 0x3F) + output += '=' + break + } + + return output + } + + exports.toByteArray = b64ToByteArray + exports.fromByteArray = uint8ToBase64 +}(typeof exports === 'undefined' ? (this.base64js = {}) : exports)) http://git-wip-us.apache.org/repos/asf/cordova-windows/blob/3aca1d87/node_modules/base64-js/package.json ---------------------------------------------------------------------- diff --git a/node_modules/base64-js/package.json b/node_modules/base64-js/package.json new file mode 100644 index 0000000..73e3e47 --- /dev/null +++ b/node_modules/base64-js/package.json @@ -0,0 +1,102 @@ +{ + "_args": [ + [ + { + "raw": "[email protected]", + "scope": null, + "escapedName": "base64-js", + "name": "base64-js", + "rawSpec": "0.0.8", + "spec": "0.0.8", + "type": "version" + }, + "d:\\cordova\\cordova-windows\\node_modules\\plist" + ] + ], + "_from": "[email protected]", + "_id": "[email protected]", + "_inCache": true, + "_installable": true, + "_location": "/base64-js", + "_nodeVersion": "0.10.35", + "_npmUser": { + "name": "feross", + "email": "[email protected]" + }, + "_npmVersion": "2.1.16", + "_phantomChildren": {}, + "_requested": { + "raw": "[email protected]", + "scope": null, + "escapedName": "base64-js", + "name": "base64-js", + "rawSpec": "0.0.8", + "spec": "0.0.8", + "type": "version" + }, + "_requiredBy": [ + "/plist" + ], + "_resolved": "https://registry.npmjs.org/base64-js/-/base64-js-0.0.8.tgz";, + "_shasum": "1101e9544f4a76b1bc3b26d452ca96d7a35e7978", + "_shrinkwrap": null, + "_spec": "[email protected]", + "_where": "d:\\cordova\\cordova-windows\\node_modules\\plist", + "author": { + "name": "T. Jameson Little", + "email": "[email protected]" + }, + "bugs": { + "url": "https://github.com/beatgammit/base64-js/issues"; + }, + "dependencies": {}, + "description": "Base64 encoding/decoding in pure JS", + "devDependencies": { + "tape": "~2.3.2" + }, + "directories": {}, + "dist": { + "shasum": "1101e9544f4a76b1bc3b26d452ca96d7a35e7978", + "tarball": "https://registry.npmjs.org/base64-js/-/base64-js-0.0.8.tgz"; + }, + "engines": { + "node": ">= 0.4" + }, + "gitHead": "b4a8a5fa9b0caeddb5ad94dd1108253d8f2a315f", + "homepage": "https://github.com/beatgammit/base64-js";, + "license": "MIT", + "main": "lib/b64.js", + "maintainers": [ + { + "name": "beatgammit", + "email": "[email protected]" + }, + { + "name": "feross", + "email": "[email protected]" + } + ], + "name": "base64-js", + "optionalDependencies": {}, + "readme": "ERROR: No README data found!", + "repository": { + "type": "git", + "url": "git://github.com/beatgammit/base64-js.git" + }, + "scripts": { + "test": "tape test/*.js" + }, + "testling": { + "files": "test/*.js", + "browsers": [ + "ie/6..latest", + "chrome/4..latest", + "firefox/3..latest", + "safari/5.1..latest", + "opera/11.0..latest", + "iphone/6", + "ipad/6" + ] + }, + "version": "0.0.8" +} http://git-wip-us.apache.org/repos/asf/cordova-windows/blob/3aca1d87/node_modules/base64-js/test/convert.js ---------------------------------------------------------------------- diff --git a/node_modules/base64-js/test/convert.js b/node_modules/base64-js/test/convert.js new file mode 100644 index 0000000..60b09c0 --- /dev/null +++ b/node_modules/base64-js/test/convert.js @@ -0,0 +1,51 @@ +var test = require('tape'), + b64 = require('../lib/b64'), + checks = [ + 'a', + 'aa', + 'aaa', + 'hi', + 'hi!', + 'hi!!', + 'sup', + 'sup?', + 'sup?!' + ]; + +test('convert to base64 and back', function (t) { + t.plan(checks.length); + + for (var i = 0; i < checks.length; i++) { + var check = checks[i], + b64Str, + arr, + str; + + b64Str = b64.fromByteArray(map(check, function (char) { return char.charCodeAt(0); })); + + arr = b64.toByteArray(b64Str); + str = map(arr, function (byte) { return String.fromCharCode(byte); }).join(''); + + t.equal(check, str, 'Checked ' + check); + } + +}); + +function map (arr, callback) { + var res = [], + kValue, + mappedValue; + + for (var k = 0, len = arr.length; k < len; k++) { + if ((typeof arr === 'string' && !!arr.charAt(k))) { + kValue = arr.charAt(k); + mappedValue = callback(kValue, k, arr); + res[k] = mappedValue; + } else if (typeof arr !== 'string' && k in arr) { + kValue = arr[k]; + mappedValue = callback(kValue, k, arr); + res[k] = mappedValue; + } + } + return res; +} http://git-wip-us.apache.org/repos/asf/cordova-windows/blob/3aca1d87/node_modules/base64-js/test/url-safe.js ---------------------------------------------------------------------- diff --git a/node_modules/base64-js/test/url-safe.js b/node_modules/base64-js/test/url-safe.js new file mode 100644 index 0000000..dc437e9 --- /dev/null +++ b/node_modules/base64-js/test/url-safe.js @@ -0,0 +1,18 @@ +var test = require('tape'), + b64 = require('../lib/b64'); + +test('decode url-safe style base64 strings', function (t) { + var expected = [0xff, 0xff, 0xbe, 0xff, 0xef, 0xbf, 0xfb, 0xef, 0xff]; + + var actual = b64.toByteArray('//++/++/++//'); + for (var i = 0; i < actual.length; i++) { + t.equal(actual[i], expected[i]) + } + + actual = b64.toByteArray('__--_--_--__'); + for (var i = 0; i < actual.length; i++) { + t.equal(actual[i], expected[i]) + } + + t.end(); +}); http://git-wip-us.apache.org/repos/asf/cordova-windows/blob/3aca1d87/node_modules/big-integer/BigInteger.js ---------------------------------------------------------------------- diff --git a/node_modules/big-integer/BigInteger.js b/node_modules/big-integer/BigInteger.js new file mode 100644 index 0000000..ec9b6d1 --- /dev/null +++ b/node_modules/big-integer/BigInteger.js @@ -0,0 +1,1195 @@ +var bigInt = (function (undefined) { + "use strict"; + + var BASE = 1e7, + LOG_BASE = 7, + MAX_INT = 9007199254740992, + MAX_INT_ARR = smallToArray(MAX_INT), + LOG_MAX_INT = Math.log(MAX_INT); + + function Integer(v, radix) { + if (typeof v === "undefined") return Integer[0]; + if (typeof radix !== "undefined") return +radix === 10 ? parseValue(v) : parseBase(v, radix); + return parseValue(v); + } + + function BigInteger(value, sign) { + this.value = value; + this.sign = sign; + this.isSmall = false; + } + BigInteger.prototype = Object.create(Integer.prototype); + + function SmallInteger(value) { + this.value = value; + this.sign = value < 0; + this.isSmall = true; + } + SmallInteger.prototype = Object.create(Integer.prototype); + + function isPrecise(n) { + return -MAX_INT < n && n < MAX_INT; + } + + function smallToArray(n) { // For performance reasons doesn't reference BASE, need to change this function if BASE changes + if (n < 1e7) + return [n]; + if (n < 1e14) + return [n % 1e7, Math.floor(n / 1e7)]; + return [n % 1e7, Math.floor(n / 1e7) % 1e7, Math.floor(n / 1e14)]; + } + + function arrayToSmall(arr) { // If BASE changes this function may need to change + trim(arr); + var length = arr.length; + if (length < 4 && compareAbs(arr, MAX_INT_ARR) < 0) { + switch (length) { + case 0: return 0; + case 1: return arr[0]; + case 2: return arr[0] + arr[1] * BASE; + default: return arr[0] + (arr[1] + arr[2] * BASE) * BASE; + } + } + return arr; + } + + function trim(v) { + var i = v.length; + while (v[--i] === 0); + v.length = i + 1; + } + + function createArray(length) { // function shamelessly stolen from Yaffle's library https://github.com/Yaffle/BigInteger + var x = new Array(length); + var i = -1; + while (++i < length) { + x[i] = 0; + } + return x; + } + + function truncate(n) { + if (n > 0) return Math.floor(n); + return Math.ceil(n); + } + + function add(a, b) { // assumes a and b are arrays with a.length >= b.length + var l_a = a.length, + l_b = b.length, + r = new Array(l_a), + carry = 0, + base = BASE, + sum, i; + for (i = 0; i < l_b; i++) { + sum = a[i] + b[i] + carry; + carry = sum >= base ? 1 : 0; + r[i] = sum - carry * base; + } + while (i < l_a) { + sum = a[i] + carry; + carry = sum === base ? 1 : 0; + r[i++] = sum - carry * base; + } + if (carry > 0) r.push(carry); + return r; + } + + function addAny(a, b) { + if (a.length >= b.length) return add(a, b); + return add(b, a); + } + + function addSmall(a, carry) { // assumes a is array, carry is number with 0 <= carry < MAX_INT + var l = a.length, + r = new Array(l), + base = BASE, + sum, i; + for (i = 0; i < l; i++) { + sum = a[i] - base + carry; + carry = Math.floor(sum / base); + r[i] = sum - carry * base; + carry += 1; + } + while (carry > 0) { + r[i++] = carry % base; + carry = Math.floor(carry / base); + } + return r; + } + + BigInteger.prototype.add = function (v) { + var value, n = parseValue(v); + if (this.sign !== n.sign) { + return this.subtract(n.negate()); + } + var a = this.value, b = n.value; + if (n.isSmall) { + return new BigInteger(addSmall(a, Math.abs(b)), this.sign); + } + return new BigInteger(addAny(a, b), this.sign); + }; + BigInteger.prototype.plus = BigInteger.prototype.add; + + SmallInteger.prototype.add = function (v) { + var n = parseValue(v); + var a = this.value; + if (a < 0 !== n.sign) { + return this.subtract(n.negate()); + } + var b = n.value; + if (n.isSmall) { + if (isPrecise(a + b)) return new SmallInteger(a + b); + b = smallToArray(Math.abs(b)); + } + return new BigInteger(addSmall(b, Math.abs(a)), a < 0); + }; + SmallInteger.prototype.plus = SmallInteger.prototype.add; + + function subtract(a, b) { // assumes a and b are arrays with a >= b + var a_l = a.length, + b_l = b.length, + r = new Array(a_l), + borrow = 0, + base = BASE, + i, difference; + for (i = 0; i < b_l; i++) { + difference = a[i] - borrow - b[i]; + if (difference < 0) { + difference += base; + borrow = 1; + } else borrow = 0; + r[i] = difference; + } + for (i = b_l; i < a_l; i++) { + difference = a[i] - borrow; + if (difference < 0) difference += base; + else { + r[i++] = difference; + break; + } + r[i] = difference; + } + for (; i < a_l; i++) { + r[i] = a[i]; + } + trim(r); + return r; + } + + function subtractAny(a, b, sign) { + var value, isSmall; + if (compareAbs(a, b) >= 0) { + value = subtract(a,b); + } else { + value = subtract(b, a); + sign = !sign; + } + value = arrayToSmall(value); + if (typeof value === "number") { + if (sign) value = -value; + return new SmallInteger(value); + } + return new BigInteger(value, sign); + } + + function subtractSmall(a, b, sign) { // assumes a is array, b is number with 0 <= b < MAX_INT + var l = a.length, + r = new Array(l), + carry = -b, + base = BASE, + i, difference; + for (i = 0; i < l; i++) { + difference = a[i] + carry; + carry = Math.floor(difference / base); + difference %= base; + r[i] = difference < 0 ? difference + base : difference; + } + r = arrayToSmall(r); + if (typeof r === "number") { + if (sign) r = -r; + return new SmallInteger(r); + } return new BigInteger(r, sign); + } + + BigInteger.prototype.subtract = function (v) { + var n = parseValue(v); + if (this.sign !== n.sign) { + return this.add(n.negate()); + } + var a = this.value, b = n.value; + if (n.isSmall) + return subtractSmall(a, Math.abs(b), this.sign); + return subtractAny(a, b, this.sign); + }; + BigInteger.prototype.minus = BigInteger.prototype.subtract; + + SmallInteger.prototype.subtract = function (v) { + var n = parseValue(v); + var a = this.value; + if (a < 0 !== n.sign) { + return this.add(n.negate()); + } + var b = n.value; + if (n.isSmall) { + return new SmallInteger(a - b); + } + return subtractSmall(b, Math.abs(a), a >= 0); + }; + SmallInteger.prototype.minus = SmallInteger.prototype.subtract; + + BigInteger.prototype.negate = function () { + return new BigInteger(this.value, !this.sign); + }; + SmallInteger.prototype.negate = function () { + var sign = this.sign; + var small = new SmallInteger(-this.value); + small.sign = !sign; + return small; + }; + + BigInteger.prototype.abs = function () { + return new BigInteger(this.value, false); + }; + SmallInteger.prototype.abs = function () { + return new SmallInteger(Math.abs(this.value)); + }; + + function multiplyLong(a, b) { + var a_l = a.length, + b_l = b.length, + l = a_l + b_l, + r = createArray(l), + base = BASE, + product, carry, i, a_i, b_j; + for (i = 0; i < a_l; ++i) { + a_i = a[i]; + for (var j = 0; j < b_l; ++j) { + b_j = b[j]; + product = a_i * b_j + r[i + j]; + carry = Math.floor(product / base); + r[i + j] = product - carry * base; + r[i + j + 1] += carry; + } + } + trim(r); + return r; + } + + function multiplySmall(a, b) { // assumes a is array, b is number with |b| < BASE + var l = a.length, + r = new Array(l), + base = BASE, + carry = 0, + product, i; + for (i = 0; i < l; i++) { + product = a[i] * b + carry; + carry = Math.floor(product / base); + r[i] = product - carry * base; + } + while (carry > 0) { + r[i++] = carry % base; + carry = Math.floor(carry / base); + } + return r; + } + + function shiftLeft(x, n) { + var r = []; + while (n-- > 0) r.push(0); + return r.concat(x); + } + + function multiplyKaratsuba(x, y) { + var n = Math.max(x.length, y.length); + + if (n <= 30) return multiplyLong(x, y); + n = Math.ceil(n / 2); + + var b = x.slice(n), + a = x.slice(0, n), + d = y.slice(n), + c = y.slice(0, n); + + var ac = multiplyKaratsuba(a, c), + bd = multiplyKaratsuba(b, d), + abcd = multiplyKaratsuba(addAny(a, b), addAny(c, d)); + + var product = addAny(addAny(ac, shiftLeft(subtract(subtract(abcd, ac), bd), n)), shiftLeft(bd, 2 * n)); + trim(product); + return product; + } + + // The following function is derived from a surface fit of a graph plotting the performance difference + // between long multiplication and karatsuba multiplication versus the lengths of the two arrays. + function useKaratsuba(l1, l2) { + return -0.012 * l1 - 0.012 * l2 + 0.000015 * l1 * l2 > 0; + } + + BigInteger.prototype.multiply = function (v) { + var value, n = parseValue(v), + a = this.value, b = n.value, + sign = this.sign !== n.sign, + abs; + if (n.isSmall) { + if (b === 0) return Integer[0]; + if (b === 1) return this; + if (b === -1) return this.negate(); + abs = Math.abs(b); + if (abs < BASE) { + return new BigInteger(multiplySmall(a, abs), sign); + } + b = smallToArray(abs); + } + if (useKaratsuba(a.length, b.length)) // Karatsuba is only faster for certain array sizes + return new BigInteger(multiplyKaratsuba(a, b), sign); + return new BigInteger(multiplyLong(a, b), sign); + }; + + BigInteger.prototype.times = BigInteger.prototype.multiply; + + function multiplySmallAndArray(a, b, sign) { // a >= 0 + if (a < BASE) { + return new BigInteger(multiplySmall(b, a), sign); + } + return new BigInteger(multiplyLong(b, smallToArray(a)), sign); + } + SmallInteger.prototype._multiplyBySmall = function (a) { + if (isPrecise(a.value * this.value)) { + return new SmallInteger(a.value * this.value); + } + return multiplySmallAndArray(Math.abs(a.value), smallToArray(Math.abs(this.value)), this.sign !== a.sign); + }; + BigInteger.prototype._multiplyBySmall = function (a) { + if (a.value === 0) return Integer[0]; + if (a.value === 1) return this; + if (a.value === -1) return this.negate(); + return multiplySmallAndArray(Math.abs(a.value), this.value, this.sign !== a.sign); + }; + SmallInteger.prototype.multiply = function (v) { + return parseValue(v)._multiplyBySmall(this); + }; + SmallInteger.prototype.times = SmallInteger.prototype.multiply; + + function square(a) { + var l = a.length, + r = createArray(l + l), + base = BASE, + product, carry, i, a_i, a_j; + for (i = 0; i < l; i++) { + a_i = a[i]; + for (var j = 0; j < l; j++) { + a_j = a[j]; + product = a_i * a_j + r[i + j]; + carry = Math.floor(product / base); + r[i + j] = product - carry * base; + r[i + j + 1] += carry; + } + } + trim(r); + return r; + } + + BigInteger.prototype.square = function () { + return new BigInteger(square(this.value), false); + }; + + SmallInteger.prototype.square = function () { + var value = this.value * this.value; + if (isPrecise(value)) return new SmallInteger(value); + return new BigInteger(square(smallToArray(Math.abs(this.value))), false); + }; + + function divMod1(a, b) { // Left over from previous version. Performs faster than divMod2 on smaller input sizes. + var a_l = a.length, + b_l = b.length, + base = BASE, + result = createArray(b.length), + divisorMostSignificantDigit = b[b_l - 1], + // normalization + lambda = Math.ceil(base / (2 * divisorMostSignificantDigit)), + remainder = multiplySmall(a, lambda), + divisor = multiplySmall(b, lambda), + quotientDigit, shift, carry, borrow, i, l, q; + if (remainder.length <= a_l) remainder.push(0); + divisor.push(0); + divisorMostSignificantDigit = divisor[b_l - 1]; + for (shift = a_l - b_l; shift >= 0; shift--) { + quotientDigit = base - 1; + if (remainder[shift + b_l] !== divisorMostSignificantDigit) { + quotientDigit = Math.floor((remainder[shift + b_l] * base + remainder[shift + b_l - 1]) / divisorMostSignificantDigit); + } + // quotientDigit <= base - 1 + carry = 0; + borrow = 0; + l = divisor.length; + for (i = 0; i < l; i++) { + carry += quotientDigit * divisor[i]; + q = Math.floor(carry / base); + borrow += remainder[shift + i] - (carry - q * base); + carry = q; + if (borrow < 0) { + remainder[shift + i] = borrow + base; + borrow = -1; + } else { + remainder[shift + i] = borrow; + borrow = 0; + } + } + while (borrow !== 0) { + quotientDigit -= 1; + carry = 0; + for (i = 0; i < l; i++) { + carry += remainder[shift + i] - base + divisor[i]; + if (carry < 0) { + remainder[shift + i] = carry + base; + carry = 0; + } else { + remainder[shift + i] = carry; + carry = 1; + } + } + borrow += carry; + } + result[shift] = quotientDigit; + } + // denormalization + remainder = divModSmall(remainder, lambda)[0]; + return [arrayToSmall(result), arrayToSmall(remainder)]; + } + + function divMod2(a, b) { // Implementation idea shamelessly stolen from Silent Matt's library http://silentmatt.com/biginteger/ + // Performs faster than divMod1 on larger input sizes. + var a_l = a.length, + b_l = b.length, + result = [], + part = [], + base = BASE, + guess, xlen, highx, highy, check; + while (a_l) { + part.unshift(a[--a_l]); + if (compareAbs(part, b) < 0) { + result.push(0); + continue; + } + xlen = part.length; + highx = part[xlen - 1] * base + part[xlen - 2]; + highy = b[b_l - 1] * base + b[b_l - 2]; + if (xlen > b_l) { + highx = (highx + 1) * base; + } + guess = Math.ceil(highx / highy); + do { + check = multiplySmall(b, guess); + if (compareAbs(check, part) <= 0) break; + guess--; + } while (guess); + result.push(guess); + part = subtract(part, check); + } + result.reverse(); + return [arrayToSmall(result), arrayToSmall(part)]; + } + + function divModSmall(value, lambda) { + var length = value.length, + quotient = createArray(length), + base = BASE, + i, q, remainder, divisor; + remainder = 0; + for (i = length - 1; i >= 0; --i) { + divisor = remainder * base + value[i]; + q = truncate(divisor / lambda); + remainder = divisor - q * lambda; + quotient[i] = q | 0; + } + return [quotient, remainder | 0]; + } + + function divModAny(self, v) { + var value, n = parseValue(v); + var a = self.value, b = n.value; + var quotient; + if (b === 0) throw new Error("Cannot divide by zero"); + if (self.isSmall) { + if (n.isSmall) { + return [new SmallInteger(truncate(a / b)), new SmallInteger(a % b)]; + } + return [Integer[0], self]; + } + if (n.isSmall) { + if (b === 1) return [self, Integer[0]]; + if (b == -1) return [self.negate(), Integer[0]]; + var abs = Math.abs(b); + if (abs < BASE) { + value = divModSmall(a, abs); + quotient = arrayToSmall(value[0]); + var remainder = value[1]; + if (self.sign) remainder = -remainder; + if (typeof quotient === "number") { + if (self.sign !== n.sign) quotient = -quotient; + return [new SmallInteger(quotient), new SmallInteger(remainder)]; + } + return [new BigInteger(quotient, self.sign !== n.sign), new SmallInteger(remainder)]; + } + b = smallToArray(abs); + } + var comparison = compareAbs(a, b); + if (comparison === -1) return [Integer[0], self]; + if (comparison === 0) return [Integer[self.sign === n.sign ? 1 : -1], Integer[0]]; + + // divMod1 is faster on smaller input sizes + if (a.length + b.length <= 200) + value = divMod1(a, b); + else value = divMod2(a, b); + + quotient = value[0]; + var qSign = self.sign !== n.sign, + mod = value[1], + mSign = self.sign; + if (typeof quotient === "number") { + if (qSign) quotient = -quotient; + quotient = new SmallInteger(quotient); + } else quotient = new BigInteger(quotient, qSign); + if (typeof mod === "number") { + if (mSign) mod = -mod; + mod = new SmallInteger(mod); + } else mod = new BigInteger(mod, mSign); + return [quotient, mod]; + } + + BigInteger.prototype.divmod = function (v) { + var result = divModAny(this, v); + return { + quotient: result[0], + remainder: result[1] + }; + }; + SmallInteger.prototype.divmod = BigInteger.prototype.divmod; + + BigInteger.prototype.divide = function (v) { + return divModAny(this, v)[0]; + }; + SmallInteger.prototype.over = SmallInteger.prototype.divide = BigInteger.prototype.over = BigInteger.prototype.divide; + + BigInteger.prototype.mod = function (v) { + return divModAny(this, v)[1]; + }; + SmallInteger.prototype.remainder = SmallInteger.prototype.mod = BigInteger.prototype.remainder = BigInteger.prototype.mod; + + BigInteger.prototype.pow = function (v) { + var n = parseValue(v), + a = this.value, + b = n.value, + value, x, y; + if (b === 0) return Integer[1]; + if (a === 0) return Integer[0]; + if (a === 1) return Integer[1]; + if (a === -1) return n.isEven() ? Integer[1] : Integer[-1]; + if (n.sign) { + return Integer[0]; + } + if (!n.isSmall) throw new Error("The exponent " + n.toString() + " is too large."); + if (this.isSmall) { + if (isPrecise(value = Math.pow(a, b))) + return new SmallInteger(truncate(value)); + } + x = this; + y = Integer[1]; + while (true) { + if (b & 1 === 1) { + y = y.times(x); + --b; + } + if (b === 0) break; + b /= 2; + x = x.square(); + } + return y; + }; + SmallInteger.prototype.pow = BigInteger.prototype.pow; + + BigInteger.prototype.modPow = function (exp, mod) { + exp = parseValue(exp); + mod = parseValue(mod); + if (mod.isZero()) throw new Error("Cannot take modPow with modulus 0"); + var r = Integer[1], + base = this.mod(mod); + while (exp.isPositive()) { + if (base.isZero()) return Integer[0]; + if (exp.isOdd()) r = r.multiply(base).mod(mod); + exp = exp.divide(2); + base = base.square().mod(mod); + } + return r; + }; + SmallInteger.prototype.modPow = BigInteger.prototype.modPow; + + function compareAbs(a, b) { + if (a.length !== b.length) { + return a.length > b.length ? 1 : -1; + } + for (var i = a.length - 1; i >= 0; i--) { + if (a[i] !== b[i]) return a[i] > b[i] ? 1 : -1; + } + return 0; + } + + BigInteger.prototype.compareAbs = function (v) { + var n = parseValue(v), + a = this.value, + b = n.value; + if (n.isSmall) return 1; + return compareAbs(a, b); + }; + SmallInteger.prototype.compareAbs = function (v) { + var n = parseValue(v), + a = Math.abs(this.value), + b = n.value; + if (n.isSmall) { + b = Math.abs(b); + return a === b ? 0 : a > b ? 1 : -1; + } + return -1; + }; + + BigInteger.prototype.compare = function (v) { + // See discussion about comparison with Infinity: + // https://github.com/peterolson/BigInteger.js/issues/61 + if (v === Infinity) { + return -1; + } + if (v === -Infinity) { + return 1; + } + + var n = parseValue(v), + a = this.value, + b = n.value; + if (this.sign !== n.sign) { + return n.sign ? 1 : -1; + } + if (n.isSmall) { + return this.sign ? -1 : 1; + } + return compareAbs(a, b) * (this.sign ? -1 : 1); + }; + BigInteger.prototype.compareTo = BigInteger.prototype.compare; + + SmallInteger.prototype.compare = function (v) { + if (v === Infinity) { + return -1; + } + if (v === -Infinity) { + return 1; + } + + var n = parseValue(v), + a = this.value, + b = n.value; + if (n.isSmall) { + return a == b ? 0 : a > b ? 1 : -1; + } + if (a < 0 !== n.sign) { + return a < 0 ? -1 : 1; + } + return a < 0 ? 1 : -1; + }; + SmallInteger.prototype.compareTo = SmallInteger.prototype.compare; + + BigInteger.prototype.equals = function (v) { + return this.compare(v) === 0; + }; + SmallInteger.prototype.eq = SmallInteger.prototype.equals = BigInteger.prototype.eq = BigInteger.prototype.equals; + + BigInteger.prototype.notEquals = function (v) { + return this.compare(v) !== 0; + }; + SmallInteger.prototype.neq = SmallInteger.prototype.notEquals = BigInteger.prototype.neq = BigInteger.prototype.notEquals; + + BigInteger.prototype.greater = function (v) { + return this.compare(v) > 0; + }; + SmallInteger.prototype.gt = SmallInteger.prototype.greater = BigInteger.prototype.gt = BigInteger.prototype.greater; + + BigInteger.prototype.lesser = function (v) { + return this.compare(v) < 0; + }; + SmallInteger.prototype.lt = SmallInteger.prototype.lesser = BigInteger.prototype.lt = BigInteger.prototype.lesser; + + BigInteger.prototype.greaterOrEquals = function (v) { + return this.compare(v) >= 0; + }; + SmallInteger.prototype.geq = SmallInteger.prototype.greaterOrEquals = BigInteger.prototype.geq = BigInteger.prototype.greaterOrEquals; + + BigInteger.prototype.lesserOrEquals = function (v) { + return this.compare(v) <= 0; + }; + SmallInteger.prototype.leq = SmallInteger.prototype.lesserOrEquals = BigInteger.prototype.leq = BigInteger.prototype.lesserOrEquals; + + BigInteger.prototype.isEven = function () { + return (this.value[0] & 1) === 0; + }; + SmallInteger.prototype.isEven = function () { + return (this.value & 1) === 0; + }; + + BigInteger.prototype.isOdd = function () { + return (this.value[0] & 1) === 1; + }; + SmallInteger.prototype.isOdd = function () { + return (this.value & 1) === 1; + }; + + BigInteger.prototype.isPositive = function () { + return !this.sign; + }; + SmallInteger.prototype.isPositive = function () { + return this.value > 0; + }; + + BigInteger.prototype.isNegative = function () { + return this.sign; + }; + SmallInteger.prototype.isNegative = function () { + return this.value < 0; + }; + + BigInteger.prototype.isUnit = function () { + return false; + }; + SmallInteger.prototype.isUnit = function () { + return Math.abs(this.value) === 1; + }; + + BigInteger.prototype.isZero = function () { + return false; + }; + SmallInteger.prototype.isZero = function () { + return this.value === 0; + }; + BigInteger.prototype.isDivisibleBy = function (v) { + var n = parseValue(v); + var value = n.value; + if (value === 0) return false; + if (value === 1) return true; + if (value === 2) return this.isEven(); + return this.mod(n).equals(Integer[0]); + }; + SmallInteger.prototype.isDivisibleBy = BigInteger.prototype.isDivisibleBy; + + function isBasicPrime(v) { + var n = v.abs(); + if (n.isUnit()) return false; + if (n.equals(2) || n.equals(3) || n.equals(5)) return true; + if (n.isEven() || n.isDivisibleBy(3) || n.isDivisibleBy(5)) return false; + if (n.lesser(25)) return true; + // we don't know if it's prime: let the other functions figure it out + } + + BigInteger.prototype.isPrime = function () { + var isPrime = isBasicPrime(this); + if (isPrime !== undefined) return isPrime; + var n = this.abs(), + nPrev = n.prev(); + var a = [2, 3, 5, 7, 11, 13, 17, 19], + b = nPrev, + d, t, i, x; + while (b.isEven()) b = b.divide(2); + for (i = 0; i < a.length; i++) { + x = bigInt(a[i]).modPow(b, n); + if (x.equals(Integer[1]) || x.equals(nPrev)) continue; + for (t = true, d = b; t && d.lesser(nPrev) ; d = d.multiply(2)) { + x = x.square().mod(n); + if (x.equals(nPrev)) t = false; + } + if (t) return false; + } + return true; + }; + SmallInteger.prototype.isPrime = BigInteger.prototype.isPrime; + + BigInteger.prototype.isProbablePrime = function (iterations) { + var isPrime = isBasicPrime(this); + if (isPrime !== undefined) return isPrime; + var n = this.abs(); + var t = iterations === undefined ? 5 : iterations; + // use the Fermat primality test + for (var i = 0; i < t; i++) { + var a = bigInt.randBetween(2, n.minus(2)); + if (!a.modPow(n.prev(), n).isUnit()) return false; // definitely composite + } + return true; // large chance of being prime + }; + SmallInteger.prototype.isProbablePrime = BigInteger.prototype.isProbablePrime; + + BigInteger.prototype.next = function () { + var value = this.value; + if (this.sign) { + return subtractSmall(value, 1, this.sign); + } + return new BigInteger(addSmall(value, 1), this.sign); + }; + SmallInteger.prototype.next = function () { + var value = this.value; + if (value + 1 < MAX_INT) return new SmallInteger(value + 1); + return new BigInteger(MAX_INT_ARR, false); + }; + + BigInteger.prototype.prev = function () { + var value = this.value; + if (this.sign) { + return new BigInteger(addSmall(value, 1), true); + } + return subtractSmall(value, 1, this.sign); + }; + SmallInteger.prototype.prev = function () { + var value = this.value; + if (value - 1 > -MAX_INT) return new SmallInteger(value - 1); + return new BigInteger(MAX_INT_ARR, true); + }; + + var powersOfTwo = [1]; + while (powersOfTwo[powersOfTwo.length - 1] <= BASE) powersOfTwo.push(2 * powersOfTwo[powersOfTwo.length - 1]); + var powers2Length = powersOfTwo.length, highestPower2 = powersOfTwo[powers2Length - 1]; + + function shift_isSmall(n) { + return ((typeof n === "number" || typeof n === "string") && +Math.abs(n) <= BASE) || + (n instanceof BigInteger && n.value.length <= 1); + } + + BigInteger.prototype.shiftLeft = function (n) { + if (!shift_isSmall(n)) { + throw new Error(String(n) + " is too large for shifting."); + } + n = +n; + if (n < 0) return this.shiftRight(-n); + var result = this; + while (n >= powers2Length) { + result = result.multiply(highestPower2); + n -= powers2Length - 1; + } + return result.multiply(powersOfTwo[n]); + }; + SmallInteger.prototype.shiftLeft = BigInteger.prototype.shiftLeft; + + BigInteger.prototype.shiftRight = function (n) { + var remQuo; + if (!shift_isSmall(n)) { + throw new Error(String(n) + " is too large for shifting."); + } + n = +n; + if (n < 0) return this.shiftLeft(-n); + var result = this; + while (n >= powers2Length) { + if (result.isZero()) return result; + remQuo = divModAny(result, highestPower2); + result = remQuo[1].isNegative() ? remQuo[0].prev() : remQuo[0]; + n -= powers2Length - 1; + } + remQuo = divModAny(result, powersOfTwo[n]); + return remQuo[1].isNegative() ? remQuo[0].prev() : remQuo[0]; + }; + SmallInteger.prototype.shiftRight = BigInteger.prototype.shiftRight; + + function bitwise(x, y, fn) { + y = parseValue(y); + var xSign = x.isNegative(), ySign = y.isNegative(); + var xRem = xSign ? x.not() : x, + yRem = ySign ? y.not() : y; + var xBits = [], yBits = []; + var xStop = false, yStop = false; + while (!xStop || !yStop) { + if (xRem.isZero()) { // virtual sign extension for simulating two's complement + xStop = true; + xBits.push(xSign ? 1 : 0); + } + else if (xSign) xBits.push(xRem.isEven() ? 1 : 0); // two's complement for negative numbers + else xBits.push(xRem.isEven() ? 0 : 1); + + if (yRem.isZero()) { + yStop = true; + yBits.push(ySign ? 1 : 0); + } + else if (ySign) yBits.push(yRem.isEven() ? 1 : 0); + else yBits.push(yRem.isEven() ? 0 : 1); + + xRem = xRem.over(2); + yRem = yRem.over(2); + } + var result = []; + for (var i = 0; i < xBits.length; i++) result.push(fn(xBits[i], yBits[i])); + var sum = bigInt(result.pop()).negate().times(bigInt(2).pow(result.length)); + while (result.length) { + sum = sum.add(bigInt(result.pop()).times(bigInt(2).pow(result.length))); + } + return sum; + } + + BigInteger.prototype.not = function () { + return this.negate().prev(); + }; + SmallInteger.prototype.not = BigInteger.prototype.not; + + BigInteger.prototype.and = function (n) { + return bitwise(this, n, function (a, b) { return a & b; }); + }; + SmallInteger.prototype.and = BigInteger.prototype.and; + + BigInteger.prototype.or = function (n) { + return bitwise(this, n, function (a, b) { return a | b; }); + }; + SmallInteger.prototype.or = BigInteger.prototype.or; + + BigInteger.prototype.xor = function (n) { + return bitwise(this, n, function (a, b) { return a ^ b; }); + }; + SmallInteger.prototype.xor = BigInteger.prototype.xor; + + var LOBMASK_I = 1 << 30, LOBMASK_BI = (BASE & -BASE) * (BASE & -BASE) | LOBMASK_I; + function roughLOB(n) { // get lowestOneBit (rough) + // SmallInteger: return Min(lowestOneBit(n), 1 << 30) + // BigInteger: return Min(lowestOneBit(n), 1 << 14) [BASE=1e7] + var v = n.value, x = typeof v === "number" ? v | LOBMASK_I : v[0] + v[1] * BASE | LOBMASK_BI; + return x & -x; + } + + function max(a, b) { + a = parseValue(a); + b = parseValue(b); + return a.greater(b) ? a : b; + } + function min(a,b) { + a = parseValue(a); + b = parseValue(b); + return a.lesser(b) ? a : b; + } + function gcd(a, b) { + a = parseValue(a).abs(); + b = parseValue(b).abs(); + if (a.equals(b)) return a; + if (a.isZero()) return b; + if (b.isZero()) return a; + var c = Integer[1], d, t; + while (a.isEven() && b.isEven()) { + d = Math.min(roughLOB(a), roughLOB(b)); + a = a.divide(d); + b = b.divide(d); + c = c.multiply(d); + } + while (a.isEven()) { + a = a.divide(roughLOB(a)); + } + do { + while (b.isEven()) { + b = b.divide(roughLOB(b)); + } + if (a.greater(b)) { + t = b; b = a; a = t; + } + b = b.subtract(a); + } while (!b.isZero()); + return c.isUnit() ? a : a.multiply(c); + } + function lcm(a, b) { + a = parseValue(a).abs(); + b = parseValue(b).abs(); + return a.divide(gcd(a, b)).multiply(b); + } + function randBetween(a, b) { + a = parseValue(a); + b = parseValue(b); + var low = min(a, b), high = max(a, b); + var range = high.subtract(low); + if (range.isSmall) return low.add(Math.round(Math.random() * range)); + var length = range.value.length - 1; + var result = [], restricted = true; + for (var i = length; i >= 0; i--) { + var top = restricted ? range.value[i] : BASE; + var digit = truncate(Math.random() * top); + result.unshift(digit); + if (digit < top) restricted = false; + } + result = arrayToSmall(result); + return low.add(typeof result === "number" ? new SmallInteger(result) : new BigInteger(result, false)); + } + var parseBase = function (text, base) { + var val = Integer[0], pow = Integer[1], + length = text.length; + if (2 <= base && base <= 36) { + if (length <= LOG_MAX_INT / Math.log(base)) { + return new SmallInteger(parseInt(text, base)); + } + } + base = parseValue(base); + var digits = []; + var i; + var isNegative = text[0] === "-"; + for (i = isNegative ? 1 : 0; i < text.length; i++) { + var c = text[i].toLowerCase(), + charCode = c.charCodeAt(0); + if (48 <= charCode && charCode <= 57) digits.push(parseValue(c)); + else if (97 <= charCode && charCode <= 122) digits.push(parseValue(c.charCodeAt(0) - 87)); + else if (c === "<") { + var start = i; + do { i++; } while (text[i] !== ">"); + digits.push(parseValue(text.slice(start + 1, i))); + } + else throw new Error(c + " is not a valid character"); + } + digits.reverse(); + for (i = 0; i < digits.length; i++) { + val = val.add(digits[i].times(pow)); + pow = pow.times(base); + } + return isNegative ? val.negate() : val; + }; + + function stringify(digit) { + var v = digit.value; + if (typeof v === "number") v = [v]; + if (v.length === 1 && v[0] <= 35) { + return "0123456789abcdefghijklmnopqrstuvwxyz".charAt(v[0]); + } + return "<" + v + ">"; + } + function toBase(n, base) { + base = bigInt(base); + if (base.isZero()) { + if (n.isZero()) return "0"; + throw new Error("Cannot convert nonzero numbers to base 0."); + } + if (base.equals(-1)) { + if (n.isZero()) return "0"; + if (n.isNegative()) return new Array(1 - n).join("10"); + return "1" + new Array(+n).join("01"); + } + var minusSign = ""; + if (n.isNegative() && base.isPositive()) { + minusSign = "-"; + n = n.abs(); + } + if (base.equals(1)) { + if (n.isZero()) return "0"; + return minusSign + new Array(+n + 1).join(1); + } + var out = []; + var left = n, divmod; + while (left.isNegative() || left.compareAbs(base) >= 0) { + divmod = left.divmod(base); + left = divmod.quotient; + var digit = divmod.remainder; + if (digit.isNegative()) { + digit = base.minus(digit).abs(); + left = left.next(); + } + out.push(stringify(digit)); + } + out.push(stringify(left)); + return minusSign + out.reverse().join(""); + } + + BigInteger.prototype.toString = function (radix) { + if (radix === undefined) radix = 10; + if (radix !== 10) return toBase(this, radix); + var v = this.value, l = v.length, str = String(v[--l]), zeros = "0000000", digit; + while (--l >= 0) { + digit = String(v[l]); + str += zeros.slice(digit.length) + digit; + } + var sign = this.sign ? "-" : ""; + return sign + str; + }; + SmallInteger.prototype.toString = function (radix) { + if (radix === undefined) radix = 10; + if (radix != 10) return toBase(this, radix); + return String(this.value); + }; + + BigInteger.prototype.valueOf = function () { + return +this.toString(); + }; + BigInteger.prototype.toJSNumber = BigInteger.prototype.valueOf; + + SmallInteger.prototype.valueOf = function () { + return this.value; + }; + SmallInteger.prototype.toJSNumber = SmallInteger.prototype.valueOf; + + function parseStringValue(v) { + if (isPrecise(+v)) { + var x = +v; + if (x === truncate(x)) + return new SmallInteger(x); + throw "Invalid integer: " + v; + } + var sign = v[0] === "-"; + if (sign) v = v.slice(1); + var split = v.split(/e/i); + if (split.length > 2) throw new Error("Invalid integer: " + split.join("e")); + if (split.length === 2) { + var exp = split[1]; + if (exp[0] === "+") exp = exp.slice(1); + exp = +exp; + if (exp !== truncate(exp) || !isPrecise(exp)) throw new Error("Invalid integer: " + exp + " is not a valid exponent."); + var text = split[0]; + var decimalPlace = text.indexOf("."); + if (decimalPlace >= 0) { + exp -= text.length - decimalPlace - 1; + text = text.slice(0, decimalPlace) + text.slice(decimalPlace + 1); + } + if (exp < 0) throw new Error("Cannot include negative exponent part for integers"); + text += (new Array(exp + 1)).join("0"); + v = text; + } + var isValid = /^([0-9][0-9]*)$/.test(v); + if (!isValid) throw new Error("Invalid integer: " + v); + var r = [], max = v.length, l = LOG_BASE, min = max - l; + while (max > 0) { + r.push(+v.slice(min, max)); + min -= l; + if (min < 0) min = 0; + max -= l; + } + trim(r); + return new BigInteger(r, sign); + } + + function parseNumberValue(v) { + if (isPrecise(v)) { + if (v !== truncate(v)) throw new Error(v + " is not an integer."); + return new SmallInteger(v); + } + return parseStringValue(v.toString()); + } + + function parseValue(v) { + if (typeof v === "number") { + return parseNumberValue(v); + } + if (typeof v === "string") { + return parseStringValue(v); + } + return v; + } + // Pre-define numbers in range [-999,999] + for (var i = 0; i < 1000; i++) { + Integer[i] = new SmallInteger(i); + if (i > 0) Integer[-i] = new SmallInteger(-i); + } + // Backwards compatibility + Integer.one = Integer[1]; + Integer.zero = Integer[0]; + Integer.minusOne = Integer[-1]; + Integer.max = max; + Integer.min = min; + Integer.gcd = gcd; + Integer.lcm = lcm; + Integer.isInstance = function (x) { return x instanceof BigInteger || x instanceof SmallInteger; }; + Integer.randBetween = randBetween; + return Integer; +})(); + +// Node.js check +if (typeof module !== "undefined" && module.hasOwnProperty("exports")) { + module.exports = bigInt; +} --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
