/* Natural Number Example (Scala Version)
   H. Conrad Cunningham
   Version #1: 22 September 2008
   Version #2: 30 September 2008
     Added "require" precondition check to Succ and exceptions for 
       illegal comparisons, changed deprecated "boolean" to "Boolean"
   Version #2b: 16 February 2010
     Added more comments to explain Scala.

   The original Scala version of this was developed in Fall 2008 for
   the Multiparadigm Programming class (CSci 581/582).  It was based
   partly on previous Java and Ruby versions.  The Spring 2010 version
   mostly added new comments for the Software Design class.

123456789012345678901234567890123456789012345678901234567890123456789012345678

  This file defines a class hierarchy with abstract base class Nat
  and subclasses Zero, Succ, and Err.  This cluster defines a
  structural representation for the "natural numbers" inspired by
  Peano's Postulates.  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) as follows:

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

  The design of the Nat hierarchy uses the Composite design pattern to
  represent the natural numbers.  The abstract base class for the set
  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.)

  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.)

  The implementation below overrides Scala methods:

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

  Caveats: 

  - This program is one of the author's first Scala programs and was
    constructed, in part, to enable him to learn the features the Scala class
    structure and how to adapt object-oriented concepts previously used in the
    Java and Ruby environments into Scala.  It may not, in all cases,
    reflect the best Scala programming style.  

  - This 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.  

   Syntax notes:
   * Keyword "trait" introduces the construct.
   * This trait 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 >.
   * This trait 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 class of our Natural numbers.  It
  specifies the operations that Nats must support.  Additional
  operations should be included in a fully functional implementation.

  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.

  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 equals,
  defining it in terms of an abstract method equalsNat.

*/

abstract class Nat extends Ord[Nat] {

  def +(n: Nat): Nat  // addition:    this + n
  def -(n: Nat): Nat  // subtraction: this - n

  def pred:  Nat  // return "predecessor" of this natural number
  def toInt: Int  // convert to builtin integer representation

  /* This 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.
  */
  override def equals(that: Any): Boolean =
    that.isInstanceOf[Nat] && equalsNat(that.asInstanceOf[Nat])

  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.  

  Note that this object provides 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 {

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

  // Subtract Nat argument n:  0 - n = 0 if n = 0; otherwise error
  def -(n: Nat): Nat = if (n.equalsNat(Zero)) Zero else Err
  
  // Predecessor method undefined for Zero
  def pred: Nat = Err

  // Return Int equivalent
  def toInt: Int = 0

  // Convert Zero structure to String
  override def toString: String = "Zero"

  // Return true if and only if arg n is Zero
  def equalsNat(n: Nat): Boolean = n eq Zero

  // Determine whether receiver is smaller than Nat argument n; error if not  
  // comparable.  Note this may throw an exception.
  def <(n: Nat): Boolean =
    if (n.equalsNat(Zero)) false
    else if (n.isInstanceOf[Succ]) true
    else throw new RuntimeException("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 {

  require(m ne Err) // throw IllegalArgumentException if not
                    // ne and eq denote reference equality operators rather
                    // than value comparisons

  // Add Nat argument n to the receiver by recursively moving one
  // layer of Succ from the receiver to the argument on successive calls, 
  // stopping when the receiver becomes 0.	
  def +(n: Nat): Nat = if (n.equalsNat(Err)) Err else m + (new Succ(n))

  // Subtract Nat argument n from 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): Nat =
    if (n.equalsNat(Zero)) this
    else if (n.isInstanceOf[Succ]) pred - n.pred 
    else Err

  // Return predecessor
  def pred: Nat = m

  // Return Int equivalent
  def toInt: Int =  1 + pred.toInt

  // Convert Succ structure to String
  override def toString: String = "Succ(" + pred + ")"

  // Determine whether receiver and argument n have some number of
  // nested Nats.
  def equalsNat(n: Nat): Boolean =
    if ((n eq Zero) || (n eq Err)) false
    else pred.equalsNat(n.pred)

  //  Determine whether Nat argument 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 throw new RuntimeException("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 +(n: Nat): Nat = Err
  def -(n: Nat): Nat = Err

  // Predecessor method undefined for Err
  def pred: Nat = Err

  // There is no integer equivalent, so return negative value.
  def toInt: Int = -1
  
  // Convert Err structure to String
  override def toString: String = "Err"

  // Comparing for equality is tricky because of possible Err nested
  // inside Succ structure.
  def equalsNat(n: Nat): Boolean =
    if (n eq Err) true
    else if (n eq Zero) false
    else if (n.isInstanceOf[Succ]) Err.equalsNat(n.pred) 
    else false

  // Less than comparison needed to complete trait Ord
  def <(n: Nat): Boolean = 
    throw new RuntimeException("No ordering between Err and " + n)
}


/*
   Object Nat 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 {

  // Method to convert Int to Nat
  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.

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

*/

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("Zero as String       ==> " + Zero)
    println("Err as String        ==> " + Err)
    println("three as String      ==> " + three)
    println("six as String        ==> " + six)
    println("big as String        ==> " + big)
    println("bad as String        ==> " + bad)

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

    // Test Zero methods

    println("Zero + Zero          ==> " + (Zero + Zero))
    println("Zero + three         ==> " + (Zero + three))
    println("Zero + Err           ==> " + (Zero + Err))

    println("Zero - Zero          ==> " + (Zero - Zero))
    println("Zero - three         ==> " + (Zero - three))
    println("Zero - Err           ==> " + (Zero - Err))

    println("Zero == Zero         ==> " + (Zero == Zero))
    println("Zero == three        ==> " + (Zero == three))
    println("Zero == Err          ==> " + (Zero == Err))
    println("Zero == bad          ==> " + (Zero == bad))

    println("Zero < Zero          ==> " + (Zero < Zero))
    println("Zero < three         ==> " + (Zero < three))

    print(  "Zero < Err           ==> ")
    try   { println((Zero < Err)) }
    catch { case ex => println("Error:  " + ex.getMessage)}

//  println("Zero < bad           ==> " + (Zero < bad))

    println("Zero <= Zero         ==> " + (Zero <= Zero))

    print(  "Zero <= Err          ==> ")
    try   { println((Zero <= Err)) }
    catch { case ex => println("Error:  " + ex.getMessage) }

//  println("Zero <= bad          ==> " + (Zero <= bad))

    println("Zero > Zero          ==> " + (Zero > Zero))
    println("Zero > three         ==> " + (Zero > three))

    print(  "Zero > Err           ==> ")
    try   { println((Zero > Err)) }
    catch { case ex => println("Error:  " + ex.getMessage) }

//  println("Zero > bad           ==> " + (Zero > bad))

    println("Zero.toInt           ==> " + Zero.toInt)

    // Test Succ methods

    println("three + Zero         ==> " + (three + Zero))
    println("three + three        ==> " + (three + three))
    println("three + Err          ==> " + (three + Err))

    println("three - Zero         ==> " + (three - Zero))
    println("three - three        ==> " + (three - three))
    println("three - six          ==> " + (three - six))
    println("three - Err          ==> " + (three - Err))

    println("three == Zero        ==> " + (three == Zero))
    println("three == three       ==> " + (three == three)) 
    println("three == six         ==> " + (three == six))
    println("three == Err         ==> " + (three == Err))
    println("three == bad         ==> " + (three == bad))

    println("three < Zero         ==> " + (three < Zero))
    println("three < three        ==> " + (three < three))
    println("three < six          ==> " + (three < six))
    println("six   < three        ==> " + (six < three))

    print(  "three < Err          ==> ")
    try   { println((three < Err)) }
    catch { case ex => println("Error:  " + ex.getMessage) }

//  println("three < bad          ==> " + (three < bad))

    println("three <= Zero        ==> " + (three <= Zero))
    println("three <= three       ==> " + (three <= three))
    println("three <= six         ==> " + (three <= six))
    println("six   <= three       ==> " + (six <= three))

    print(  "three <= Err         ==> ")
    try   { println((three <= Err)) }
    catch { case ex => println("Error:  " + ex.getMessage) }

//  println("three <= bad         ==> " + (three <= bad))

    println("three > Zero         ==> " + (three > Zero))
    println("three > three        ==> " + (three > three))
    println("three > six          ==> " + (three > six))
    println("six   > three        ==> " + (six > three))

    print(  "three > Err          ==> ")
    try   { println((three > Err)) }
    catch { case ex => println("Error:  " + ex.getMessage) }

//  println("three > bad          ==> " + (three > bad))

    println("three.toInt          ==> " + three.toInt)

    println("three.pred           ==> " + three.pred)

    // Test Err methods

    println("Err + Zero           ==> " + (Err + Zero))
    println("Err + three          ==> " + (Err + three))
    println("Err + Err            ==> " + (Err + Err))

    println("Err - Zero           ==> " + (Err - Zero))
    println("Err - three          ==> " + (Err - three))
    println("Err - Err            ==> " + (Err - Err))

    println("Err == Zero          ==> " + (Err == Zero))
    println("Err == three         ==> " + (Err == three)) 
    println("Err == Err           ==> " + (Err == Err)) 
    println("Err == bad           ==> " + (Err == bad)) 

    print(  "Err < three          ==> ")
    try   { println((Err < three)) }
    catch { case ex => println("Error:  " + ex.getMessage) }

    println("Err.toInt            ==> " + Err.toInt)

    // Test precondition on Succ construction
    print(  "new Succ(Err)        ==> ")
    try   { println(new Succ(Err)) }
    catch { case ex => 
              println("Error on Succ constructor precondition check:  " + 
                       ex.getMessage) 
          }
  }
}