+// =============================================================================
+
+// This program recognizes four types of numbers:
+// - Surreal symbols, like those generated by Axiom 1.
+// - Surreal numbers, like those selected by Axiom 2.
+// - Reduced form numbers, per Definition 7.
+// - Named form numbers, which are the equivalence classes induced by
+// Definition 6, represented by the first representative reduced
+// form number encountered at runtime.
+//
+// Although the surrealNumber type can represent any of these four types of
+// numbers, the surrealUniverse contains only named form numbers.
+//
+// All equality tests (e.g. eq, geq, leq) in this program actually test for
+// similarity per Definition 6.
+
+// =============================================================================
+
+type surrealUniverse struct {
+ // The elements in this slice are stored in order according to Axiom 3.
+ // Thus, numbers[0] < numbers[1] < ... < numbers[n].
+ numbers []surrealNumber
+ nextUniqueID uint
+}
+
+func (u *surrealUniverse) getIndex(num surrealNumber) int {
+ for i := 0; i < len(u.numbers); i++ {
+ if num.identifier == u.numbers[i].identifier {
+ return i
+ }
+ }
+ return -1 // This should be unreachable.
+}
+
+func (u *surrealUniverse) cardinality() int {
+ return len(u.numbers)
+}
+
+func (u *surrealUniverse) insert(num surrealNumber) {
+ // Before we can insert a number into the universe, we must first determine
+ // if it is newly discovered. We do this by looking at its ancestors, all
+ // guaranteed to be on the number line by construction, finding three
+ // cases:
+ //
+ // 1. There are zero ancestors.
+ // We have rediscovered 0 and can abort the insertion unless creating
+ // a brand new universe.
+ //
+ // 2. There is one ancestor.
+ // If the number extends the number line, it is new, otherwise it will
+ // be similar to a form with two ancestors and should be ignored since
+ // the two ancestor form is a better visual representation.
+ //
+ // 3. There are two ancestors.
+ // The number is only new if both ancestors are side-by-side on the
+ // number line.
+
+ ancestorCount := num.leftSet.cardinality() + num.rightSet.cardinality()
+ switch ancestorCount {
+ case 0:
+ if u.cardinality() == 0 {
+ num.identifier = u.nextUniqueID
+ u.nextUniqueID++
+ u.numbers = append(u.numbers, num)
+ }
+ case 1:
+ if num.leftSet.cardinality() == 1{
+ index := u.getIndex(num.leftSet.members[0])
+ num.identifier = u.nextUniqueID
+ u.nextUniqueID++
+ if index+1 == u.cardinality() {
+ u.numbers = append(u.numbers, num)
+ }
+ } else {
+ index := u.getIndex(num.rightSet.members[0])
+ num.identifier = u.nextUniqueID
+ u.nextUniqueID++
+ if index == 0 {
+ u.numbers = append(u.numbers[:1], u.numbers...)
+ u.numbers[0] = num
+ }
+ }
+ case 2:
+ leftIndex := u.getIndex(num.leftSet.members[0])
+ rightIndex := u.getIndex(num.rightSet.members[0])
+ if leftIndex+1 == rightIndex {
+ num.identifier = u.nextUniqueID
+ u.nextUniqueID++
+ u.numbers = append(u.numbers[:rightIndex+1], u.numbers[rightIndex:]...)
+ u.numbers[rightIndex] = num
+ }
+ }
+}
+
+// =============================================================================
+
+// Note: The following comparison functions apply only to numbers already in
+// the universe, not to new numbers constructed from the universe. To
+// determine where a (potentially) new number goes, first insert it into the
+// universe.
+
+// This function implements Axiom 3 and is the root of all other comparisons.
+func (u *surrealUniverse) isRelated(numA, numB surrealNumber) bool {
+ // By construction, no number in this program will ever have more than one
+ // element in its right or left sets, nor will those elements be of a form
+ // other than that 'registered' with the universe. That allows direct
+ // comparisons using the surrealNumber.identifier field via u.getIndex().
+
+ // ---------------------------------
+
+ // First we implement the check "no member of the first number's left set
+ // is greater than or equal to the second number".
+ if numA.leftSet.cardinality() == 1 {
+ if u.getIndex(numA.leftSet.members[0]) >= u.getIndex(numB) {
+ return false
+ }
+ }
+
+ // Now we implement the check "no member of the second number's right set
+ // is less than or equal to the first number".
+ if numB.rightSet.cardinality() == 1 {
+ if u.getIndex(numB.rightSet.members[0]) <= u.getIndex(numA) {
+ return false
+ }
+ }
+
+ return true
+}
+
+func (u *surrealUniverse) isSimilar(numA, numB surrealNumber) bool {
+ if u.isRelated(numA, numB) && u.isRelated(numB, numA) {
+ return true
+ }
+ return false
+}
+
+func (u *surrealUniverse) equal(left, right surrealNumber) bool {
+ return u.isSimilar(left, right)
+}
+
+func (u *surrealUniverse) lessThanOrEqual(left, right surrealNumber) bool {
+ return u.isRelated(left, right)
+}
+
+func (u *surrealUniverse) lessThan(left, right surrealNumber) bool {
+ return u.lessThanOrEqual(left, right) && !u.equal(left, right)
+}
+
+func (u *surrealUniverse) greaterThanOrEqual(left, right surrealNumber) bool {
+ return !u.lessThan(left, right)
+}
+
+func (u *surrealUniverse) greaterThan(left, right surrealNumber) bool {
+ return !u.isRelated(left, right)
+}
+
+// =============================================================================
+
+type surrealNumber struct {
+ leftSet surrealSet
+ rightSet surrealSet
+ identifier uint
+ generation int
+}
+
+type surrealSet struct {
+ members []surrealNumber
+}
+
+func (s *surrealSet) isMember(num surrealNumber, u surrealUniverse) bool {
+ for i := 0; i < len(s.members); i++ {
+ if u.equal(num, s.members[i]) {
+ return true
+ }
+ }
+ return false
+}
+
+func (s *surrealSet) cardinality() int {
+ return len(s.members)
+}
+
+func (s *surrealSet) insert(num surrealNumber, u surrealUniverse) {
+ if !s.isMember(num, u) {
+ s.members = append(s.members, num)
+ }
+}
+
+func (s *surrealSet) remove(num surrealNumber, u surrealUniverse) {
+ for i := 0; i < len(s.members); i++ {
+ if u.equal(num, s.members[i]) {
+ s.members[i] = s.members[len(s.members)-1]
+ s.members = s.members[:len(s.members)-1]
+ }
+ }
+}
+
+// =============================================================================
+