string-trim-navigation.md

Trimmed string navigation problem

You are given a multiline string $source$ – the content of a source file, and two numbers $startLine$ and $endLine$ such that $0 \le startLine \le endLine < nLines$ where $nLines$ is the number of lines in $source$.

Trimming

You need to produce the resulting string $result$ such that:

• It does not have any content from the $source$ lines whose zero-based line numbers $i < startLine$ or $i > endLine$.

• It contains the lines at indices $i$ such that $startLine \le i \le endLine$, transformed by trimming the shortest
  common indentation (whitespace prefix) that they all have.

  Example: for the $source$ given below and $startLine = 1$, $endLine = 3$:

  foo {
      bar {
          x = 1
      }
      y = 2
  }
  

  The expected $result$ is:

  bar {
      x = 1
  }
  

  For the same $source$ and $startLine = endLine = 2$ the expected $result$ would be:

  x = 1
  

Performance: $O(n)$ time with no more than two passes over the $source$; $O(1)$ additional memory.

Navigation

Once you have the $result$, you receive a series of requests, each with a single index $x_i$ of a character in $result$, $0 \le x_i < length(result)$.

For each of the requests, you need to produce an index $y_i$ that points to the corresponding character in the original $source$ (note that it is always there: all $result$'s characters come from somewhere in the $source$).

In this example, there is a single request, and its $x_1 = 14$ points to the index before the location marked as <here> in $result$:

bar {
    x = <here>1
}

The expected $y_1 = 28$ is the index in $source$ right before the location marked as <here>:

foo {
    bar {
        x = <here>1
    }
    y = 2
}

Performance: $O(log(lines))$ time to handle each request, $O(lines)$ additional memory, where $lines$ is the number of lines in $result$.