This is your brain; this is your brain on OCaml December 16, 2005 | 10:02 am

I just had code handed to me by an employee who wrote during his 2 weeks notice. We encountered a bug in one of his classes, and since I was writing JUnit tests anyways, I figured I would do a bit of clean-up.

What I didn’t realize is that Ocaml has warped me, and my concept of “cleanup” is very different than everyone else’s.

This is the original code:

public static String[] findAvialable(int startValue, int endValue, String[] usedValues) {
    ArrayList values = new ArrayList();
    int total = endValue - startValue + 1;
    for (int i = 0; i < total; i++) {
      int currentValue = startValue + i;
      boolean used = false;
      for (int j = 0; j < usedValues.length; j++) {
        if (Integer.parseInt(usedValues[j]) == currentValue) {
          used = true;
          break;
        }
      }
      if (!used) {
        values.add(new Integer(currentValue));
      }
    }
    String[] result = new String[values.size()];
    for (int i = 0; i < result.length; i++) {
      result[i] = ((Integer)values.get(i)).toString();
    }
    return result;
}

This is what I did to it after “cleanup”:

  /**
   * Returns a string array consisting of all the integer values between two points
   * whose string representation is not in usedValues.
   *
   * @param startValue int The minimum allowed value (inclusive).
   * @param endValue int The maximum allowed valued (inclusive).
   * @param usedValues String[] The String representation of the used integers, or null.
   * @return String[] The String representation of the available integers.
   */
  public static String[] findAvialable(final int startValue, final int endValue,
                                       final String[] usedValues) {
    // Validate some assumptions
    if (startValue > endValue) {
      throw new IllegalArgumentException("Cannot have a start value greater than the end value");
    }
 
    // Cache a repeatedly calculated value
    final int length = endValue - startValue + 1;
 
    // Handle a simple case
    if (usedValues == null || usedValues.length == 0) {
      final List out = new ArrayList(length);
      for (int i = 0; i < length; i++) {
        out.add(Integer.toString(startValue + i));
      }
      return (String[])out.toArray(ArrayUtils.EMPTY_STRING_ARRAY);
    }
 
    // Validate usedValues for the complicated case
    if (Arrays.asList(usedValues).contains(null)) {
      throw new IllegalArgumentException("Used values may be null, but may not contain null");
    }
 
    // Create a set of used values as Integers.
    final Set used = SetUtils.transformedSet(new HashSet(length), new Transformer() {
      public Object transform(final Object object) {
        return new Integer(Integer.parseInt(object.toString()));
      }
    });
 
    // Add all the used values
    used.addAll(Arrays.asList(usedValues));
 
    // Create a list of values we can use
    final List avail = ListUtils.transformedList(new ArrayList(length),
                                                 TransformerUtils.stringValueTransformer());
 
    // Add those possible start values that
    for (int i = 0; i < length; i++) {
      final Integer iObj = new Integer(startValue + i);
      if (!used.contains(iObj)) {
        avail.add(iObj);
      }
    }
 
    return (String[])avail.toArray(ArrayUtils.EMPTY_STRING_ARRAY);
  }

The sick part is that I didn’t even realize how functional that code was until I walked through it.

Tags: ,

  • TheHawk

    You are a sick man… but instead of the for loop you could have created a List of Ints between Start Value and End Value (which is more natural with the program) and then RemoveALL the elements in the used set.

  • http://enfranchisedmind.com/blog Robert Fischer

    Good call — I actually did that when I went back to my code after lunch. Particularly considering that the number of “used” elements is known to be small in this implementation, that’s a much better way to go. There is a type mismatch between the used set and the available list, but the resolution is left as an exercise for the reader.

    I also changed the List to a TreeSet, which retains the sorting I need but substantially improves performance in the removeAll call. I had to create a singleton Comparator that compared on length first, and then on content, but it’s still pretty nifty.

    The other change I made was to change new Integer(Integer.parseInt(object.toString())) to just new Integer(object.toString()).

  • Pingback: The Cheap Sitcom Clip Scene Blog Post | Enfranchised Mind

  • Przemek

    1) startValue > endValue is not error, it is convenient way to express empty set, in that case it doesnt break anything – you just get empty array of Strings
    2) do you really want complexity o((endValue-startValue)*usedValues.length) in production code?
    3) Good, fast and “in java way” code (my first try):

    public static String[] findAvialable(int startValue, int endValue, String[] usedValues) {
    describe empty sets!
    TreeSet allUsed = new TreeSet(Arrays.asList(usedValues));
    ArrayList results = new ArrayList();
    for (int i = startValue; i <= endValue; i++ ){
    String s = ""+i;
    if ( !allUsed.contains(s)){
    results.add(s);
    }
    }
    return results.toArray(new String[results.size()]);
    }

  • http://www.robertcfischer.com Robert Fischer

    Yeah, shifting to use Strings as the basis instead of ints as the basis is a lot smarter.