# MIT License, Copyright (c) 2022 Marvin Borner
# ternary implementation of T.Æ. Mogensen and Douglas W. Jones (see refs in README)
# → refer to std/Math for more advanced functions

:import std/Box B
:import std/Combinator .
:import std/Logic .
:import std/Pair .

# negative trit indicating coefficient of (-1)
t⁻ [[[2]]] ⧗ Trit

# positive trit indicating coefficient of (+1)
t⁺ [[[1]]] ⧗ Trit

# zero trit indicating coefficient of 0
t⁰ [[[0]]] ⧗ Trit

# returns true if a trit is negative
t⁻? [0 true false false] ⧗ Trit → Boolean

:test (t⁻? t⁻) (true)
:test (t⁻? t⁺) (false)
:test (t⁻? t⁰) (false)

# returns true if a trit is positive
t⁺? [0 false true false] ⧗ Trit → Boolean

:test (t⁺? t⁻) (false)
:test (t⁺? t⁺) (true)
:test (t⁺? t⁰) (false)

# returns true if a trit is zero
t⁰? [0 false false true] ⧗ Trit → Boolean

:test (t⁰? t⁻) (false)
:test (t⁰? t⁺) (false)
:test (t⁰? t⁰) (true)

# shifts a negative trit into a balanced ternary number
↑⁻‣ [[[[[2 (4 3 2 1 0)]]]]] ⧗ Number → Number

:test (↑⁻(+0)) ((-1))
:test (↑⁻(-1)) ((-4))
:test (↑⁻(+42)) ((+125))

# shifts a positive trit into a balanced ternary number
↑⁺‣ [[[[[1 (4 3 2 1 0)]]]]] ⧗ Number → Number

:test (↑⁺(+0)) ((+1))
:test (↑⁺(-1)) ((-2))
:test (↑⁺(+42)) ((+127))

# shifts a zero trit into a balanced ternary number
↑⁰‣ [[[[[0 (4 3 2 1 0)]]]]] ⧗ Number → Number

:test (↑⁰(+0)) ([[[[0 3]]]])
:test (↑⁰(+1)) ((+3))
:test (↑⁰(+42)) ((+126))

# shifts a specified trit into a balanced ternary number
up [[[[[[5 2 1 0 (4 3 2 1 0)]]]]]] ⧗ Trit → Number → Number

:test (up t⁻ (+42)) (↑⁻(+42))
:test (up t⁺ (+42)) (↑⁺(+42))
:test (up t⁰ (+42)) (↑⁰(+42))

# infinity
# WARNING: using this mostly results in undefined behavior! (TODO?)
infty z [[[[[1 (4 1)]]]]] ⧗ Number

# negates a balanced ternary number
negate [[[[[4 3 1 2 0]]]]] ⧗ Number → Number

-‣ negate

:test (-(+0)) ((+0))
:test (-(-1)) ((+1))
:test (-(+42)) ((-42))

# converts a balanced ternary number to a list of trits
list! [0 z a⁻ a⁺ a⁰] ⧗ Number → List
	z [[0]]
	a⁻ [t⁻ : 0]
	a⁺ [t⁺ : 0]
	a⁰ [t⁰ : 0]

# TODO: Tests!

# strips leading 0s from a balanced ternary number
strip [^(0 z a⁻ a⁺ a⁰)] ⧗ Number → Number
	z (+0) : true
	a⁻ &[[↑⁻1 : false]]
	a⁺ &[[↑⁺1 : false]]
	a⁰ &[[(0 (+0) ↑⁰1) : 0]]

%‣ strip

:test (%[[[[0 3]]]]) ((+0))
:test (%[[[[2 (0 (0 (0 (0 3))))]]]]) ((-1))
:test (%(+42)) ((+42))

# returns true if balanced ternary number is zero
zero? [0 true [false] [false] i] ⧗ Number → Boolean

=?‣ zero?

:test (=?(+0)) (true)
:test (=?(-1)) (false)
:test (=?(+1)) (false)
:test (=?(+42)) (false)

# returns true if balanced ternary number is not zero
not-zero? [0 false [true] [true] i] ⧗ Number → Boolean

≠?‣ not-zero?

:test (≠?(+0)) (false)
:test (≠?(-1)) (true)
:test (≠?(+1)) (true)
:test (≠?(+42)) (true)

# extracts least significant trit from a balanced ternary number
lst [0 t⁰ [t⁻] [t⁺] [t⁰]] ⧗ Number → Trit

:test (lst (-1)) (t⁻)
:test (lst (+0)) (t⁰)
:test (lst (+1)) (t⁺)
:test (lst (+42)) (t⁰)

# extracts most significant trit from a balanced ternary number
mst [B.get t⁰ (0 z a⁻ a⁺ a⁰)] ⧗ Number → Trit
	z B.empty
	a⁻ [B.store! 0 t⁻]
	a⁺ [B.store! 0 t⁺]
	a⁰ [0]

:test (mst (-1)) (t⁻)
:test (mst (+0)) (t⁰)
:test (mst (+1)) (t⁺)
:test (mst (+42)) (t⁺)

# returns true if balanced ternary number is negative
negative? t⁻? ∘ mst ⧗ Number → Boolean

<?‣ negative?

:test (<?(+0)) (false)
:test (<?(-1)) (true)
:test (<?(+1)) (false)
:test (<?(+42)) (false)

# returns true if balanced ternary number is positive
positive? t⁺? ∘ mst ⧗ Number → Boolean

>?‣ positive?

:test (>?(+0)) (false)
:test (>?(-1)) (false)
:test (>?(+1)) (true)
:test (>?(+42)) (true)

# converts the normal balanced ternary representation into abstract
# infinity can't be abstracted in finite time
# → the abstract representation is used in eq?/add/sub/mul
abstract! [0 z a⁻ a⁺ a⁰] ⧗ Number → AbstractNumber
	z (+0)
	a⁻ [[[[[2 4]]]]]
	a⁺ [[[[[1 4]]]]]
	a⁰ [[[[[0 4]]]]]

→^‣ abstract!

:test (→^(-3)) ([[[[0 [[[[2 [[[[3]]]]]]]]]]]])
:test (→^(+0)) ([[[[3]]]])
:test (→^(+3)) ([[[[0 [[[[1 [[[[3]]]]]]]]]]]])

# converts the abstracted balanced ternary representation back to normal
normal! y [[0 z a⁻ a⁺ a⁰]] ⧗ AbstractNumber → Number
	z (+0)
	a⁻ [↑⁻(2 0)]
	a⁺ [↑⁺(2 0)]
	a⁰ [↑⁰(2 0)]

→_‣ normal!

:test (→_[[[[3]]]]) ((+0))
:test (→_(→^(+42))) ((+42))
:test (→_(→^(-42))) ((-42))

# returns true if two balanced ternary numbers are equal
# → ignores leading 0s!
eq? [[abs 1 →^0]] ⧗ Number → Number → Boolean
	abs [0 z a⁻ a⁺ a⁰]
		z [=?(→_0)]
		a⁻ [[0 false [2 0] [false] [false]]]
		a⁺ [[0 false [false] [2 0] [false]]]
		a⁰ [[0 (1 0) [false] [false] [2 0]]]

…=?… eq?

# returns true if two balanced ternary numbers are not equal
not-eq? not! ∘∘ eq? ⧗ Number → Number → Boolean

…≠?… not-eq?

:test ((-42) =? (-42)) (true)
:test ((-1) =? (-1)) (true)
:test ((-1) =? (+0)) (false)
:test ((+0) =? (+0)) (true)
:test ((+1) =? (+0)) (false)
:test ((+1) =? (+1)) (true)
:test ((+42) =? (+42)) (true)
:test ([[[[(1 (0 (0 (0 (0 3)))))]]]] =? (+1)) (true)
:test ((+1) ≠? (+0)) (true)
:test ((-42) ≠? (+42)) (true)

# adds (+1) to a balanced ternary number (can introduce leading 0s)
inc [~(0 z a⁻ a⁺ a⁰)] ⧗ Number → Number
	z (+0) : (+1)
	a⁻ &[[↑⁻1 : ↑⁰1]]
	a⁺ &[[↑⁺1 : ↑⁻0]]
	a⁰ &[[↑⁰1 : ↑⁺1]]

++‣ inc

:test (++(-42) =? (-41)) (true)
:test (++(-1) =? (+0)) (true)
:test (++(+0) =? (+1)) (true)
:test (++(++(++(++(++(+0))))) =? (+5)) (true)
:test (++(+42) =? (+43)) (true)

# subs (+1) from a balanced ternary number (can introduce leading 0s)
dec [~(0 z a⁻ a⁺ a⁰)] ⧗ Number → Number
	z (+0) : (-1)
	a⁻ &[[↑⁻1 : ↑⁺0]]
	a⁺ &[[↑⁺1 : ↑⁰1]]
	a⁰ &[[↑⁰1 : ↑⁻1]]

--‣ dec

:test (--(-42) =? (-43)) (true)
:test (--(+0) =? (-1)) (true)
:test (--(--(--(--(--(+5))))) =? (+0)) (true)
:test (--(+1) =? (+0)) (true)
:test (--(+42) =? (+41)) (true)

# adds two balanced ternary numbers (can introduce leading 0s)
add [[abs 1 →^0]] ⧗ Number → Number → Number
	abs [c (0 z a⁻ a⁺ a⁰)]
		b⁻ [1 ↑⁺(3 0 t⁻) ↑⁰(3 0 t⁰) ↑⁻(3 0 t⁰)]
		b⁰ [up 1 (3 0 t⁰)]
		b⁺ [1 ↑⁰(3 0 t⁰) ↑⁻(3 0 t⁺) ↑⁺(3 0 t⁰)]
		a⁻ [[[1 (b⁻ 1) b⁻' b⁰ b⁻]]]
			b⁻' [1 ↑⁰(3 0 t⁻) ↑⁻(3 0 t⁰) ↑⁺(3 0 t⁻)]
		a⁺ [[[1 (b⁺ 1) b⁰ b⁺' b⁺]]]
			b⁺' [1 ↑⁺(3 0 t⁰) ↑⁰(3 0 t⁺) ↑⁻(3 0 t⁺)]
		a⁰ [[[1 (b⁰ 1) b⁻ b⁺ b⁰]]]
		z [[0 --(→_1) ++(→_1) →_1]]
		c [[1 0 t⁰]]

…+… add

:test ((-42) + (-1) =? (-43)) (true)
:test ((-5) + (+6) =? (+1)) (true)
:test ((-1) + (+0) =? (-1)) (true)
:test ((+0) + (+0) =? (+0)) (true)
:test ((+1) + (+2) =? (+3)) (true)
:test ((+42) + (+1) =? (+43)) (true)

# subs two balanced ternary numbers (can introduce leading 0s)
sub [[1 + -0]] ⧗ Number → Number → Number

…-… sub

:test ((-42) - (-1) =? (-41)) (true)
:test ((-5) - (+6) =? (-11)) (true)
:test ((-1) - (+0) =? (-1)) (true)
:test ((+0) - (+0) =? (+0)) (true)
:test ((+1) - (+2) =? (-1)) (true)
:test ((+42) - (+1) =? (+41)) (true)

# returns true if number is greater than other number
gre? positive? ∘∘ sub ⧗ Number → Number → Boolean

…>?… gre?

:test ((+1) >? (+2)) (false)
:test ((+2) >? (+2)) (false)
:test ((+3) >? (+2)) (true)

# returns true if number is less than other number
les? \gre? ⧗ Number → Number → Boolean

…<?… les?

:test ((+1) <? (+2)) (true)
:test ((+2) <? (+2)) (false)
:test ((+3) <? (+2)) (false)

# returns true if number is less than or equal to other number
leq? not! ∘∘ gre? ⧗ Number → Number → Boolean

…≤?… leq?

:test ((+1) ≤? (+2)) (true)
:test ((+2) ≤? (+2)) (true)
:test ((+3) ≤? (+2)) (false)

# returns true if number is greater than or equal to other number
geq? \leq? ⧗ Number → Number → Boolean

…≥?… geq?

:test ((+1) ≥? (+2)) (false)
:test ((+2) ≥? (+2)) (true)
:test ((+3) ≥? (+2)) (true)

# returns eq, lt, gt depending on comparison of two numbers
compare-case [[[[[go (1 - 0)]]]]] ⧗ a → b → c → Number → Number → d
	go [=?0 5 (>?0 4 3)]

# returns 1 if a>b, -1 if a<b and 0 if a=b
# also: spaceship operator
compare compare-case (+0) (+1) (-1) ⧗ Number → Number → Number

:test (compare (+2) (+2)) ((+0))
:test (compare (+2) (+1)) ((+1))
:test (compare (+1) (+2)) ((-1))

…<=>… compare

# negates a balanced ternary number if <0
abs [<?0 -0 0] ⧗ Number → Number

|‣ abs

:test (|(+0)) ((+0))
:test (|(-1)) ((+1))
:test (|(+42)) ((+42))

# apply a function n times to a value
# ~> substitute church numbers
apply z [[[rec]]] ⧗ Number → (a → a) → a → a
	rec =?1 case-end case-apply
		case-apply 0 ∘ (2 --1 0)
		case-end i

:test (apply (+5) ++‣ (+3)) ((+8))

# muls two balanced ternary numbers (can introduce leading 0s)
mul [[1 z a⁻ a⁺ a⁰]] ⧗ Number → Number → Number
	z (+0)
	a⁻ [↑⁰0 - 1]
	a⁺ [↑⁰0 + 1]
	a⁰ [↑⁰0]

…⋅… mul

:test ((+42) ⋅ (+0) =? (+0)) (true)
:test ((-1) ⋅ (+42) =? (-42)) (true)
:test ((+3) ⋅ (+11) =? (+33)) (true)
:test ((+42) ⋅ (-4) =? (-168)) (true)

# rshifts least significant trit of a balanced ternary number
# WARNING: Not necessarily equivalent to (/ (+3)): e.g. /³(+5) == (+2)!
div³ [~(0 z a⁻ a⁺ a⁰)] ⧗ Number → Number
	z (+0) : (+0)
	a⁻ &[[↑⁻1 : 1]]
	a⁺ &[[↑⁺1 : 1]]
	a⁰ &[[↑⁰1 : 1]]

/³‣ div³

:test (/³(+6)) ((+2))
:test (/³(-6)) ((-2))
:test (/³(+5)) ((+2))

# divs a balanced ternary number by two (binary >>1)
div² [z [[[[rec]]]] (+0) 0 0] ⧗ Number → Number
	rec =?1 case-end case-div
		case-div 3 /³(2 + 0) /³1 0
		case-end 2

/²‣ div²

:test (/²(+6) =? (+3)) (true)
:test (/²(-6) =? (-3)) (true)
:test (/²(+5) =? (+2)) (true)

# divs a balanced ternary number by three by fixing rshift
/³*‣ [fix /³0]
	fix [/²(1 - 0)]

:test (/³*(+6) =? (+2)) (true)
:test (/³*(-6) =? (-2)) (true)
:test (/³*(+5) =? (+1)) (true)

# returns the smallest number in a range such that a predicate is true
binary-search z [[[[rec]]]] ⧗ (Number → Boolean) → Number → Number → Number
	rec (0 =? 1) case-end case-search
		case-search go /²(0 + 1)
			go [3 0 (4 3 2 0) (4 3 ++0 1)]
		case-end 0

:test (binary-search [(0 ⋅ 0) >? (+150)] (+0) (+100)) ((+13))

# returns the maximum of a unimodal function in a specified domain
ternary-search z [[[[rec]]]] ⧗ (Number → Number) → Number → Number → Number
	rec (1 =? 0) case-end case-search
		case-search go (1 + /³*(0 - 1)) (0 - /³*(0 - 1))
			call [=?0 (6 5 ++2 --1) (>?0 (6 5 4 --1) (6 5 ++2 3))]
			go [[call ((4 1) - (4 0))]]
		case-end 0

:test ((ternary-search [-((0 - (+3)) ⋅ (0 - (+3)))] (+0) (+5)) =? (+3)) (true)

# finds quotient and remainder using binary search
# TODO: fix for numbers <=1 (case analysis, q,r<0)
# TODO: faster algorithm
quot-rem [[go --(binary-search [0 ⋅ 1 >? 2] (+0) 1)]] ⧗ Number → Number → (Pair Number Number)
	go [0 : (2 - (1 ⋅ 0))]

# divs two balanced ternary numbers
div ^‣ ∘∘ quot-rem ⧗ Number → Number

…/… div

:test ((+42) / (+4) =? (+10)) (true)
:test ((+5) / (+3) =? (+1)) (true)

# returns remainder of integer division
mod ~‣ ∘∘ quot-rem ⧗ Number → Number

…%… mod

:test ((+42) % (+4) =? (+2)) (true)
:test ((+7) % (+3) =? (+1)) (true)
:test ((+8) % (+2) =? (+0)) (true)

# returns true if the number is even (remainder mod 2 == 0)
# TODO: faster solution (using tupling?)
even? z [[rec]] ⧗ Number → Boolean
	rec =?0 case-end case-rec
		case-rec t⁰? (lst 0) (1 /³0) ¬(1 /³0)
		case-end true

=²?‣ even?

:test (=²?(+0)) (true)
:test (=²?(+1)) (false)
:test (=²?(+41)) (false)
:test (=²?(+42)) (true)

# returns true if the number is odd (remainder mod 2 == 1)
odd? ¬‣ ∘ even? ⧗ Number → Boolean

≠²?‣ odd?

:test (≠²?(+0)) (false)
:test (≠²?(+1)) (true)
:test (≠²?(+41)) (true)
:test (≠²?(+42)) (false)

# returns max number of two
max [[(1 ≤? 0) 0 1]] ⧗ Number → Number → Number

:test (max (+5) (+2)) ((+5))

# returns min number of two
min [[(1 ≤? 0) 1 0]] ⧗ Number → Number → Number

:test (min (+5) (+2)) ((+2))

# clamps a number between two numbers
clamp [[[min 1 (max 0 2)]]] ⧗ Number → Number → Number

:test (clamp (+0) (+5) (+3)) ((+3))
:test (clamp (+0) (+5) (-2)) ((+0))
:test (clamp (+0) (+5) (+7)) ((+5))