code:
self.Flatted = (function (exports) {
  'use strict';

  function _typeof(o) {
    "@babel/helpers - typeof";

    return _typeof = "function" == typeof Symbol && "symbol" == typeof Symbol.iterator ? function (o) {
      return typeof o;
    } : function (o) {
      return o && "function" == typeof Symbol && o.constructor === Symbol && o !== Symbol.prototype ? "symbol" : typeof o;
    }, _typeof(o);
  }

  /// <reference types="../types/index.d.ts" />

  // (c) 2020-present Andrea Giammarchi

  var $parse = JSON.parse,
    $stringify = JSON.stringify;
  var keys = Object.keys;
  var Primitive = String; // it could be Number
  var primitive = 'string'; // it could be 'number'

  var ignore = {};
  var object = 'object';
  var noop = function noop(_, value) {
    return value;
  };
  var primitives = function primitives(value) {
    return value instanceof Primitive ? Primitive(value) : value;
  };
  var Primitives = function Primitives(_, value) {
    return _typeof(value) === primitive ? new Primitive(value) : value;
  };
  var revive = function revive(input, parsed, output, $) {
    var lazy = [];
    for (var ke = keys(output), length = ke.length, y = 0; y < length; y++) {
      var k = ke[y];
      var value = output[k];
      if (value instanceof Primitive) {
        var tmp = input[value];
        if (_typeof(tmp) === object && !parsed.has(tmp)) {
          parsed.add(tmp);
          output[k] = ignore;
          lazy.push({
            k: k,
            a: [input, parsed, tmp, $]
          });
        } else output[k] = $.call(output, k, tmp);
      } else if (output[k] !== ignore) output[k] = $.call(output, k, value);
    }
    for (var _length = lazy.length, i = 0; i < _length; i++) {
      var _lazy$i = lazy[i],
        _k = _lazy$i.k,
        a = _lazy$i.a;
      output[_k] = $.call(output, _k, revive.apply(null, a));
    }
    return output;
  };
  var set = function set(known, input, value) {
    var index = Primitive(input.push(value) - 1);
    known.set(value, index);
    return index;
  };

  /**
   * Converts a specialized flatted string into a JS value.
   * @param {string} text
   * @param {((this: any, key: string, value: any) => any) | undefined): any} [reviver]
   * @returns {any}
   */
  var parse = function parse(text, reviver) {
    var input = $parse(text, Primitives).map(primitives);
    var value = input[0];
    var $ = reviver || noop;
    var tmp = _typeof(value) === object && value ? revive(input, new Set(), value, $) : value;
    return $.call({
      '': tmp
    }, '', tmp);
  };

  /**
   * Converts a JS value into a specialized flatted string.
   * @param {any} value
   * @param {((this: any, key: string, value: any) => any) | (string | number)[] | null | undefined} [replacer]
   * @param {string | number | undefined} [space]
   * @returns {string}
   */
  var stringify = function stringify(value, replacer, space) {
    var $ = replacer && _typeof(replacer) === object ? function (k, v) {
      return k === '' || -1 < replacer.indexOf(k) ? v : void 0;
    } : replacer || noop;
    var known = new Map();
    var input = [];
    var output = [];
    var i = +set(known, input, $.call({
      '': value
    }, '', value));
    var firstRun = !i;
    while (i < input.length) {
      firstRun = true;
      output[i] = $stringify(input[i++], replace, space);
    }
    return '[' + output.join(',') + ']';
    function replace(key, value) {
      if (firstRun) {
        firstRun = !firstRun;
        return value;
      }
      var after = $.call(this, key, value);
      switch (_typeof(after)) {
        case object:
          if (after === null) return after;
        case primitive:
          return known.get(after) || set(known, input, after);
      }
      return after;
    }
  };

  /**
   * Converts a generic value into a JSON serializable object without losing recursion.
   * @param {any} value
   * @returns {any}
   */
  var toJSON = function toJSON(value) {
    return $parse(stringify(value));
  };

  /**
   * Converts a previously serialized object with recursion into a recursive one.
   * @param {any} value
   * @returns {any}
   */
  var fromJSON = function fromJSON(value) {
    return parse($stringify(value));
  };

  exports.fromJSON = fromJSON;
  exports.parse = parse;
  exports.stringify = stringify;
  exports.toJSON = toJSON;

  return exports;

})({});


flatted

description: A super light and fast circular JSON parser.

build: npm run cjs && npm run rollup:esm && npm run rollup:es && npm run rollup:babel && npm run min && npm run test && npm run size

cjs: ascjs esm cjs

rollup:es: rollup --config rollup/es.config.js && sed -i.bck 's/^var /self./' es.js && rm -rf es.js.bck

rollup:esm: rollup --config rollup/esm.config.js

rollup:babel: rollup --config rollup/babel.config.js && sed -i.bck 's/^var /self./' index.js && rm -rf index.js.bck

min: terser index.js -c -m -o min.js

size: cat index.js | wc -c;cat min.js | wc -c;gzip -c9 min.js | wc -c;cat min.js | brotli | wc -c; cat es.js | brotli | wc -c; cat esm.js | brotli | wc -c

test: c8 node test/index.js

test:php: php php/test.php

test:py: python python/test.py

ts: tsc -p .

coverage: mkdir -p ./coverage; c8 report --reporter=text-lcov > ./coverage/lcov.info

type: git

keywords: circular JSON fast parser minimal

author: Andrea Giammarchi

license: ISC

type: module

license: mit


code:
<?php

/*!
 * ISC License
 *
 * Copyright (c) 2018-2021, Andrea Giammarchi, @WebReflection
 *
 * Permission to use, copy, modify, and/or distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH
 * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
 * AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT,
 * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
 * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
 * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
 * PERFORMANCE OF THIS SOFTWARE.
 */

class FlattedString {
  public $value = '';
  public function __construct($value) {
    $this->value = $value;
  }
}

class Flatted {

  // public utilities
  public static function parse($json, $assoc = false, $depth = 512, $options = 0) {
    $input = array_map(
      'Flatted::asString',
      array_map(
        'Flatted::wrap',
        json_decode($json, $assoc, $depth, $options)
      )
    );
    $value = &$input[0];
    $set = array();
    $set[] = &$value;
    if (is_array($value))
      return Flatted::loop(false, array_keys($value), $input, $set, $value);
    if (is_object($value))
      return Flatted::loop(true, Flatted::keys($value), $input, $set, $value);
    return $value;
  }

  public static function stringify($value, $options = 0, $depth = 512) {
    $known = new stdClass;
    $known->key = array();
    $known->value = array();
    $input = array();
    $output = array();
    $i = intval(Flatted::index($known, $input, $value));
    while ($i < count($input)) {
      $output[$i] = Flatted::transform($known, $input, $input[$i]);
      $i++;
    }
    return json_encode($output, $options, $depth);
  }

  // private helpers
  private static function asString($value) {
    return $value instanceof FlattedString ? $value->value : $value;
  }

  private static function index(&$known, &$input, &$value) {
    $input[] = &$value;
    $index = strval(count($input) - 1);
    $known->key[] = &$value;
    $known->value[] = &$index;
    return $index;
  }

  private static function keys(&$value) {
    $obj = new ReflectionObject($value);
    $props = $obj->getProperties();
    $keys = array();
    foreach ($props as $prop)
      $keys[] = $prop->getName();
    return $keys;
  }

  private static function loop($obj, $keys, &$input, &$set, &$output) {
    foreach ($keys as $key) {
      $value = $obj ? $output->$key : $output[$key];
      if ($value instanceof FlattedString)
        Flatted::ref($obj, $key, $input[$value->value], $input, $set, $output);
    }
    return $output;
  }

  private static function relate(&$known, &$input, &$value) {
    if (is_string($value) || is_array($value) || is_object($value)) {
      $key = array_search($value, $known->key, true);
      if ($key !== false)
        return $known->value[$key];
      return Flatted::index($known, $input, $value);
    }
    return $value;
  }

  private static function ref($obj, &$key, &$value, &$input, &$set, &$output) {
    if (is_array($value) && !in_array($value, $set, true)) {
      $set[] = $value;
      $value = Flatted::loop(false, array_keys($value), $input, $set, $value);
    }
    elseif (is_object($value) && !in_array($value, $set, true)) {
      $set[] = $value;
      $value = Flatted::loop(true, Flatted::keys($value), $input, $set, $value);
    }
    if ($obj) {
      $output->$key = &$value;
    }
    else {
      $output[$key] = &$value;
    }
  }

  private static function transform(&$known, &$input, &$value) {
    if (is_array($value)) {
      return array_map(
        function ($value) use(&$known, &$input) {
          return Flatted::relate($known, $input, $value);
        },
        $value
      );
    }
    if (is_object($value)) {
      $object = new stdClass;
      $keys = Flatted::keys($value);
      foreach ($keys as $key)
        $object->$key = Flatted::relate($known, $input, $value->$key);
      return $object;
    }
    return $value;
  }

  private static function wrap($value) {
    if (is_string($value)) {
      return new FlattedString($value);
    }
    if (is_array($value)) {
      return array_map('Flatted::wrap', $value);
    }
    if (is_object($value)) {
      $keys = Flatted::keys($value);
      foreach ($keys as $key) {
        $value->$key = self::wrap($value->$key);
      }
    }
    return $value;
  }
}
?>


code:
# ISC License
#
# Copyright (c) 2018-2021, Andrea Giammarchi, @WebReflection
#
# Permission to use, copy, modify, and/or distribute this software for any
# purpose with or without fee is hereby granted, provided that the above
# copyright notice and this permission notice appear in all copies.
#
# THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH
# REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
# AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT,
# INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
# LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
# OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
# PERFORMANCE OF THIS SOFTWARE.

import json as _json

class _Known:
    def __init__(self):
        self.key = []
        self.value = []

class _String:
    def __init__(self, value):
        self.value = value

def _array_keys(value):
    keys = []
    i = 0
    for _ in value:
        keys.append(i)
        i += 1
    return keys

def _object_keys(value):
    keys = []
    for key in value:
        keys.append(key)
    return keys

def _is_array(value):
    return isinstance(value, list) or isinstance(value, tuple)

def _is_object(value):
    return isinstance(value, dict)

def _is_string(value):
    return isinstance(value, str)

def _index(known, input, value):
    input.append(value)
    index = str(len(input) - 1)
    known.key.append(value)
    known.value.append(index)
    return index

def _loop(keys, input, known, output):
    for key in keys:
        value = output[key]
        if isinstance(value, _String):
            _ref(key, input[int(value.value)], input, known, output)

    return output

def _ref(key, value, input, known, output):
    if _is_array(value) and not value in known:
        known.append(value)
        value = _loop(_array_keys(value), input, known, value)
    elif _is_object(value) and not value in known:
        known.append(value)
        value = _loop(_object_keys(value), input, known, value)

    output[key] = value

def _relate(known, input, value):
    if _is_string(value) or _is_array(value) or _is_object(value):
        try:
            return known.value[known.key.index(value)]
        except:
            return _index(known, input, value)

    return value

def _transform(known, input, value):
    if _is_array(value):
        output = []
        for val in value:
            output.append(_relate(known, input, val))
        return output

    if _is_object(value):
        obj = {}
        for key in value:
            obj[key] = _relate(known, input, value[key])
        return obj

    return value

def _wrap(value):
    if _is_string(value):
        return _String(value)

    if _is_array(value):
        i = 0
        for val in value:
            value[i] = _wrap(val)
            i += 1

    elif _is_object(value):
        for key in value:
            value[key] = _wrap(value[key])

    return value

def parse(value, *args, **kwargs):
    json = _json.loads(value, *args, **kwargs)
    wrapped = []
    for value in json:
        wrapped.append(_wrap(value))

    input = []
    for value in wrapped:
        if isinstance(value, _String):
            input.append(value.value)
        else:
            input.append(value)

    value = input[0]

    if _is_array(value):
        return _loop(_array_keys(value), input, [value], value)

    if _is_object(value):
        return _loop(_object_keys(value), input, [value], value)

    return value

def stringify(value, *args, **kwargs):
    known = _Known()
    input = []
    output = []
    i = int(_index(known, input, value))
    while i < len(input):
        output.append(_transform(known, input, input[i]))
        i += 1
    return _json.dumps(output, *args, **kwargs)


code:
export function parse(text: string, reviver?: (this: any, key: string, value: any) => any): any;
export function stringify(value: any, replacer?: (string | number)[] | ((this: any, key: string, value: any) => any), space?: string | number | undefined): string;
export function toJSON(value: any): any;
export function fromJSON(value: any): any;


code:
# FlushWritable
A Writable stream that flushes before emitting finish.

##ChangeLog

### v1.0.0
- **Initial Public Release**


code:
# FlushWritable [![Build Status](https://travis-ci.org/TomFrost/FlushWritable.svg?branch=master)](https://travis-ci.org/TomFrost/FlushWritable)
A Writable stream that flushes before emitting finish.

Sponsored by [Leadnomics](http://www.leadnomics.com).

## What it is
Node.js's Streams API is a fantastic tool, but has a nagging shortcoming:
while the Transform stream implements a `_flush` method that is called before
its final events are fired, the Writable stream does not.  So if you're
buffering rows to be INSERTed into a SQL table rather than slowly writing one
at a time, or you're buffering bytes for a transfer to S3, there is no way of
flushing those buffers to the target data store before the `finish` event is
emitted.

**FlushWritable is a drop-in replacement for stream.Writable** that implements
a `_flush` call that behaves exactly how Transform._flush does.  It's called
with a callback, waits for the callback to be called, and _then_ fires
`finish` (or `error` if an error was passed).  No additional execution after
the `finish` event, no implementing nonstandard event types, no chaining a
shell Transform stream before the Writable to hijack its `_flush` call.  And
it's fully futureproof against the Node.js team actually adding a `_flush`
method to the native stream.Writable in a later version of Node, so you don't
have to worry about your code breaking on upgrade.

## How does it work?
It's pretty simple.  Writable is an EventEmitter.  FlushWritable extends
Writable and overrides EventEmitter.emit in its own prototype, listening for a
request that `finish` be emitted.  When that comes in, it blocks that event
from emitting, and calls `_flush` if it's defined.

The callback it passes to `_flush` will trigger `finish` to actually be
emitted.  If that callback is called with a truthy first argument, `error` is
emitted instead.  All other events pass right through and are emitted as
expected.  If a future version of node adds a `Writable.prototype._flush`
method, the whole thing short-circuits and native functionality takes over.

## Installation
In your project folder, type:

	npm install flushwritable --save

## Usage
Just extend FlushWritable instead of stream.Writable in your write stream, and
feel free to define a `_flush(cb)` function!

```javascript
var FlushWritable = require('flushwritable'),
    util = require('util');

function MyWriteStream(opts) {
    FlushWritable.call(this, opts);
    this._buffer = [];
}
util.inherits(MyWriteStream, FlushWritable);

MyWriteStream.prototype._flush = function(cb) {
	writeBufferSomewhere(this._buffer, cb);
};

MyWriteStream.prototype._write = function(data, encoding, cb) {
	this._buffer.push(data);
	cb();
};
```

## License
FlushWritable is distributed under the MIT license.

## Credits
FlushWritable was created by Tom Frost at Leadnomics in 2014.


code:
/*
 * FlushWritable
 * Copyright 2014 Tom Frost
 */

var EventEmitter = require('events').EventEmitter,
	Writable = require('stream').Writable,
	util = require('util');

/**
 * FlushWritable is a drop-in replacement for stream.Writable that implements
 * the Transform stream's _flush() method.  FlushWritable is meant to be
 * extended, just like stream.Writable.  However, in the child class's
 * prototype, a method called _flush(cb) can be defined that will halt the
 * firing of the 'finish' event until the callback is called.  If the callback
 * if called with a truthy first argument, 'error' is emitted instead.
 * @param {Object} [opts] Options to configure this Writable stream.  See the
 *      Node.js docs for stream.Writable.
 * @constructor
 */
function FlushWritable(opts) {
	Writable.call(this, opts);
}
util.inherits(FlushWritable, Writable);

FlushWritable.prototype.emit = function(evt) {
	if (evt === 'finish' && this._flush && !Writable.prototype._flush) {
		this._flush(function(err) {
			if (err)
				EventEmitter.prototype.emit.call(this, 'error', err);
			else
				EventEmitter.prototype.emit.call(this, 'finish');
		}.bind(this));
	}
	else {
		var args = Array.prototype.slice.call(arguments);
		EventEmitter.prototype.emit.apply(this, args);
	}
};

module.exports = FlushWritable;


flushwritable

description: A Writable stream that flushes before emitting finish

test: test

test: mocha -R spec test

keywords: stream streams writable flush transform wrapper

author: Tom Frost <tom@frosteddesign.com>

license: MIT


code:
/*
 * FlushWritable
 * Copyright 2014 Tom Frost
 */

var FlushWritable = require('../lib/FlushWritable'),
	Readable = require('stream').Readable,
	util = require('util'),
	should = require('should');

function TestWritable() {
	FlushWritable.call(this);
}
util.inherits(TestWritable, FlushWritable);

TestWritable.prototype._flush = function(cb) {
	this.flushCalled = true;
	setTimeout(function() {
		cb(this.err);
	}.bind(this), 10);
};

TestWritable.prototype._write = function(data, encoding, cb) {
	cb();
};

function TestReadable() {
	this.i = 0;
	Readable.call(this);
}
util.inherits(TestReadable, Readable);

TestReadable.prototype._read = function() {
	if (this.i++ === 2)
		this.push(null);
	else
		this.push('foo');
};

describe('FlushWritable', function() {
	it('should call _flush prior to emitting finish', function(done) {
		var r = new TestReadable(),
			w = new TestWritable(),
			finished = false;
		w.on('finish', function() {
			finished = true;
		});
		r.pipe(w);
		setTimeout(function() {
			w.should.have.property('flushCalled');
			finished.should.eql(false);
			setTimeout(function() {
				finished.should.eql(true);
				done();
			}, 10);
		}, 5);
	});
	it('should emit error instead of finish for errors in cb', function(done) {
		var r = new TestReadable(),
			w = new TestWritable(),
			finished = false,
			errored = false;
		w.on('finish', function() {
			finished = true;
		});
		w.on('error', function() {
			errored = true;
		});
		w.err = new Error('bar');
		r.pipe(w);
		setTimeout(function() {
			finished.should.eql(false);
			errored.should.eql(true);
			done();
		}, 15);
	});
	it('should finish immediately if no _flush is defined', function(done) {
		var r = new TestReadable(),
			w = new TestWritable(),
			finished = false;
		w.on('finish', function() {
			finished = true;
		});
		w._flush = undefined;
		r.pipe(w);
		setTimeout(function() {
			finished.should.eql(true);
			done();
		}, 5);
	});
});


code:
## Follow Redirects

Drop-in replacement for Node's `http` and `https` modules that automatically follows redirects.

[![npm version](https://img.shields.io/npm/v/follow-redirects.svg)](https://www.npmjs.com/package/follow-redirects)
[![Build Status](https://github.com/follow-redirects/follow-redirects/workflows/CI/badge.svg)](https://github.com/follow-redirects/follow-redirects/actions)
[![Coverage Status](https://coveralls.io/repos/follow-redirects/follow-redirects/badge.svg?branch=master)](https://coveralls.io/r/follow-redirects/follow-redirects?branch=master)
[![npm downloads](https://img.shields.io/npm/dm/follow-redirects.svg)](https://www.npmjs.com/package/follow-redirects)
[![Sponsor on GitHub](https://img.shields.io/static/v1?label=Sponsor&message=%F0%9F%92%96&logo=GitHub)](https://github.com/sponsors/RubenVerborgh)

`follow-redirects` provides [request](https://nodejs.org/api/http.html#http_http_request_options_callback) and [get](https://nodejs.org/api/http.html#http_http_get_options_callback)
 methods that behave identically to those found on the native [http](https://nodejs.org/api/http.html#http_http_request_options_callback) and [https](https://nodejs.org/api/https.html#https_https_request_options_callback)
 modules, with the exception that they will seamlessly follow redirects.

```javascript
const { http, https } = require('follow-redirects');

http.get('http://bit.ly/900913', response => {
  response.on('data', chunk => {
    console.log(chunk);
  });
}).on('error', err => {
  console.error(err);
});
```

You can inspect the final redirected URL through the `responseUrl` property on the `response`.
If no redirection happened, `responseUrl` is the original request URL.

```javascript
const request = https.request({
  host: 'bitly.com',
  path: '/UHfDGO',
}, response => {
  console.log(response.responseUrl);
  // 'http://duckduckgo.com/robots.txt'
});
request.end();
```

## Options
### Global options
Global options are set directly on the `follow-redirects` module:

```javascript
const followRedirects = require('follow-redirects');
followRedirects.maxRedirects = 10;
followRedirects.maxBodyLength = 20 * 1024 * 1024; // 20 MB
```

The following global options are supported:

- `maxRedirects` (default: `21`) – sets the maximum number of allowed redirects; if exceeded, an error will be emitted.

- `maxBodyLength` (default: 10MB) – sets the maximum size of the request body; if exceeded, an error will be emitted.

### Per-request options
Per-request options are set by passing an `options` object:

```javascript
const url = require('url');
const { http, https } = require('follow-redirects');

const options = url.parse('http://bit.ly/900913');
options.maxRedirects = 10;
options.beforeRedirect = (options, response, request) => {
  // Use this to adjust the request options upon redirecting,
  // to inspect the latest response headers,
  // or to cancel the request by throwing an error

  // response.headers = the redirect response headers
  // response.statusCode = the redirect response code (eg. 301, 307, etc.)

  // request.url = the requested URL that resulted in a redirect
  // request.headers = the headers in the request that resulted in a redirect
  // request.method = the method of the request that resulted in a redirect
  if (options.hostname === "example.com") {
    options.auth = "user:password";
  }
};
http.request(options);
```

In addition to the [standard HTTP](https://nodejs.org/api/http.html#http_http_request_options_callback) and [HTTPS options](https://nodejs.org/api/https.html#https_https_request_options_callback),
the following per-request options are supported:
- `followRedirects` (default: `true`) – whether redirects should be followed.

- `maxRedirects` (default: `21`) – sets the maximum number of allowed redirects; if exceeded, an error will be emitted.

- `maxBodyLength` (default: 10MB) – sets the maximum size of the request body; if exceeded, an error will be emitted.

- `beforeRedirect` (default: `undefined`) – optionally change the request `options` on redirects, or abort the request by throwing an error.

- `agents` (default: `undefined`) – sets the `agent` option per protocol, since HTTP and HTTPS use different agents. Example value: `{ http: new http.Agent(), https: new https.Agent() }`

- `trackRedirects` (default: `false`) – whether to store the redirected response details into the `redirects` array on the response object.

### Advanced usage
By default, `follow-redirects` will use the Node.js default implementations
of [`http`](https://nodejs.org/api/http.html)
and [`https`](https://nodejs.org/api/https.html).
To enable features such as caching and/or intermediate request tracking,
you might instead want to wrap `follow-redirects` around custom protocol implementations:

```javascript
const { http, https } = require('follow-redirects').wrap({
  http: require('your-custom-http'),
  https: require('your-custom-https'),
});
```

Such custom protocols only need an implementation of the `request` method.

## Browser Usage

Due to the way the browser works,
the `http` and `https` browser equivalents perform redirects by default.

By requiring `follow-redirects` this way:
```javascript
const http = require('follow-redirects/http');
const https = require('follow-redirects/https');
```
you can easily tell webpack and friends to replace
`follow-redirect` by the built-in versions:

```json
{
  "follow-redirects/http"  : "http",
  "follow-redirects/https" : "https"
}
```

## Contributing

Pull Requests are always welcome. Please [file an issue](https://github.com/follow-redirects/follow-redirects/issues)
 detailing your proposal before you invest your valuable time. Additional features and bug fixes should be accompanied
 by tests. You can run the test suite locally with a simple `npm test` command.

## Debug Logging

`follow-redirects` uses the excellent [debug](https://www.npmjs.com/package/debug) for logging. To turn on logging
 set the environment variable `DEBUG=follow-redirects` for debug output from just this module. When running the test
 suite it is sometimes advantageous to set `DEBUG=*` to see output from the express server as well.

## Authors

- [Ruben Verborgh](https://ruben.verborgh.org/)
- [Olivier Lalonde](mailto:olalonde@gmail.com)
- [James Talmage](mailto:james@talmage.io)

## License

[MIT License](https://github.com/follow-redirects/follow-redirects/blob/master/LICENSE)


code:
var debug;

module.exports = function () {
  if (!debug) {
    try {
      /* eslint global-require: off */
      debug = require("debug")("follow-redirects");
    }
    catch (error) { /* */ }
    if (typeof debug !== "function") {
      debug = function () { /* */ };
    }
  }
  debug.apply(null, arguments);
};


code: module.exports = require("./").https;


code:
var url = require("url");
var URL = url.URL;
var http = require("http");
var https = require("https");
var Writable = require("stream").Writable;
var assert = require("assert");
var debug = require("./debug");

// Whether to use the native URL object or the legacy url module
var useNativeURL = false;
try {
  assert(new URL());
}
catch (error) {
  useNativeURL = error.code === "ERR_INVALID_URL";
}

// URL fields to preserve in copy operations
var preservedUrlFields = [
  "auth",
  "host",
  "hostname",
  "href",
  "path",
  "pathname",
  "port",
  "protocol",
  "query",
  "search",
  "hash",
];

// Create handlers that pass events from native requests
var events = ["abort", "aborted", "connect", "error", "socket", "timeout"];
var eventHandlers = Object.create(null);
events.forEach(function (event) {
  eventHandlers[event] = function (arg1, arg2, arg3) {
    this._redirectable.emit(event, arg1, arg2, arg3);
  };
});

// Error types with codes
var InvalidUrlError = createErrorType(
  "ERR_INVALID_URL",
  "Invalid URL",
  TypeError
);
var RedirectionError = createErrorType(
  "ERR_FR_REDIRECTION_FAILURE",
  "Redirected request failed"
);
var TooManyRedirectsError = createErrorType(
  "ERR_FR_TOO_MANY_REDIRECTS",
  "Maximum number of redirects exceeded",
  RedirectionError
);
var MaxBodyLengthExceededError = createErrorType(
  "ERR_FR_MAX_BODY_LENGTH_EXCEEDED",
  "Request body larger than maxBodyLength limit"
);
var WriteAfterEndError = createErrorType(
  "ERR_STREAM_WRITE_AFTER_END",
  "write after end"
);

// istanbul ignore next
var destroy = Writable.prototype.destroy || noop;

// An HTTP(S) request that can be redirected
function RedirectableRequest(options, responseCallback) {
  // Initialize the request
  Writable.call(this);
  this._sanitizeOptions(options);
  this._options = options;
  this._ended = false;
  this._ending = false;
  this._redirectCount = 0;
  this._redirects = [];
  this._requestBodyLength = 0;
  this._requestBodyBuffers = [];

  // Attach a callback if passed
  if (responseCallback) {
    this.on("response", responseCallback);
  }

  // React to responses of native requests
  var self = this;
  this._onNativeResponse = function (response) {
    try {
      self._processResponse(response);
    }
    catch (cause) {
      self.emit("error", cause instanceof RedirectionError ?
        cause : new RedirectionError({ cause: cause }));
    }
  };

  // Perform the first request
  this._performRequest();
}
RedirectableRequest.prototype = Object.create(Writable.prototype);

RedirectableRequest.prototype.abort = function () {
  destroyRequest(this._currentRequest);
  this._currentRequest.abort();
  this.emit("abort");
};

RedirectableRequest.prototype.destroy = function (error) {
  destroyRequest(this._currentRequest, error);
  destroy.call(this, error);
  return this;
};

// Writes buffered data to the current native request
RedirectableRequest.prototype.write = function (data, encoding, callback) {
  // Writing is not allowed if end has been called
  if (this._ending) {
    throw new WriteAfterEndError();
  }

  // Validate input and shift parameters if necessary
  if (!isString(data) && !isBuffer(data)) {
    throw new TypeError("data should be a string, Buffer or Uint8Array");
  }
  if (isFunction(encoding)) {
    callback = encoding;
    encoding = null;
  }

  // Ignore empty buffers, since writing them doesn't invoke the callback
  // https://github.com/nodejs/node/issues/22066
  if (data.length === 0) {
    if (callback) {
      callback();
    }
    return;
  }
  // Only write when we don't exceed the maximum body length
  if (this._requestBodyLength + data.length <= this._options.maxBodyLength) {
    this._requestBodyLength += data.length;
    this._requestBodyBuffers.push({ data: data, encoding: encoding });
    this._currentRequest.write(data, encoding, callback);
  }
  // Error when we exceed the maximum body length
  else {
    this.emit("error", new MaxBodyLengthExceededError());
    this.abort();
  }
};

// Ends the current native request
RedirectableRequest.prototype.end = function (data, encoding, callback) {
  // Shift parameters if necessary
  if (isFunction(data)) {
    callback = data;
    data = encoding = null;
  }
  else if (isFunction(encoding)) {
    callback = encoding;
    encoding = null;
  }

  // Write data if needed and end
  if (!data) {
    this._ended = this._ending = true;
    this._currentRequest.end(null, null, callback);
  }
  else {
    var self = this;
    var currentRequest = this._currentRequest;
    this.write(data, encoding, function () {
      self._ended = true;
      currentRequest.end(null, null, callback);
    });
    this._ending = true;
  }
};

// Sets a header value on the current native request
RedirectableRequest.prototype.setHeader = function (name, value) {
  this._options.headers[name] = value;
  this._currentRequest.setHeader(name, value);
};

// Clears a header value on the current native request
RedirectableRequest.prototype.removeHeader = function (name) {
  delete this._options.headers[name];
  this._currentRequest.removeHeader(name);
};

// Global timeout for all underlying requests
RedirectableRequest.prototype.setTimeout = function (msecs, callback) {
  var self = this;

  // Destroys the socket on timeout
  function destroyOnTimeout(socket) {
    socket.setTimeout(msecs);
    socket.removeListener("timeout", socket.destroy);
    socket.addListener("timeout", socket.destroy);
  }

  // Sets up a timer to trigger a timeout event
  function startTimer(socket) {
    if (self._timeout) {
      clearTimeout(self._timeout);
    }
    self._timeout = setTimeout(function () {
      self.emit("timeout");
      clearTimer();
    }, msecs);
    destroyOnTimeout(socket);
  }

  // Stops a timeout from triggering
  function clearTimer() {
    // Clear the timeout
    if (self._timeout) {
      clearTimeout(self._timeout);
      self._timeout = null;
    }

    // Clean up all attached listeners
    self.removeListener("abort", clearTimer);
    self.removeListener("error", clearTimer);
    self.removeListener("response", clearTimer);
    self.removeListener("close", clearTimer);
    if (callback) {
      self.removeListener("timeout", callback);
    }
    if (!self.socket) {
      self._currentRequest.removeListener("socket", startTimer);
    }
  }

  // Attach callback if passed
  if (callback) {
    this.on("timeout", callback);
  }

  // Start the timer if or when the socket is opened
  if (this.socket) {
    startTimer(this.socket);
  }
  else {
    this._currentRequest.once("socket", startTimer);
  }

  // Clean up on events
  this.on("socket", destroyOnTimeout);
  this.on("abort", clearTimer);
  this.on("error", clearTimer);
  this.on("response", clearTimer);
  this.on("close", clearTimer);

  return this;
};

// Proxy all other public ClientRequest methods
[
  "flushHeaders", "getHeader",
  "setNoDelay", "setSocketKeepAlive",
].forEach(function (method) {
  RedirectableRequest.prototype[method] = function (a, b) {
    return this._currentRequest[method](a, b);
  };
});

// Proxy all public ClientRequest properties
["aborted", "connection", "socket"].forEach(function (property) {
  Object.defineProperty(RedirectableRequest.prototype, property, {
    get: function () { return this._currentRequest[property]; },
  });
});

RedirectableRequest.prototype._sanitizeOptions = function (options) {
  // Ensure headers are always present
  if (!options.headers) {
    options.headers = {};
  }

  // Since http.request treats host as an alias of hostname,
  // but the url module interprets host as hostname plus port,
  // eliminate the host property to avoid confusion.
  if (options.host) {
    // Use hostname if set, because it has precedence
    if (!options.hostname) {
      options.hostname = options.host;
    }
    delete options.host;
  }

  // Complete the URL object when necessary
  if (!options.pathname && options.path) {
    var searchPos = options.path.indexOf("?");
    if (searchPos < 0) {
      options.pathname = options.path;
    }
    else {
      options.pathname = options.path.substring(0, searchPos);
      options.search = options.path.substring(searchPos);
    }
  }
};

// Executes the next native request (initial or redirect)
RedirectableRequest.prototype._performRequest = function () {
  // Load the native protocol
  var protocol = this._options.protocol;
  var nativeProtocol = this._options.nativeProtocols[protocol];
  if (!nativeProtocol) {
    throw new TypeError("Unsupported protocol " + protocol);
  }

  // If specified, use the agent corresponding to the protocol
  // (HTTP and HTTPS use different types of agents)
  if (this._options.agents) {
    var scheme = protocol.slice(0, -1);
    this._options.agent = this._options.agents[scheme];
  }

  // Create the native request and set up its event handlers
  var request = this._currentRequest =
        nativeProtocol.request(this._options, this._onNativeResponse);
  request._redirectable = this;
  for (var event of events) {
    request.on(event, eventHandlers[event]);
  }

  // RFC7230§5.3.1: When making a request directly to an origin server, […]
  // a client MUST send only the absolute path […] as the request-target.
  this._currentUrl = /^\//.test(this._options.path) ?
    url.format(this._options) :
    // When making a request to a proxy, […]
    // a client MUST send the target URI in absolute-form […].
    this._options.path;

  // End a redirected request
  // (The first request must be ended explicitly with RedirectableRequest#end)
  if (this._isRedirect) {
    // Write the request entity and end
    var i = 0;
    var self = this;
    var buffers = this._requestBodyBuffers;
    (function writeNext(error) {
      // Only write if this request has not been redirected yet
      /* istanbul ignore else */
      if (request === self._currentRequest) {
        // Report any write errors
        /* istanbul ignore if */
        if (error) {
          self.emit("error", error);
        }
        // Write the next buffer if there are still left
        else if (i < buffers.length) {
          var buffer = buffers[i++];
          /* istanbul ignore else */
          if (!request.finished) {
            request.write(buffer.data, buffer.encoding, writeNext);
          }
        }
        // End the request if `end` has been called on us
        else if (self._ended) {
          request.end();
        }
      }
    }());
  }
};

// Processes a response from the current native request
RedirectableRequest.prototype._processResponse = function (response) {
  // Store the redirected response
  var statusCode = response.statusCode;
  if (this._options.trackRedirects) {
    this._redirects.push({
      url: this._currentUrl,
      headers: response.headers,
      statusCode: statusCode,
    });
  }

  // RFC7231§6.4: The 3xx (Redirection) class of status code indicates
  // that further action needs to be taken by the user agent in order to
  // fulfill the request. If a Location header field is provided,
  // the user agent MAY automatically redirect its request to the URI
  // referenced by the Location field value,
  // even if the specific status code is not understood.

  // If the response is not a redirect; return it as-is
  var location = response.headers.location;
  if (!location || this._options.followRedirects === false ||
      statusCode < 300 || statusCode >= 400) {
    response.responseUrl = this._currentUrl;
    response.redirects = this._redirects;
    this.emit("response", response);

    // Clean up
    this._requestBodyBuffers = [];
    return;
  }

  // The response is a redirect, so abort the current request
  destroyRequest(this._currentRequest);
  // Discard the remainder of the response to avoid waiting for data
  response.destroy();

  // RFC7231§6.4: A client SHOULD detect and intervene
  // in cyclical redirections (i.e., "infinite" redirection loops).
  if (++this._redirectCount > this._options.maxRedirects) {
    throw new TooManyRedirectsError();
  }

  // Store the request headers if applicable
  var requestHeaders;
  var beforeRedirect = this._options.beforeRedirect;
  if (beforeRedirect) {
    requestHeaders = Object.assign({
      // The Host header was set by nativeProtocol.request
      Host: response.req.getHeader("host"),
    }, this._options.headers);
  }

  // RFC7231§6.4: Automatic redirection needs to done with
  // care for methods not known to be safe, […]
  // RFC7231§6.4.2–3: For historical reasons, a user agent MAY change
  // the request method from POST to GET for the subsequent request.
  var method = this._options.method;
  if ((statusCode === 301 || statusCode === 302) && this._options.method === "POST" ||
      // RFC7231§6.4.4: The 303 (See Other) status code indicates that
      // the server is redirecting the user agent to a different resource […]
      // A user agent can perform a retrieval request targeting that URI
      // (a GET or HEAD request if using HTTP) […]
      (statusCode === 303) && !/^(?:GET|HEAD)$/.test(this._options.method)) {
    this._options.method = "GET";
    // Drop a possible entity and headers related to it
    this._requestBodyBuffers = [];
    removeMatchingHeaders(/^content-/i, this._options.headers);
  }

  // Drop the Host header, as the redirect might lead to a different host
  var currentHostHeader = removeMatchingHeaders(/^host$/i, this._options.headers);

  // If the redirect is relative, carry over the host of the last request
  var currentUrlParts = parseUrl(this._currentUrl);
  var currentHost = currentHostHeader || currentUrlParts.host;
  var currentUrl = /^\w+:/.test(location) ? this._currentUrl :
    url.format(Object.assign(currentUrlParts, { host: currentHost }));

  // Create the redirected request
  var redirectUrl = resolveUrl(location, currentUrl);
  debug("redirecting to", redirectUrl.href);
  this._isRedirect = true;
  spreadUrlObject(redirectUrl, this._options);

  // Drop confidential headers when redirecting to a less secure protocol
  // or to a different domain that is not a superdomain
  if (redirectUrl.protocol !== currentUrlParts.protocol &&
     redirectUrl.protocol !== "https:" ||
     redirectUrl.host !== currentHost &&
     !isSubdomain(redirectUrl.host, currentHost)) {
    removeMatchingHeaders(/^(?:(?:proxy-)?authorization|cookie)$/i, this._options.headers);
  }

  // Evaluate the beforeRedirect callback
  if (isFunction(beforeRedirect)) {
    var responseDetails = {
      headers: response.headers,
      statusCode: statusCode,
    };
    var requestDetails = {
      url: currentUrl,
      method: method,
      headers: requestHeaders,
    };
    beforeRedirect(this._options, responseDetails, requestDetails);
    this._sanitizeOptions(this._options);
  }

  // Perform the redirected request
  this._performRequest();
};

// Wraps the key/value object of protocols with redirect functionality
function wrap(protocols) {
  // Default settings
  var exports = {
    maxRedirects: 21,
    maxBodyLength: 10 * 1024 * 1024,
  };

  // Wrap each protocol
  var nativeProtocols = {};
  Object.keys(protocols).forEach(function (scheme) {
    var protocol = scheme + ":";
    var nativeProtocol = nativeProtocols[protocol] = protocols[scheme];
    var wrappedProtocol = exports[scheme] = Object.create(nativeProtocol);

    // Executes a request, following redirects
    function request(input, options, callback) {
      // Parse parameters, ensuring that input is an object
      if (isURL(input)) {
        input = spreadUrlObject(input);
      }
      else if (isString(input)) {
        input = spreadUrlObject(parseUrl(input));
      }
      else {
        callback = options;
        options = validateUrl(input);
        input = { protocol: protocol };
      }
      if (isFunction(options)) {
        callback = options;
        options = null;
      }

      // Set defaults
      options = Object.assign({
        maxRedirects: exports.maxRedirects,
        maxBodyLength: exports.maxBodyLength,
      }, input, options);
      options.nativeProtocols = nativeProtocols;
      if (!isString(options.host) && !isString(options.hostname)) {
        options.hostname = "::1";
      }

      assert.equal(options.protocol, protocol, "protocol mismatch");
      debug("options", options);
      return new RedirectableRequest(options, callback);
    }

    // Executes a GET request, following redirects
    function get(input, options, callback) {
      var wrappedRequest = wrappedProtocol.request(input, options, callback);
      wrappedRequest.end();
      return wrappedRequest;
    }

    // Expose the properties on the wrapped protocol
    Object.defineProperties(wrappedProtocol, {
      request: { value: request, configurable: true, enumerable: true, writable: true },
      get: { value: get, configurable: true, enumerable: true, writable: true },
    });
  });
  return exports;
}

function noop() { /* empty */ }

function parseUrl(input) {
  var parsed;
  /* istanbul ignore else */
  if (useNativeURL) {
    parsed = new URL(input);
  }
  else {
    // Ensure the URL is valid and absolute
    parsed = validateUrl(url.parse(input));
    if (!isString(parsed.protocol)) {
      throw new InvalidUrlError({ input });
    }
  }
  return parsed;
}

function resolveUrl(relative, base) {
  /* istanbul ignore next */
  return useNativeURL ? new URL(relative, base) : parseUrl(url.resolve(base, relative));
}

function validateUrl(input) {
  if (/^\[/.test(input.hostname) && !/^\[[:0-9a-f]+\]$/i.test(input.hostname)) {
    throw new InvalidUrlError({ input: input.href || input });
  }
  if (/^\[/.test(input.host) && !/^\[[:0-9a-f]+\](:\d+)?$/i.test(input.host)) {
    throw new InvalidUrlError({ input: input.href || input });
  }
  return input;
}

function spreadUrlObject(urlObject, target) {
  var spread = target || {};
  for (var key of preservedUrlFields) {
    spread[key] = urlObject[key];
  }

  // Fix IPv6 hostname
  if (spread.hostname.startsWith("[")) {
    spread.hostname = spread.hostname.slice(1, -1);
  }
  // Ensure port is a number
  if (spread.port !== "") {
    spread.port = Number(spread.port);
  }
  // Concatenate path
  spread.path = spread.search ? spread.pathname + spread.search : spread.pathname;

  return spread;
}

function removeMatchingHeaders(regex, headers) {
  var lastValue;
  for (var header in headers) {
    if (regex.test(header)) {
      lastValue = headers[header];
      delete headers[header];
    }
  }
  return (lastValue === null || typeof lastValue === "undefined") ?
    undefined : String(lastValue).trim();
}

function createErrorType(code, message, baseClass) {
  // Create constructor
  function CustomError(properties) {
    Error.captureStackTrace(this, this.constructor);
    Object.assign(this, properties || {});
    this.code = code;
    this.message = this.cause ? message + ": " + this.cause.message : message;
  }

  // Attach constructor and set default properties
  CustomError.prototype = new (baseClass || Error)();
  Object.defineProperties(CustomError.prototype, {
    constructor: {
      value: CustomError,
      enumerable: false,
    },
    name: {
      value: "Error [" + code + "]",
      enumerable: false,
    },
  });
  return CustomError;
}

function destroyRequest(request, error) {
  for (var event of events) {
    request.removeListener(event, eventHandlers[event]);
  }
  request.on("error", noop);
  request.destroy(error);
}

function isSubdomain(subdomain, domain) {
  assert(isString(subdomain) && isString(domain));
  var dot = subdomain.length - domain.length - 1;
  return dot > 0 && subdomain[dot] === "." && subdomain.endsWith(domain);
}

function isString(value) {
  return typeof value === "string" || value instanceof String;
}

function isFunction(value) {
  return typeof value === "function";
}

function isBuffer(value) {
  return typeof value === "object" && ("length" in value);
}

function isURL(value) {
  return URL && value instanceof URL;
}

// Exports
module.exports = wrap({ http: http, https: https });
module.exports.wrap = wrap;


follow-redirects

description: HTTP and HTTPS modules that follow redirects.

lint: eslint *.js test

test: nyc mocha

keywords: http https url redirect client location utility

author: Ruben Verborgh <ruben@verborgh.org> (https://ruben.verborgh.org/)

contributors: Olivier Lalonde <olalonde@gmail.com> (http://www.syskall.com)

type: individual


code:
0.2.0 / 2021-05-31
==================

  * Use `req.socket` over deprecated `req.connection`

0.1.2 / 2017-09-14
==================

  * perf: improve header parsing
  * perf: reduce overhead when no `X-Forwarded-For` header

0.1.1 / 2017-09-10
==================

  * Fix trimming leading / trailing OWS
  * perf: hoist regular expression

0.1.0 / 2014-09-21
==================

  * Initial release


code:
# forwarded

[![NPM Version][npm-image]][npm-url]
[![NPM Downloads][downloads-image]][downloads-url]
[![Node.js Version][node-version-image]][node-version-url]
[![Build Status][ci-image]][ci-url]
[![Test Coverage][coveralls-image]][coveralls-url]

Parse HTTP X-Forwarded-For header

## Installation

This is a [Node.js](https://nodejs.org/en/) module available through the
[npm registry](https://www.npmjs.com/). Installation is done using the
[`npm install` command](https://docs.npmjs.com/getting-started/installing-npm-packages-locally):

```sh
$ npm install forwarded
```

## API

```js
var forwarded = require('forwarded')
```

### forwarded(req)

```js
var addresses = forwarded(req)
```

Parse the `X-Forwarded-For` header from the request. Returns an array
of the addresses, including the socket address for the `req`, in reverse
order (i.e. index `0` is the socket address and the last index is the
furthest address, typically the end-user).

## Testing

```sh
$ npm test
```

## License

[MIT](LICENSE)

[ci-image]: https://badgen.net/github/checks/jshttp/forwarded/master?label=ci
[ci-url]: https://github.com/jshttp/forwarded/actions?query=workflow%3Aci
[npm-image]: https://img.shields.io/npm/v/forwarded.svg
[npm-url]: https://npmjs.org/package/forwarded
[node-version-image]: https://img.shields.io/node/v/forwarded.svg
[node-version-url]: https://nodejs.org/en/download/
[coveralls-image]: https://img.shields.io/coveralls/jshttp/forwarded/master.svg
[coveralls-url]: https://coveralls.io/r/jshttp/forwarded?branch=master
[downloads-image]: https://img.shields.io/npm/dm/forwarded.svg
[downloads-url]: https://npmjs.org/package/forwarded


code:
/*!
 * forwarded
 * Copyright(c) 2014-2017 Douglas Christopher Wilson
 * MIT Licensed
 */

'use strict'

/**
 * Module exports.
 * @public
 */

module.exports = forwarded

/**
 * Get all addresses in the request, using the `X-Forwarded-For` header.
 *
 * @param {object} req
 * @return {array}
 * @public
 */

function forwarded (req) {
  if (!req) {
    throw new TypeError('argument req is required')
  }

  // simple header parsing
  var proxyAddrs = parse(req.headers['x-forwarded-for'] || '')
  var socketAddr = getSocketAddr(req)
  var addrs = [socketAddr].concat(proxyAddrs)

  // return all addresses
  return addrs
}

/**
 * Get the socket address for a request.
 *
 * @param {object} req
 * @return {string}
 * @private
 */

function getSocketAddr (req) {
  return req.socket
    ? req.socket.remoteAddress
    : req.connection.remoteAddress
}

/**
 * Parse the X-Forwarded-For header.
 *
 * @param {string} header
 * @private
 */

function parse (header) {
  var end = header.length
  var list = []
  var start = header.length

  // gather addresses, backwards
  for (var i = header.length - 1; i >= 0; i--) {
    switch (header.charCodeAt(i)) {
      case 0x20: /*   */
        if (start === end) {
          start = end = i
        }
        break
      case 0x2c: /* , */
        if (start !== end) {
          list.push(header.substring(start, end))
        }
        start = end = i
        break
      default:
        start = i
        break
    }
  }

  // final address
  if (start !== end) {
    list.push(header.substring(start, end))
  }

  return list
}


forwarded

description: Parse HTTP X-Forwarded-For header

contributors: Douglas Christopher Wilson <doug@somethingdoug.com>

keywords: x-forwarded-for http req

repository: jshttp/forwarded

bench: node benchmark/index.js

lint: eslint .

test: mocha --reporter spec --bail --check-leaks test/

test-ci: nyc --reporter=lcov --reporter=text npm test

test-cov: nyc --reporter=html --reporter=text npm test

version: node scripts/version-history.js && git add HISTORY.md


code:
# Fraction.js - ℚ in JavaScript

[![NPM Package](https://img.shields.io/npm/v/fraction.js.svg?style=flat)](https://npmjs.org/package/fraction.js "View this project on npm")
[![MIT license](http://img.shields.io/badge/license-MIT-brightgreen.svg)](http://opensource.org/licenses/MIT)

Tired of inprecise numbers represented by doubles, which have to store rational and irrational numbers like PI or sqrt(2) the same way? Obviously the following problem is preventable:

```javascript
1 / 98 * 98 // = 0.9999999999999999
```

If you need more precision or just want a fraction as a result, just include *Fraction.js*:

```javascript
var Fraction = require('fraction.js');
// or
import Fraction from 'fraction.js';
```

and give it a trial:

```javascript
Fraction(1).div(98).mul(98) // = 1
```

Internally, numbers are represented as *numerator / denominator*, which adds just a little overhead. However, the library is written with performance and accuracy in mind, which makes it the perfect basis for [Polynomial.js](https://github.com/infusion/Polynomial.js) and [Math.js](https://github.com/josdejong/mathjs).

Convert decimal to fraction
===
The simplest job for fraction.js is to get a fraction out of a decimal:
```javascript
var x = new Fraction(1.88);
var res = x.toFraction(true); // String "1 22/25"
```

Examples / Motivation
===
A simple example might be

```javascript
var f = new Fraction("9.4'31'"); // 9.4313131313131...
f.mul([-4, 3]).mod("4.'8'"); // 4.88888888888888...
```
The result is

```javascript
console.log(f.toFraction()); // -4154 / 1485
```
You could of course also access the sign (s), numerator (n) and denominator (d) on your own:
```javascript
f.s * f.n / f.d = -1 * 4154 / 1485 = -2.797306...
```

If you would try to calculate it yourself, you would come up with something like:

```javascript
(9.4313131 * (-4 / 3)) % 4.888888 = -2.797308133...
```

Quite okay, but yea - not as accurate as it could be.

Laplace Probability
===
Simple example. What's the probability of throwing a 3, and 1 or 4, and 2 or 4 or 6 with a fair dice?

P({3}):
```javascript
var p = new Fraction([3].length, 6).toString(); // 0.1(6)
```

P({1, 4}):
```javascript
var p = new Fraction([1, 4].length, 6).toString(); // 0.(3)
```

P({2, 4, 6}):
```javascript
var p = new Fraction([2, 4, 6].length, 6).toString(); // 0.5
```

Convert degrees/minutes/seconds to precise rational representation:
===

57+45/60+17/3600
```javascript
var deg = 57; // 57°
var min = 45; // 45 Minutes
var sec = 17; // 17 Seconds

new Fraction(deg).add(min, 60).add(sec, 3600).toString() // -> 57.7547(2)
```

Rational approximation of irrational numbers
===

Now it's getting messy ;d To approximate a number like *sqrt(5) - 2* with a numerator and denominator, you can reformat the equation as follows: *pow(n / d + 2, 2) = 5*.

Then the following algorithm will generate the rational number besides the binary representation.

```javascript
var x = "/", s = "";

var a = new Fraction(0),
    b = new Fraction(1);
for (var n = 0; n <= 10; n++) {

  var c = a.add(b).div(2);

  console.log(n + "\t" + a + "\t" + b + "\t" + c + "\t" + x);

  if (c.add(2).pow(2) < 5) {
    a = c;
    x = "1";
  } else {
    b = c;
    x = "0";
  }
  s+= x;
}
console.log(s)
```

The result is

```
n   a[n]        b[n]        c[n]            x[n]
0   0/1         1/1         1/2             /
1   0/1         1/2         1/4             0
2   0/1         1/4         1/8             0
3   1/8         1/4         3/16            1
4   3/16        1/4         7/32            1
5   7/32        1/4         15/64           1
6   15/64       1/4         31/128          1
7   15/64       31/128      61/256          0
8   15/64       61/256      121/512         0
9   15/64       121/512     241/1024        0
10  241/1024    121/512     483/2048        1
```
Thus the approximation after 11 iterations of the bisection method is *483 / 2048* and the binary representation is 0.00111100011 (see [WolframAlpha](http://www.wolframalpha.com/input/?i=sqrt%285%29-2+binary))

I published another example on how to approximate PI with fraction.js on my [blog](http://www.xarg.org/2014/03/precise-calculations-in-javascript/) (Still not the best idea to approximate irrational numbers, but it illustrates the capabilities of Fraction.js perfectly).

Get the exact fractional part of a number
---
```javascript
var f = new Fraction("-6.(3416)");
console.log("" + f.mod(1).abs()); // 0.(3416)
```

Mathematical correct modulo
---
The behaviour on negative congruences is different to most modulo implementations in computer science. Even the *mod()* function of Fraction.js behaves in the typical way. To solve the problem of having the mathematical correct modulo with Fraction.js you could come up with this:

```javascript
var a = -1;
var b = 10.99;

console.log(new Fraction(a)
  .mod(b)); // Not correct, usual Modulo

console.log(new Fraction(a)
  .mod(b).add(b).mod(b)); // Correct! Mathematical Modulo
```

fmod() impreciseness circumvented
---
It turns out that Fraction.js outperforms almost any fmod() implementation, including JavaScript itself, [php.js](http://phpjs.org/functions/fmod/), C++, Python, Java and even Wolframalpha due to the fact that numbers like 0.05, 0.1, ... are infinite decimal in base 2.

The equation *fmod(4.55, 0.05)* gives *0.04999999999999957*, wolframalpha says *1/20*. The correct answer should be **zero**, as 0.05 divides 4.55 without any remainder.

Parser
===

Any function (see below) as well as the constructor of the *Fraction* class parses its input and reduce it to the smallest term.

You can pass either Arrays, Objects, Integers, Doubles or Strings.

Arrays / Objects
---
```javascript
new Fraction(numerator, denominator);
new Fraction([numerator, denominator]);
new Fraction({n: numerator, d: denominator});
```

Integers
---
```javascript
new Fraction(123);
```

Doubles
---
```javascript
new Fraction(55.4);
```

**Note:** If you pass a double as it is, Fraction.js will perform a number analysis based on Farey Sequences. If you concern performance, cache Fraction.js objects and pass arrays/objects.

The method is really precise, but too large exact numbers, like 1234567.9991829 will result in a wrong approximation. If you want to keep the number as it is, convert it to a string, as the string parser will not perform any further observations. If you have problems with the approximation, in the file `examples/approx.js` is a different approximation algorithm, which might work better in some more specific use-cases.

Strings
---
```javascript
new Fraction("123.45");
new Fraction("123/45"); // A rational number represented as two decimals, separated by a slash
new Fraction("123:45"); // A rational number represented as two decimals, separated by a colon
new Fraction("4 123/45"); // A rational number represented as a whole number and a fraction
new Fraction("123.'456'"); // Note the quotes, see below!
new Fraction("123.(456)"); // Note the brackets, see below!
new Fraction("123.45'6'"); // Note the quotes, see below!
new Fraction("123.45(6)"); // Note the brackets, see below!
```

Two arguments
---
```javascript
new Fraction(3, 2); // 3/2 = 1.5
```

Repeating decimal places
---
*Fraction.js* can easily handle repeating decimal places. For example *1/3* is *0.3333...*. There is only one repeating digit. As you can see in the examples above, you can pass a number like *1/3* as "0.'3'" or "0.(3)", which are synonym. There are no tests to parse something like 0.166666666 to 1/6! If you really want to handle this number, wrap around brackets on your own with the function below for example: 0.1(66666666)

Assume you want to divide 123.32 / 33.6(567). [WolframAlpha](http://www.wolframalpha.com/input/?i=123.32+%2F+%2812453%2F370%29) states that you'll get a period of 1776 digits. *Fraction.js* comes to the same result. Give it a try:

```javascript
var f = new Fraction("123.32");
console.log("Bam: " + f.div("33.6(567)"));
```

To automatically make a number like "0.123123123" to something more Fraction.js friendly like "0.(123)", I hacked this little brute force algorithm in a 10 minutes. Improvements are welcome...

```javascript
function formatDecimal(str) {

  var comma, pre, offset, pad, times, repeat;

  if (-1 === (comma = str.indexOf(".")))
    return str;

  pre = str.substr(0, comma + 1);
  str = str.substr(comma + 1);

  for (var i = 0; i < str.length; i++) {

    offset = str.substr(0, i);

    for (var j = 0; j < 5; j++) {

      pad = str.substr(i, j + 1);

      times = Math.ceil((str.length - offset.length) / pad.length);

      repeat = new Array(times + 1).join(pad); // Silly String.repeat hack

      if (0 === (offset + repeat).indexOf(str)) {
        return pre + offset + "(" + pad + ")";
      }
    }
  }
  return null;
}

var f, x = formatDecimal("13.0123123123"); // = 13.0(123)
if (x !== null) {
  f = new Fraction(x);
}
```

Attributes
===

The Fraction object allows direct access to the numerator, denominator and sign attributes. It is ensured that only the sign-attribute holds sign information so that a sign comparison is only necessary against this attribute.

```javascript
var f = new Fraction('-1/2');
console.log(f.n); // Numerator: 1
console.log(f.d); // Denominator: 2
console.log(f.s); // Sign: -1
```

Functions
===

Fraction abs()
---
Returns the actual number without any sign information

Fraction neg()
---
Returns the actual number with flipped sign in order to get the additive inverse

Fraction add(n)
---
Returns the sum of the actual number and the parameter n

Fraction sub(n)
---
Returns the difference of the actual number and the parameter n

Fraction mul(n)
---
Returns the product of the actual number and the parameter n

Fraction div(n)
---
Returns the quotient of the actual number and the parameter n

Fraction pow(exp)
---
Returns the power of the actual number, raised to an possible rational exponent. If the result becomes non-rational the function returns `null`.

Fraction mod(n)
---
Returns the modulus (rest of the division) of the actual object and n (this % n). It's a much more precise [fmod()](#fmod-impreciseness-circumvented) if you like. Please note that *mod()* is just like the modulo operator of most programming languages. If you want a mathematical correct modulo, see [here](#mathematical-correct-modulo).

Fraction mod()
---
Returns the modulus (rest of the division) of the actual object (numerator mod denominator)

Fraction gcd(n)
---
Returns the fractional greatest common divisor

Fraction lcm(n)
---
Returns the fractional least common multiple

Fraction ceil([places=0-16])
---
Returns the ceiling of a rational number with Math.ceil

Fraction floor([places=0-16])
---
Returns the floor of a rational number with Math.floor

Fraction round([places=0-16])
---
Returns the rational number rounded with Math.round

Fraction roundTo(multiple)
---
Rounds a fraction to the closest multiple of another fraction.

Fraction inverse()
---
Returns the multiplicative inverse of the actual number (n / d becomes d / n) in order to get the reciprocal

Fraction simplify([eps=0.001])
---
Simplifies the rational number under a certain error threshold. Ex. `0.333` will be `1/3` with `eps=0.001`

boolean equals(n)
---
Check if two numbers are equal

int compare(n)
---
Compare two numbers.
```
result < 0: n is greater than actual number
result > 0: n is smaller than actual number
result = 0: n is equal to the actual number
```

boolean divisible(n)
---
Check if two numbers are divisible (n divides this)

double valueOf()
---
Returns a decimal representation of the fraction

String toString([decimalPlaces=15])
---
Generates an exact string representation of the actual object. For repeated decimal places all digits are collected within brackets, like `1/3 = "0.(3)"`. For all other numbers, up to `decimalPlaces` significant digits are collected - which includes trailing zeros if the number is getting truncated. However, `1/2 = "0.5"` without trailing zeros of course.

**Note:** As `valueOf()` and `toString()` are provided, `toString()` is only called implicitly in a real string context. Using the plus-operator like `"123" + new Fraction` will call valueOf(), because JavaScript tries to combine two primitives first and concatenates them later, as string will be the more dominant type. `alert(new Fraction)` or `String(new Fraction)` on the other hand will do what you expect. If you really want to have control, you should call `toString()` or `valueOf()` explicitly!

String toLatex(excludeWhole=false)
---
Generates an exact LaTeX representation of the actual object. You can see a [live demo](http://www.xarg.org/2014/03/precise-calculations-in-javascript/) on my blog.

The optional boolean parameter indicates if you want to exclude the whole part. "1 1/3" instead of "4/3"

String toFraction(excludeWhole=false)
---
Gets a string representation of the fraction

The optional boolean parameter indicates if you want to exclude the whole part. "1 1/3" instead of "4/3"

Array toContinued()
---
Gets an array of the fraction represented as a continued fraction. The first element always contains the whole part.

```javascript
var f = new Fraction('88/33');
var c = f.toContinued(); // [2, 1, 2]
```

Fraction clone()
---
Creates a copy of the actual Fraction object

Exceptions
===
If a really hard error occurs (parsing error, division by zero), *fraction.js* throws exceptions! Please make sure you handle them correctly.

Installation
===
Installing fraction.js is as easy as cloning this repo or use the following command:

```
npm install fraction.js
```

Using Fraction.js with the browser
===
```html
<script src="fraction.js"></script>
<script>
    console.log(Fraction("123/456"));
</script>
```

Using Fraction.js with TypeScript
===
```js
import Fraction from "fraction.js";
console.log(Fraction("123/456"));
```

Coding Style
===
As every library I publish, fraction.js is also built to be as small as possible after compressing it with Google Closure Compiler in advanced mode. Thus the coding style orientates a little on maxing-out the compression rate. Please make sure you keep this style if you plan to extend the library.

Precision
===
Fraction.js tries to circumvent floating point errors, by having an internal representation of numerator and denominator. As it relies on JavaScript, there is also a limit. The biggest number representable is `Number.MAX_SAFE_INTEGER / 1` and the smallest is `-1 / Number.MAX_SAFE_INTEGER`, with `Number.MAX_SAFE_INTEGER=9007199254740991`. If this is not enough, there is `bigfraction.js` shipped experimentally, which relies on `BigInt` and should become the new Fraction.js eventually.

Testing
===
If you plan to enhance the library, make sure you add test cases and all the previous tests are passing. You can test the library with

```
npm test
```

Copyright and licensing
===
Copyright (c) 2023, [Robert Eisele](https://raw.org/)
Licensed under the MIT license.


code:
/**
 * @license Fraction.js v4.2.1 20/08/2023
 * https://www.xarg.org/2014/03/rational-numbers-in-javascript/
 *
 * Copyright (c) 2023, Robert Eisele (robert@raw.org)
 * Dual licensed under the MIT or GPL Version 2 licenses.
 **/

/**
 *
 * This class offers the possibility to calculate fractions.
 * You can pass a fraction in different formats. Either as array, as double, as string or as an integer.
 *
 * Array/Object form
 * [ 0 => <numerator>, 1 => <denominator> ]
 * [ n => <numerator>, d => <denominator> ]
 *
 * Integer form
 * - Single integer value
 *
 * Double form
 * - Single double value
 *
 * String form
 * 123.456 - a simple double
 * 123/456 - a string fraction
 * 123.'456' - a double with repeating decimal places
 * 123.(456) - synonym
 * 123.45'6' - a double with repeating last place
 * 123.45(6) - synonym
 *
 * Example:
 *
 * let f = new Fraction("9.4'31'");
 * f.mul([-4, 3]).div(4.9);
 *
 */

(function(root) {

  "use strict";

  // Set Identity function to downgrade BigInt to Number if needed
  if (typeof BigInt === 'undefined') BigInt = function(n) { if (isNaN(n)) throw new Error(""); return n; };

  const C_ONE = BigInt(1);
  const C_ZERO = BigInt(0);
  const C_TEN = BigInt(10);
  const C_TWO = BigInt(2);
  const C_FIVE = BigInt(5);

  // Maximum search depth for cyclic rational numbers. 2000 should be more than enough.
  // Example: 1/7 = 0.(142857) has 6 repeating decimal places.
  // If MAX_CYCLE_LEN gets reduced, long cycles will not be detected and toString() only gets the first 10 digits
  const MAX_CYCLE_LEN = 2000;

  // Parsed data to avoid calling "new" all the time
  const P = {
    "s": C_ONE,
    "n": C_ZERO,
    "d": C_ONE
  };

  function assign(n, s) {

    try {
      n = BigInt(n);
    } catch (e) {
      throw InvalidParameter();
    }
    return n * s;
  }

  // Creates a new Fraction internally without the need of the bulky constructor
  function newFraction(n, d) {

    if (d === C_ZERO) {
      throw DivisionByZero();
    }

    const f = Object.create(Fraction.prototype);
    f["s"] = n < C_ZERO ? -C_ONE : C_ONE;

    n = n < C_ZERO ? -n : n;

    const a = gcd(n, d);

    f["n"] = n / a;
    f["d"] = d / a;
    return f;
  }

  function factorize(num) {

    const factors = {};

    let n = num;
    let i = C_TWO;
    let s = C_FIVE - C_ONE;

    while (s <= n) {

      while (n % i === C_ZERO) {
        n/= i;
        factors[i] = (factors[i] || C_ZERO) + C_ONE;
      }
      s+= C_ONE + C_TWO * i++;
    }

    if (n !== num) {
      if (n > 1)
        factors[n] = (factors[n] || C_ZERO) + C_ONE;
    } else {
      factors[num] = (factors[num] || C_ZERO) + C_ONE;
    }
    return factors;
  }

  const parse = function(p1, p2) {

    let n = C_ZERO, d = C_ONE, s = C_ONE;

    if (p1 === undefined || p1 === null) {
      /* void */
    } else if (p2 !== undefined) {
      n = BigInt(p1);
      d = BigInt(p2);
      s = n * d;

      if (n % C_ONE !== C_ZERO || d % C_ONE !== C_ZERO) {
        throw NonIntegerParameter();
      }

    } else if (typeof p1 === "object") {
      if ("d" in p1 && "n" in p1) {
        n = BigInt(p1["n"]);
        d = BigInt(p1["d"]);
        if ("s" in p1)
          n*= BigInt(p1["s"]);
      } else if (0 in p1) {
        n = BigInt(p1[0]);
        if (1 in p1)
          d = BigInt(p1[1]);
      } else if (p1 instanceof BigInt) {
        n = BigInt(p1);
      } else {
        throw InvalidParameter();
      }
      s = n * d;
    } else if (typeof p1 === "bigint") {
      n = p1;
      s = p1;
      d = C_ONE;
    } else if (typeof p1 === "number") {

      if (isNaN(p1)) {
        throw InvalidParameter();
      }

      if (p1 < 0) {
        s = -C_ONE;
        p1 = -p1;
      }

      if (p1 % 1 === 0) {
        n = BigInt(p1);
      } else if (p1 > 0) { // check for != 0, scale would become NaN (log(0)), which converges really slow

        let z = 1;

        let A = 0, B = 1;
        let C = 1, D = 1;

        let N = 10000000;

        if (p1 >= 1) {
          z = 10 ** Math.floor(1 + Math.log10(p1));
          p1/= z;
        }

        // Using Farey Sequences

        while (B <= N && D <= N) {
          let M = (A + C) / (B + D);

          if (p1 === M) {
            if (B + D <= N) {
              n = A + C;
              d = B + D;
            } else if (D > B) {
              n = C;
              d = D;
            } else {
              n = A;
              d = B;
            }
            break;

          } else {

            if (p1 > M) {
              A+= C;
              B+= D;
            } else {
              C+= A;
              D+= B;
            }

            if (B > N) {
              n = C;
              d = D;
            } else {
              n = A;
              d = B;
            }
          }
        }
        n = BigInt(n) * BigInt(z);
        d = BigInt(d);

      }

    } else if (typeof p1 === "string") {

      let ndx = 0;

      let v = C_ZERO, w = C_ZERO, x = C_ZERO, y = C_ONE, z = C_ONE;

      let match = p1.match(/\d+|./g);

      if (match === null)
        throw InvalidParameter();

      if (match[ndx] === '-') {// Check for minus sign at the beginning
        s = -C_ONE;
        ndx++;
      } else if (match[ndx] === '+') {// Check for plus sign at the beginning
        ndx++;
      }

      if (match.length === ndx + 1) { // Check if it's just a simple number "1234"
        w = assign(match[ndx++], s);
      } else if (match[ndx + 1] === '.' || match[ndx] === '.') { // Check if it's a decimal number

        if (match[ndx] !== '.') { // Handle 0.5 and .5
          v = assign(match[ndx++], s);
        }
        ndx++;

        // Check for decimal places
        if (ndx + 1 === match.length || match[ndx + 1] === '(' && match[ndx + 3] === ')' || match[ndx + 1] === "'" && match[ndx + 3] === "'") {
          w = assign(match[ndx], s);
          y = C_TEN ** BigInt(match[ndx].length);
          ndx++;
        }

        // Check for repeating places
        if (match[ndx] === '(' && match[ndx + 2] === ')' || match[ndx] === "'" && match[ndx + 2] === "'") {
          x = assign(match[ndx + 1], s);
          z = C_TEN ** BigInt(match[ndx + 1].length) - C_ONE;
          ndx+= 3;
        }

      } else if (match[ndx + 1] === '/' || match[ndx + 1] === ':') { // Check for a simple fraction "123/456" or "123:456"
        w = assign(match[ndx], s);
        y = assign(match[ndx + 2], C_ONE);
        ndx+= 3;
      } else if (match[ndx + 3] === '/' && match[ndx + 1] === ' ') { // Check for a complex fraction "123 1/2"
        v = assign(match[ndx], s);
        w = assign(match[ndx + 2], s);
        y = assign(match[ndx + 4], C_ONE);
        ndx+= 5;
      }

      if (match.length <= ndx) { // Check for more tokens on the stack
        d = y * z;
        s = /* void */
        n = x + d * v + z * w;
      } else {
        throw InvalidParameter();
      }

    } else {
      throw InvalidParameter();
    }

    if (d === C_ZERO) {
      throw DivisionByZero();
    }

    P["s"] = s < C_ZERO ? -C_ONE : C_ONE;
    P["n"] = n < C_ZERO ? -n : n;
    P["d"] = d < C_ZERO ? -d : d;
  };

  function modpow(b, e, m) {

    let r = C_ONE;
    for (; e > C_ZERO; b = (b * b) % m, e >>= C_ONE) {

      if (e & C_ONE) {
        r = (r * b) % m;
      }
    }
    return r;
  }

  function cycleLen(n, d) {

    for (; d % C_TWO === C_ZERO;
      d/= C_TWO) {
    }

    for (; d % C_FIVE === C_ZERO;
      d/= C_FIVE) {
    }

    if (d === C_ONE) // Catch non-cyclic numbers
      return C_ZERO;

    // If we would like to compute really large numbers quicker, we could make use of Fermat's little theorem:
    // 10^(d-1) % d == 1
    // However, we don't need such large numbers and MAX_CYCLE_LEN should be the capstone,
    // as we want to translate the numbers to strings.

    let rem = C_TEN % d;
    let t = 1;

    for (; rem !== C_ONE; t++) {
      rem = rem * C_TEN % d;

      if (t > MAX_CYCLE_LEN)
        return C_ZERO; // Returning 0 here means that we don't print it as a cyclic number. It's likely that the answer is `d-1`
    }
    return BigInt(t);
  }

  function cycleStart(n, d, len) {

    let rem1 = C_ONE;
    let rem2 = modpow(C_TEN, len, d);

    for (let t = 0; t < 300; t++) { // s < ~log10(Number.MAX_VALUE)
      // Solve 10^s == 10^(s+t) (mod d)

      if (rem1 === rem2)
        return BigInt(t);

      rem1 = rem1 * C_TEN % d;
      rem2 = rem2 * C_TEN % d;
    }
    return 0;
  }

  function gcd(a, b) {

    if (!a)
      return b;
    if (!b)
      return a;

    while (1) {
      a%= b;
      if (!a)
        return b;
      b%= a;
      if (!b)
        return a;
    }
  }

  /**
   * Module constructor
   *
   * @constructor
   * @param {number|Fraction=} a
   * @param {number=} b
   */
  function Fraction(a, b) {

    parse(a, b);

    if (this instanceof Fraction) {
      a = gcd(P["d"], P["n"]); // Abuse a
      this["s"] = P["s"];
      this["n"] = P["n"] / a;
      this["d"] = P["d"] / a;
    } else {
      return newFraction(P['s'] * P['n'], P['d']);
    }
  }

  var DivisionByZero = function() {return new Error("Division by Zero");};
  var InvalidParameter = function() {return new Error("Invalid argument");};
  var NonIntegerParameter = function() {return new Error("Parameters must be integer");};

  Fraction.prototype = {

    "s": C_ONE,
    "n": C_ZERO,
    "d": C_ONE,

    /**
     * Calculates the absolute value
     *
     * Ex: new Fraction(-4).abs() => 4
     **/
    "abs": function() {

      return newFraction(this["n"], this["d"]);
    },

    /**
     * Inverts the sign of the current fraction
     *
     * Ex: new Fraction(-4).neg() => 4
     **/
    "neg": function() {

      return newFraction(-this["s"] * this["n"], this["d"]);
    },

    /**
     * Adds two rational numbers
     *
     * Ex: new Fraction({n: 2, d: 3}).add("14.9") => 467 / 30
     **/
    "add": function(a, b) {

      parse(a, b);
      return newFraction(
        this["s"] * this["n"] * P["d"] + P["s"] * this["d"] * P["n"],
        this["d"] * P["d"]
      );
    },

    /**
     * Subtracts two rational numbers
     *
     * Ex: new Fraction({n: 2, d: 3}).add("14.9") => -427 / 30
     **/
    "sub": function(a, b) {

      parse(a, b);
      return newFraction(
        this["s"] * this["n"] * P["d"] - P["s"] * this["d"] * P["n"],
        this["d"] * P["d"]
      );
    },

    /**
     * Multiplies two rational numbers
     *
     * Ex: new Fraction("-17.(345)").mul(3) => 5776 / 111
     **/
    "mul": function(a, b) {

      parse(a, b);
      return newFraction(
        this["s"] * P["s"] * this["n"] * P["n"],
        this["d"] * P["d"]
      );
    },

    /**
     * Divides two rational numbers
     *
     * Ex: new Fraction("-17.(345)").inverse().div(3)
     **/
    "div": function(a, b) {

      parse(a, b);
      return newFraction(
        this["s"] * P["s"] * this["n"] * P["d"],
        this["d"] * P["n"]
      );
    },

    /**
     * Clones the actual object
     *
     * Ex: new Fraction("-17.(345)").clone()
     **/
    "clone": function() {
      return newFraction(this['s'] * this['n'], this['d']);
    },

    /**
     * Calculates the modulo of two rational numbers - a more precise fmod
     *
     * Ex: new Fraction('4.(3)').mod([7, 8]) => (13/3) % (7/8) = (5/6)
     **/
    "mod": function(a, b) {

      if (a === undefined) {
        return newFraction(this["s"] * this["n"] % this["d"], C_ONE);
      }

      parse(a, b);
      if (0 === P["n"] && 0 === this["d"]) {
        throw DivisionByZero();
      }

      /*
       * First silly attempt, kinda slow
       *
       return that["sub"]({
       "n": num["n"] * Math.floor((this.n / this.d) / (num.n / num.d)),
       "d": num["d"],
       "s": this["s"]
       });*/

      /*
       * New attempt: a1 / b1 = a2 / b2 * q + r
       * => b2 * a1 = a2 * b1 * q + b1 * b2 * r
       * => (b2 * a1 % a2 * b1) / (b1 * b2)
       */
      return newFraction(
        this["s"] * (P["d"] * this["n"]) % (P["n"] * this["d"]),
        P["d"] * this["d"]
      );
    },

    /**
     * Calculates the fractional gcd of two rational numbers
     *
     * Ex: new Fraction(5,8).gcd(3,7) => 1/56
     */
    "gcd": function(a, b) {

      parse(a, b);

      // gcd(a / b, c / d) = gcd(a, c) / lcm(b, d)

      return newFraction(gcd(P["n"], this["n"]) * gcd(P["d"], this["d"]), P["d"] * this["d"]);
    },

    /**
     * Calculates the fractional lcm of two rational numbers
     *
     * Ex: new Fraction(5,8).lcm(3,7) => 15
     */
    "lcm": function(a, b) {

      parse(a, b);

      // lcm(a / b, c / d) = lcm(a, c) / gcd(b, d)

      if (P["n"] === C_ZERO && this["n"] === C_ZERO) {
        return newFraction(C_ZERO, C_ONE);
      }
      return newFraction(P["n"] * this["n"], gcd(P["n"], this["n"]) * gcd(P["d"], this["d"]));
    },

    /**
     * Gets the inverse of the fraction, means numerator and denominator are exchanged
     *
     * Ex: new Fraction([-3, 4]).inverse() => -4 / 3
     **/
    "inverse": function() {
      return newFraction(this["s"] * this["d"], this["n"]);
    },

    /**
     * Calculates the fraction to some integer exponent
     *
     * Ex: new Fraction(-1,2).pow(-3) => -8
     */
    "pow": function(a, b) {

      parse(a, b);

      // Trivial case when exp is an integer

      if (P['d'] === C_ONE) {

        if (P['s'] < C_ZERO) {
          return newFraction((this['s'] * this["d"]) ** P['n'], this["n"] ** P['n']);
        } else {
          return newFraction((this['s'] * this["n"]) ** P['n'], this["d"] ** P['n']);
        }
      }

      // Negative roots become complex
      //     (-a/b)^(c/d) = x
      // <=> (-1)^(c/d) * (a/b)^(c/d) = x
      // <=> (cos(pi) + i*sin(pi))^(c/d) * (a/b)^(c/d) = x
      // <=> (cos(c*pi/d) + i*sin(c*pi/d)) * (a/b)^(c/d) = x       # DeMoivre's formula
      // From which follows that only for c=0 the root is non-complex
      if (this['s'] < C_ZERO) return null;

      // Now prime factor n and d
      let N = factorize(this['n']);
      let D = factorize(this['d']);

      // Exponentiate and take root for n and d individually
      let n = C_ONE;
      let d = C_ONE;
      for (let k in N) {
        if (k === '1') continue;
        if (k === '0') {
          n = C_ZERO;
          break;
        }
        N[k]*= P['n'];

        if (N[k] % P['d'] === C_ZERO) {
          N[k]/= P['d'];
        } else return null;
        n*= BigInt(k) ** N[k];
      }

      for (let k in D) {
        if (k === '1') continue;
        D[k]*= P['n'];

        if (D[k] % P['d'] === C_ZERO) {
          D[k]/= P['d'];
        } else return null;
        d*= BigInt(k) ** D[k];
      }

      if (P['s'] < C_ZERO) {
        return newFraction(d, n);
      }
      return newFraction(n, d);
    },

    /**
     * Check if two rational numbers are the same
     *
     * Ex: new Fraction(19.6).equals([98, 5]);
     **/
    "equals": function(a, b) {

      parse(a, b);
      return this["s"] * this["n"] * P["d"] === P["s"] * P["n"] * this["d"]; // Same as compare() === 0
    },

    /**
     * Check if two rational numbers are the same
     *
     * Ex: new Fraction(19.6).equals([98, 5]);
     **/
    "compare": function(a, b) {

      parse(a, b);
      let t = (this["s"] * this["n"] * P["d"] - P["s"] * P["n"] * this["d"]);

      return (C_ZERO < t) - (t < C_ZERO);
    },

    /**
     * Calculates the ceil of a rational number
     *
     * Ex: new Fraction('4.(3)').ceil() => (5 / 1)
     **/
    "ceil": function(places) {

      places = C_TEN ** BigInt(places || 0);

      return newFraction(this["s"] * places * this["n"] / this["d"] +
        (places * this["n"] % this["d"] > C_ZERO && this["s"] >= C_ZERO ? C_ONE : C_ZERO),
        places);
    },

    /**
     * Calculates the floor of a rational number
     *
     * Ex: new Fraction('4.(3)').floor() => (4 / 1)
     **/
    "floor": function(places) {

      places = C_TEN ** BigInt(places || 0);

      return newFraction(this["s"] * places * this["n"] / this["d"] -
        (places * this["n"] % this["d"] > C_ZERO && this["s"] < C_ZERO ? C_ONE : C_ZERO),
        places);
    },

    /**
     * Rounds a rational numbers
     *
     * Ex: new Fraction('4.(3)').round() => (4 / 1)
     **/
    "round": function(places) {

      places = C_TEN ** BigInt(places || 0);

      /* Derivation:

      s >= 0:
        round(n / d) = trunc(n / d) + (n % d) / d >= 0.5 ? 1 : 0
                     = trunc(n / d) + 2(n % d) >= d ? 1 : 0
      s < 0:
        round(n / d) =-trunc(n / d) - (n % d) / d > 0.5 ? 1 : 0
                     =-trunc(n / d) - 2(n % d) > d ? 1 : 0

      =>:

      round(s * n / d) = s * trunc(n / d) + s * (C + 2(n % d) > d ? 1 : 0)
          where C = s >= 0 ? 1 : 0, to fix the >= for the positve case.
      */

      return newFraction(this["s"] * places * this["n"] / this["d"] +
        this["s"] * ((this["s"] >= C_ZERO ? C_ONE : C_ZERO) + C_TWO * (places * this["n"] % this["d"]) > this["d"] ? C_ONE : C_ZERO),
        places);
    },

    /**
     * Check if two rational numbers are divisible
     *
     * Ex: new Fraction(19.6).divisible(1.5);
     */
    "divisible": function(a, b) {

      parse(a, b);
      return !(!(P["n"] * this["d"]) || ((this["n"] * P["d"]) % (P["n"] * this["d"])));
    },

    /**
     * Returns a decimal representation of the fraction
     *
     * Ex: new Fraction("100.'91823'").valueOf() => 100.91823918239183
     **/
    'valueOf': function() {
      // Best we can do so far
      return Number(this["s"] * this["n"]) / Number(this["d"]);
    },

    /**
     * Creates a string representation of a fraction with all digits
     *
     * Ex: new Fraction("100.'91823'").toString() => "100.(91823)"
     **/
    'toString': function(dec) {

      let N = this["n"];
      let D = this["d"];

      function trunc(x) {
          return typeof x === 'bigint' ? x : Math.floor(x);
      }

      dec = dec || 15; // 15 = decimal places when no repetition

      let cycLen = cycleLen(N, D); // Cycle length
      let cycOff = cycleStart(N, D, cycLen); // Cycle start

      let str = this['s'] < C_ZERO ? "-" : "";

      // Append integer part
      str+= trunc(N / D);

      N%= D;
      N*= C_TEN;

      if (N)
        str+= ".";

      if (cycLen) {

        for (let i = cycOff; i--;) {
          str+= trunc(N / D);
          N%= D;
          N*= C_TEN;
        }
        str+= "(";
        for (let i = cycLen; i--;) {
          str+= trunc(N / D);
          N%= D;
          N*= C_TEN;
        }
        str+= ")";
      } else {
        for (let i = dec; N && i--;) {
          str+= trunc(N / D);
          N%= D;
          N*= C_TEN;
        }
      }
      return str;
    },

    /**
     * Returns a string-fraction representation of a Fraction object
     *
     * Ex: new Fraction("1.'3'").toFraction() => "4 1/3"
     **/
    'toFraction': function(excludeWhole) {

      let n = this["n"];
      let d = this["d"];
      let str = this['s'] < C_ZERO ? "-" : "";

      if (d === C_ONE) {
        str+= n;
      } else {
        let whole = n / d;
        if (excludeWhole && whole > C_ZERO) {
          str+= whole;
          str+= " ";
          n%= d;
        }

        str+= n;
        str+= '/';
        str+= d;
      }
      return str;
    },

    /**
     * Returns a latex representation of a Fraction object
     *
     * Ex: new Fraction("1.'3'").toLatex() => "\frac{4}{3}"
     **/
    'toLatex': function(excludeWhole) {

      let n = this["n"];
      let d = this["d"];
      let str = this['s'] < C_ZERO ? "-" : "";

      if (d === C_ONE) {
        str+= n;
      } else {
        let whole = n / d;
        if (excludeWhole && whole > C_ZERO) {
          str+= whole;
          n%= d;
        }

        str+= "\\frac{";
        str+= n;
        str+= '}{';
        str+= d;
        str+= '}';
      }
      return str;
    },

    /**
     * Returns an array of continued fraction elements
     *
     * Ex: new Fraction("7/8").toContinued() => [0,1,7]
     */
    'toContinued': function() {

      let a = this['n'];
      let b = this['d'];
      let res = [];

      do {
        res.push(a / b);
        let t = a % b;
        a = b;
        b = t;
      } while (a !== C_ONE);

      return res;
    },

    "simplify": function(eps) {

      eps = eps || 0.001;

      const thisABS = this['abs']();
      const cont = thisABS['toContinued']();

      for (let i = 1; i < cont.length; i++) {

        let s = newFraction(cont[i - 1], C_ONE);
        for (let k = i - 2; k >= 0; k--) {
          s = s['inverse']()['add'](cont[k]);
        }

        if (Math.abs(s['sub'](thisABS).valueOf()) < eps) {
          return s['mul'](this['s']);
        }
      }
      return this;
    }
  };

  if (typeof define === "function" && define["amd"]) {
    define([], function() {
      return Fraction;
    });
  } else if (typeof exports === "object") {
    Object.defineProperty(exports, "__esModule", { 'value': true });
    Fraction['default'] = Fraction;
    Fraction['Fraction'] = Fraction;
    module['exports'] = Fraction;
  } else {
    root['Fraction'] = Fraction;
  }

})(this);