// (c) 2020 Aaron Taylor <ataylor at subgeniuskitty dot com>
// See LICENSE.txt file for copyright and license details.

package main

import (
    "flag"
    "fmt"
    "log"
)

// =============================================================================

// TODO: Anywhere we do simple comparisons for number equality testing, we need
// to upgrade to dual-LEQ comparisons.

// =============================================================================

type surrealUniverse struct {
    // TODO: Note that the elements of this array are maintained in order
    // w.r.t. Axiom 2. Maybe I should just rename number -> numberLine?
    numbers []surrealNumber
    nextUniqueID int
}

func (u *surrealUniverse) getIndex(num surrealNumber) (exists bool, index int) {
    // TODO: After I implement a LEQ comparison function, the fact that
    // u.numbers[] is ordered by that comparison will allow me to greatly
    // shorten the search.
    for i := 0; i < len(u.numbers); i++ {
        if num.number == u.numbers[i].number {
            return true, i
        }
    }
    return false, 0
}

func (u *surrealUniverse) cardinality() int {
    return len(u.numbers)
}

func (u *surrealUniverse) insert(num surrealNumber) {
    exists, _ := u.getIndex(num)
    if !exists {
        num.metadata.identifier = u.nextUniqueID
        u.nextUniqueID++
        // Find spot to insert based on ordering defined in Axiom 2.
        // TODO: Insert some comments explaining the basic algorithm.
        for i := 0; i < len(u.numbers); i++ {

//            if num.number.leftSet != nil {
//                // By assumption, everything is in reduced form by this point,
//                // thus there is precisely one element at this time.
//                _, leftIndex := u.getIndex(num.number.leftSet[0])
//                _, rightIndex := u.getIndex(u.numbers[i])
//                if leftIndex >= rightIndex {
//                    // num is NOT LEQ to u.numbers[i]
//                }
//            }
//            if u.numbers[i].rightSet != nil {
//                // TODO: How do I check if the second number's rightSet is less
//                // than or equal to the first number? After all, the first
//                // number isn't on the numberline yet.
//            }

// =================================================================================================
//// Algorithm
//foreach u.numbers as oldNum, in increasing order:
//    if newNum <= oldNum:
//        if oldNum <= newNum:
//            // the number are the same, just in a different reduced form.
//        else:
//            // Insert newNum immediately before oldNum
//    else:
//        if more oldNums exist:
//            // loop and try the next oldNum
//        else:
//            // Found a new largest number?
// =================================================================================================

//            if !lessThanOrEqual(num, u.numbers[i]) {
//                if i+1 < len(u.numbers) {
//                    // There are still more entries to check.
//                    continue
//                } else {
//                    // New largest number. Append to numberline.
//                    u.numbers = append(u.numbers, num)
//                }
//            } else {
//                // Found insertion spot between two existing numbers.
//                u.numbers = append(u.numbers[:i], num, u.numbers[i:]...)
//            }
        }
    }
}

func (u *surrealUniverse) remove(num surrealNumber) {
    for i := 0; i < len(u.numbers); i++ {
        if num.number == u.numbers[i].number {
            u.numbers = append(u.numbers[:i], u.numbers[i+1:]...)
        }
    }
}

// TODO: Note that this is only for numbers already in the universe, not for
// new numbers constructed FROM the universe.  To determine where a new number
// goes, insert it into the universe.
func (u *surrealUniverse) lessThanOrEqual(left, right surrealNumber) bool {
    _, leftIndex := u.getIndex(left)
    _, rightIndex := u.getIndex(right)
    if leftIndex <= rightIndex {
        return true
    } else {
        return false
    }
}

// =============================================================================

type surrealNumber struct {
    number surrealValue
    metadata surrealMetadata
}

// TODO: Note that this is split from the metadata so we can do direct
// comparisons when numbers are in reduced form.
type surrealValue struct {
    leftSet *surrealSet
    rightSet *surrealSet
}

type surrealMetadata struct {
    identifier int
    generation int
}

// =============================================================================

type surrealSet struct {
    members []surrealNumber
}

func (s *surrealSet) isMember(num surrealNumber) bool {
    for i := 0; i < len(s.members); i++ {
        if num.number == s.members[i].number {
            return true
        }
    }
    return false
}

func (s *surrealSet) cardinality() int {
    return len(s.members)
}

func (s *surrealSet) insert(num surrealNumber) {
    if !s.isMember(num) {
        s.members = append(s.members, num)
    }
}

func (s *surrealSet) remove(num surrealNumber) {
    for i := 0; i < len(s.members); i++ {
        if num.number == s.members[i].number {
            s.members[i] = s.members[len(s.members)-1]
            s.members = s.members[:len(s.members)-1]
        }
    }
}

// =============================================================================

func main() {
    // Obtain termination conditions from user.
    remainingGenerations := flag.Int("generations", 2, "Number of generations of surreal numbers to breed.")
    flag.Parse()
    if *remainingGenerations < 1 {
        log.Fatal("ERROR: The argument to '-generations' must be greater than zero.")
    }

    // Build a universe to contain all the surreal numbers we breed.
    // Seed it by hand with the number zero as generation-0.
    var universe surrealUniverse
    universe.insert(surrealNumber{surrealValue{nil, nil}, surrealMetadata{0, 0}})

    for generation := 1; generation <= *remainingGenerations; generation++ {
        potentialNumbers := permuteExistingNumbers(generation, universe)
        validNumbers := pruneInvalidNumbers(potentialNumbers, universe)
        addNumbersToUniverse(validNumbers, &universe)
    }

    // TODO: These are just for checking progress. How do I want to render the
    // final generation vs magnitude chart?
    fmt.Println("Total Numbers:", len(universe.numbers))
    fmt.Println(universe.numbers)
}

// =============================================================================

// We will only build permutations with 0 or 1 elements in each of the left and
// right sets. This covers all the reduced form permutations. Any longer
// permutations will be similar to one of the reduced forms.
func permuteExistingNumbers(generation int, universe surrealUniverse) []surrealNumber {
    var numbers []surrealNumber

    // First build permutations with 1 element in each set.
    for i := 0; i < universe.cardinality(); i++ {
        for j := 0; j < universe.cardinality(); j++ {
            var leftSet, rightSet surrealSet
            leftSet.insert(universe.numbers[i])
            rightSet.insert(universe.numbers[j])
            newSurrealNumber := surrealNumber{surrealValue{&leftSet,&rightSet},surrealMetadata{0,generation}}
            numbers = append(numbers, newSurrealNumber)
        }
    }
    // Now build permutations with one empty set and one 1-element set.
    for i := 0; i < universe.cardinality(); i++ {
        var tempSet surrealSet
        tempSet.insert(universe.numbers[i])
        newSurrealNumber := surrealNumber{surrealValue{&tempSet,nil},surrealMetadata{0,generation}}
        numbers = append(numbers, newSurrealNumber)
        newSurrealNumber = surrealNumber{surrealValue{nil,&tempSet},surrealMetadata{0,generation}}
        numbers = append(numbers, newSurrealNumber)
    }

    return numbers
}

func pruneInvalidNumbers(candidates []surrealNumber, universe surrealUniverse) []surrealNumber {
    var numbers []surrealNumber
    for i := 0; i < len(candidates); i++ {
        if isValidSurrealNumber(candidates[i], universe) {
            numbers = append(numbers, candidates[i])
        }
    }
    return numbers
}

// Although a non-reduced-form number is technically valid, for the purposes of
// this program we're declaring it invalid.
func isValidSurrealNumber(candidate surrealNumber, universe surrealUniverse) bool {
    // Is the number in reduced form per Definition 3?
    if candidate.number.leftSet.cardinality() > 1 || candidate.number.rightSet.cardinality() > 1 {
        return false
    }

    // Is the number valid per Axiom 1?
    if candidate.number.leftSet != nil && candidate.number.rightSet != nil {
        // TODO: This needs to be beefed up since <|> = <-1|1>.
        if candidate.number.leftSet == candiate.number.rightSet {
            return false
        }
        if !universe.lessThanOrEqual(candidate.number.leftSet[0], candidate.number.rightSet[0]) {
            return false
        }
    }

    return true
}

func addNumbersToUniverse(numbers []surrealNumber, universe *surrealUniverse) {
    for i := 0; i < len(numbers); i++ {
        universe.insert(numbers[i])
    }
}