Over a million developers have joined DZone.
Platinum Partner

Dart: An Algorithm to Unindent Code

· Performance Zone

The Performance Zone is brought to you in partnership with New Relic. Quickly learn how to use Docker and containers in general to create packaged images for easy management, testing, and deployment of software.

Have you ever had to write an algorithm to unindent a block of code consistently? Figuring out the maximum amount of whitespace among all the lines and then removing that amount of whitespace is non-trivial. Remembering to ignore lines that only have whitespace makes the problem even harder. Here's some Dart code that I wrote to do it. I do believe the performance is O(num_lines * max_line_length), which I think is optimal. It should be easy to port this to other languages if you need it:

/**
 * Remove the indentation from the given lines.
 * 
 * Only remove as much indentation as the line with the least amount of
 * indentation.
 */
List<String> unindentFilter(List<String> lines) {
  // Make a copy so that we can modify it in place.
  lines = new List<String>.from(lines);
  
  // Make sure there is at least one line.
  if (!lines.isEmpty()) {
  
    // Figure out how much indentation the first line has.
    var indentation = new List<String>();
    for (String char in lines[0].splitChars()) {
      if (char == " " || char == "\t") {
        indentation.add(char);
      } else {
        break;
      }      
    }
    
    // Figure out the least amount of indentation any of the other lines has.
    for (var i = 1; i < lines.length; i++) {
      String line = lines[i];
      List<String> chars = line.splitChars();
      
      // Lines that only have whitespace should be set to "" and ignored.
      var whitespaceOnly = true;
      for (var char in chars) {
        if (char != " " && char != "\t") {
          whitespaceOnly = false;
          break;
        }          
      }
      if (whitespaceOnly) {
        lines[i] = "";          
      } else {
        
        // If the line has something other than whitespace, see how its
        // indentation compares to the least amount of indentation we've
        // seen so far.
        for (var j = 0; j < indentation.length && j < chars.length; j++) {
          String char = chars[j];
          if ((char != " " && char != "\t") ||
              char != indentation[j]) {
            
            // We found a new line with less indentation.
            indentation.removeRange(j, indentation.length - j);
            break;
          } 
        }
      }
    }
    
    // Loop over all the lines, and remove the right amount of indentation.
    for (var i = 0; i < lines.length; i++) {
      String line = lines[i];
      
      // Ignore blank lines.
      if (line != "") {
        
        // Otherwise, trim off the right amount of indentation.
        List<String> chars = line.splitChars();
        List<String> unindented = chars.getRange(indentation.length, chars.length - indentation.length);
        lines[i] = Strings.concatAll(unindented);
      }
    }
  }
  
  return lines;
}

Here are some tests:

test("unindentFilter unindents code", () {
  expect(merger.unindentFilter(["  1",
                                "  2"]),
         equals(["1",
                 "2"]));
});

test("unindentFilter unindents code where the first line is indented the most", () {
  expect(merger.unindentFilter(["\t    1",
                                "\t  2",
                                "\t    3"]),
         equals(["  1",
                 "2",
                 "  3"]));
});

test("unindentFilter does nothing for unindented code", () {
  expect(merger.unindentFilter(["1",
                                "2",
                                "3"]),
         equals(["1",
                 "2",
                 "3"]));
});

test("unindentFilter handles empty lists", () {
  expect(merger.unindentFilter([]),
         equals([]));
});

test("unindentFilter does not try to handle inconsistent indentation", () {
  expect(merger.unindentFilter(["\t1",
                                "  2",
                                "    3"
                                "        4"]),
         equals(["\t1",
                 "  2",
                 "    3"
                 "        4"]));
});

test("unindentFilter handles really awkward short lines", () {
  expect(merger.unindentFilter(["    1",
                                "2"]),
         equals(["    1",
                 "2"]));
});

test("unindentFilter handles blank lines and lines with only indentation", () {
  expect(merger.unindentFilter(["  1",
                                "",
                                " ",
                                "    2"]),
         equals(["1",
                 "",
                 "",
                 "  2"]));
});

The Performance Zone is brought to you in partnership with New Relic. Read more about providing a framework that gets you started on the right path to move your IT services to cloud computing, and give you an understanding as to why certain applications should not move to the cloud.

Topics:

Published at DZone with permission of Shannon Behrens , DZone MVB .

Opinions expressed by DZone contributors are their own.

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}