# Natural Number Example (Version #2)
# H. C. Cunningham
# 13 September 2006

# This file defines a class hierarchy with base class Nat and subclasses
# Zero, Succ, and Err.  This cluster of classes 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 natural numbers.  The "abstract" base class for the set is Nat.
# Subclass Zero is a leaf case of the Composite 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.  Subclass Err, which represents errors, is a second leaf case of
# the Composite pattern.

# The designs and implementations of subclasses Zero and Err also reflect
# the Singleton design pattern, which provides for exactly one instance of
# each of those classes to be created.

# In addition, subclass Err reflects the Null Object pattern, in that its
# instances are null or inert objects 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 such as
# is_less?.)

# 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 to_s to a Nat object.)

# The implementation below redefines several Ruby methods from root class
# Object:
#
#     to_s is redefined to print the Nat structure in a parenthesized
#       notation,
#     eql? is redefined to compare for equal values 
#       (assuming Singletons for Zero and Err)
#     == is redefined to be the same as eql?
#     clone is redefined to do deep copy of Nat structure

# Note: The builtin definition of clone just creates copies for the
# top-level object in a structure, not for any other objects referenced by
# that object.  That is, it does a shallow copy.

# Caveats: This program is one of the author's first Ruby programs and was
# constructed, in part, to enable him to learn the features the Ruby class
# structure and how to adapt object-oriented concepts previously used in the
# Java environment into Ruby.  It may not, in all cases, reflect the best
# Ruby programming style.  Also, this class hierarchy does not implement all
# the features that would be needed for a natural number abstract data type
# in the Ruby environment.

# Issues for future thought and work:
#     use of module Comparable mixins or other support for comparisons
#     connection of Nat to Integer or Numeric?
#     overriding of other default methods from Object
#     implement other arithmetic operators?

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

# Because Ruby does not support abstract classes, we achieve a similar
# result by causing an attempt to create objects of the class or call any of
# the abstract methods to raise exception NotImplementedError.

# Class Nat provides default implementations for some methods.  Some of the
# subclasses will need to override these to get the desired behaviors.  For
# example, clone is overridden in Succ to give the desired deep copy
# functionality.

class Nat
  def initialize;   raise NotImplementedError;  end

  # Deferred methods
  def add(x);       raise NotImplementedError;  end
  def sub(x);       raise NotImplementedError;  end
  def is_less?(x);  raise NotImplementedError;  end
  def to_i;         raise NotImplementedError;  end

  # Default concrete methods to redefine Object methods.
  # May be overridden when alternative functionality needed.
  def clone;  self;             end  # by default, no copy
  def to_s;   self.class.to_s;  end  # by default, return class name
  def ==(n);  self.eql? n;      end  # by default, same as eql?

  # Class method to convert Fixnum to Nat
  def Nat.to_n(i)
    if i.instance_of? Fixnum 
      if i > 0
        Succ.new(to_n(i-1))
      elsif i == 0
        Zero.the_zero
      else
        Err.the_err
      end
    else
      Err.the_err
    end
  end

end

#####
# Subclass Zero represents the natural number 0.  It is a leaf case of the
# Composite design pattern.  The class implements the Singleton design
# pattern by (1) making method "new" private, (2) creating one object of the
# class and storing its reference in class variable @@zero, and (3)
# introducing a class method Zero.the_zero to enable clients of the class to
# get the reference to the Singleton.

class Zero < Nat

  # Disallow external calls of new, to implement Singleton.
  private_class_method :new
  @@zero = nil

  def initialize; end

  # Accessor for Singleton object Zero
  def Zero.the_zero
    @@zero = new if @@zero == nil 
    @@zero
  end

  # Add Nat argument n:  0 + n = n; otherwise error
  def add(n)
    if n.kind_of? Nat
      n
    else
      Err.the_err
    end
  end

  # Subtract Nat argument n:  0 - n = 0 if n = 0; otherwise error
  def sub(n)
    if @@zero.eql? n  # compare values; eql? overridden in subclasses
      @@zero
    else
      Err.the_err
    end
  end

  # Return Fixnum equivalent
  def to_i;  0;  end

  # Determine whether receiver is smaller than Nat argument n; error if not  
  # comparable 
  def is_less?(n)
    if n.instance_of? Succ or Zero.the_zero.eql? n
      ! @@zero.eql? n  # compare values; eql? overridden in subclasses
    else
      raise "Attempt to compare unordered objects"
    end
  end
      
  # Equal iff Nat argument n is the same object as Singleton Zero
  def eql?(n);  @@zero.equal? n;  end

end

#####
# 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 < Nat

  # Initialize reference to Nat for which this is successor; error if
  # argument n is not a Nat.
  def initialize(n)
    if n.instance_of? Succ or Zero.the_zero.eql? n
      @rest = n
    else
      raise "Attempt to create illegal Succ object"
    end
  end

  # 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 add(n)
    if n.instance_of? Succ or Zero.the_zero.eql? n
      @rest.add(Succ.new(n))
    else
      Err.the_err
    end
  end

  # 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 sub(n)
    if n.instance_of? Succ
      @rest.sub(n.pred)
    elsif Zero.the_zero.eql? n
      self
    else
      Err.the_err
    end
  end

  # Redefine clone to do deep copy of Succ sequences (but not Zero or Err)
  def clone;  Succ.new(@rest.clone);  end

  # Return Fixnum equivalent
  def to_i;  1 + @rest.to_i;  end

  # Convert Succ structure to String
  def to_s;  self.class.to_s + "(" + @rest.to_s + ")";  end

  # 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 is_less?(n)
    if n.instance_of? Succ
      @rest.is_less? n.pred
    elsif Zero.the_zero.eql? n
      false
    else
      raise "Attempt to compare unordered objects"
    end
  end

  # Determine whether receiver and argument n have some number of nested Nats.
  def eql?(n)
    if n.instance_of? Succ
      @rest.eql? n.pred
    else
      false
    end
  end

  # Return predecessor of this Succ
  def pred;  @rest;  end

end

#####
# Subclass Err represents an error value.  Like Zero, it is a leaf case of
# the Composite design pattern that also implements the Singleton design
# pattern.  In addition, Nil implements the Null Object pattern in that it
# (in most cases) represents an inert Nat object that can be returned in
# most error situations.

class Err < Nat

  # Disallow external calls of new, to implement Singleton.
  private_class_method :new
  @@err = nil

  def initialize;  end

  # Accessor for Singleton object Zero
  def Err.the_err
    @@err = new if @@err == nil 
    @@err
  end

  # If possible, do not do anything for any mutator operation

  def add(n);  self;  end

  def sub(n);  self;  end

  # There is no Fixnum equivalent, so return negative value.
  def to_i;  -1;  end

  def is_less?(n)
    raise "Attempt to compare unordered object Err"
  end
  
  # Comparing for equality is tricky because of possible Err nested inside
  # Succ structure.
  def eql?(n)
    if @@err.equal? n  # compare for identity to Singleton Err object
      true
    elsif Zero.the_zero.eql? n
      false
    elsif n.instance_of? Succ
      self.eql? n.pred
    else
      false
    end
  end

end

#####
# Class method TestNat
# This class does some testing of the Nat hierarchy methods.  The testing is
# not as complete as would be desirable.

class TestNat

  # Call "TestNat.do_test" to do some tests of the classes defined in
  # this file.

  def TestNat.do_test

    # Bad data to use in tests
    bad = "BAD"
    puts "bad = \"#{bad}\""
    big = 1000000000000
    puts "big = #{big}"

    # Test restriction on instantiation of Nat objects
    begin
      print "Nat.new                ==> "; puts Nat.new
    rescue NotImplementedError
      puts "Exception: " + $!
    end

    # Test Zero creation
    print "zero = Zero.the_zero   ==> "; puts (zero = Zero.the_zero)
    print "zero.to_s              ==> "; puts zero.to_s
    print "zero.inspect           ==> "; puts zero.inspect

    # Test Err creation
    print "err = Err.the_err      ==> "; puts (err = Err.the_err)
    print "err.to_s               ==> "; puts err.to_s
    print "err.inspect            ==> "; puts err.inspect

    # Test Succ creation
    print "three = Succ.new(Succ.new(Succ.new(zero))) ==> ";
    puts (three = Succ.new(Succ.new(Succ.new(zero))))
    print "three.to_s             ==> "; puts three
    puts  "three.inspect          ==> "; puts three.inspect

    # Test conversion from Fixnum to Nat
    print "Nat.to_n(0)            ==> "; puts Nat.to_n(0)
    print "Nat.to_n(5)            ==> "; puts Nat.to_n(5)
    print "Nat.to_n(-1)           ==> "; puts Nat.to_n(-1)
    print "Nat.to_n(bad)          ==> "; puts Nat.to_n(bad)
    print "Nat.to_n(big)          ==> "; puts Nat.to_n(big)

    # Test Zero methods
    print "zero.add(zero)         ==> "; puts zero.add(zero)
    print "zero.add(three)        ==> "; puts zero.add(three)
    print "zero.add(err)          ==> "; puts zero.add(err)
    print "zero.add(bad)          ==> "; puts zero.add(bad)

    print "zero.sub(zero)         ==> "; puts zero.sub(zero)
    print "zero.sub(three)        ==> "; puts zero.sub(three)
    print "zero.sub(err)          ==> "; puts zero.sub(err)
    print "zero.sub(bad)          ==> "; puts zero.sub(bad)

    print "zero.eql? zero         ==> "; puts (zero.eql? zero)
    print "zero.eql? three        ==> "; puts (zero.eql? three)
    print "zero.eql? err          ==> "; puts (zero.eql? err)
    print "zero.eql? bad          ==> "; puts (zero.eql? bad)

    print "zero == zero           ==> "; puts (zero == zero)
    print "zero == three          ==> "; puts (zero == three)
    print "zero == err            ==> "; puts (zero == err)
    print "zero == bad            ==> "; puts (zero.eql? bad)

    print "zero.is_less? zero     ==> "; puts (zero.is_less? zero)
    print "zero.is_less? three    ==> "; puts (zero.is_less? three)
    begin
      print "zero.is_less? err      ==> "; puts (zero.is_less? err)
    rescue 
      puts "Exception: " + $!
    end
    begin
      print "zero.is_less? bad      ==> "; puts (zero.is_less? bad)
    rescue 
      puts "Exception: " + $!
    end

    print "zero.to_i              ==> "; puts zero.to_i

    print "zero.clone             ==> "; puts zero.clone.inspect

    # Test Succ methods
    print "three.add(zero)        ==> "; puts three.add(zero)
    print "six = three.add(three) ==> "; puts (six = three.add(three))
    print "six.to_s               ==> "; puts six.to_s
    print "three.add(err)         ==> "; puts three.add(err)
    print "three.add(bad)         ==> "; puts three.add(bad)

    print "three.sub(zero)        ==> "; puts three.sub(zero)
    print "three.sub(three)       ==> "; puts three.sub(three)
    print "three.sub(six)         ==> "; puts three.sub(six) 
    print "three.sub(err)         ==> "; puts three.sub(err)
    print "three.sub(bad)         ==> "; puts three.sub(bad)

    print "three.eql? zero        ==> "; puts (three.eql? zero) 
    print "three.eql? three       ==> "; puts (three.eql? three) 
    print "three.eql? six         ==> "; puts (three.eql? six) 
    print "three.eql? err         ==> "; puts (three.eql? err) 
    print "three.eql? bad         ==> "; puts (three.eql? bad) 

    print "three == zero          ==> "; puts (three == zero) 
    print "three == three         ==> "; puts (three == three) 
    print "three == six           ==> "; puts (three == six) 
    print "three == err           ==> "; puts (three == err) 
    print "three == bad           ==> "; puts (three == bad) 

    print "three.is_less? zero    ==> "; puts (three.is_less? zero)
    print "three.is_less? three   ==> "; puts (three.is_less? three)
    print "three.is_less? six     ==> "; puts (three.is_less? six)
    begin
      print "three.is_less? err     ==> "; puts (three.is_less? err)
    rescue 
      puts "Exception: " + $!
    end
    begin
      print "three.is_less? bad     ==> "; puts (three.is_less? bad)
    rescue 
      puts "Exception: " + $!
    end

    print "three.to_i             ==> "; puts three.to_i

    print "three.pred             ==> "; puts three.pred

    puts  "three.clone            ==> "; puts three.clone.inspect
    print "three.clone.equal? three ==> "; puts (three.clone.equal? three)

    # Test Err methods
    print "err.add(zero)          ==> "; puts err.add(zero)
    print "err.add(three)         ==> "; puts err.add(three)
    print "err.add(err)           ==> "; puts err.add(err)
    print "err.add(bad)           ==> "; puts err.add(bad)

    print "err.sub(zero)          ==> "; puts err.sub(zero)
    print "err.sub(three)         ==> "; puts err.sub(three)
    print "err.sub(err)           ==> "; puts err.sub(err)
    print "err.sub(bad)           ==> "; puts err.sub(bad)

    print "err.eql? zero          ==> "; puts (err.eql? zero)
    print "err.eql? three         ==> "; puts (err.eql? three) 
    print "err.eql? err           ==> "; puts (err.eql? err) 
    print "err.eql? bad           ==> "; puts (err.eql? bad) 

    print "err == zero            ==> "; puts (err == zero) 
    print "err == three           ==> "; puts (err == three) 
    print "err == err             ==> "; puts (err == err) 
    print "err == bad             ==> "; puts (err == bad) 

    begin
      print "err.is_less? three     ==> "; puts (err.is_less? three)
    rescue 
      puts  "Exception: " + $!
    end

    print "err.to_i               ==> "; puts err.to_i

    print "err.clone              ==> "; puts err.clone.inspect

    r = "esrever".reverse;  s = "deksafiesiarpeerf";  puts "\"#{s}\".#{r}"

  end

end