1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
|
//
// Copyright (c) Microsoft Corporation. All rights reserved.
// Licensed under the MIT License. See License.txt in the project root for license information.
//
// This file contain implementations details that are subject to change without notice.
// Use at your own risk.
//
using System;
using System.Collections.Generic;
using System.ComponentModel.Composition;
using System.Diagnostics;
namespace Microsoft.VisualStudio.Text.Differencing.Implementation
{
/// <summary>
/// Generate a maximal common subsequence (or longest common subsequence) of
/// two sequences (ILists).
/// </summary>
[Export(typeof(IDifferenceService))]
internal sealed class MaximalSubsequenceAlgorithm : IDifferenceService
{
#region IDifferenceService Members
static readonly Microsoft.TeamFoundation.Diff.Copy.IDiffChange[] Empty = new Microsoft.TeamFoundation.Diff.Copy.IDiffChange[0];
public IDifferenceCollection<T> DifferenceSequences<T>(IList<T> left, IList<T> right)
{
return DifferenceSequences<T>(left, right, null);
}
public IDifferenceCollection<T> DifferenceSequences<T>(IList<T> left, IList<T> right, ContinueProcessingPredicate<T> continueProcessingPredicate)
{
return DifferenceSequences<T>(left, right, left, right, continueProcessingPredicate);
}
#endregion
internal static DifferenceCollection<T> DifferenceSequences<T>(IList<T> left, IList<T> right, IList<T> originalLeft, IList<T> originalRight, ContinueProcessingPredicate<T> continueProcessingPredicate)
{
if (left == null)
throw new ArgumentNullException("left");
if (right == null)
throw new ArgumentNullException("right");
Microsoft.TeamFoundation.Diff.Copy.IDiffChange[] changes;
if ((left.Count == 0) || (right.Count == 0))
{
if ((left.Count == 0) && (right.Count == 0))
{
changes = MaximalSubsequenceAlgorithm.Empty;
}
else
{
changes = new Microsoft.TeamFoundation.Diff.Copy.IDiffChange[1];
changes[0] = new Microsoft.TeamFoundation.Diff.Copy.DiffChange(0, left.Count,
0, right.Count);
}
}
else
changes = ComputeMaximalSubsequence<T>(left, right, continueProcessingPredicate);
return DiffChangeCollectionHelper<T>.Create(changes, originalLeft, originalRight);
}
private static Microsoft.TeamFoundation.Diff.Copy.IDiffChange[] ComputeMaximalSubsequence<T>(IList<T> left, IList<T> right, ContinueProcessingPredicate<T> continueProcessingPredicate)
{
var lcs = new Microsoft.TeamFoundation.Diff.Copy.LcsDiff<T>();
var diffs = lcs.Diff(left, right, EqualityComparer<T>.Default, (continueProcessingPredicate == null)
? (Microsoft.TeamFoundation.Diff.Copy.ContinueDifferencePredicate<T>)null
: (int originalIndex, IList<T> originalSequence, int longestMatchSoFar) => { return continueProcessingPredicate(originalIndex, originalSequence, longestMatchSoFar);});
return diffs;
}
}
}
|
