From: Pit Capitain <pit@...>
Date: 2002-04-25T21:49:28+09:00
Subject: String#pred (long) (was: Numberic#prev)

On 25 Apr 2002, at 19:45, ts wrote about Paul Brannan's 
implementation of String#pred

>  Well, this is not really the reverse of the algorithm for #succ. You
>  can see it for example with "9%".

First some thoughts on String#pred:

Since there exist strings s1 and s2 with s1 != s2 but s1.succ == 
s2.succ (i.e. "9" and "09") it cannot be guaranteed that

  (1)  s.succ.pred == s

for all strings s.

Because there exist strings s1 such that there's no string s2 with 
s1 == s2.succ (i.e. "00") it also cannot be guaranteed that

  (2)  s.pred.succ == s

for all strings s.


For (1) I'd suggest that s1.pred returns the shortest s2 with s1 == 
s2.succ (i.e. "10".pred == "9", not "09").

For (2) (for all strings s1 that do not have s2 with s1 == s2.succ) 
we could define s1.pred to either

(a) raise an error
(b) return something meaningful according to the POLS

Of course another possibility would be to modify String#succ in a 
way that String#pred would be easily comprehensible. Is there any 
code that relies on the current implementation of String#succ?

How about a vote on rubygarden?


Anyway, here's an implementation of String#pred so that s1.pred 
returns the shortest string s2 such that s1 == s2.succ if such 
strings exists (not proven though), and returns a dummy string 
else. Because I don't know how to post attachments I include the 
source and some unit tests here.

Regards,
Pit


The code in file pred.rb (neither optimized nor beautified):

class String
  
  def pred
    case self
    when ''
      ''
    when /[1-9B-Zb-z]/
      alnum_pred
    when /[0Aa].*[0Aa]/
      alnum_pred
    when /[0Aa]\000*$/
      binary_pred
    when /[0Aa]/
      new_pred
    else
      binary_pred
    end
  end
  
  def alnum_pred
    result = dup
    zero_idx = last_idx = borrowed = borrowed_chars = nil
    idx = size
    while idx > 0
      idx -= 1
      last_idx = idx unless last_idx
      case result[ idx ]
      when ?1 .. ?9, ?B .. ?Z, ?b .. ?z
        result[ idx ] -= 1
        zero_idx = idx if result[ idx ] == ?0
        borrowed = nil
        break
      when ?0
        borrowed = result[ idx ] = ?9
        borrowed_chars = 1
      when ?A, ?a
        result[ idx ] += ( ?Z - ?A )
        zero_idx = idx
        if borrowed == result[ idx ]
          borrowed_chars -= 1
        else
          borrowed = result[ idx ]
          borrowed_chars = 1
        end
      else
        last_idx = nil if last_idx == idx
      end
    end
    if borrowed && borrowed_chars > 0
      result = new_pred
    elsif zero_idx && zero_idx < last_idx
      idx = 0
      loop do
        case result[ idx ]
        when ?1 .. ?9, ?A .. ?Y, ?a .. ?y
          break
        when ?0, ?Z, ?z
          result[ idx, 1 ] = '' if idx == zero_idx
          break
        else
          idx += 1
        end
      end
    end
    result
  end
  
  def binary_pred
    result = dup
    idx = size
    while idx > 0
      idx -= 1
      if result[ idx ] > 0
        result[ idx ] -= 1
        break
      else
        result[ idx ] = 255
      end
    end
    if idx == 0
      case result[ idx ]
      when 0
        result[ 0, 1 ] = '' if size > 1
      when 255
        result = new_pred
      end
    end
    result
  end
  
  def new_pred
    "new_pred " + self
  end
  
end


The unit tests in file pred_test.rb:

require 'pred'
require 'test/unit'

class PredTest < Test::Unit::TestCase

  def assert_pred( pred, str, msg = str )
    assert_equal( pred, str.pred, "pred #{msg}" )
  end

  def assert_inverse( str, msg = str )
    assert_equal( str, str.pred.succ, "inverse #{msg}" )
  end

  def assert_pred_with_inverse( pred, str, msg = str )
    assert_pred( pred, str, msg )
    assert_inverse( str, msg )
  end

  def test_01_empty
    assert_pred_with_inverse( '', '', 'empty' )
  end

  def test_02_simple_alnum
    assert_pred_with_inverse( '1', '2' )
    assert_pred_with_inverse( '42', '43' )
    assert_pred_with_inverse( '3999', '4000' )
    assert_pred_with_inverse( '00399', '00400' )
    assert_pred_with_inverse( 'A', 'B' )
    assert_pred_with_inverse( 'HH', 'HI' )
    assert_pred_with_inverse( 'AZZ', 'BAA' )
    assert_pred_with_inverse( 'AAAZZ', 'AABAA' )
    assert_pred_with_inverse( 'd', 'e' )
    assert_pred_with_inverse( 'xx', 'xy' )
    assert_pred_with_inverse( 'yzz', 'zaa' )
    assert_pred_with_inverse( 'zzyzz', 'zzzaa' )
    assert_pred_with_inverse( '8Z9z', '9A0a' )
    assert_pred_with_inverse( ' /4-Z++9 $z #9#', ' /5-A++0 $a #0#' )
  end

  def test_03_leading_1Aa
    assert_pred_with_inverse( '0', '1' )
    assert_pred_with_inverse( '99', '100' )
    assert_pred_with_inverse( '00099', '00100' )
    assert_pred_with_inverse( 'Z', 'AA' )
    assert_pred_with_inverse( 'zZz', 'aaAa' )
    assert_pred_with_inverse( '9zZ', '10aA' )
    assert_pred_with_inverse( 'Z9z9', 'AA0a0' )
    assert_pred_with_inverse( ' /9-Z++9 $z #9#', ' /10-A++0 $a #0#' )
  end

  def test_04_illegal_alnum
    assert_pred( 'new_pred 00', '00' )
    assert_pred( 'new_pred 0000', '0000' )
    assert_pred( 'new_pred A0', 'A0' )
    assert_pred( 'new_pred 0a0', '0a0' )
    assert_pred( 'new_pred 00Aa', '00Aa' )
    assert_pred( 'new_pred aA', 'aA' )
    assert_pred( 'new_pred Aa00', 'Aa00' )
  end

  def test_05_simple_binary
    assert_pred_with_inverse( ' ', '!' )
    assert_pred_with_inverse( '!$', '!%' )
    assert_pred_with_inverse( "$\377\377\377", "%\000\000\000" )
    assert_pred_with_inverse( "<==\377", "<=>\000" )
    assert_pred_with_inverse( "\377 ", "\377!" )
  end

  def test_06_leading_001
    assert_pred_with_inverse( "\000", "\001" )
    assert_pred_with_inverse( "\377", "\001\000" )
    assert_pred_with_inverse( "\377\377\377", "\001\000\000\000" )
    assert_pred_with_inverse( "\000\000\377", "\000\001\000" )
  end

  def test_07_binary_with_0Aa
    assert_pred_with_inverse( '/', '0' )
    assert_pred_with_inverse( '@', 'A' )
    assert_pred_with_inverse( '`', 'a' )
    assert_pred_with_inverse( "$ @\377", "$ A\000" )
    assert_pred_with_inverse( "+/\377\377", "+0\000\000" )
  end

  def test_08_illegal_binary
    assert_pred( "new_pred \000", "\000" )
    assert_pred( "new_pred \000\000", "\000\000" )
    assert_pred( "new_pred 0\001", "0\001" )
    assert_pred( "new_pred A+", "A+" )
    assert_pred( "new_pred <a>", "<a>" )
  end

end