package kata.wordwrap.a20110716;

/**
  * Word Wrap Kata.
  * Copyright (c) 2011, Peter Kofler, licensed under BSD License.
  */
public class WordWrapRecursive {

   private static final char BLANK = ' ';
   private static final char NEWLINE = '\n';

   public static String wrap(String line, int maxLineLen) {
      if (line.length() <= maxLineLen) {
         return line;
      }

      final int indexOfBlank = line.lastIndexOf(BLANK, maxLineLen);
      final int split;
      final int offset;
      if (indexOfBlank > -1) {
         split = indexOfBlank;
         offset = 1;
      } else {
         split = maxLineLen;
         offset = 0;
      }
      return line.substring(0, split) + NEWLINE //
            + wrap(line.substring(split + offset), maxLineLen);
   }

   /*
    * When N characters are split into n+1 elements, then
    * n+1 times length() is called
    * worst case n*maxLineLen characters were checked (almost all)
    * 3*n Strings are created
    * n StringBuilders are created (on the fly)
    */

   /*
    * Worst case for searching "no blanks found"
    * n = N/maxLineLen
    * Worst case for allocation "every run length = maxLineLen/2, z.B. maxLineLen=4, runs=2
    * n = N/(maxLineLen/2+1) ~ twice as much
    */
}