/* Natural Number Arithmetic using Peano-Inspired Structures
   Using Functional Object-Oriented Style with Ordinary Classes
   H. Conrad Cunningham, Professor
   Computer and Information Science
   University of Mississippi

1234567890123456789012345678901234567890123456789012345678901234567890

2008-09-22: Developed for Fall 2008 Multiparadigm Programming course
2008-09-30: Added "require" precondition check to Succ;
            exceptions for illegal comparisons;
	    changed deprecated "boolean" to "Boolean"
2010-02-16: Added more comments to explain Scala features
2012-02-14: Made code/comments better match case class versions
2016-02-10: Cleaned code and format; changed obsolete Scala usage
2019-02-24: Updated code to use interpolated lists; updated comments
2019-02-26: Updated format and comments

The original Scala version of this was developed in Fall 2008 for the
first offering of Multiparadigm Programming (as CSci 581/582, now CSci
556).  It was based partly on previous Java and Ruby versions.  I
subsequently modified the code and comments for various courses in
Spring 2010, Spring 2012, Spring 2016, and Spring 2019.

This file defines a type hierarchy with abstract class Nat and
classes/objects Zero, Succ, and Err that extend the trait.  This
cluster defines a structural representation for the "natural numbers"
inspired by Peano's Postulates, a well-know axiomization of the
natural numbers.  The implementation does not use any builtin integer
type.  We consider 0 as being a natural number as is customary for
many computer scientists.

Mathematically, we can define the set Nat (of natural numbers)
inductively as follows:

    x in Nat if and only if 
         (1) x = 0                                -- zero
      or (2) (Exists y : y in Nat :: x = Succ(y)) -- successor

The design of the Nat hierarchy uses the Composite design pattern to
represent the natural numbers. The base type for the hierarchy is Nat.
Singleton object Zero is a leaf case of the Composite design pattern;
it represents 0. Subclass Succ is the composite case of the Composite
pattern; it represents the successor (i.e. add 1) to the single Nat
value it contains.  Singleton object Err, which represents errors, is
a second leaf case of the Composite pattern.

Aside: The Composite design pattern is a type hierarchy with a base
class and two types of subclasses.  The leaf subclasses denote
irreducible objects of that base class.  The composite subclasses
denote objects of the base class that contain a collection of other
(composite or leaf) objects of the base class.

The design of singleton object Err also illustrates the Null Object
design pattern, in that it is a null or inert object that can be
safely returned by operations in error situations.  (Of course, this
is not a complete solution for errors that arise in ordered comparison
operations.)

2019-02-24 Note: A design that uses the Scala Option algebraic data
type might be a better Scala design than introducing Null Object Err.

The Nat hierarchy essentially gives a unary representation for the
natural numbers; there is one Succ object in a linear structure for
each natural number value greater than 0. (This may be seen visually
by applying toString to a Nat object.)

Example:  The object created by the Scala code 

    new Succ(new Succ(new Succ(Zero)))

represents the integer value 3.

The implementation overrides Scala methods:

    toString to print the Nat structure in a parenthesized notation
    
    equals is redefined to compare for equal values.

Caveat: This program was one of my first Scala programs developed in
2008. I constructed it, in part, to learn the object-oriented features
of Scala and to learn how to adapt the object-oriented techniques I
used perviously in Java and Ruby. The original program did not, in all
cases, reflect the best Scala programming style.  For example, this
version relies too much on the type queries (isInstanceOf) and casting
(asInstanceOf). I created other versions to explore use of features
like case classes and pattern matching.  The class hierarchy does not
implement all the features that would be needed for a natural number
abstract data type in the Scala environment.

*/


/* Mixin trait Ord is adapted that that in from _A Scala Tutorial for
   Java Programmers_.  This trait can be mixed in to any class and
   provide all six ordered operations just by implementing equals and
   < appropriately.

   2019-02-24 Note: Using builtin trait scala.math.Ordered would
   enable better use of Scala features.

   Scala syntax notes:

   * Keyword "trait" introduces the construct.

   * Ord has a generic type parameter T to represent the type of
     the elements to be compared.

   * Traits do not have a constructor and, hence, no constructor
     parameters.

   * Methods can be named using operator symbols such as < and >.

   * Ord has abstract method < and concrete methods <=, >. and >=.
     The concrete methods are defined directly or indirectly in terms
     of the abstract method < and the builtin method ==.

*/

trait Ord[T] {
  def < (that: T): Boolean
  def <=(that: T): Boolean = (this < that) || (this == that)
  def > (that: T): Boolean = !(this <= that)
  def >=(that: T): Boolean = !(this < that)
}


/* Abstract class Nat is the base type for our Natural numbers.  It
   specifies the operations that Nats must support.  Additional
   operations should be included in a fully functional implementation.

   Abstract class Nat provides default implementations for some
   methods.  Some of the subclasses will need to override these to get
   the desired behaviors.  For example, toString is overridden to give
   a meaningful display of the data.

   The binary operators (i.e. methods) for addition (+) and
   subtraction (-) are defined so that they can be used in the infix
   style. For example, x + y represents the method call x.+(y).

   Note that Nat extends (i.e. mixes-in) trait Ord with the specific
   type parameter being Nat itself.

   Also note that Nat overrides the default definition of the equals
   operator, defining it in terms of abstract method equalsNat.

   2019-02-24 Note: Using a "sealed trait" would likely be a better
   Scala design.

*/

abstract class Nat extends Ord[Nat] {

  // returns Nat to which applying Succ would get this back
  def pred:  Nat

  // adds n to this and returns result  
  def +(n: Nat): Nat

  // subtracts n from this and returns result   
  def -(n: Nat): Nat

  // returns builtin integer representation for this Nat
  def toInt: Int

  /* Method equals overrides the default definition of equals and
     defines it in terms of abstract method equalsNat.

     Syntax notes:

     * isInstance[T] returns true if and only if the receiver object
       has type T.
       
     * asInstance[T] "coerces" its receiver object to be considered as
       an instance of type T.  This fails if the object does not
       inherit from T.
       
     * The == operator calls the "equals" method.
  */
  
  override def equals(that: Any): Boolean =
    that.isInstanceOf[Nat] && equalsNat(that.asInstanceOf[Nat])

  // equals comparison limited to Nat objects.
  def equalsNat(n: Nat): Boolean // this == n 
}


/* Singleton object Zero represents the natural number 0.  It is a
   leaf case of the Composite design pattern.

   This object gives concrete definitions of abstract methods +, -,
   pred, toInt, and equalsNat from Nat and < from Ord.  It also
   overrides the definition of toString.

*/

object Zero extends Nat {

  // predecessor undefined for Zero
  def pred: Nat = Err

  // 0 + n = n
  def +(n: Nat): Nat = n

  // 0 - n = 0 if n = 0; otherwise error
  def -(n: Nat): Nat = if (n.equalsNat(Zero)) Zero else Err
  
  def toInt: Int = 0

  override def toString: String = "Zero"

  def equalsNat(n: Nat): Boolean = (n eq Zero) // eq is identity op

  /* Comparison operation (<) provides the missing relational operator
     for trait Ord.  It determines whether the receiver is smaller
     than the Nat argument n.  It is an error if not comparable.

     This method may throw an exception.
  */
  
  def <(n: Nat): Boolean = 
    if (n.equalsNat(Zero))
      false 
    else if (n.isInstanceOf[Succ])
      true 
    else
      sys.error(s"No ordering between Zero and $n")
}


/* Subclass Succ is the composite case of the Composite design
   pattern. It has one attribute that is itself a Nat.  An object of
   the class represents the successor value (i.e. one greater) to the
   attribute.
*/

class Succ(m: Nat) extends Nat {
  // 'this' object represents value m+1

  require(m ne Err) // throw IllegalArgumentException if not
                    // ne and eq are reference equality operators

  def pred: Nat = m

  /* The (+) method implementation adds its Nat argument n to the
     receiver by recursively moving one "layer" of Succ constructors
     from the receiver to the argument on each successive call,
     stopping when the receiver becomes Zero.
  */

  def +(n: Nat): Nat =
     if (n.equalsNat(Err))
       Err
     else
       m + (new Succ(n))

  /* The (-) method implementation subtracts its Nat argument n from
     the receiver by recursively removing one layer of Succ
     constructors from both the receiver and the argument on each
     successive call, stopping when one or other becomes Zero.
  */

  def -(n: Nat): Nat =
    if (n.equalsNat(Zero))
      this
    else if (n.isInstanceOf[Succ])
      pred - n.pred
    else
      Err

  def toInt: Int =  1 + pred.toInt

  override def toString: String = "Succ(" + pred + ")"

  /* The equalsNat method determines whether receiver and argument n
     have some number of nested Nats by removing one layer of Succ
     constructors for each call.
  */
  
  def equalsNat(n:Nat): Boolean =
    (n ne Zero) && (n ne Err) && pred.equalsNat(n.pred)

  /* The (<) method implementation determines whether n is smaller
     than the receiver by recursively removing one layer of Succ from
     both the receiver and the argument on successive calls, stopping
     when one or other becomes Zero.
  */
  
  def <(n: Nat): Boolean =
    if (n.equalsNat(Zero))
      false 
    else if (n.isInstanceOf[Succ])
      pred < n.pred 
    else
      sys.error(s"No ordering between Succ and $n")
}


/* Subclass Err represents an error value.  Like Zero, it is a leaf
   case of the Composite design pattern that itself is a Singleton.

   In addition, Err implements the Null Object pattern in that it (in
   most cases) represents an inert Nat object that can be returned in
   most error situations.
*/

object Err extends Nat {

  // If possible, do not do anything for any mutator operation
  def pred: Nat      = Err
  def +(n: Nat): Nat = Err
  def -(n: Nat): Nat = Err

  // There is no nonnegative integer equivalent, so return -1 
  def toInt: Int = -1
  
  override def toString: String = "Err"

  // Assumes Err not nested within Succ.
  def equalsNat(n: Nat): Boolean =
    (n eq Err) || (n ne Zero) // modify if nested Err possible

  def <(n: Nat): Boolean = 
    sys.error(s"No ordering between Err and $n")
}


/* Singleton object Nat, called the companion object for the Nat
   class, holds the utility methods associated with the Nat hierarchy.

   Note: This object has the same name as the class Nat, but the
   object is different from the class.
*/

object Nat {

  // toNat converts an Int to the Nat equivalent.  
  def toNat(i: Int): Nat =
    if (i > 0)
      new Succ(toNat(i-1))
    else if (i == 0)
      Zero
    else
      Err

}


/* Object TestNats does some testing of the Nat hierarchy methods.
   The testing is probably not as complete as would be desirable.

    Note the syntax for catching an exception toward the end of this
    method.

    2019-02-24 Note: It would be better to compare outputs versus
    expected results on tests.

*/

/* Do import to allow toNat to be called without "Nat." prefix. */

import Nat._

object TestNats {

  // Main method for testing
  def main(args: Array[String]) {

    // Constants to use in tests
    val three = new Succ(new Succ(new Succ(Zero)))
    val six   = new Succ(new Succ(new Succ(three)))
    val big   = 100
    val bad   = -1

    // Test toString
    println(s"Zero as String  ==> $Zero")
    println(s"Err as String   ==> $Err")
    println(s"three as String ==> $three")
    println(s"six as String   ==> $six")
    println(s"big as String   ==> $big")
    println(s"bad as String   ==> $bad")

    // Test conversion from Int to Nat and testing toString
    println(s"Nat.toNat(0)    ==> ${toNat(0)}")
    println(s"Nat.toNat(5)    ==> ${toNat(5)}")
    println(s"Nat.toNat(big)  ==> ${toNat(big)}")
    println(s"Nat.toNat(bad)  ==> ${toNat(bad)}")


    // Test Zero methods

    println(s"Zero + Zero     ==> ${Zero + Zero}")
    println(s"Zero + three    ==> ${Zero + three}")
    println(s"Zero + Err      ==> ${Zero + Err}")

    println(s"Zero - Zero     ==> ${Zero - Zero}")
    println(s"Zero - three    ==> ${Zero - three}")
    println(s"Zero - Err      ==> ${Zero - Err}")

    println(s"Zero == Zero    ==> ${Zero == Zero}")
    println(s"Zero == three   ==> ${Zero == three}")
    println(s"Zero == Err     ==> ${Zero == Err}")
    println(s"Zero == bad     ==> ${Zero == bad}")

    println(s"Zero < Zero     ==> ${Zero < Zero}")
    println(s"Zero < three    ==> ${Zero < three}")

    print(   "Zero < Err      ==> ")
    try   { println((Zero < Err)) }
    catch { case ex: Throwable => 
              println(s"ERROR\n  ${ex.getMessage}") }

//  println(s"Zero < bad      ==> ${Zero < bad}")

    println(s"Zero <= Zero    ==> ${Zero <= Zero}")

    print(  "Zero <= Err     ==> ")
    try   { println((Zero <= Err)) }
    catch { case ex: Throwable => 
              println(s"ERROR\n  ${ex.getMessage}") }

//  println(s"Zero <= bad     ==> ${Zero <= bad}")

    println(s"Zero > Zero     ==> ${Zero > Zero}")
    println(s"Zero > three    ==> ${Zero > three}")

    print(  "Zero > Err      ==> ")
    try   { println((Zero > Err)) }
    catch { case ex: Throwable => 
              println(s"ERROR\n  ${ex.getMessage}") }

//  println(s"Zero > bad      ==> ${Zero > bad}")

    println(s"Zero.pred       ==> ${Zero.pred}")
    println(s"Zero.toInt      ==> ${Zero.toInt}")


    // Test Succ methods

    println(s"three + Zero    ==> ${three + Zero}")
    println(s"three + three   ==> ${three + three}")
    println(s"three + Err     ==> ${three + Err}")

    println(s"three - Zero    ==> ${three - Zero}")
    println(s"three - three   ==> ${three - three}")
    println(s"three - six     ==> ${three - six}")
    println(s"three - Err     ==> ${three - Err}")

    println(s"three == Zero   ==> ${three == Zero}")
    println(s"three == three  ==> ${three == three}") 
    println(s"three == six    ==> ${three == six}")
    println(s"three == Err    ==> ${three == Err}")
    println(s"three == bad    ==> ${three == bad}")

    println(s"three < Zero    ==> ${three < Zero}")
    println(s"three < three   ==> ${three < three}")
    println(s"three < six     ==> ${three < six}")
    println(s"six   < three   ==> ${six < three}")

    print(  "three < Err     ==> ")
    try   { println((three < Err)) }
    catch { case ex: Throwable => 
              println(s"ERROR\n  ${ex.getMessage}") }

//  println(s"three < bad     ==> ${three < bad}")

    println(s"three <= Zero   ==> ${three <= Zero}")
    println(s"three <= three  ==> ${three <= three}")
    println(s"three <= six    ==> ${three <= six}")
    println(s"six   <= three  ==> ${six <= three}")

    print(   "three <= Err    ==> ")
    try   { println((three <= Err)) }
    catch { case ex: Throwable =>
              println(s"ERROR\n  ${ex.getMessage}") }

//  println(s"three <= bad    ==> ${three <= bad}")

    println(s"three > Zero    ==> ${three > Zero}")
    println(s"three > three   ==> ${three > three}")
    println(s"three > six     ==> ${three > six}")
    println(s"six   > three   ==> ${six > three}")

    print(   "three > Err     ==> ")
    try   { println((three > Err)) }
    catch { case ex: Throwable => 
              println(s"ERROR\n  ${ex.getMessage}") }

//  println(s"three > bad     ==> ${three > bad}")

    println(s"three.pred      ==> ${three.pred}")
    println(s"three.toInt     ==> ${three.toInt}")


    // Test Err methods

    println(s"Err + Zero      ==> ${Err + Zero}")
    println(s"Err + three     ==> ${Err + three}")
    println(s"Err + Err       ==> ${Err + Err}")

    println(s"Err - Zero      ==> ${Err - Zero}")
    println(s"Err - three     ==> ${Err - three}")
    println(s"Err - Err       ==> ${Err - Err}")

    println(s"Err == Zero     ==> ${Err == Zero}")
    println(s"Err == three    ==> ${Err == three}") 
    println(s"Err == Err      ==> ${Err == Err}") 
    println(s"Err == bad      ==> ${Err == bad}") 

    print(  "Err < three==> ")
    try   { println((Err < three)) }
    catch { case ex: Throwable => 
              println(s"ERROR\n  ${ex.getMessage}") }

    println(s"Err.pred   ==> ${Err.pred}")
    println(s"Err.toInt  ==> ${Err.toInt}")

    // Test precondition on Succ construction
    print(   "new Succ(Err)   ==>")
    try   { println(new Succ(Err)) }
    catch { case ex: Throwable =>
              println("ERROR\n  Succ constructor precondition fails")
              println(s"  ${ex.getMessage}")
          }
  }
}