Compute and return the source text (all equalities and deletions).

@param diffs
LinkedList of Diff objects.
@return Source text.
767307
public String diff_text1(LinkedList<Diff> diffs) {
        StringBuilder text = new StringBuilder();
        for (Diff aDiff : diffs) {
            if (aDiff.operation != Operation.INSERT) {
                text.append(aDiff.text);
            }
        }
        return text.toString();
    }
405580
public int countDifferencesBetweenAnd(String first, String second) {
        if (first == null) {
            if (second == null) {
                return 0;
            } else {
                first = "";
            }
        } else if (second == null) {
            second = "";
        }
        LinkedList<DiffMatchPatch.Diff> diffs = getDiffs(first, second);
        int diffCount = 0;
        for (DiffMatchPatch.Diff diff : diffs) {
            if (diff.operation != DiffMatchPatch.Operation.EQUAL) {
                diffCount++;
            }
        }
        return diffCount;
    }
206935
def diff_cleanupSemanticLossless(self, diffs):
    

    def diff_cleanupSemanticScore(one, two):
      """Given two strings, compute a score representing whether the
      internal boundary falls on logical boundaries.
      Scores range from 6 (best) to 0 (worst).
      Closure, but does not reference any external variables.

      Args:
        one: First string.
        two: Second string.

      Returns:
        The score.
      """
      if not one or not two:
        # Edges are the best.
        return 6

      # Each port of this function behaves slightly differently due to
      # subtle differences in each language's definition of things like
      # 'whitespace'.  Since this function's purpose is largely cosmetic,
      # the choice has been made to use each language's native features
      # rather than force total conformity.
      char1 = one[-1]
      char2 = two[0]
      nonAlphaNumeric1 = not char1.isalnum()
      nonAlphaNumeric2 = not char2.isalnum()
      whitespace1 = nonAlphaNumeric1 and char1.isspace()
      whitespace2 = nonAlphaNumeric2 and char2.isspace()
      lineBreak1 = whitespace1 and (char1 == "\r" or char1 == "\n")
      lineBreak2 = whitespace2 and (char2 == "\r" or char2 == "\n")
      blankLine1 = lineBreak1 and self.BLANKLINEEND.search(one)
      blankLine2 = lineBreak2 and self.BLANKLINESTART.match(two)

      if blankLine1 or blankLine2:
        # Five points for blank lines.
        return 5
      elif lineBreak1 or lineBreak2:
        # Four points for line breaks.
        return 4
      elif nonAlphaNumeric1 and not whitespace1 and whitespace2:
        # Three points for end of sentences.
        return 3
      elif whitespace1 or whitespace2:
        # Two points for whitespace.
        return 2
      elif nonAlphaNumeric1 or nonAlphaNumeric2:
        # One point for non-alphanumeric.
        return 1
      return 0

    pointer = 1
    # Intentionally ignore the first and last element (don't need checking).
    while pointer < len(diffs) - 1:
      if (diffs[pointer - 1][0] == self.DIFF_EQUAL and
          diffs[pointer + 1][0] == self.DIFF_EQUAL):
        # This is a single edit surrounded by equalities.
        equality1 = diffs[pointer - 1][1]
        edit = diffs[pointer][1]
        equality2 = diffs[pointer + 1][1]

        # First, shift the edit as far left as possible.
        commonOffset = self.diff_commonSuffix(equality1, edit)
        if commonOffset:
          commonString = edit[-commonOffset:]
          equality1 = equality1[:-commonOffset]
          edit = commonString + edit[:-commonOffset]
          equality2 = commonString + equality2

        # Second, step character by character right, looking for the best fit.
        bestEquality1 = equality1
        bestEdit = edit
        bestEquality2 = equality2
        bestScore = (diff_cleanupSemanticScore(equality1, edit) +
            diff_cleanupSemanticScore(edit, equality2))
        while edit and equality2 and edit[0] == equality2[0]:
          equality1 += edit[0]
          edit = edit[1:] + equality2[0]
          equality2 = equality2[1:]
          score = (diff_cleanupSemanticScore(equality1, edit) +
              diff_cleanupSemanticScore(edit, equality2))
          # The >= encourages trailing rather than leading whitespace on edits.
          if score >= bestScore:
            bestScore = score
            bestEquality1 = equality1
            bestEdit = edit
            bestEquality2 = equality2

        if diffs[pointer - 1][1] != bestEquality1:
          # We have an improvement, save it back to the diff.
          if bestEquality1:
            diffs[pointer - 1] = (diffs[pointer - 1][0], bestEquality1)
          else:
            del diffs[pointer - 1]
            pointer -= 1
          diffs[pointer] = (diffs[pointer][0], bestEdit)
          if bestEquality2:
            diffs[pointer + 1] = (diffs[pointer + 1][0], bestEquality2)
          else:
            del diffs[pointer + 1]
            pointer -= 1
      pointer += 1
208147
def diff_cleanupMerge(self, diffs):
    
    diffs.append((self.DIFF_EQUAL, ''))  # Add a dummy entry at the end.
    pointer = 0
    count_delete = 0
    count_insert = 0
    text_delete = ''
    text_insert = ''
    while pointer < len(diffs):
      if diffs[pointer][0] == self.DIFF_INSERT:
        count_insert += 1
        text_insert += diffs[pointer][1]
        pointer += 1
      elif diffs[pointer][0] == self.DIFF_DELETE:
        count_delete += 1
        text_delete += diffs[pointer][1]
        pointer += 1
      elif diffs[pointer][0] == self.DIFF_EQUAL:
        # Upon reaching an equality, check for prior redundancies.
        if count_delete + count_insert > 1:
          if count_delete != 0 and count_insert != 0:
            # Factor out any common prefixies.
            commonlength = self.diff_commonPrefix(text_insert, text_delete)
            if commonlength != 0:
              x = pointer - count_delete - count_insert - 1
              if x >= 0 and diffs[x][0] == self.DIFF_EQUAL:
                diffs[x] = (diffs[x][0], diffs[x][1] +
                            text_insert[:commonlength])
              else:
                diffs.insert(0, (self.DIFF_EQUAL, text_insert[:commonlength]))
                pointer += 1
              text_insert = text_insert[commonlength:]
              text_delete = text_delete[commonlength:]
            # Factor out any common suffixes.
            commonlength = self.diff_commonSuffix(text_insert, text_delete)
            if commonlength != 0:
              diffs[pointer] = (diffs[pointer][0], text_insert[-commonlength:] +
                  diffs[pointer][1])
              text_insert = text_insert[:-commonlength]
              text_delete = text_delete[:-commonlength]
          # Delete the offending records and add the merged ones.
          new_ops = []
          if len(text_delete) != 0:
            new_ops.append((self.DIFF_DELETE, text_delete))
          if len(text_insert) != 0:
            new_ops.append((self.DIFF_INSERT, text_insert))
          pointer -= count_delete + count_insert
          diffs[pointer : pointer + count_delete + count_insert] = new_ops
          pointer += len(new_ops) + 1
        elif pointer != 0 and diffs[pointer - 1][0] == self.DIFF_EQUAL:
          # Merge this equality with the previous one.
          diffs[pointer - 1] = (diffs[pointer - 1][0],
                                diffs[pointer - 1][1] + diffs[pointer][1])
          del diffs[pointer]
        else:
          pointer += 1

        count_insert = 0
        count_delete = 0
        text_delete = ''
        text_insert = ''

    if diffs[-1][1] == '':
      diffs.pop()  # Remove the dummy entry at the end.

    # Second pass: look for single edits surrounded on both sides by equalities
    # which can be shifted sideways to eliminate an equality.
    # e.g: A<ins>BA</ins>C -> <ins>AB</ins>AC
    changes = False
    pointer = 1
    # Intentionally ignore the first and last element (don't need checking).
    while pointer < len(diffs) - 1:
      if (diffs[pointer - 1][0] == self.DIFF_EQUAL and
          diffs[pointer + 1][0] == self.DIFF_EQUAL):
        # This is a single edit surrounded by equalities.
        if diffs[pointer][1].endswith(diffs[pointer - 1][1]):
          # Shift the edit over the previous equality.
          if diffs[pointer - 1][1] != "":
            diffs[pointer] = (diffs[pointer][0],
                diffs[pointer - 1][1] +
                diffs[pointer][1][:-len(diffs[pointer - 1][1])])
            diffs[pointer + 1] = (diffs[pointer + 1][0],
                                  diffs[pointer - 1][1] + diffs[pointer + 1][1])
          del diffs[pointer - 1]
          changes = True
        elif diffs[pointer][1].startswith(diffs[pointer + 1][1]):
          # Shift the edit over the next equality.
          diffs[pointer - 1] = (diffs[pointer - 1][0],
                                diffs[pointer - 1][1] + diffs[pointer + 1][1])
          diffs[pointer] = (diffs[pointer][0],
              diffs[pointer][1][len(diffs[pointer + 1][1]):] +
              diffs[pointer + 1][1])
          del diffs[pointer + 1]
          changes = True
      pointer += 1

    # If shifts were made, the diff needs reordering and another shift sweep.
    if changes:
      self.diff_cleanupMerge(diffs)
179024
def _get_diff_text(old, new):
    '''
    
    '''
    diff = difflib.unified_diff(old.splitlines(1),
                                new.splitlines(1))
    return ''.join([x.replace('\r', '') for x in diff])
1342251
private LinkedList<Change> compute(String text1, String text2, boolean checkLines) {
        LinkedList<Change> diffs = new LinkedList<>();

        if (text1.length() == 0) {
            // Just add some text (speedup).
            diffs.add(new Change(Operation.INSERT, text2));
            return diffs;
        }

        if (text2.length() == 0) {
            // Just delete some text (speedup).
            diffs.add(new Change(Operation.DELETE, text1));
            return diffs;
        }

        String longtext = text1.length() > text2.length() ? text1 : text2;
        String shorttext = text1.length() > text2.length() ? text2 : text1;
        int i = longtext.indexOf(shorttext);
        if (i != -1) {
            // Shorter text is inside the longer text (speedup).
            Operation op = (text1.length() > text2.length()) ?
                           Operation.DELETE : Operation.INSERT;
            diffs.add(new Change(op, longtext.substring(0, i)));
            diffs.add(new Change(Operation.EQUAL, shorttext));
            diffs.add(new Change(op, longtext.substring(i + shorttext.length())));
            return diffs;
        }

        if (shorttext.length() == 1) {
            // Single character string.
            // After the previous speedup, the character can't be an equality.
            diffs.add(new Change(Operation.DELETE, text1));
            diffs.add(new Change(Operation.INSERT, text2));
            return diffs;
        }

        // Check to see if the problem can be split in two.
        String[] hm = halfMatch(text1, text2);
        if (hm != null) {
            // A half-match was found, sort out the return data.
            String text1_a = hm[0];
            String text1_b = hm[1];
            String text2_a = hm[2];
            String text2_b = hm[3];
            String mid_common = hm[4];
            // Send both pairs off for separate processing.
            LinkedList<Change> diffs_a = main(text1_a, text2_a, checkLines);
            LinkedList<Change> diffs_b = main(text1_b, text2_b, checkLines);
            // Merge the results.
            diffs = diffs_a;
            diffs.add(new Change(Operation.EQUAL, mid_common));
            diffs.addAll(diffs_b);
            return diffs;
        }

        if (checkLines && text1.length() > 100 && text2.length() > 100) {
            return lineMode(text1, text2);
        }

        return bisect(text1, text2);
    }
1179258
private String getText(SToken currNode) {

    List<DataSourceSequence> sSequences = ((SDocumentGraph) currNode.getGraph()).
            getOverlappedDataSourceSequence(currNode, SALT_TYPE.STEXT_OVERLAPPING_RELATION);

    // only support one text for spanns
    if (sSequences == null || sSequences.size() != 1) {
      log.error("rst supports only one text and only text level");
      return null;
    }
    
    log.debug("sSequences {}", sSequences.toString());

    /**
     * Check if it is a text data structure. As described in the salt manual in
     * chapter "5.8 More specific nodes and relations" the start and end point
     * of a range of token is stored in superordinate node of type SSequentialDS
     */
    if (sSequences.get(0).getDataSource() instanceof STextualDS) {
      STextualDS text = ((STextualDS) sSequences.get(0).getDataSource());
      int start = sSequences.get(0).getStart().intValue();
      int end = sSequences.get(0).getEnd().intValue();
      return text.getText().substring(start, end);


    }

    // something fundamentally goes wrong
    log.error("{} instead of {}",
            sSequences.get(0).getDataSource().getClass().getName(),
            STextualDS.class
            .getName());


    return null;
  }
902716
@Override
    public List<String> sources() {
        List<String> sources = new ArrayList<>();
        for (int i = 0; i < this._sections.size(); i++) {
            for (int j = 0; j < this._sections.get(i).consumer.sources().size(); j++) {
                sources.add(this._sections.get(i).consumer.sources().get(j));
            }
        }
        return sources;
    }
326628
def calculate_with_diff
      progress_bar = nil
      if @config[:show_progress]
        progress_bar = ProgressBar.create format: '%a |%B| %p%% %e', length: 80, smoothing: 0.5,
                                         total: @sources.length*(@sources.length-1)/2
      end

      matrix = {}
      @sources.each_with_index do |a,i|
        a_id = id_of(a)
        a_text = text_of(a)

        @sources[i + 1..-1].each do |b|
          b_id   = id_of(b)
          b_text = text_of(b)

          stats = FastHtmlDiff::DiffBuilder.new(a_text, b_text).statistics

          # http://en.wikipedia.org/wiki/Dice%27s_coefficient
          total_count = 2 * stats[:matches][:words] + stats[:insertions][:words] + stats[:deletions][:words]
          similarity = 2 * stats[:matches][:words] / total_count.to_f

          # Build the similarity matrix,
          matrix[a_id] ||= {a_id => 1}
          matrix[a_id][b_id] = similarity
          matrix[b_id] ||= {b_id => 1}
          matrix[b_id][a_id] = similarity

          progress_bar.increment unless progress_bar.nil?
        end
      end
      matrix
    end
186224
public static DiffBuilder compare(final Object control) {
        final Source controlSource = getSource(control);
        return new DiffBuilder(controlSource);
    }
747298
protected String transformMardownLinks(String content, ReferenceContext references) {
		if (!isMarkdownToHtmlReferenceTransformation()) {
			return content;
		}

		// Prepare replacement data structures
		final Map<BasedSequence, String> replacements = new TreeMap<>((cmp1, cmp2) -> {
			final int cmp = Integer.compare(cmp2.getStartOffset(), cmp1.getStartOffset());
			if (cmp != 0) {
				return cmp;
			}
			return Integer.compare(cmp2.getEndOffset(), cmp1.getEndOffset());
		});

		// Visit the links and record the transformations
		final MutableDataSet options = new MutableDataSet();
		final Parser parser = Parser.builder(options).build();
		final Node document = parser.parse(content);
		final NodeVisitor visitor = new NodeVisitor(
				new VisitHandler<>(Link.class, it -> {
					URL url = FileSystem.convertStringToURL(it.getUrl().toString(), true);
					url = transformURL(url, references);
					if (url != null) {
						replacements.put(it.getUrl(), convertURLToString(url));
					}
				}));
		visitor.visitChildren(document);

		// Apply the replacements
		if (!replacements.isEmpty()) {
			final StringBuilder buffer = new StringBuilder(content);
			for (final Entry<BasedSequence, String> entry : replacements.entrySet()) {
				final BasedSequence seq = entry.getKey();
				buffer.replace(seq.getStartOffset(), seq.getEndOffset(), entry.getValue());
			}
			return buffer.toString();
		}
		return content;
	}
278334
public LinkedList<Patch> patch_make(String text1, String text2) {
        if (text1 == null || text2 == null) {
            throw new IllegalArgumentException("Null inputs. (patch_make)");
        }
        // No diffs provided, compute our own.
        LinkedList<Diff> diffs = diff_main(text1, text2, true);
        if (diffs.size() > 2) {
            diff_cleanupSemantic(diffs);
            diff_cleanupEfficiency(diffs);
        }
        return patch_make(text1, diffs);
    }
128434
public int diff_xIndex(LinkedList<Diff> diffs, int loc) {
        int chars1 = 0;
        int chars2 = 0;
        int last_chars1 = 0;
        int last_chars2 = 0;
        Diff lastDiff = null;
        for (Diff aDiff : diffs) {
            if (aDiff.operation != Operation.INSERT) {
                // Equality or deletion.
                chars1 += aDiff.text.length();
            }
            if (aDiff.operation != Operation.DELETE) {
                // Equality or insertion.
                chars2 += aDiff.text.length();
            }
            if (chars1 > loc) {
                // Overshot the location.
                lastDiff = aDiff;
                break;
            }
            last_chars1 = chars1;
            last_chars2 = chars2;
        }
        if (lastDiff != null && lastDiff.operation == Operation.DELETE) {
            // The location was deleted.
            return last_chars2;
        }
        // Add the remaining character length.
        return last_chars2 + (loc - last_chars1);
    }
602218
public String generateDiff(GenericObject from, GenericObject to) {
        StringBuilder builder = new StringBuilder();

        builder.append("<table class=\"nomargin diff\">");
        builder.append("<thead>");
        builder.append("<tr>");
        builder.append("<th/>");
        builder.append("<th class=\"texttitle\">From</th>");
        builder.append("<th/>");
        builder.append("<th class=\"texttitle\">To</th>");
        builder.append("</tr>");
        builder.append("</thead>");

        builder.append("<tbody>");

        writeDiff(builder, from, to);

        builder.append("</tbody>");
        builder.append("</table>");

        return builder.toString();
    }
713394
public String getSource()
	{
		final Element element = getElement("Source", 0);

		if (element != null)
			return element.getText();
		else
			return null;
	}
35695
private String[] getEquivalents(String segment) {
        Set<String> result = new HashSet<String>();
        Set<String> basic = getEquivalents2(segment);
        Set<String> permutations = new HashSet<String>();

        // now get all the permutations
        // add only the ones that are canonically equivalent
        // TODO: optimize by not permuting any class zero.
        Iterator<String> it = basic.iterator();
        while (it.hasNext()) {
            String item = it.next();
            permutations.clear();
            permute(item, SKIP_ZEROS, permutations);
            Iterator<String> it2 = permutations.iterator();
            while (it2.hasNext()) {
                String possible = it2.next();

/*
                String attempt = Normalizer.normalize(possible, Normalizer.DECOMP, 0);
                if (attempt.equals(segment)) {
*/
                if (Normalizer.compare(possible, segment,0)==0) {

                    if (PROGRESS) System.out.println("Adding Permutation: " + Utility.hex(possible));
                    result.add(possible);

                } else {
                    if (PROGRESS) System.out.println("-Skipping Permutation: " + Utility.hex(possible));
                }
            }
        }

        // convert into a String[] to clean up storage
        String[] finalResult = new String[result.size()];
        result.toArray(finalResult);
        return finalResult;
    }
135856
public static <T> void dump(Iterable<Difference<T>> diffs) {
		for(Difference<T> diff: diffs) {
			System.out.println(diff);
		}
	}