protected List diff_bisect()

in Python/Product/PythonTools/PythonTools/Editor/Formatting/DiffMatchPatch.cs [448:559]

• 92 lines of code
• 32 McCabe index (conditional complexity)

    protected List<Diff> diff_bisect(string text1, string text2,
        DateTime deadline) {
      // Cache the text lengths to prevent multiple calls.
      int text1_length = text1.Length;
      int text2_length = text2.Length;
      int max_d = (text1_length + text2_length + 1) / 2;
      int v_offset = max_d;
      int v_length = 2 * max_d;
      int[] v1 = new int[v_length];
      int[] v2 = new int[v_length];
      for (int x = 0; x < v_length; x++) {
        v1[x] = -1;
        v2[x] = -1;
      }
      v1[v_offset + 1] = 0;
      v2[v_offset + 1] = 0;
      int delta = text1_length - text2_length;
      // If the total number of characters is odd, then the front path will
      // collide with the reverse path.
      bool front = (delta % 2 != 0);
      // Offsets for start and end of k loop.
      // Prevents mapping of space beyond the grid.
      int k1start = 0;
      int k1end = 0;
      int k2start = 0;
      int k2end = 0;
      for (int d = 0; d < max_d; d++) {
        // Bail out if deadline is reached.
        if (DateTime.Now > deadline) {
          break;
        }

        // Walk the front path one step.
        for (int k1 = -d + k1start; k1 <= d - k1end; k1 += 2) {
          int k1_offset = v_offset + k1;
          int x1;
          if (k1 == -d || k1 != d && v1[k1_offset - 1] < v1[k1_offset + 1]) {
            x1 = v1[k1_offset + 1];
          } else {
            x1 = v1[k1_offset - 1] + 1;
          }
          int y1 = x1 - k1;
          while (x1 < text1_length && y1 < text2_length
                && text1[x1] == text2[y1]) {
            x1++;
            y1++;
          }
          v1[k1_offset] = x1;
          if (x1 > text1_length) {
            // Ran off the right of the graph.
            k1end += 2;
          } else if (y1 > text2_length) {
            // Ran off the bottom of the graph.
            k1start += 2;
          } else if (front) {
            int k2_offset = v_offset + delta - k1;
            if (k2_offset >= 0 && k2_offset < v_length && v2[k2_offset] != -1) {
              // Mirror x2 onto top-left coordinate system.
              int x2 = text1_length - v2[k2_offset];
              if (x1 >= x2) {
                // Overlap detected.
                return diff_bisectSplit(text1, text2, x1, y1, deadline);
              }
            }
          }
        }

        // Walk the reverse path one step.
        for (int k2 = -d + k2start; k2 <= d - k2end; k2 += 2) {
          int k2_offset = v_offset + k2;
          int x2;
          if (k2 == -d || k2 != d && v2[k2_offset - 1] < v2[k2_offset + 1]) {
            x2 = v2[k2_offset + 1];
          } else {
            x2 = v2[k2_offset - 1] + 1;
          }
          int y2 = x2 - k2;
          while (x2 < text1_length && y2 < text2_length
              && text1[text1_length - x2 - 1]
              == text2[text2_length - y2 - 1]) {
            x2++;
            y2++;
          }
          v2[k2_offset] = x2;
          if (x2 > text1_length) {
            // Ran off the left of the graph.
            k2end += 2;
          } else if (y2 > text2_length) {
            // Ran off the top of the graph.
            k2start += 2;
          } else if (!front) {
            int k1_offset = v_offset + delta - k2;
            if (k1_offset >= 0 && k1_offset < v_length && v1[k1_offset] != -1) {
              int x1 = v1[k1_offset];
              int y1 = v_offset + x1 - k1_offset;
              // Mirror x2 onto top-left coordinate system.
              x2 = text1_length - v2[k2_offset];
              if (x1 >= x2) {
                // Overlap detected.
                return diff_bisectSplit(text1, text2, x1, y1, deadline);
              }
            }
          }
        }
      }
      // Diff took too long and hit the deadline or
      // number of diffs equals number of characters, no commonality at all.
      List<Diff> diffs = new List<Diff>();
      diffs.Add(new Diff(Operation.DELETE, text1));
      diffs.Add(new Diff(Operation.INSERT, text2));
      return diffs;
    }