BenfordsLaw
// This source code is subject to the terms of the Mozilla Public License 2.0 at https://mozilla.org/MPL/2.0/
// © RicardoSantos

//@version=5

// @description Methods to deal with Benford's law which states that a distribution of first and higher order digits
// of numerical strings has a characteristic pattern.
//	"Benford's law is an observation about the leading digits of the numbers found in real-world data sets. 
// Intuitively, one might expect that the leading digits of these numbers would be uniformly distributed so that 
// each of the digits from 1 to 9 is equally likely to appear. In fact, it is often the case that 1 occurs more 
// frequently than 2, 2 more frequently than 3, and so on. This observation is a simplified version of Benford's law. 
// 	More precisely, the law gives a prediction of the frequency of leading digits using base-10 logarithms that 
// predicts specific frequencies which decrease as the digits increase from 1 to 9." ~(2)
// ---
// reference:
// - 1: https://en.wikipedia.org/wiki/Benford%27s_law
// - 2: https://brilliant.org/wiki/benfords-law/
// - 4: https://github.com/vineettanna/Benfords-Law/tree/master
library("BenfordsLaw")

//#region	0:
//#region	0.1: Imports.

import RicardoSantos/MathExtension/2 as me
import RicardoSantos/DebugConsole/13 as console

//#endregion	0.1
//#region	0.2: Variables.

console.Console logger = console.new()

//#endregion	0.2
//#endregion	0
//#region	1: Helpers.
//#region	1.1: cumsum_difference ()

// @function Calculate the cumulative sum difference of two arrays of same size.
// @param a `array<float>` List of values.
// @param b `array<float>` List of values.
// @returns List with CumSum Difference between arrays.
export cumsum_difference (array<float> a, array<float> b) =>
	switch
		a.size() != b.size() => runtime.error('Array `b` size does not match `a` size.')
	array<float> _csdiff = array.new<float>(a.size())
	float _asum = 0.0
	float _bsum = 0.0
	for [_i, _ai] in a
		_asum += _ai
		_bsum += b.get(_i)
		_csdiff.set(_i, math.abs(_asum - _bsum))
	_csdiff

//#endregion	1.1
//#region	1.2: Methods for processing numbers.
//#region	1.2.0: fractional_int ()

// @function Transform a floating number including its fractional part to integer form ex:. `1.2345 -> 12345`.
// @param number `float` The number to transform.
// @returns Transformed number.
export fractional_int (float number) =>
	float _n = number
	while me.fractional(_n) != 0
		_n *= 10
	int(_n)

//#endregion	1.2.0
//#region	1.2.1: split_to_digits ()

// @function Transforms a integer number into a list of its digits.
// @param number  `int`  Number to transform.
// @param reverse `bool` `default=true`, Reverse the order of the digits, if true, last will be first.
// @returns Transformed number digits list.
export split_to_digits (int number, bool reverse=true) =>
	int _n = number
	array<int> _digits = array.new<int>(0)
	if reverse
		while _n > 0
			_digits.push(_n % 10)
			_n := int(_n / 10)
	else
		while _n > 0
			_digits.unshift(_n % 10)
			_n := int(_n / 10)
	_digits

//#endregion	1.2.1
//#region	1.2.2: digit_in ()

// @function Digit at index.
// @param number `int` Number to parse.
// @param digit  `int` `default=0`, Index of digit.
// @returns Digit found at the index.
export digit_in (int number, int digit=0) =>
	array<int> _n = split_to_digits(number, false)
	if digit < _n.size()
		_n.get(digit)
	else
		int(na)

//#endregion	1.2.2
//#endregion	1.2
//#region	1.3: Methods to extract digit information from lists of numbers.
//#region	1.3.0: digits_from ()

// @function Process a list of `int` values and get the list of digits.
// @param data   `array<int>` List of numbers.
// @param dindex `int`        `default=0`, Index of digit.
// @returns List of digits at the index.
export digits_from (array<int> data, int dindex=0) =>
	_clean = array.new<int>(0)
	for [_i, _e] in data
		int _d = digit_in(_e, dindex)
		if _d != 0 and not na(_d)
			_clean.push(_d)
	_clean

//#endregion	1.3.0
//#region	1.3.1: digit_counters () 

// @function Score digits.
// @param digits `array<int>` List of digits.
// @returns List of counters per digit (1-9).
export digit_counters (array<int> digits) =>
	switch
		digits.min() < 0 => runtime.error('Digits must be positive integers.')
		digits.max() > 9 => runtime.error('Not a single digit.')
	array<int> _counters = array.new<int>(9, 0)
	array<int> _sorted = digits.copy()		, _sorted.sort()
	int _base_idx = 0
	for _i = 1 to 9
		int _idx = _sorted.lastindexof(_i)
		if _idx >= 0
			_counters.set(_i-1, _idx - _base_idx)
			_base_idx := _idx
	_counters

//#endregion	1.3.1
//#region	1.3.2: digit_distribution () 

// @function Calculates the frequency distribution based on counters provided.
// @param counters `array<int>` List of counters, must have size(9).
// @returns Distribution of the frequency of the digits.
export digit_distribution (array<int> counters) =>
	switch
		counters.size() != 9 => runtime.error('Counters list must have size 9.')
	int _sum = counters.sum()
	array<float> _distribution = array.new<float>(9, 0.0)
	for _i = 0 to 8 // array index starts at 0
		_distribution.set(_i, counters.get(_i) / _sum)
	_distribution

//#endregion	1.3.2
//#endregion	1.3
//#region	1.4: Benford's Law Expected Distribution.
//#region	1.4.0: digit_p (): Expected probability for digit.

// P(d|i) = log10(1 + 1 / d)
// where i = 1 and 1 <= d <= 9

// @function Expected probability for digit according to Benford.
// @param digit `int` Digit number reference in range `1 -> 9`.
// @returns Probability of digit according to Benford's law.
export digit_p (int digit) =>
	switch 
		digit < 1 and digit > 9 => runtime.error('Must provide a integer digit within 1 >= d <= 9 range')
	math.log10(1.0 + 1.0 / digit)

//#endregion	1.4.0
//#region	1.4.1: benfords_distribution ()

// @function Calculated Expected distribution per digit according to Benford's Law.
// @returns List with the expected distribution.
export benfords_distribution () =>
	_b = array.new<float>(9)
	for _i = 1 to 9
		_b.set(_i, digit_p(_i))
	_b

//#endregion	1.4.1
//#region	1.4.2: benfords_distribution_aprox ()

// @function Aproximate Expected distribution per digit according to Benford's Law.
// @returns List with the expected distribution.
export benfords_distribution_aprox () => 
	//                1         2         3         4         5         6         7         8         9
	array.from(0.301030, 0.176091, 0.124939, 0.096910, 0.079181, 0.066947, 0.057992, 0.051153, 0.045757)

// int d = input.int(1)
// plot(benfords_distribution(d))

//#endregion	1.4.2
//#endregion	1.4
//#endregion	1
//#region	2: Test.
//#region	2.0: Calculate the distribution and error.

// @function Tests Benford's Law on provided list of digits.
// @param digits `array<int>` List of digits.
// @returns Tuple with:
// - Counters: Score of each digit.
// - Sample distribution: Frequency for each digit.
// - Expected distribution: Expected frequency according to Benford's.
// - Cumulative Sum of difference: 
export test_benfords (array<int> digits, bool calculate_benfords=false) =>
	array<int>   _series_counters       = digit_counters(digits)
	array<float> _series_distribution   = digit_distribution(_series_counters)
	array<float> _benfords_distribution = calculate_benfords? benfords_distribution() : benfords_distribution_aprox()
	array<float> _cumsum_difference     = cumsum_difference(_series_distribution, _benfords_distribution)
	[_series_counters, _series_distribution, _benfords_distribution, _cumsum_difference]

//#endregion	2.0
//#region	2.1: Display results to a table.

// @function Runs the test and displays the tested data in a table.
// @param digits        `array<int>` List of digits.
// @param _text_color   `color`      `default=#e3e3e3`, Color of the table text.
// @param _border_color `color`      `default=#a0a0a0`, Color of the table border.
// @param _frame_color  `color`      `default=#5a5a5a`, Color of the table frame.
export to_table (
 array<int> digits                    ,
 color      _text_color   = #e3e3e3 ,
 color      _border_color = #a0a0a0 ,
 color      _frame_color  = #5a5a5a ) =>
	[_scounters, _sdist, _bdist, _csdiff] = test_benfords(digits)
	_T = table.new(position.top_right, 6, 11, #000000, _frame_color, 3, _border_color, 1)
	_T.cell(0, 0, 'Digit:'                , text_color=_text_color)
	_T.cell(1, 0, 'Counters:'             , text_color=_text_color)
	_T.cell(2, 0, 'Actual Distribution:'  , text_color=_text_color)
	_T.cell(3, 0, 'Expected Distribution:', text_color=_text_color)
	_T.cell(4, 0, 'Cum. Sum. Difference:' , text_color=_text_color)
	for _i = 1 to 9
		_idx = _i - 1
		_T.cell(0, _i, str.tostring(_i)                  , text_color=_text_color)
		_T.cell(1, _i, str.tostring(_scounters.get(_idx)), text_color=_text_color)
		_T.cell(2, _i, str.tostring(_sdist.get(_idx))    , text_color=_text_color)
		_T.cell(3, _i, str.tostring(_bdist.get(_idx))    , text_color=_text_color)
		_T.cell(4, _i, str.tostring(_csdiff.get(_idx))   , text_color=_text_color)
	float _actual = _csdiff.max()
	float _cuttoff = 1.36 / math.sqrt(_scounters.sum())
	bool _is_benfords = _actual <= _cuttoff
	_T.cell(2, 10, str.format('actual: {0}', _actual)         , text_color=_text_color)
	_T.cell(3, 10, str.format('cuttoff: {0}', _cuttoff)       , text_color=_text_color)
	_T.cell(4, 10, str.format('is benford? {0}', _is_benfords), text_color=_text_color)
	//
	_T

//#endregion	2.1
//#endregion	2
//#region	3: Example.
//#region	3.0: Inputs.

int window = input.int(100)
int idx    = input.int(0)

//#endregion	3.0
//#region	3.1: Extract digits from price data.

int price = math.round(close * 100000)
var array<int> prices = array.new<int>(window, price)
prices.unshift(price), prices.pop()
digits = digits_from(prices, idx)

//#endregion	3.1
//#region	3.2: Output.

to_table(digits)

logger.queue(str.tostring(digits))

// if barstate.islast
// 	digits = array.new<int>(100)
// 	for _i=0 to 99
// 		digits.set(_i, math.round(math.random() * 100000))
// 	digits := digits_from(digits, idx)
// 	test_benfords_to_table(digits)
// 	logger.queue_one(str.tostring(digits))

logger.update()
//#endregion	3.2
//#endregion	3