// Provides the basic functionality to interact with the Collatz conjecture. The
// parameterisation uses the same (P,a,b) notation as Conway's generalisations.
// Besides the function and reverse function, there is also functionality to
// retrieve the hailstone sequence, the "stopping time"/"total stopping time",
// or tree-graph.
//  import collatz "github.com/Skenvy/Collatz/go"
package collatz

import (
        "fmt"
        "math"
        "math/big"
)

////////////////////////////////////////////////////////////////////////////////
// Define a series of "constants", the _go_ way. We want default P, a, and b
// values, "known cycles", verified maximum and minimum, all as constants, but
// neither arrays, slices, or big.Int can be constant, so we need funcs instead.
////////////////////////////////////////////////////////////////////////////////

// Default value for P, the modulus condition.
const _DEFAULT_P int64 = 2

// Default value for a, the input's multiplicand.
const _DEFAULT_A int64 = 3

// Default value for b, the value added to the multiplied value.
const _DEFAULT_B int64 = 1

// Returns DEFAULT_P, the default value for P,
// the modulus condition.
func DEFAULT_P() (DEFAULT_P *big.Int) {
        return big.NewInt(_DEFAULT_P)
}

// Returns DEFAULT_A, the default value for a,
// the input's multiplicand.
func DEFAULT_A() (DEFAULT_A *big.Int) {
        return big.NewInt(_DEFAULT_A)
}

// Returns DEFAULT_B, the default value for b,
// the value added to the multiplied value.
func DEFAULT_B() (DEFAULT_B *big.Int) {
        return big.NewInt(_DEFAULT_B)
}

// Return a big.Int with a value of 0.
func ZERO() (ZERO *big.Int) {
        return big.NewInt(0)
}

// Return a big.Int with a value of 1.
func ONE() (ONE *big.Int) {
        return big.NewInt(1)
}

// Map an array of ints to an array of big ints, for some mapping function.
func mapIntsToBigIntsGeneric(ai *[]int64, m func(int64) *big.Int) *[]*big.Int {
        aim := make([]*big.Int, len(*ai))
        for index, value := range *ai {
                aim[index] = m(value)
        }
        return &aim
}

// Map an array of ints to an array of big ints with the same value.
func mapIntsToBigInts(ai *[]int64) *[]*big.Int {
        return mapIntsToBigIntsGeneric(ai, func(value int64) *big.Int { return big.NewInt(value) })
}

// The four KNOWN_CYCLES for the standard parameterisation.
func KNOWN_CYCLES() (KNOWN_CYCLES [4]*[]*big.Int) {
        return [4]*[]*big.Int{mapIntsToBigInts(&[]int64{1, 4, 2}), mapIntsToBigInts(&[]int64{-1, -2}),
                mapIntsToBigInts(&[]int64{-5, -14, -7, -20, -10}),
                mapIntsToBigInts(&[]int64{-17, -50, -25, -74, -37, -110, -55, -164, -82, -41, -122, -61, -182, -91, -272, -136, -68, -34})}
}

// The current value up to which the standard parameterisation has been verified.
func VERIFIED_MAXIMUM() (VERIFIED_MAXIMUM *big.Int) {
        VERIFIED_MAXIMUM = new(big.Int)
        VERIFIED_MAXIMUM, ok := VERIFIED_MAXIMUM.SetString("295147905179352825856", 10)
        if !ok {
                fmt.Println("__VERIFIED_MAXIMUM: SetString: error")
                return big.NewInt(1)
        }
        return VERIFIED_MAXIMUM
}

// The current value down to which the standard parameterisation has been verified.
func VERIFIED_MINIMUM() (VERIFIED_MINIMUM *big.Int) {
        //TODO: Check the actual lowest bound.
        return big.NewInt(-272)
}

////////////////////////////////////////////////////////////////////////////////
// Define the enums. A stringy struct is a more readable way of making an enum,
// but a struct cannot be const, only var. So instead our pattern for enums is
// to make a new type of int64, set constants of this new type, and then have a
// function that acts on instances of the new type to return their strings. Also
// include another new type that includes one of the new int64 types and has an
// Error() function that prints the message associated with the Error Message
// type, to satisfy the error interface, with a custom error of few messages.
////////////////////////////////////////////////////////////////////////////////

// Error message constants, to be used as input to the FailedSaneParameterCheck
type SaneParameterErrMsg int64

const (
        // Message to print in the FailedSaneParameterCheck if P, the modulus, is zero.
        SANE_PARAMS_P SaneParameterErrMsg = iota
        // Message to print in the FailedSaneParameterCheck if a, the multiplicand, is zero.
        SANE_PARAMS_A
)

// Get the string associated with the SaneParameterErrMsg
func (spem SaneParameterErrMsg) String() (ErrorMessage string) {
        switch spem {
        case SANE_PARAMS_P:
                return "'P' should not be 0 ~ violates modulo being non-zero."
        case SANE_PARAMS_A:
                return "'a' should not be 0 ~ violates the reversability."
        }
        return "unknown"
}

// Thrown when either P, the modulus, or a, the
// multiplicand, are zero. Create as either or;
//  FailedSaneParameterCheck(SANE_PARAMS_P)
//  FailedSaneParameterCheck(SANE_PARAMS_A)
type FailedSaneParameterCheck SaneParameterErrMsg

// Construct a FailedSaneParameterCheck with
// a message associated with the provided enum.
func (fspc FailedSaneParameterCheck) Error() string {
        return fmt.Sprint(SaneParameterErrMsg(fspc).String())
}

// SequenceState for Cycle Control: Descriptive flags to indicate
// when some event occurs in the hailstone sequences or tree graph
// reversal, when set to verbose, or stopping time check.
type SequenceState int64

const (
        // A TreeGraph sequence state that indicates the lack
        // of another state, as this state can't be nil
        NO_STATE SequenceState = iota
        // A Hailstone sequence state that indicates the stopping
        // time, a value less than the initial, has been reached.
        STOPPING_TIME
        // A Hailstone sequence state that indicates the total
        // stopping time, a value of 1, has been reached.
        TOTAL_STOPPING_TIME
        // A Hailstone and TreeGraph sequence state that indicates the
        // first occurence of a value that subsequently forms a cycle.
        CYCLE_INIT
        // A Hailstone and TreeGraph sequence state that indicates the
        // last occurence of a value that has already formed a cycle.
        CYCLE_LENGTH
        // A Hailstone and TreeGraph sequence state that indicates the sequence
        // or traversal has executed some imposed 'maximum' amount of times.
        MAX_STOP_OUT_OF_BOUNDS
        // A Hailstone sequence state that indicates the sequence terminated
        // by reaching "0", a special type of "stopping time".
        ZERO_STOP
)

// Get the string associated with the SequenceState
func (ss SequenceState) String() (StateString string) {
        switch ss {
        case NO_STATE:
                return "NO_STATE"
        case STOPPING_TIME:
                return "STOPPING_TIME"
        case TOTAL_STOPPING_TIME:
                return "TOTAL_STOPPING_TIME"
        case CYCLE_INIT:
                return "CYCLE_INIT"
        case CYCLE_LENGTH:
                return "CYCLE_LENGTH"
        case MAX_STOP_OUT_OF_BOUNDS:
                return "MAX_STOP_OUT_OF_BOUNDS"
        case ZERO_STOP:
                return "ZERO_STOP"
        }
        return "unknown"
}

////////////////////////////////////////////////////////////////////////////////
// The start of the functionality: the "function" and "reverse function"
////////////////////////////////////////////////////////////////////////////////

// Handles the sanity check for the parameterisation (P,a,b) required by both
// the function and reverse function. Returns an error of type;
//  FailedSaneParameterCheck(SANE_PARAMS_P)
//  FailedSaneParameterCheck(SANE_PARAMS_A)
// Has arguments;
//  - P: Modulus used to devide n, iff n is equivalent to (0 mod P).
//  - a: Factor by which to multiply n.
//  - b: Value to add to the scaled value of n.
func assertSaneParameterication(P *big.Int, a *big.Int, b *big.Int) error {
        // Sanity check (P,a,b) ~ P absolutely can't be 0. a "could" be zero
        // theoretically, although would violate the reversability (if ~a is 0 then a
        // value of "b" as the input to the reverse function would have a pre-emptive
        // value of every number not divisible by P). The function doesn't _have_ to
        // be reversable, but we are only interested in dealing with the class of
        // functions that exhibit behaviour consistant with the collatz function. If
        // _every_ input not divisable by P went straight to "b", it would simply
        // cause a cycle consisting of "b" and every b/P^z that is an integer. While
        // P in [-1, 1] could also be a reasonable check, as it makes every value
        // either a 1 or 2 length cycle, it's not strictly an illegal operation.
        // "b" being zero would cause behaviour not consistant with the collatz
        // function, but would not violate the reversability, so no check either.
        // " != 0" is redundant for python assertions.
        if P.Cmp(ZERO()) == 0 {
                return FailedSaneParameterCheck(SANE_PARAMS_P)
        }
        if a.Cmp(ZERO()) == 0 {
                return FailedSaneParameterCheck(SANE_PARAMS_A)
        }
        return nil
}

// Returns the result of a single application of a Collatz-esque function.
//  - n: The value on which to perform the Collatz-esque function
//  - P: Modulus used to devide n, iff n is equivalent to (0 mod P).
//  - a: Factor by which to multiply n.
//  - b: Value to add to the scaled value of n.
func ParameterisedFunction(n *big.Int, P *big.Int, a *big.Int, b *big.Int) (result *big.Int, sanity error) {
        sanity = assertSaneParameterication(P, a, b)
        if sanity != nil {
                return
        }
        q, m := new(big.Int), new(big.Int)
        q, m = q.DivMod(n, P, m)
        if m.Cmp(ZERO()) == 0 { // n%P is zero
                result = q // n/P
        } else {
                result = new(big.Int).Add(new(big.Int).Mul(a, n), b) //(a*n + b)
        }
        return
}

// Returns the result of a single application of the Collatz function.
//  - n: The value on which to perform the Collatz-esque function
func Function(n *big.Int) (result *big.Int) {
        result, _ = ParameterisedFunction(n, DEFAULT_P(), DEFAULT_A(), DEFAULT_B())
        return
}

// Returns the output of a single application of a Collatz-esque reverse function.
// If there is no error in the parameters, then the value of preNDivP will always
// be an actual result, while preANplusB may either be a result, or nil.
//  - n: The value on which to perform the reverse Collatz function
//  - P: Modulus used to devide n, iff n is equivalent to (0 mod P)
//  - a: Factor by which to multiply n.
//  - b: Value to add to the scaled value of n.
func ParameterisedReverseFunction(n *big.Int, P *big.Int, a *big.Int, b *big.Int) (preNDivP *big.Int, preANplusB *big.Int, sanity error) {
        // Every input can be reversed as the result of "n/P" division, which yields
        // "Pn"... {f(n) = an + b}≡{(f(n) - b)/a = n} ~ if n was such that the
        // muliplication step was taken instead of the division by the modulus, then
        // (f(n) - b)/a) must be an integer that is not in (0 mod P). Because we're
        // not placing restrictions on the parameters yet, although there is a better
        // way of shortcutting this for the default variables, we need to always
        // attempt (f(n) - b)/a)
        sanity = assertSaneParameterication(P, a, b)
        if sanity != nil {
                return
        }
        preNDivP = new(big.Int).Mul(P, n)
        // The condition to return preANplusB is (n-b)%a is zero AND (n-b)%(P*a) is not zero
        n_sub_b := new(big.Int).Sub(n, b)
        preANplusB, nsubb_mod_a := new(big.Int), new(big.Int)
        preANplusB, nsubb_mod_a = preANplusB.DivMod(n_sub_b, a, nsubb_mod_a)
        // Inverse of the condition to include this output, then set it to nil.
        if !(nsubb_mod_a.Cmp(ZERO()) == 0 && new(big.Int).Mod(n_sub_b, (new(big.Int).Mul(P, a))).Cmp(ZERO()) != 0) {
                preANplusB = nil
        }
        return
}

// Returns the output of a single application of the Collatz reverse function.
// The value of preNDivP will always be an actual result, while preANplusB
// may either be a result, or nil.
//  - n: The value on which to perform the reverse Collatz function
func ReverseFunction(n *big.Int) (preNDivP *big.Int, preANplusB *big.Int) {
        preNDivP, preANplusB, _ = ParameterisedReverseFunction(n, DEFAULT_P(), DEFAULT_A(), DEFAULT_B())
        return
}

////////////////////////////////////////////////////////////////////////////////
// The "Hailstone Sequence" and "Stopping Time" functions.
////////////////////////////////////////////////////////////////////////////////

// Provides the appropriate lambda to use to check if iterations on an initial
// value have reached either the stopping time, or total stopping time.
//  - n: The initial value to confirm against a stopping time check.
//  - total_stop: If false, the lambda will confirm that iterations of n
//    have reached the oriented stopping time to reach a value closer to 0.
//    If true, the lambda will simply check equality to 1.
// return (func(x *big.Int) bool): The lambda to check for the stopping time.
func stoppingTimeTerminus(n *big.Int, total_stop bool) func(x *big.Int) bool {
        one := ONE()
        zero := ZERO()
        if total_stop {
                return func(x *big.Int) bool { return x.Cmp(one) == 0 }
        } else if n.Cmp(zero) >= 0 {
                return func(x *big.Int) bool { return ((x.Cmp(n) == -1) && (x.Cmp(zero) == 1)) }
        } else {
                return func(x *big.Int) bool { return ((x.Cmp(n) == 1) && (x.Cmp(zero) == -1)) }
        }
}

// Contains the results of computing a hailstone sequence. Can be created via;
//  ParameterisedHailstoneSequence(~)
//  NewHailstoneSequence(~)
type HailstoneSequence struct {
        // The set of values that comprise the hailstone sequence.
        values []*big.Int
        // The functions used to determine if the terminal condition has been met.
        terminate func(x *big.Int) bool
        // A terminal condition that reflects the final state of the hailstone sequencing,
        // whether than be that it succeeded at determining the stopping time, the total
        // stopping time, found a cycle, or got stuck on zero (or surpassed the max total).
        terminalCondition SequenceState
        // A status value that has different meanings depending on what the terminal condition
        // was. If the sequence completed either via reaching the stopping or total stopping time,
        // or getting stuck on zero, then this value is the stopping/terminal time. If the sequence
        // got stuck on a cycle, then this value is the cycle length. If the sequencing passes the
        // maximum stopping time then this is the value that was provided as that maximum.
        terminalStatus int
}

// Initialise and compute a new Hailstone Sequence.
//  - initialValue: The value to begin the hailstone sequence from.
//  - P: Modulus used to devide n, iff n is equivalent to (0 mod P).
//  - a: Factor by which to multiply n.
//  - b: Value to add to the scaled value of n.
//  - maxTotalStoppingTime: Maximum amount of times to iterate the function, if 1 is not reached.
//  - totalStoppingTime: Whether or not to execute until the "total" stopping time
//    (number of iterations to obtain 1) rather than the regular stopping time
//    (number of iterations to reach a value less than the initial value).
func ParameterisedHailstoneSequence(initialValue *big.Int, P *big.Int, a *big.Int, b *big.Int, maxTotalStoppingTime int, totalStoppingTime bool) (*HailstoneSequence, error) {
        // Call out the function before any magic returns to trap bad values.
        _, err := ParameterisedFunction(initialValue, P, a, b)
        if err != nil {
                return nil, err
        }
        var hs HailstoneSequence
        hs.terminate = stoppingTimeTerminus(initialValue, totalStoppingTime)
        if initialValue.Cmp(ZERO()) == 0 {
                // 0 is always an immediate stop.
                hs.values = []*big.Int{ZERO()}
                hs.terminalCondition = ZERO_STOP
                hs.terminalStatus = 0
        } else if initialValue.Cmp(ONE()) == 0 {
                // 1 is always an immediate stop, with 0 stopping time.
                hs.values = []*big.Int{ONE()}
                hs.terminalCondition = TOTAL_STOPPING_TIME
                hs.terminalStatus = 0
        } else {
                // Otherwise, hail!
                minMaxTotalStoppingTime := int(math.Max(float64(maxTotalStoppingTime), 1))
                hs.values = make([]*big.Int, 1, minMaxTotalStoppingTime+1)
                hs.values[0] = initialValue
                var cycleMap map[string]bool = make(map[string]bool, maxTotalStoppingTime+1)
                cycleMap[initialValue.String()] = true
                zero := ZERO()
                for k := 1; k <= minMaxTotalStoppingTime; k++ {
                        next, err := ParameterisedFunction(hs.values[k-1], P, a, b)
                        if err != nil {
                                return nil, err
                        }
                        // Check if the next hailstone is either the stopping time, total
                        // stopping time, the same as the initial value, or stuck at zero.
                        if hs.terminate(next) {
                                hs.values = append(hs.values, next)
                                if next.Cmp(ONE()) == 0 {
                                        hs.terminalCondition = TOTAL_STOPPING_TIME
                                } else {
                                        hs.terminalCondition = STOPPING_TIME
                                }
                                hs.terminalStatus = k
                                return &hs, nil
                        }
                        if cycleMap[next.String()] {
                                hs.values = append(hs.values, next)
                                cycle_init := 1
                                for j := 1; j <= k; j++ {
                                        if hs.values[k-j].Cmp(next) == 0 {
                                                cycle_init = j
                                                break
                                        }
                                }
                                hs.terminalCondition = CYCLE_LENGTH
                                hs.terminalStatus = cycle_init
                                return &hs, nil
                        }
                        if next.Cmp(zero) == 0 {
                                hs.values = append(hs.values, zero)
                                hs.terminalCondition = ZERO_STOP
                                hs.terminalStatus = -k
                                return &hs, nil
                        }
                        hs.values = append(hs.values, next)
                        cycleMap[next.String()] = true
                }
                hs.terminalCondition = MAX_STOP_OUT_OF_BOUNDS
                hs.terminalStatus = minMaxTotalStoppingTime
        }
        return &hs, nil
}

// Initialise and compute a new Hailstone Sequence.
//  - initialValue: The value to begin the hailstone sequence from.
//  - P: Modulus used to devide n, iff n is equivalent to (0 mod P).
//  - a: Factor by which to multiply n.
//  - b: Value to add to the scaled value of n.
//  - maxTotalStoppingTime: Maximum amount of times to iterate the function, if 1 is not reached.
//  - totalStoppingTime: Whether or not to execute until the "total" stopping time
//    (number of iterations to obtain 1) rather than the regular stopping time
//    (number of iterations to reach a value less than the initial value).
func NewHailstoneSequence(initialValue *big.Int, maxTotalStoppingTime int) *HailstoneSequence {
        ret, _ := ParameterisedHailstoneSequence(initialValue, DEFAULT_P(), DEFAULT_A(), DEFAULT_B(), maxTotalStoppingTime, true)
        return ret
}

// Returns the stopping time, the amount of iterations required to reach a
// value less than the initial value, or -Inf if maxStoppingTime is exceeded.
// Alternatively, if totalStoppingTime is True, then it will instead count
// the amount of iterations to reach 1. If the sequence does not stop, but
// instead ends in a cycle, the result will be +Inf.
// If (P,a,b) are such that it is possible to get stuck on zero, the result
// will be the negative of what would otherwise be the "total stopping time"
// to reach 1, where 0 is considered a "total stop" that should not occur as
// it does form a cycle of length 1.
//  - initialValue: The value for which to find the stopping time.
//  - P: Modulus used to devide n, iff n is equivalent to (0 mod P).
//  - a: Factor by which to multiply n.
//  - b: Value to add to the scaled value of n.
//  - maxStoppingTime: Maximum amount of times to iterate the function,
//    if the stopping time is not reached. IF the maxStoppingTime is reached,
//    the function will return null.
//  - totalStoppingTime: Whether or not to execute until the "total" stopping
//    time (number of iterations to obtain 1) rather than the regular stopping
//    time (number of iterations to reach a value less than the initial value).
// return (float64): The stopping time, or, in a special case, infinity, null or a negative.
func ParameterisedStoppingTime(initialValue *big.Int, P *big.Int, a *big.Int, b *big.Int, maxStoppingTime int, totalStoppingTime bool) (float64, error) {
        // The information is contained in the hailstone sequence. Although the "max~time"
        // for hailstones is named for "total stopping" time and the "max~time" for this
        // "stopping time" function is _not_ "total", they are handled the same way, as
        // the default for "totalStoppingTime" for hailstones is true, but for this, is
        // false. Thus the naming difference.
        hail, err := ParameterisedHailstoneSequence(initialValue, P, a, b, maxStoppingTime, totalStoppingTime)
        // For total/regular/zero stopping time, the value is already the same as
        // that present, for cycles we report infinity instead of the cycle length,
        // and for max stop out of bounds, we report null instead of the max stop cap
        if err != nil {
                return math.Inf(-1), err
        }
        switch hail.terminalCondition {
        case STOPPING_TIME:
                return float64(hail.terminalStatus), nil
        case TOTAL_STOPPING_TIME:
                return float64(hail.terminalStatus), nil
        case CYCLE_LENGTH:
                return math.Inf(1), nil
        case MAX_STOP_OUT_OF_BOUNDS:
                return math.Inf(-1), nil
        case ZERO_STOP:
                return float64(hail.terminalStatus), nil
        }
        return math.Inf(-1), nil
}

// Returns the stopping time, the amount of iterations required to reach a
// value less than the initial value, or -Inf if maxStoppingTime is exceeded.
//  - initialValue: The value for which to find the stopping time.
// return float64: The stopping time, or, in a cycle case, infinity.
func StoppingTime(initialValue *big.Int) float64 {
        stop, _ := ParameterisedStoppingTime(initialValue, DEFAULT_P(), DEFAULT_A(), DEFAULT_B(), 1000, false)
        return stop
}

////////////////////////////////////////////////////////////////////////////////
// The "Tree Graph" type, and functions related to it.
////////////////////////////////////////////////////////////////////////////////

// Nodes that form a "tree graph", structured as a tree, with their own node's value,
// as well as references to either possible child node, where a node can only ever have
// two children, as there are only ever two reverse values. Also records any possible
// "terminal sequence state", whether that be that the "orbit distance" has been reached,
// as an "out of bounds" stop, which is the regularly expected terminal state. Other
// terminal states possible however include the cycle state and cycle length (end) states.
type TreeGraphNode struct {
        // The value of this node in the tree.
        nodeValue *big.Int
        // The terminal state; null if not a terminal node, MAX_STOP_OUT_OF_BOUNDS if the maxOrbitDistance
        // has been reached, CYCLE_LENGTH if the node's value is found to have occured previously, or
        // CYCLE_INIT, retroactively applied when a CYCLE_LENGTH state node is found.
        terminalSequenceState SequenceState
        // The "Pre N/P" child of this node that is always
        // present if this is not a terminal node.
        preNDivPNode *TreeGraphNode
        // The "Pre aN+b" child of this node that is present
        // if it exists and this is not a terminal node.
        preANplusBNode *TreeGraphNode
        // A map of previous graph nodes which maps instances of
        // TreeGraphNode to themselves, to enable cycle detection.
        cycleCheck map[string]*TreeGraphNode
}

// Create an instance of TreeGraphNode which will yield its entire sub-tree of all child nodes.
//  - nodeValue: The value for which to find the tree graph node reversal.
//  - maxOrbitDistance: The maximum distance/orbit/branch length to travel.
//  - P: Modulus used to devide n, iff n is equivalent to (0 mod P).
//  - a: Factor by which to multiply n.
//  - b: Value to add to the scaled value of n.
func newTreeGraphRootNode(nodeValue *big.Int, maxOrbitDistance int, P *big.Int, a *big.Int, b *big.Int) (*TreeGraphNode, error) {
        this := new(TreeGraphNode)
        this.nodeValue = nodeValue
        if int(math.Max(float64(maxOrbitDistance), 0)) == 0 {
                this.terminalSequenceState = MAX_STOP_OUT_OF_BOUNDS
                this.preNDivPNode = nil
                this.preANplusBNode = nil
                this.cycleCheck = nil
        } else {
                preNDivP, preANplusB, err := ParameterisedReverseFunction(nodeValue, P, a, b)
                if err != nil {
                        return nil, err
                }
                this.cycleCheck = make(map[string]*TreeGraphNode, 1+int(math.Pow(2, float64(maxOrbitDistance))))
                this.cycleCheck[nodeValue.String()] = this
                preNDivPNode, err := newTreeGraphInnerNode(preNDivP, maxOrbitDistance-1, P, a, b, this.cycleCheck)
                if err != nil {
                        return nil, err
                }
                this.preNDivPNode = preNDivPNode
                if preANplusB != nil {
                        preANplusBNode, err := newTreeGraphInnerNode(preANplusB, maxOrbitDistance-1, P, a, b, this.cycleCheck)
                        if err != nil {
                                return nil, err
                        }
                        this.preANplusBNode = preANplusBNode
                } else {
                        this.preANplusBNode = nil
                }
        }
        return this, nil
}

// Create an instance of TreeGraphNode which will yield its entire sub-tree of all child nodes.
// This is used internally by itself and the public constructor to pass the cycle checking map,
// recursively determining subsequent child nodes.
//  - nodeValue: The value for which to find the tree graph node reversal.
//  - maxOrbitDistance: The maximum distance/orbit/branch length to travel.
//  - P: Modulus used to devide n, iff n is equivalent to (0 mod P).
//  - a: Factor by which to multiply n.
//  - b: Value to add to the scaled value of n.
//  - cycleCheck: Checks if this node's value already occurred.
func newTreeGraphInnerNode(nodeValue *big.Int, maxOrbitDistance int, P *big.Int, a *big.Int, b *big.Int, cycleCheck map[string]*TreeGraphNode) (*TreeGraphNode, error) {
        this := new(TreeGraphNode)
        this.nodeValue = nodeValue
        this.cycleCheck = cycleCheck
        if this.cycleCheck[nodeValue.String()] != nil {
                this.cycleCheck[nodeValue.String()].terminalSequenceState = CYCLE_INIT
                this.cycleCheck = nil
                this.terminalSequenceState = CYCLE_LENGTH
                this.preNDivPNode = nil
                this.preANplusBNode = nil
        } else if int(math.Max(float64(maxOrbitDistance), 0)) == 0 {
                this.cycleCheck = nil
                this.terminalSequenceState = MAX_STOP_OUT_OF_BOUNDS
                this.preNDivPNode = nil
                this.preANplusBNode = nil
        } else {
                this.cycleCheck[nodeValue.String()] = this
                this.terminalSequenceState = NO_STATE
                preNDivP, preANplusB, err := ParameterisedReverseFunction(nodeValue, P, a, b)
                if err != nil {
                        return nil, err
                }
                preNDivPNode, err := newTreeGraphInnerNode(preNDivP, maxOrbitDistance-1, P, a, b, this.cycleCheck)
                if err != nil {
                        return nil, err
                }
                this.preNDivPNode = preNDivPNode
                if preANplusB != nil {
                        preANplusBNode, err := newTreeGraphInnerNode(preANplusB, maxOrbitDistance-1, P, a, b, this.cycleCheck)
                        if err != nil {
                                return nil, err
                        }
                        this.preANplusBNode = preANplusBNode
                } else {
                        this.preANplusBNode = nil
                }
        }
        return this, nil
}

// Create an instance of TreeGraphNode by directly passing it the values required to instantiate,
// intended to be used in testing by manually creating trees in reverse, by passing expected child
// nodes to their parents until the entire expected tree is created.
//  - nodeValue: The value expected of this node.
//  - terminalSequenceState: The expected sequence state;
//    null, MAX_STOP_OUT_OF_BOUNDS, CYCLE_INIT or CYCLE_LENGTH.
//  - preNDivPNode: The expected "Pre N/P" child node.
//  - preANplusBNode: The expected "Pre aN+b" child node.
func newTreeGraphNode(nodeValue *big.Int, terminalSequenceState SequenceState, preNDivPNode *TreeGraphNode, preANplusBNode *TreeGraphNode, cycleCheck map[string]*TreeGraphNode) *TreeGraphNode {
        this := new(TreeGraphNode)
        this.nodeValue = nodeValue
        this.terminalSequenceState = terminalSequenceState
        this.preNDivPNode = preNDivPNode
        this.preANplusBNode = preANplusBNode
        this.cycleCheck = cycleCheck
        return this
}

// This will only confirm an equality if the whole subtree of both nodes, including
// node values, sequence states, and child nodes, checked recursively, are equal.
//  - t1: The TreeGraphNode with which to compare equality.
//  - t2: The TreeGraphNode with which to compare equality.
// return true, if the entire sub-trees are equal.
func subTreeEquals(t1 *TreeGraphNode, t2 *TreeGraphNode) bool {
        if t1.nodeValue.Cmp(t2.nodeValue) != 0 || t1.terminalSequenceState != t2.terminalSequenceState {
                return false
        }
        if t1.preNDivPNode == nil && t2.preNDivPNode != nil {
                return false
        }
        if t1.preNDivPNode != nil && !subTreeEquals(t1.preNDivPNode, t2.preNDivPNode) {
                return false
        }
        if t1.preANplusBNode == nil && t2.preANplusBNode != nil {
                return false
        }
        if t1.preANplusBNode != nil && !subTreeEquals(t1.preANplusBNode, t2.preANplusBNode) {
                return false
        }
        return true
}

// Contains the results, in a "root node" of computing the Tree Graph via;
//  ParameterisedTreeGraph(~)
//  NewTreeGraph(~)
type TreeGraph struct {
        // The root node of the tree of TreeGraphNode's.
        root *TreeGraphNode
}

// Create a new TreeGraph with the root node defined by the inputs.
// Returns a directed tree graph of the reverse function values up to a maximum
// nesting of maxOrbitDistance, with the initialValue as the root.
//  - initialValue: The root value of the directed tree graph.
//  - maxOrbitDistance: Maximum amount of times to iterate the reverse
//    function. There is no natural termination to populating the tree
//    graph, equivalent to the termination of hailstone sequences or
//    stopping time attempts, so this is not an optional argument like
//    maxStoppingTime / maxTotalStoppingTime, as it is the intended target
//    of orbits to obtain, rather than a limit to avoid uncapped computation.
//  - P: Modulus used to devide n, iff n is equivalent to (0 mod P).
//  - a: Factor by which to multiply n.
//  - b: Value to add to the scaled value of n.
func ParameterisedTreeGraph(initialValue *big.Int, maxOrbitDistance int, P *big.Int, a *big.Int, b *big.Int) (*TreeGraph, error) {
        rootNode, err := newTreeGraphRootNode(initialValue, maxOrbitDistance, P, a, b)
        if err != nil {
                return nil, err
        }
        return newTreeGraph(rootNode), nil
}

// Create a new TreeGraph by directly passing it the root node.
// Intended to be used in testing by manually creating trees.
//  - root: The root node of the tree.
func newTreeGraph(rootNode *TreeGraphNode) *TreeGraph {
        tree := new(TreeGraph)
        tree.root = rootNode
        return tree
}

// The equality between TreeGraphs is determined by the equality check on
// subtrees. A subtree check will be done on both TreeGraph's root nodes.
func TreeGraphEquals(t1 *TreeGraph, t2 *TreeGraph) bool {
        if t1 == nil && t2 != nil {
                return false
        }
        if t1 != nil && t2 == nil {
                return false
        }
        if t1 == nil && t2 == nil {
                return true
        }
        return subTreeEquals(t1.root, t2.root)
}

// Create a new TreeGraph with the root node defined by the inputs.
// Returns a directed tree graph of the reverse function values up to a maximum
// nesting of maxOrbitDistance, with the initialValue as the root.
//  - initialValue: The root value of the directed tree graph.
//  - maxOrbitDistance: Maximum amount of times to iterate the reverse
//    function. There is no natural termination to populating the tree
//    graph, equivalent to the termination of hailstone sequences or
//    stopping time attempts, so this is not an optional argument like
//    maxStoppingTime / maxTotalStoppingTime, as it is the intended target
//    of orbits to obtain, rather than a limit to avoid uncapped computation.
func NewTreeGraph(initialValue *big.Int, maxOrbitDistance int) (*TreeGraph, error) {
        return ParameterisedTreeGraph(initialValue, maxOrbitDistance, DEFAULT_P(), DEFAULT_A(), DEFAULT_B())
}