```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

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

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

```