Successor: Ruby String.succ For Java

For my master thesis I’m working on a Java application that should allow you to specify string intervals. A string interval can be specified by defining a start string and an end string, from which the system should be able to generate a list of successive strings in lexicographical order.

Knowing of the function string.succ in Ruby and the ability to specify string ranges, I figured that something similar would also exist in Java. After browsing the webs for hours, I didn’t find anything however. Moreover, even C# with all its extra convenience methods doesn’t come with this (see also Mack Allen’s post here)!

The code below is my stab at creating string.succ in Java. It (mostly) does exactly the same thing as the Ruby version. Mostly I say, try for example the range ("test1".."test10") in irb and Successor.range("test1","test10",false) in a java console.

See the main() function for examples!

Update 5-6-2009: Made it a lot shorter by getting rid of the helper classes, which turned out to be overkill.

/**
* Successor.java: A utility class for generating string successors.
*
* Copyright (c) 2009, R de Lange
*
* This program is free software; you can redistribute it and/or
* modify it under the terms of the GNU General Public License
* as published by the Free Software Foundation; either version 3
* of the License, or (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*/
import java.util.*;
import java.io.*;

/**
* The Successor utility class can be used to find string successors or
* to generate lists of successive strings.
*
* @author R de Lange
* @created June 5, 2009
*/
public class Successor {

/**
* Main class to test Successor. Examples taken from Ruby string#succ.
*
* Call should yield
* Successor.succ(“abcd”) #=> “abce”
* Successor.succ(“THX1138”) #=> “THX1139”
* Successor.succ(“<>”) #=> “<>”
* Successor.succ(“1999zzz”) #=> “2000aaa”
* Successor.succ(“ZZZ9999”) #=> “AAAA0000”
* Successor.succ(“***”) #=> “**+”
*
* – For an interactive console interface for testing Successor.succ(str), specify the -i argument
* – To test successor ranges using Successor.range(str), specify the -r argument. Adding an arbitrary
* extra argument (e.g. -r e) will toggle the ‘exclusive’ boolean for successor ranges.
*/
public static void main(String[] args) throws Exception{
if(args.length == 0){
System.out.println(“Running Successor examples…”);
System.out.println(“abcd #=> ” + Successor.succ(“abcd”));
System.out.println(“THX1138 #=> ” + Successor.succ(“THX1138”));
System.out.println(“<> #=> ” + Successor.succ(“<>”));
System.out.println(“1999zzz #=> ” + Successor.succ(“1999zzz”));
System.out.println(“ZZZ9999 #=> ” + Successor.succ(“ZZZ9999”));
System.out.println(“*** #=> ” + Successor.succ(“***”));
}
else {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
String command = args[0];
if(command.equals(“-i”)) {
String line = “”;
while(!line.equals(“quit”)){
System.out.print(“String? “);
line = in.readLine();
if(!line.equals(“quit”)) System.out.println(Successor.succ(line));
}
}
else if(command.equals(“-r”)) {
String left = “”, right=””;
while(true){
System.out.print(“Left? “);
left = in.readLine();
System.out.print(“Right? “);
right = in.readLine();
System.out.println(Arrays.deepToString(Successor.range(left, right, args.length == 2).toArray()));
}
}
}
}

/**
* Returns the successor to str. The successor is calculated by incrementing characters starting from the rightmost
* alphanumeric (or the rightmost character if there are no alphanumerics) in the string. Incrementing a digit always
* results in another digit, and incrementing a letter results in another letter of the same case. Incrementing
* nonalphanumerics uses the system default character set’s collating sequence. If the increment generates a ‘carry’,
* the character to the left of it is incremented. This process repeats until there is no carry, adding an additional
* character if necessary.
*/
public static String succ(String str){
char[] cstr = str.toCharArray();
if(cstr.length == 0) return “”;

int letterOrDigitIndex = getLastLetterOrDigitIndex(cstr, cstr.length-1);
if(letterOrDigitIndex >= 0)
return alphanumSucc(cstr, letterOrDigitIndex);
else {
// Increment rightmost character
cstr[cstr.length-1] = (char) (cstr[cstr.length-1] + 1);
return new String(cstr);
}
}

/**
* Alias of Successor.succ(str)
*/
public static String next(String str){ return Successor.succ(str); }

/**
* Returns a range of string successors as a list. Starting from str1, this method will add all successors
* to a list until the successor string equals str2. If the ‘exclusive’ boolean is true, str2 will be included
* in the resulting list, otherwise excluded. If the successor str2 is not found after generating half a million
* successors, the range is assumed to be invalid, in which case it will return an empty list.
*/
public static List range(String str1, String str2, boolean exclusive){
int counter, limit = 500000;
ArrayList result = new ArrayList();

result.add(str1);
String currentSuccessor = str1;
for(counter = 0;counter<=limit && !currentSuccessor.equals(str2); counter++){ currentSuccessor = Successor.succ(currentSuccessor); if((currentSuccessor.equals(str2) && !exclusive)|| !currentSuccessor.equals(str2)) result.add(currentSuccessor); } if(counter > limit) {
System.err.println(“Range could not be created, level too deep.”);
result.clear();
}
return result;
}

/**
* Calculates the successive string for strings that contain alphanumeric characters.
* See the description of Successor.succ(str) for more informtionon this function
*/
private static String alphanumSucc(char[] cstr, int lastLetterOrDigitIndex){
char succ = charSucc(cstr[lastLetterOrDigitIndex]);

int currentIndex = lastLetterOrDigitIndex;
cstr[currentIndex] = succ;

// Loop while we have a carry
while(succHasCarry(succ) && lastLetterOrDigitIndex >= 0){
lastLetterOrDigitIndex = getLastLetterOrDigitIndex(cstr, lastLetterOrDigitIndex-1);
if(lastLetterOrDigitIndex >= 0) {
currentIndex = lastLetterOrDigitIndex;
succ = charSucc(cstr[currentIndex]);
cstr[currentIndex] = succ;
}
}

// Check if we still have a carry left
if(succHasCarry(succ)) cstr = insertCarry(cstr, succ, currentIndex);

// Finished!
return new String(cstr);
}

/**
* Create a new array in which the given carry is inserted at the given index
* @return A new char array of length cstr.length+1, which contains all values of
* cstr + the carry char inserted at the given index.
*/
private static char[] insertCarry(char[] cstr, char carry, int index){
char[] result = new char[cstr.length+1];
System.arraycopy(cstr,0,result,0,index+1);
result[index] = carry;
System.arraycopy(cstr,index,result,index+1,cstr.length);
return result;
}

/**
* Determines whether the given char array contains alphanumeric characters
* @return the highest index at which an alphanumeric character can be found, or -1 if none were found
*/
private static int getLastLetterOrDigitIndex(char[] cstr, int lastIndex){
int result = -1;
for(int i=lastIndex;i>=0 && result < 0;i--) { if(Character.isLetterOrDigit(cstr[i])) result = i; } return result; } /** * Determines if a given *successor* character (returned by charSucc(char c)) is a * character with a carry. * * @param c - the successor char * @return true if c is '0', 'a' or 'A'. */ private static boolean succHasCarry(char c){ return c == '0' || c == 'a' || c == 'A'; } /** * Determines the successor of the given char * @param c - the char * @return the successor of char c */ private static char charSucc(char c) { char result; switch(c) { case '9': result = '0'; break; case 'z': result = 'a'; break; case 'Z': result = 'A'; break; default: result = (char) (c + 1); } return result; } } [/sourcecode]

~ by moiristo on May 26, 2009.