Over a million developers have joined DZone.

Dart: An Algorithm to Unindent Code

· Performance Zone

See Gartner’s latest research on the application performance monitoring landscape and how APM suites are becoming more and more critical to the business, brought to you in partnership with AppDynamics.

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 AppDynamics.  See Gartner’s latest research on the application performance monitoring landscape and how APM suites are becoming more and more critical to the business.

Topics:

Published at DZone with permission of Shannon Behrens, DZone MVB. See the original article here.

Opinions expressed by DZone contributors are their own.

The best of DZone straight to your inbox.

SEE AN EXAMPLE
Please provide a valid email address.

Thanks for subscribing!

Awesome! Check your inbox to verify your email so you can start receiving the latest in tech news and resources.
Subscribe

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

{{ parent.tldr }}

{{ parent.urlSource.name }}