← Back to branch summary

~ubuntu-branches/ubuntu/trusty/monodevelop/trusty-proposed

« back to all changes in this revision

Viewing changes to external/ngit/NGit/NGit.Diff/MyersDiff.cs

  • Committer: Package Import Robot
  • Author(s): Jo Shields
  • Date: 2013-05-12 09:46:03 UTC
  • mto: This revision was merged to the branch mainline in revision 29.
  • Revision ID: package-import@ubuntu.com-20130512094603-mad323bzcxvmcam0
Tags: upstream-4.0.5+dfsg
Import upstream version 4.0.5+dfsg

Show diffs side-by-side

added added

removed removed

Lines of Context:
external/ngit/NGit/NGit.Diff/MyersDiff.cs
50
50
namespace NGit.Diff
51
51
{
52
52
        /// <summary>
53
 
        /// Diff algorithm, based on "An O(ND) Difference Algorithm and its
54
 
        /// Variations", by Eugene Myers.
 
53
        /// Diff algorithm, based on "An O(ND) Difference Algorithm and its Variations",
 
54
        /// by Eugene Myers.
55
55
        /// </summary>
56
56
        /// <remarks>
57
 
        /// Diff algorithm, based on "An O(ND) Difference Algorithm and its
58
 
        /// Variations", by Eugene Myers.
 
57
        /// Diff algorithm, based on "An O(ND) Difference Algorithm and its Variations",
 
58
        /// by Eugene Myers.
 
59
        /// <p>
59
60
        /// The basic idea is to put the line numbers of text A as columns ("x") and the
60
 
        /// lines of text B as rows ("y").  Now you try to find the shortest "edit path"
61
 
        /// from the upper left corner to the lower right corner, where you can
62
 
        /// always go horizontally or vertically, but diagonally from (x,y) to
63
 
        /// (x+1,y+1) only if line x in text A is identical to line y in text B.
64
 
        /// Myers' fundamental concept is the "furthest reaching D-path on diagonal k":
65
 
        /// a D-path is an edit path starting at the upper left corner and containing
66
 
        /// exactly D non-diagonal elements ("differences").  The furthest reaching
67
 
        /// D-path on diagonal k is the one that contains the most (diagonal) elements
68
 
        /// which ends on diagonal k (where k = y - x).
 
61
        /// lines of text B as rows ("y"). Now you try to find the shortest "edit path"
 
62
        /// from the upper left corner to the lower right corner, where you can always go
 
63
        /// horizontally or vertically, but diagonally from (x,y) to (x+1,y+1) only if
 
64
        /// line x in text A is identical to line y in text B.
 
65
        /// <p>
 
66
        /// Myers' fundamental concept is the "furthest reaching D-path on diagonal k": a
 
67
        /// D-path is an edit path starting at the upper left corner and containing
 
68
        /// exactly D non-diagonal elements ("differences"). The furthest reaching D-path
 
69
        /// on diagonal k is the one that contains the most (diagonal) elements which
 
70
        /// ends on diagonal k (where k = y - x).
 
71
        /// <p>
69
72
        /// Example:
 
73
        /// <pre>
70
74
        /// H E L L O   W O R L D
71
75
        /// ____
72
76
        /// L     \___
73
77
        /// O         \___
74
78
        /// W             \________
75
 
        /// Since every D-path has exactly D horizontal or vertical elements, it can
76
 
        /// only end on the diagonals -D, -D+2, ..., D-2, D.
77
 
        /// Since every furthest reaching D-path contains at least one furthest
78
 
        /// reaching (D-1)-path (except for D=0), we can construct them recursively.
 
79
        /// </pre>
 
80
        /// <p>
 
81
        /// Since every D-path has exactly D horizontal or vertical elements, it can only
 
82
        /// end on the diagonals -D, -D+2, ..., D-2, D.
 
83
        /// <p>
 
84
        /// Since every furthest reaching D-path contains at least one furthest reaching
 
85
        /// (D-1)-path (except for D=0), we can construct them recursively.
 
86
        /// <p>
79
87
        /// Since we are really interested in the shortest edit path, we can start
80
88
        /// looking for a 0-path, then a 1-path, and so on, until we find a path that
81
89
        /// ends in the lower right corner.
 
90
        /// <p>
82
91
        /// To save space, we do not need to store all paths (which has quadratic space
83
 
        /// requirements), but generate the D-paths simultaneously from both sides.
84
 
        /// When the ends meet, we will have found "the middle" of the path.  From the
85
 
        /// end points of that diagonal part, we can generate the rest recursively.
 
92
        /// requirements), but generate the D-paths simultaneously from both sides. When
 
93
        /// the ends meet, we will have found "the middle" of the path. From the end
 
94
        /// points of that diagonal part, we can generate the rest recursively.
 
95
        /// <p>
86
96
        /// This only requires linear space.
87
 
        /// The overall (runtime) complexity is
 
97
        /// <p>
 
98
        /// The overall (runtime) complexity is:
 
99
        /// <pre>
88
100
        /// O(N * D^2 + 2 * N/2 * (D/2)^2 + 4 * N/4 * (D/4)^2 + ...)
89
101
        /// = O(N * D^2 * 5 / 4) = O(N * D^2),
90
 
        /// (With each step, we have to find the middle parts of twice as many regions
91
 
        /// as before, but the regions (as well as the D) are halved.)
92
 
        /// So the overall runtime complexity stays the same with linear space,
93
 
        /// albeit with a larger constant factor.
 
102
        /// </pre>
 
103
        /// <p>
 
104
        /// (With each step, we have to find the middle parts of twice as many regions as
 
105
        /// before, but the regions (as well as the D) are halved.)
 
106
        /// <p>
 
107
        /// So the overall runtime complexity stays the same with linear space, albeit
 
108
        /// with a larger constant factor.
94
109
        /// </remarks>
95
110
        /// <?></?>
96
111
        public class MyersDiff<S> where S:Sequence
97
112
        {
98
 
                private sealed class _LowLevelDiffAlgorithm_110 : LowLevelDiffAlgorithm
 
113
                private sealed class _LowLevelDiffAlgorithm_114 : LowLevelDiffAlgorithm
99
114
                {
100
 
                        public _LowLevelDiffAlgorithm_110()
 
115
                        public _LowLevelDiffAlgorithm_114()
101
116
                        {
102
117
                        }
103
118
 
110
125
 
111
126
                /// <summary>Singleton instance of MyersDiff.</summary>
112
127
                /// <remarks>Singleton instance of MyersDiff.</remarks>
113
 
                public static readonly DiffAlgorithm INSTANCE = new _LowLevelDiffAlgorithm_110();
 
128
                public static readonly DiffAlgorithm INSTANCE = new _LowLevelDiffAlgorithm_114();
114
129
 
115
130
                /// <summary>
116
131
                /// The list of edits found during the last call to
287
302
                                        if (((d + k - this.middleK) % 2) != 0)
288
303
                                        {
289
304
                                                throw new RuntimeException(MessageFormat.Format(JGitText.Get().unexpectedOddResult
290
 
                                                        , d, k, this.middleK));
 
305
                                                        , Sharpen.Extensions.ValueOf(d), Sharpen.Extensions.ValueOf(k), Sharpen.Extensions.ValueOf
 
306
                                                        (this.middleK)));
291
307
                                        }
292
308
                                        return (d + k - this.middleK) / 2;
293
309
                                }
297
313
                                        // TODO: remove
298
314
                                        if (k < this.beginK || k > this.endK)
299
315
                                        {
300
 
                                                throw new RuntimeException(MessageFormat.Format(JGitText.Get().kNotInRange, k, this
301
 
                                                        .beginK, this.endK));
 
316
                                                throw new RuntimeException(MessageFormat.Format(JGitText.Get().kNotInRange, Sharpen.Extensions.ValueOf
 
317
                                                        (k), Sharpen.Extensions.ValueOf(this.beginK), Sharpen.Extensions.ValueOf(this.endK
 
318
                                                        )));
302
319
                                        }
303
320
                                        return this.x.Get(this.GetIndex(d, k));
304
321
                                }
308
325
                                        // TODO: remove
309
326
                                        if (k < this.beginK || k > this.endK)
310
327
                                        {
311
 
                                                throw new RuntimeException(MessageFormat.Format(JGitText.Get().kNotInRange, k, this
312
 
                                                        .beginK, this.endK));
 
328
                                                throw new RuntimeException(MessageFormat.Format(JGitText.Get().kNotInRange, Sharpen.Extensions.ValueOf
 
329
                                                        (k), Sharpen.Extensions.ValueOf(this.beginK), Sharpen.Extensions.ValueOf(this.endK
 
330
                                                        )));
313
331
                                        }
314
332
                                        return this.snake.Get(this.GetIndex(d, k));
315
333
                                }