def initialize string
    case string
    when String
        @string, @ptree = string, nil
    when Node
        @string, @ptree = nil, string
    else
        @string, @ptree = String(string), nil
    end
    @copy = @lexstat = nil
end

#
# === LEXICAL ANALYZER ===
#

def rewind
    @copy = @string.dup.strip
    @lexstat = nil
end

RE_SPACE	= '([ \t])'
RE_INTEGER	= '([-+]?\d+)'
RE_EXP		= '([eE][-+]?[0-9]+)'
RE_REAL		= "([-+]?[0-9]*(\\.[0-9]*#{RE_EXP}?|#{RE_EXP}))"
RE_YEAR		= "([-+]?[0-9]{1,4})"
RE_MONTH	= "(0?[1-9]|1[0-2])"
RE_DAY		= "([12][0-9]|30|31|0?[1-9])"
RE_HOUR		= "(2[0-3]|[0-1]?[0-9])"
RE_MINUTE	= "([0-5]?[0-9])"
RE_SECOND	= "((#{RE_MINUTE}|60)(\\.[0-9]*)?)"
RE_NAME		= "(%|[a-zA-Z][a-zA-Z_]*([0-9]+[a-zA-Z_]+)*)"

RE_DATE		= "#{RE_YEAR}-#{RE_MONTH}-#{RE_DAY}"
RE_TIME		= "#{RE_HOUR}((:[0-5]?[0-9]|[0-5][0-9])(:#{RE_SECOND})?)?"
RE_HandM	= "#{RE_HOUR}((:[0-5]?[0-9]|[0-5][0-9]))?"

def next_token

    # decomment
    @copy.sub!(/^#.*/, '');

    if @copy.sub!(%r{^\s*(\))}, '') then
	@lexstat = nil
	return [$1, $1]
    end

    if @copy.sub!(%r{^\s*(\()\s*}, '') then
	return [$1, $1]
    end

    if @copy.sub!(%r{^[ \t]*(@|after|from|since|ref)[ \t]*}i, '') then
	@lexstat = :SHIFT_SEEN
	return [:SHIFT, $1]
    end

    if @copy.sub!(%r{^[ \t]*(per|PER|/)[ \t]*}, '') then
	@lexstat = nil
	return [:DIVIDE, $1]
    end

    if @copy.sub!(%r{^(\^|\*\*)}, '') then
	@lexstat = nil
	return [:EXPONENT, $1]
    end

    if @copy.sub!(%r{^(\.|\*|[ \t]+)}, '') then
	@lexstat = nil
	return [:MULTIPLY, $1]
    end

    if :SHIFT_SEEN === @lexstat \
    and @copy.sub!(%r{^#{RE_DATE}T?[ \t]*}, '') then
	y, m, d = $1, $2, $3
	@lexstat = :DATE_SEEN
	return [:DATE, XDate.new(y.to_i, m.to_i, d.to_i)]
    end

    if :SHIFT_SEEN === @lexstat \
    and @copy.sub!(%r{^now[ \t]*}, '') then
	@lexstat = nil
	return [:DATE, :now]
    end

    if :DATE_SEEN === @lexstat \
    and @copy.sub!(%r{^#{RE_TIME}[ \t]*}, '') then
	h, m, s = $1, $3, $5
        m = m.sub(/:/,'') if m
	s = 0 if s.nil?
	@lexstat = :TIME_SEEN
	return [:TIME, ((h.to_i * 60 + m.to_i) * 60 + Float(s))]
    end

    if :DATE_SEEN === @lexstat \
    and @copy.sub!(%r{^([0-2][0-9])([0-5][0-9])[ \t]*}, '') then
	h, m = $1, $2
	@lexstat = :TIME_SEEN
	return [:TIME, ((h.to_i * 60 + m.to_i) * 60.0)]
    end

    if :DATE_SEEN === @lexstat \
    and @copy.sub!(%r{^([0-9])([0-5][0-9])[ \t]*}, '') then
	h, m = $1, $2
	@lexstat = :TIME_SEEN
	return [:TIME, ((h.to_i * 60 + m.to_i) * 60.0)]
    end

    if :TIME_SEEN === @lexstat \
    and @copy.sub!(%r{^UTC[ \t]*}, '') then
	@lexstat = nil
	return [:ZONE, 0]
    end

    if :TIME_SEEN === @lexstat \
    and @copy.sub!(%r{^([-+]?)#{RE_HandM}[ \t]*}, '') then
	sgn, h, m = $1, $2, $4
        m = m.sub(/:/,'') if m
	@lexstat = nil
	h = h.to_i
	h = -h if sgn == "-"
	m = m.to_i
	m = -m if sgn == "-"
	return [:ZONE, ((h * 60) + m)]
    end

    if @copy.sub!(%r{^#{RE_NAME}}, '') then
	@lexstat = nil
	return [:NAME, $1]
    end

    if @copy.sub!(%r{^#{RE_REAL}}, '') then
	@lexstat = nil
	return [:REAL, $1.to_f]
    end

    if @copy.sub!(%r{^#{RE_INTEGER}}, '') then
	@lexstat = nil
	return [:INT, $1.to_i]
    end

    if @copy.sub!(%r{^(-)}, '') then
	@lexstat = nil
	return [:MULTIPLY, $1]
    end

    if @copy.sub!(%r{^(.)}, '') then
	return [$1, $1]
    end

    return [false, false]

end

#
# === USER LEVEL METHODS ===
#

def tokens
    rewind
    x = []
    while (t = next_token).first
	x.push t
    end
    x
end

def do_parse2
    rewind
    return ErrorNode.new('') if @string.nil? or @string.empty?
    pa = do_parse
    pa ? pa : ErrorNode.new(@string)
end

def ptree
    @ptree = do_parse2 if not @ptree
    @ptree
end

def dup
    @string ? self.class.new(@string) : self.class.new(@ptree)
end

def parse
    dup.parse!
end

def parse!
    @ptree = do_parse2 if not @ptree
    self
end

def self::parse(string)
    new(string).parse!
end

=begin
--- reduce0
    just do nothing.
=end

def reduce0
    self
end

=begin
--- reduce1
    removes unnecessary parentheses.
=end

def reduce1
    @string = ptree.to_s
    self
end

=begin
--- reduce2
    removes shift operator within multiplication/division/exponent
=end

def reduce2
    @ptree = ptree.reduce2
    @string = nil
    self
end

=begin
--- reduce3
    flattens expression and collects all factors
=end

def reduce3
    @ptree = ptree.reduce3
    @string = nil
    self
end

=begin
--- reduce4
    collects terms with the same name
=end

def reduce4
    @ptree = ptree.reduce4
    @string = nil
    self
end

=begin
--- reduce5
    expands all terms recursively
=end

def reduce5
    @ptree = ptree.reduce5
    @string = nil
    self
end

attr_reader :string

def to_s
    @string = @ptree.to_s if @string.nil?
    @string
end

def inspect
    if @ptree.nil? then
	"Units{#{@string}}"
    else
	"Units[#{@ptree.inspect}]".gsub(/Units::/, '').gsub(/Node\[/, '[')
    end
end

def self::[](string)
    new(string)
end

def self::parse(string)
    new(string).parse!
end

def eval(x = 0)
    r5 = ptree.reduce5
    case r = r5.ref
    when TimeNode
	r.add(x, r5.name)
    else
	fac = NumberNode.new(x + r.value)
	self.class.new(MulNode.new(fac, r5.deref))
    end
end

def convert(numeric, to_units)
    to_units = Units.new( to_units ) if to_units.is_a?(String)
    r5 = dup.ptree.reduce5
    case r = r5.ref
    when TimeNode
	r.add_time(r5.deref.mul(numeric)).div_time(to_units.ptree)
    else
	shift1 = r.value
	numeric = shift1 + numeric if shift1 != 0
	fact = r5.divide(tp = to_units.dup.ptree).reduce5.value
	numeric *= fact if fact != 1
	shift2 = tp.reduce5.ref.value
	numeric = numeric - shift2 if shift2 != 0
	numeric
    end
end

def factor_and_offset(to_units)
    # To convert a numeric from self to to_units: 
    # scale_factor * numeric + add_offset
    to_units = Units.new( to_units ) if to_units.is_a?(String)
    add_offset = convert(0, to_units)
    scale_factor = convert(1, to_units) - add_offset
    [ scale_factor, add_offset ]
end

def convert2(val, to_units)
    # Like Units#convert, but applicable to any Numeric-like objects.
    # Returns the original value if the units are incompatible.
    to_units = Units.new( to_units ) if to_units.is_a?(String)
    if ( self == to_units )
        val
    elsif ( self =~ to_units )
        if Numeric===val
            convert( val, to_units )
        else
            factor, offset = factor_and_offset( to_units )
            val*factor + offset
        end
    else
      unless $VERBOSE.nil?
	$stderr.print( "*WARNING*: " +
                 "incompatible units: #{self.to_s} and #{to_units.to_s}\n")
        caller(0).each{|c| $stderr.print "\t* ",c,"\n"}
      end        
      val
    end
end

@@reduce = :reduce4

def self::reduce_level
    @@reduce.to_s[-1]
end

def self::reduce_level=(n)
    @@reduce = case n
    when 1 then :reduce1
    when 2 then :reduce2
    when 3 then :reduce3
    when 4 then :reduce4
    else :reduce5
    end
end

def binop(op, other)
    case other
    when Numeric
	other = NumberNode.new(other)
    when Units
	other = other.ptree
    end
    q = self.ptree.send(op, other).send(@@reduce)
    Units.new(q)
end

def *(other)
    binop(:mul, other)
end

def **(other)
    binop(:pow, other)
end

def /(other)
    binop(:divide, other)
end

def ^(other)
    binop(:shift, other)
end

def ==(other)
    case other
    when self.class
	dup.reduce5.to_s == other.dup.reduce5.to_s
    else
	false
    end
end

#def === (other)
#    reduce5.ptree.deref.to_s == other.reduce5.ptree.deref.to_s
#end

alias === ==

#def === (other)
#  # returns true if other is within a factor and/or offset of difference.
#  case other
#  when self.class
#    (self/other).reduce5.ptree.children.each do |child|
#      return false if !( NumberNode === child )
#    end
#    true
#  else
#    false
#  end
#end


def =~(other)
  case other
  when self.class
    (self/other).reduce5.ptree.children.each{ |node|
      return false unless NumberNode === node
    }
    true
  else
    false
  end
end

def self::pow_f(a, b)
    if Integer === b and b < 0 then
	a ** b.to_f
    else
	a ** b
    end
end