Get the next string, according to its natural ordering

Question

In Java, the class String implements Comparable, which means there's a total ordering on the String objects. This ordering is referred to as the class's natural ordering, and the class's compareTo method is referred to as its natural comparison method. The set of String objects is also countable in the mathematical sense.

I need a function that takes a String and returns the next one according to String's natural ordering.

For the mathematically inclined,

function(X) = Y, where Y is such that: 1) X < Y
                                       2) for all Z, if X < Z, then Y <= Z.

Can you think of a function that does this for Strings? (Those matching ^[A-Za-z0-9]+$. I don't care, but you can avoid the control characters or anything that might cause headaches with encodings, is illegal in XML, has line breaks, or similar "problematic" characters.)

Answer 1

String successor(String s) {
    return s + '\0';
}

Or with your limited alphabet:

String successor(String s) {
    return s + '0';
}

since '0' has the smallest unicode value of all legal characters.

Why you would need this is anyone's guess, though ... probably there is a less hacky solution.

Answer 2

Not sure why you would need something like that... bruteforcing something? anyway here is a very primitive solution:

public static String getNextString(String input)
{
  if(input == null || input.trim().length() < 1)
  {
    return("0");
  }
  else
  {
    String trimmed = input.trim();
    int lastPos = input.length()-1;
    int last = (int) input.charAt(lastPos);
    last++;
    if(last > (int) 'z')
    {
      if(lastPos == 0)
      {
        return "00";
      }
      else
      {
        return getNextString(trimmed.substring(0,lastPos-1)) + "0";
      }
    }

  }
}

Obviously, there might be bugs cuz i just typed this from my mobile phone on my way home...

Answer 3

As first pointed out by the other answer, the successor of a string is that string immediately followed by the char whose value is 0 (in Java, char is an unsigned integral value, [0,65535] (§4.2.1)).

// returns the lexicographical successor of a string
public static String successor(String s) {
    return s + "\0";
}

The following excerpt from SortedSet documentation prescribes this exact idiom for String, and gives a motivation WHY you'd want to use a successor method like this:

Note: several methods return subsets with restricted ranges. Such ranges are half-open, that is, they include their low endpoint but not their high endpoint (where applicable). If you need a closed range (which includes both endpoints), and the element type allows for calculation of the successor of a given value, merely request the subrange from lowEndpoint to successor(highEndpoint). For example, suppose that s is a sorted set of strings. The following idiom obtains a view containing all of the strings in s from low to high, inclusive:

SortedSet<String> sub = s.subSet(low, high+"\0");

A similar technique can be used to generate an open range (which contains neither endpoint). The following idiom obtains a view containing all of the strings in s from low to high, exclusive:

SortedSet<String> sub = s.subSet(low+"\0", high);

Note that this idiom is still awkward to use nonetheless, and it may not always be easy to compute the successor for any generic type (e.g. if it's just a SortedSet<Number>). A much more refined API is NavigableSet<E>, which extends SortedSet<E> and defines these range operations to allow any combination of open or close end points using boolean flags.

Related questions

• Inclusive range queries when only half-open range is supported? (ala SortedMap.subMap)
• Is it possible to write a generic +1 method for numeric box types in Java?
• Are upper bounds of indexed ranges always assumed to be exclusive?