<!DOCTYPE html PUBLIC “-//W3C//DTD XHTML 1.0 Transitional//EN” “www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd”> <html lang=‘en’ xml:lang=‘en’ xmlns=‘www.w3.org/1999/xhtml’>
<head> <title>rcov/ruby/1.8/gems/diff-lcs-1.1.2/lib/diff/lcs.rb</title> <link href="screen.css" media="all" rel="stylesheet" type="text/css" /> <link href="print.css" media="print" rel="stylesheet" type="text/css" /> <meta http-equiv="Content-type" content="text/html;charset=UTF-8" /> <script type="text/javascript" src="rcov.js"></script> </head> <body> <h1>Rspec Steps C0 Coverage Information - RCov</h1> <h2>rcov/ruby/1.8/gems/diff-lcs-1.1.2/lib/diff/lcs.rb</h2> <div class="report_table_wrapper"> <table class='report' id='report_table'> <thead> <tr> <th class="left_align">Name</th> <th class="right_align">Total Lines</th> <th class="right_align">Lines of Code</th> <th class="left_align">Total Coverage</th> <th class="left_align">Code Coverage</th> </tr> </thead> <tbody> <tr> <td class="left_align"><a href="rcov-ruby-1_8-gems-diff-lcs-1_1_2-lib-diff-lcs_rb.html">rcov/ruby/1.8/gems/diff-lcs-1.1.2/lib/diff/lcs.rb</a></td> <td class='right_align'><tt>1105</tt></td> <td class='right_align'><tt>553</tt></td> <td class="left_align"><div class="percent_graph_legend"><tt class=''>46.33%</tt></div> <div class="percent_graph"> <div class="covered" style="width:46px"></div> <div class="uncovered" style="width:54px"></div> </div></td> <td class="left_align"><div class="percent_graph_legend"><tt class=''>6.51%</tt></div> <div class="percent_graph"> <div class="covered" style="width:7px"></div> <div class="uncovered" style="width:93px"></div> </div></td> </tr> </tbody> </table> </div> <h3>Key</h3> <div class="key"><pre><span class='marked'>Code reported as executed by Ruby looks like this...</span><span class='marked1'>and this: this line is also marked as covered.</span><span class='inferred'>Lines considered as run by rcov, but not reported by Ruby, look like this,</span><span class='inferred1'>and this: these lines were inferred by rcov (using simple heuristics).</span><span class='uncovered'>Finally, here's a line marked as not executed.</span></pre></div> <h3>Coverage Details</h3> <table class="details"> <tbody> <tr class="inferred"> <td><pre><a name="line1">1</a> #! /usr/env/bin ruby</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line2">2</a> #--</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line3">3</a> # Copyright 2004 Austin Ziegler <diff-lcs@halostatue.ca></pre></td> </tr> <tr class="inferred"> <td><pre><a name="line4">4</a> # adapted from:</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line5">5</a> # Algorithm::Diff (Perl) by Ned Konz <perl@bike-nomad.com></pre></td> </tr> <tr class="inferred"> <td><pre><a name="line6">6</a> # Smalltalk by Mario I. Wolczko <mario@wolczko.com></pre></td> </tr> <tr class="inferred"> <td><pre><a name="line7">7</a> # implements McIlroy-Hunt diff algorithm</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line8">8</a> #</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line9">9</a> # This program is free software. It may be redistributed and/or modified</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line10">10</a> # under the terms of the GPL version 2 (or later), the Perl Artistic</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line11">11</a> # licence, or the Ruby licence.</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line12">12</a> # </pre></td> </tr> <tr class="inferred"> <td><pre><a name="line13">13</a> # $Id: lcs.rb,v 1.9 2004/10/17 20:31:10 austin Exp $</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line14">14</a> #++</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line15">15</a> </pre></td> </tr> <tr class="marked"> <td><pre><a name="line16">16</a> module Diff</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line17">17</a> # = Diff::LCS 1.1.2</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line18">18</a> # Computes "intelligent" differences between two sequenced Enumerables.</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line19">19</a> # This is an implementation of the McIlroy-Hunt "diff" algorithm for</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line20">20</a> # Enumerable objects that include Diffable.</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line21">21</a> #</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line22">22</a> # Based on Mario I. Wolczko's <mario@wolczko.com> Smalltalk version</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line23">23</a> # (1.2, 1993) and Ned Konz's <perl@bike-nomad.com> Perl version</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line24">24</a> # (Algorithm::Diff).</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line25">25</a> #</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line26">26</a> # == Synopsis</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line27">27</a> # require 'diff/lcs'</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line28">28</a> #</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line29">29</a> # seq1 = %w(a b c e h j l m n p)</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line30">30</a> # seq2 = %w(b c d e f j k l m r s t)</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line31">31</a> #</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line32">32</a> # lcs = Diff::LCS.LCS(seq1, seq2)</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line33">33</a> # diffs = Diff::LCS.diff(seq1, seq2)</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line34">34</a> # sdiff = Diff::LCS.sdiff(seq1, seq2)</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line35">35</a> # seq = Diff::LCS.traverse_sequences(seq1, seq2, callback_obj)</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line36">36</a> # bal = Diff::LCS.traverse_balanced(seq1, seq2, callback_obj)</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line37">37</a> # seq2 == Diff::LCS.patch(seq1, diffs)</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line38">38</a> # seq2 == Diff::LCS.patch!(seq1, diffs)</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line39">39</a> # seq1 == Diff::LCS.unpatch(seq2, diffs)</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line40">40</a> # seq1 == Diff::LCS.unpatch!(seq2, diffs)</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line41">41</a> # seq2 == Diff::LCS.patch(seq1, sdiff)</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line42">42</a> # seq2 == Diff::LCS.patch!(seq1, sdiff)</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line43">43</a> # seq1 == Diff::LCS.unpatch(seq2, sdiff)</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line44">44</a> # seq1 == Diff::LCS.unpatch!(seq2, sdiff)</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line45">45</a> #</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line46">46</a> # Alternatively, objects can be extended with Diff::LCS:</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line47">47</a> #</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line48">48</a> # seq1.extend(Diff::LCS)</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line49">49</a> # lcs = seq1.lcs(seq2)</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line50">50</a> # diffs = seq1.diff(seq2)</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line51">51</a> # sdiff = seq1.sdiff(seq2)</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line52">52</a> # seq = seq1.traverse_sequences(seq2, callback_obj)</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line53">53</a> # bal = seq1.traverse_balanced(seq2, callback_obj)</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line54">54</a> # seq2 == seq1.patch(diffs)</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line55">55</a> # seq2 == seq1.patch!(diffs)</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line56">56</a> # seq1 == seq2.unpatch(diffs)</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line57">57</a> # seq1 == seq2.unpatch!(diffs)</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line58">58</a> # seq2 == seq1.patch(sdiff)</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line59">59</a> # seq2 == seq1.patch!(sdiff)</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line60">60</a> # seq1 == seq2.unpatch(sdiff)</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line61">61</a> # seq1 == seq2.unpatch!(sdiff)</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line62">62</a> # </pre></td> </tr> <tr class="inferred"> <td><pre><a name="line63">63</a> # Default extensions are provided for Array and String objects through</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line64">64</a> # the use of 'diff/lcs/array' and 'diff/lcs/string'.</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line65">65</a> #</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line66">66</a> # == Introduction (by Mark-Jason Dominus)</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line67">67</a> # </pre></td> </tr> <tr class="inferred"> <td><pre><a name="line68">68</a> # <em>The following text is from the Perl documentation. The only</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line69">69</a> # changes have been to make the text appear better in Rdoc</em>.</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line70">70</a> #</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line71">71</a> # I once read an article written by the authors of +diff+; they said</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line72">72</a> # that they hard worked very hard on the algorithm until they found the</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line73">73</a> # right one.</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line74">74</a> #</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line75">75</a> # I think what they ended up using (and I hope someone will correct me,</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line76">76</a> # because I am not very confident about this) was the `longest common</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line77">77</a> # subsequence' method. In the LCS problem, you have two sequences of</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line78">78</a> # items:</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line79">79</a> #</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line80">80</a> # a b c d f g h j q z</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line81">81</a> # a b c d e f g i j k r x y z</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line82">82</a> #</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line83">83</a> # and you want to find the longest sequence of items that is present in</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line84">84</a> # both original sequences in the same order. That is, you want to find a</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line85">85</a> # new sequence *S* which can be obtained from the first sequence by</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line86">86</a> # deleting some items, and from the second sequence by deleting other</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line87">87</a> # items. You also want *S* to be as long as possible. In this case *S*</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line88">88</a> # is:</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line89">89</a> # </pre></td> </tr> <tr class="inferred"> <td><pre><a name="line90">90</a> # a b c d f g j z</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line91">91</a> #</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line92">92</a> # From there it's only a small step to get diff-like output:</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line93">93</a> #</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line94">94</a> # e h i k q r x y</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line95">95</a> # + - + + - + + +</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line96">96</a> #</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line97">97</a> # This module solves the LCS problem. It also includes a canned function</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line98">98</a> # to generate +diff+-like output.</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line99">99</a> #</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line100">100</a> # It might seem from the example above that the LCS of two sequences is</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line101">101</a> # always pretty obvious, but that's not always the case, especially when</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line102">102</a> # the two sequences have many repeated elements. For example, consider</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line103">103</a> #</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line104">104</a> # a x b y c z p d q</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line105">105</a> # a b c a x b y c z</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line106">106</a> #</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line107">107</a> # A naive approach might start by matching up the +a+ and +b+ that</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line108">108</a> # appear at the beginning of each sequence, like this:</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line109">109</a> # </pre></td> </tr> <tr class="inferred"> <td><pre><a name="line110">110</a> # a x b y c z p d q</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line111">111</a> # a b c a b y c z</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line112">112</a> #</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line113">113</a> # This finds the common subsequence +a b c z+. But actually, the LCS is</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line114">114</a> # +a x b y c z+:</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line115">115</a> #</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line116">116</a> # a x b y c z p d q</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line117">117</a> # a b c a x b y c z</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line118">118</a> #</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line119">119</a> # == Author</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line120">120</a> # This version is by Austin Ziegler <diff-lcs@halostatue.ca>.</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line121">121</a> #</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line122">122</a> # It is based on the Perl Algorithm::Diff by Ned Konz</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line123">123</a> # <perl@bike-nomad.com>, copyright &copy; 2000 - 2002 and the Smalltalk</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line124">124</a> # diff version by Mario I. Wolczko <mario@wolczko.com>, copyright &copy;</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line125">125</a> # 1993. Documentation includes work by Mark-Jason Dominus.</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line126">126</a> #</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line127">127</a> # == Licence</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line128">128</a> # Copyright &copy; 2004 Austin Ziegler</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line129">129</a> # This program is free software; you can redistribute it and/or modify it</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line130">130</a> # under the same terms as Ruby, or alternatively under the Perl Artistic</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line131">131</a> # licence.</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line132">132</a> #</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line133">133</a> # == Credits</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line134">134</a> # Much of the documentation is taken directly from the Perl</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line135">135</a> # Algorithm::Diff implementation and was written originally by Mark-Jason</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line136">136</a> # Dominus <mjd-perl-diff@plover.com> and later by Ned Konz. The basic Ruby</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line137">137</a> # implementation was re-ported from the Smalltalk implementation, available</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line138">138</a> # at ftp://st.cs.uiuc.edu/pub/Smalltalk/MANCHESTER/manchester/4.0/diff.st</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line139">139</a> #</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line140">140</a> # #sdiff and #traverse_balanced were written for the Perl version by Mike</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line141">141</a> # Schilli <m@perlmeister.com>.</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line142">142</a> #</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line143">143</a> # "The algorithm is described in <em>A Fast Algorithm for Computing Longest</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line144">144</a> # Common Subsequences</em>, CACM, vol.20, no.5, pp.350-353, May 1977, with</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line145">145</a> # a few minor improvements to improve the speed."</pre></td> </tr> <tr class="marked"> <td><pre><a name="line146">146</a> module LCS</pre></td> </tr> <tr class="marked"> <td><pre><a name="line147">147</a> VERSION = '1.1.2'</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line148">148</a> end</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line149">149</a> end</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line150">150</a> </pre></td> </tr> <tr class="marked"> <td><pre><a name="line151">151</a> require 'diff/lcs/callbacks'</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line152">152</a> </pre></td> </tr> <tr class="marked"> <td><pre><a name="line153">153</a> module Diff::LCS</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line154">154</a> # Returns an Array containing the longest common subsequence(s) between</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line155">155</a> # +self+ and +other+. See Diff::LCS#LCS.</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line156">156</a> #</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line157">157</a> # lcs = seq1.lcs(seq2)</pre></td> </tr> <tr class="marked"> <td><pre><a name="line158">158</a> def lcs(other, &block) #:yields self[ii] if there are matched subsequences:</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line159">159</a> Diff::LCS.LCS(self, other, &block)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line160">160</a> end</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line161">161</a> </pre></td> </tr> <tr class="inferred"> <td><pre><a name="line162">162</a> # Returns the difference set between +self+ and +other+. See</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line163">163</a> # Diff::LCS#diff.</pre></td> </tr> <tr class="marked"> <td><pre><a name="line164">164</a> def diff(other, callbacks = nil, &block)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line165">165</a> Diff::LCS::diff(self, other, callbacks, &block)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line166">166</a> end</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line167">167</a> </pre></td> </tr> <tr class="inferred"> <td><pre><a name="line168">168</a> # Returns the balanced ("side-by-side") difference set between +self+ and</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line169">169</a> # +other+. See Diff::LCS#sdiff.</pre></td> </tr> <tr class="marked"> <td><pre><a name="line170">170</a> def sdiff(other, callbacks = nil, &block)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line171">171</a> Diff::LCS::sdiff(self, other, callbacks, &block)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line172">172</a> end</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line173">173</a> </pre></td> </tr> <tr class="inferred"> <td><pre><a name="line174">174</a> # Traverses the discovered longest common subsequences between +self+ and</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line175">175</a> # +other+. See Diff::LCS#traverse_sequences.</pre></td> </tr> <tr class="marked"> <td><pre><a name="line176">176</a> def traverse_sequences(other, callbacks = nil, &block)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line177">177</a> traverse_sequences(self, other, callbacks || Diff::LCS::YieldingCallbacks,</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line178">178</a> &block)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line179">179</a> end</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line180">180</a> </pre></td> </tr> <tr class="inferred"> <td><pre><a name="line181">181</a> # Traverses the discovered longest common subsequences between +self+ and</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line182">182</a> # +other+ using the alternate, balanced algorithm. See</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line183">183</a> # Diff::LCS#traverse_balanced.</pre></td> </tr> <tr class="marked"> <td><pre><a name="line184">184</a> def traverse_balanced(other, callbacks = nil, &block)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line185">185</a> traverse_balanced(self, other, callbacks || Diff::LCS::YieldingCallbacks,</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line186">186</a> &block)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line187">187</a> end</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line188">188</a> </pre></td> </tr> <tr class="inferred"> <td><pre><a name="line189">189</a> # Attempts to patch a copy of +self+ with the provided +patchset+. See</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line190">190</a> # Diff::LCS#patch.</pre></td> </tr> <tr class="marked"> <td><pre><a name="line191">191</a> def patch(patchset)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line192">192</a> Diff::LCS::patch(self.dup, patchset)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line193">193</a> end</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line194">194</a> </pre></td> </tr> <tr class="inferred"> <td><pre><a name="line195">195</a> # Attempts to unpatch a copy of +self+ with the provided +patchset+.</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line196">196</a> # See Diff::LCS#patch.</pre></td> </tr> <tr class="marked"> <td><pre><a name="line197">197</a> def unpatch(patchset)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line198">198</a> Diff::LCS::unpatch(self.dup, patchset)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line199">199</a> end</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line200">200</a> </pre></td> </tr> <tr class="inferred"> <td><pre><a name="line201">201</a> # Attempts to patch +self+ with the provided +patchset+. See</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line202">202</a> # Diff::LCS#patch!. Does no autodiscovery.</pre></td> </tr> <tr class="marked"> <td><pre><a name="line203">203</a> def patch!(patchset)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line204">204</a> Diff::LCS::patch!(self, patchset)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line205">205</a> end</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line206">206</a> </pre></td> </tr> <tr class="inferred"> <td><pre><a name="line207">207</a> # Attempts to unpatch +self+ with the provided +patchset+. See</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line208">208</a> # Diff::LCS#unpatch. Does no autodiscovery.</pre></td> </tr> <tr class="marked"> <td><pre><a name="line209">209</a> def unpatch!(patchset)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line210">210</a> Diff::LCS::unpatch!(self, patchset)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line211">211</a> end</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line212">212</a> end</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line213">213</a> </pre></td> </tr> <tr class="marked"> <td><pre><a name="line214">214</a> module Diff::LCS</pre></td> </tr> <tr class="marked"> <td><pre><a name="line215">215</a> class << self</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line216">216</a> # Given two sequenced Enumerables, LCS returns an Array containing their</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line217">217</a> # longest common subsequences.</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line218">218</a> #</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line219">219</a> # lcs = Diff::LCS.LCS(seq1, seq2)</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line220">220</a> #</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line221">221</a> # This array whose contents is such that:</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line222">222</a> #</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line223">223</a> # lcs.each_with_index do |ee, ii|</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line224">224</a> # assert(ee.nil? || (seq1[ii] == seq2[ee]))</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line225">225</a> # end</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line226">226</a> #</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line227">227</a> # If a block is provided, the matching subsequences will be yielded from</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line228">228</a> # +seq1+ in turn and may be modified before they are placed into the</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line229">229</a> # returned Array of subsequences.</pre></td> </tr> <tr class="marked"> <td><pre><a name="line230">230</a> def LCS(seq1, seq2, &block) #:yields seq1[ii] for each matched:</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line231">231</a> matches = Diff::LCS.__lcs(seq1, seq2)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line232">232</a> ret = []</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line233">233</a> matches.each_with_index do |ee, ii|</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line234">234</a> unless matches[ii].nil?</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line235">235</a> if block_given?</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line236">236</a> ret << (yield seq1[ii])</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line237">237</a> else</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line238">238</a> ret << seq1[ii]</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line239">239</a> end</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line240">240</a> end</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line241">241</a> end</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line242">242</a> ret</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line243">243</a> end</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line244">244</a> </pre></td> </tr> <tr class="inferred"> <td><pre><a name="line245">245</a> # Diff::LCS.diff computes the smallest set of additions and deletions</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line246">246</a> # necessary to turn the first sequence into the second, and returns a</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line247">247</a> # description of these changes.</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line248">248</a> # </pre></td> </tr> <tr class="inferred"> <td><pre><a name="line249">249</a> # See Diff::LCS::DiffCallbacks for the default behaviour. An alternate</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line250">250</a> # behaviour may be implemented with Diff::LCS::ContextDiffCallbacks.</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line251">251</a> # If a Class argument is provided for +callbacks+, #diff will attempt</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line252">252</a> # to initialise it. If the +callbacks+ object (possibly initialised)</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line253">253</a> # responds to #finish, it will be called.</pre></td> </tr> <tr class="marked"> <td><pre><a name="line254">254</a> def diff(seq1, seq2, callbacks = nil, &block) # :yields diff changes:</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line255">255</a> callbacks ||= Diff::LCS::DiffCallbacks</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line256">256</a> if callbacks.kind_of?(Class)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line257">257</a> cb = callbacks.new rescue callbacks</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line258">258</a> callbacks = cb</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line259">259</a> end</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line260">260</a> traverse_sequences(seq1, seq2, callbacks)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line261">261</a> callbacks.finish if callbacks.respond_to?(:finish)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line262">262</a> </pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line263">263</a> if block_given?</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line264">264</a> res = callbacks.diffs.map do |hunk|</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line265">265</a> if hunk.kind_of?(Array)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line266">266</a> hunk = hunk.map { |block| yield block }</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line267">267</a> else</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line268">268</a> yield hunk</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line269">269</a> end</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line270">270</a> end</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line271">271</a> res</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line272">272</a> else</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line273">273</a> callbacks.diffs</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line274">274</a> end</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line275">275</a> end</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line276">276</a> </pre></td> </tr> <tr class="inferred"> <td><pre><a name="line277">277</a> # Diff::LCS.sdiff computes all necessary components to show two sequences</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line278">278</a> # and their minimized differences side by side, just like the Unix</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line279">279</a> # utility <em>sdiff</em> does:</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line280">280</a> #</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line281">281</a> # old < -</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line282">282</a> # same same</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line283">283</a> # before | after</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line284">284</a> # - > new</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line285">285</a> #</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line286">286</a> # See Diff::LCS::SDiffCallbacks for the default behaviour. An alternate</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line287">287</a> # behaviour may be implemented with Diff::LCS::ContextDiffCallbacks. If</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line288">288</a> # a Class argument is provided for +callbacks+, #diff will attempt to</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line289">289</a> # initialise it. If the +callbacks+ object (possibly initialised)</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line290">290</a> # responds to #finish, it will be called.</pre></td> </tr> <tr class="marked"> <td><pre><a name="line291">291</a> def sdiff(seq1, seq2, callbacks = nil, &block) #:yields diff changes:</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line292">292</a> callbacks ||= Diff::LCS::SDiffCallbacks</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line293">293</a> if callbacks.kind_of?(Class)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line294">294</a> cb = callbacks.new rescue callbacks</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line295">295</a> callbacks = cb</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line296">296</a> end</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line297">297</a> traverse_balanced(seq1, seq2, callbacks)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line298">298</a> callbacks.finish if callbacks.respond_to?(:finish)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line299">299</a> </pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line300">300</a> if block_given?</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line301">301</a> res = callbacks.diffs.map do |hunk|</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line302">302</a> if hunk.kind_of?(Array)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line303">303</a> hunk = hunk.map { |block| yield block }</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line304">304</a> else</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line305">305</a> yield hunk</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line306">306</a> end</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line307">307</a> end</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line308">308</a> res</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line309">309</a> else</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line310">310</a> callbacks.diffs</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line311">311</a> end</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line312">312</a> end</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line313">313</a> </pre></td> </tr> <tr class="inferred"> <td><pre><a name="line314">314</a> # Diff::LCS.traverse_sequences is the most general facility provided by this</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line315">315</a> # module; +diff+ and +LCS+ are implemented as calls to it.</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line316">316</a> #</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line317">317</a> # The arguments to #traverse_sequences are the two sequences to</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line318">318</a> # traverse, and a callback object, like this:</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line319">319</a> #</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line320">320</a> # traverse_sequences(seq1, seq2, Diff::LCS::ContextDiffCallbacks.new)</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line321">321</a> #</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line322">322</a> # #diff is implemented with #traverse_sequences.</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line323">323</a> #</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line324">324</a> # == Callback Methods</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line325">325</a> # Optional callback methods are <em>emphasized</em>.</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line326">326</a> #</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line327">327</a> # callbacks#match:: Called when +a+ and +b+ are pointing</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line328">328</a> # to common elements in +A+ and +B+.</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line329">329</a> # callbacks#discard_a:: Called when +a+ is pointing to an</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line330">330</a> # element not in +B+.</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line331">331</a> # callbacks#discard_b:: Called when +b+ is pointing to an</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line332">332</a> # element not in +A+.</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line333">333</a> # <em>callbacks#finished_a</em>:: Called when +a+ has reached the end of</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line334">334</a> # sequence +A+.</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line335">335</a> # <em>callbacks#finished_b</em>:: Called when +b+ has reached the end of</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line336">336</a> # sequence +B+.</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line337">337</a> #</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line338">338</a> # == Algorithm</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line339">339</a> # a---+</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line340">340</a> # v</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line341">341</a> # A = a b c e h j l m n p</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line342">342</a> # B = b c d e f j k l m r s t</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line343">343</a> # ^</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line344">344</a> # b---+</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line345">345</a> #</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line346">346</a> # If there are two arrows (+a+ and +b+) pointing to elements of</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line347">347</a> # sequences +A+ and +B+, the arrows will initially point to the first</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line348">348</a> # elements of their respective sequences. #traverse_sequences will</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line349">349</a> # advance the arrows through the sequences one element at a time,</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line350">350</a> # calling a method on the user-specified callback object before each</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line351">351</a> # advance. It will advance the arrows in such a way that if there are</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line352">352</a> # elements <tt>A[ii]</tt> and <tt>B[jj]</tt> which are both equal and</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line353">353</a> # part of the longest common subsequence, there will be some moment</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line354">354</a> # during the execution of #traverse_sequences when arrow +a+ is pointing</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line355">355</a> # to <tt>A[ii]</tt> and arrow +b+ is pointing to <tt>B[jj]</tt>. When</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line356">356</a> # this happens, #traverse_sequences will call <tt>callbacks#match</tt></pre></td> </tr> <tr class="inferred"> <td><pre><a name="line357">357</a> # and then it will advance both arrows.</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line358">358</a> #</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line359">359</a> # Otherwise, one of the arrows is pointing to an element of its sequence</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line360">360</a> # that is not part of the longest common subsequence.</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line361">361</a> # #traverse_sequences will advance that arrow and will call</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line362">362</a> # <tt>callbacks#discard_a</tt> or <tt>callbacks#discard_b</tt>, depending</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line363">363</a> # on which arrow it advanced. If both arrows point to elements that are</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line364">364</a> # not part of the longest common subsequence, then #traverse_sequences</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line365">365</a> # will advance one of them and call the appropriate callback, but it is</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line366">366</a> # not specified which it will call.</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line367">367</a> #</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line368">368</a> # The methods for <tt>callbacks#match</tt>, <tt>callbacks#discard_a</tt>,</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line369">369</a> # and <tt>callbacks#discard_b</tt> are invoked with an event comprising</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line370">370</a> # the action ("=", "+", or "-", respectively), the indicies +ii+ and</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line371">371</a> # +jj+, and the elements <tt>A[ii]</tt> and <tt>B[jj]</tt>. Return</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line372">372</a> # values are discarded by #traverse_sequences.</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line373">373</a> #</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line374">374</a> # === End of Sequences</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line375">375</a> # If arrow +a+ reaches the end of its sequence before arrow +b+ does,</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line376">376</a> # #traverse_sequence try to call <tt>callbacks#finished_a</tt> with the</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line377">377</a> # last index and element of +A+ (<tt>A[-1]</tt>) and the current index</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line378">378</a> # and element of +B+ (<tt>B[jj]</tt>). If <tt>callbacks#finished_a</tt></pre></td> </tr> <tr class="inferred"> <td><pre><a name="line379">379</a> # does not exist, then <tt>callbacks#discard_b</tt> will be called on</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line380">380</a> # each element of +B+ until the end of the sequence is reached (the call</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line381">381</a> # will be done with <tt>A[-1]</tt> and <tt>B[jj]</tt> for each element).</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line382">382</a> #</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line383">383</a> # If +b+ reaches the end of +B+ before +a+ reaches the end of +A+,</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line384">384</a> # <tt>callbacks#finished_b</tt> will be called with the current index</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line385">385</a> # and element of +A+ (<tt>A[ii]</tt>) and the last index and element of</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line386">386</a> # +B+ (<tt>A[-1]</tt>). Again, if <tt>callbacks#finished_b</tt> does not</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line387">387</a> # exist on the callback object, then <tt>callbacks#discard_a</tt> will</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line388">388</a> # be called on each element of +A+ until the end of the sequence is</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line389">389</a> # reached (<tt>A[ii]</tt> and <tt>B[-1]</tt>).</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line390">390</a> #</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line391">391</a> # There is a chance that one additional <tt>callbacks#discard_a</tt> or</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line392">392</a> # <tt>callbacks#discard_b</tt> will be called after the end of the</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line393">393</a> # sequence is reached, if +a+ has not yet reached the end of +A+ or +b+</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line394">394</a> # has not yet reached the end of +B+.</pre></td> </tr> <tr class="marked"> <td><pre><a name="line395">395</a> def traverse_sequences(seq1, seq2, callbacks = Diff::LCS::SequenceCallbacks, &block) #:yields change events:</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line396">396</a> matches = Diff::LCS.__lcs(seq1, seq2)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line397">397</a> </pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line398">398</a> run_finished_a = run_finished_b = false</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line399">399</a> string = seq1.kind_of?(String)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line400">400</a> </pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line401">401</a> a_size = seq1.size</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line402">402</a> b_size = seq2.size</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line403">403</a> ai = bj = 0</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line404">404</a> </pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line405">405</a> (0 .. matches.size).each do |ii|</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line406">406</a> b_line = matches[ii]</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line407">407</a> </pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line408">408</a> ax = string ? seq1[ii, 1] : seq1[ii]</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line409">409</a> bx = string ? seq2[bj, 1] : seq2[bj]</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line410">410</a> </pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line411">411</a> if b_line.nil?</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line412">412</a> unless ax.nil?</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line413">413</a> event = Diff::LCS::ContextChange.new('-', ii, ax, bj, bx)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line414">414</a> event = yield event if block_given?</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line415">415</a> callbacks.discard_a(event)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line416">416</a> end</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line417">417</a> else</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line418">418</a> loop do</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line419">419</a> break unless bj < b_line</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line420">420</a> bx = string ? seq2[bj, 1] : seq2[bj]</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line421">421</a> event = Diff::LCS::ContextChange.new('+', ii, ax, bj, bx)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line422">422</a> event = yield event if block_given?</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line423">423</a> callbacks.discard_b(event)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line424">424</a> bj += 1</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line425">425</a> end</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line426">426</a> bx = string ? seq2[bj, 1] : seq2[bj]</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line427">427</a> event = Diff::LCS::ContextChange.new('=', ii, ax, bj, bx)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line428">428</a> event = yield event if block_given?</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line429">429</a> callbacks.match(event)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line430">430</a> bj += 1</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line431">431</a> end</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line432">432</a> ai = ii</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line433">433</a> end</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line434">434</a> ai += 1</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line435">435</a> </pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line436">436</a> # The last entry (if any) processed was a match. +ai+ and +bj+ point</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line437">437</a> # just past the last matching lines in their sequences.</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line438">438</a> while (ai < a_size) or (bj < b_size)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line439">439</a> # last A?</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line440">440</a> if ai == a_size and bj < b_size</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line441">441</a> if callbacks.respond_to?(:finished_a) and not run_finished_a</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line442">442</a> ax = string ? seq1[-1, 1] : seq1[-1]</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line443">443</a> bx = string ? seq2[bj, 1] : seq2[bj]</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line444">444</a> event = Diff::LCS::ContextChange.new('>', (a_size - 1), ax, bj, bx)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line445">445</a> event = yield event if block_given?</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line446">446</a> callbacks.finished_a(event)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line447">447</a> run_finished_a = true</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line448">448</a> else</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line449">449</a> ax = string ? seq1[ai, 1] : seq1[ai]</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line450">450</a> loop do</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line451">451</a> bx = string ? seq2[bj, 1] : seq2[bj]</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line452">452</a> event = Diff::LCS::ContextChange.new('+', ai, ax, bj, bx)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line453">453</a> event = yield event if block_given?</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line454">454</a> callbacks.discard_b(event)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line455">455</a> bj += 1</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line456">456</a> break unless bj < b_size</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line457">457</a> end</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line458">458</a> end</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line459">459</a> end</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line460">460</a> </pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line461">461</a> # last B?</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line462">462</a> if bj == b_size and ai < a_size</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line463">463</a> if callbacks.respond_to?(:finished_b) and not run_finished_b</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line464">464</a> ax = string ? seq1[ai, 1] : seq1[ai]</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line465">465</a> bx = string ? seq2[-1, 1] : seq2[-1]</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line466">466</a> event = Diff::LCS::ContextChange.new('<', ai, ax, (b_size - 1), bx)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line467">467</a> event = yield event if block_given?</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line468">468</a> callbacks.finished_b(event)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line469">469</a> run_finished_b = true</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line470">470</a> else</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line471">471</a> bx = string ? seq2[bj, 1] : seq2[bj]</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line472">472</a> loop do</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line473">473</a> ax = string ? seq1[ai, 1] : seq1[ai]</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line474">474</a> event = Diff::LCS::ContextChange.new('-', ai, ax, bj, bx)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line475">475</a> event = yield event if block_given?</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line476">476</a> callbacks.discard_a(event)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line477">477</a> ai += 1</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line478">478</a> break unless bj < b_size</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line479">479</a> end</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line480">480</a> end</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line481">481</a> end</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line482">482</a> </pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line483">483</a> if ai < a_size</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line484">484</a> ax = string ? seq1[ai, 1] : seq1[ai]</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line485">485</a> bx = string ? seq2[bj, 1] : seq2[bj]</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line486">486</a> event = Diff::LCS::ContextChange.new('-', ai, ax, bj, bx)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line487">487</a> event = yield event if block_given?</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line488">488</a> callbacks.discard_a(event)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line489">489</a> ai += 1</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line490">490</a> end</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line491">491</a> </pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line492">492</a> if bj < b_size</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line493">493</a> ax = string ? seq1[ai, 1] : seq1[ai]</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line494">494</a> bx = string ? seq2[bj, 1] : seq2[bj]</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line495">495</a> event = Diff::LCS::ContextChange.new('+', ai, ax, bj, bx)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line496">496</a> event = yield event if block_given?</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line497">497</a> callbacks.discard_b(event)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line498">498</a> bj += 1</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line499">499</a> end</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line500">500</a> end</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line501">501</a> end</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line502">502</a> </pre></td> </tr> <tr class="inferred"> <td><pre><a name="line503">503</a> # #traverse_balanced is an alternative to #traverse_sequences. It</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line504">504</a> # uses a different algorithm to iterate through the entries in the</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line505">505</a> # computed longest common subsequence. Instead of viewing the changes as</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line506">506</a> # insertions or deletions from one of the sequences, #traverse_balanced</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line507">507</a> # will report <em>changes</em> between the sequences. To represent a</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line508">508</a> #</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line509">509</a> # The arguments to #traverse_balanced are the two sequences to traverse</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line510">510</a> # and a callback object, like this:</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line511">511</a> #</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line512">512</a> # traverse_balanced(seq1, seq2, Diff::LCS::ContextDiffCallbacks.new)</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line513">513</a> #</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line514">514</a> # #sdiff is implemented with #traverse_balanced.</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line515">515</a> #</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line516">516</a> # == Callback Methods</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line517">517</a> # Optional callback methods are <em>emphasized</em>.</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line518">518</a> #</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line519">519</a> # callbacks#match:: Called when +a+ and +b+ are pointing</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line520">520</a> # to common elements in +A+ and +B+.</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line521">521</a> # callbacks#discard_a:: Called when +a+ is pointing to an</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line522">522</a> # element not in +B+.</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line523">523</a> # callbacks#discard_b:: Called when +b+ is pointing to an</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line524">524</a> # element not in +A+.</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line525">525</a> # <em>callbacks#change</em>:: Called when +a+ and +b+ are pointing</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line526">526</a> # to the same relative position, but</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line527">527</a> # <tt>A[a]</tt> and <tt>B[b]</tt> are</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line528">528</a> # not the same; a <em>change</em> has</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line529">529</a> # occurred.</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line530">530</a> #</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line531">531</a> # #traverse_balanced might be a bit slower than #traverse_sequences,</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line532">532</a> # noticable only while processing huge amounts of data.</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line533">533</a> #</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line534">534</a> # The +sdiff+ function of this module is implemented as call to</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line535">535</a> # #traverse_balanced.</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line536">536</a> #</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line537">537</a> # == Algorithm</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line538">538</a> # a---+</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line539">539</a> # v</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line540">540</a> # A = a b c e h j l m n p</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line541">541</a> # B = b c d e f j k l m r s t</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line542">542</a> # ^</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line543">543</a> # b---+</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line544">544</a> #</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line545">545</a> # === Matches</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line546">546</a> # If there are two arrows (+a+ and +b+) pointing to elements of</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line547">547</a> # sequences +A+ and +B+, the arrows will initially point to the first</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line548">548</a> # elements of their respective sequences. #traverse_sequences will</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line549">549</a> # advance the arrows through the sequences one element at a time,</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line550">550</a> # calling a method on the user-specified callback object before each</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line551">551</a> # advance. It will advance the arrows in such a way that if there are</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line552">552</a> # elements <tt>A[ii]</tt> and <tt>B[jj]</tt> which are both equal and</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line553">553</a> # part of the longest common subsequence, there will be some moment</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line554">554</a> # during the execution of #traverse_sequences when arrow +a+ is pointing</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line555">555</a> # to <tt>A[ii]</tt> and arrow +b+ is pointing to <tt>B[jj]</tt>. When</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line556">556</a> # this happens, #traverse_sequences will call <tt>callbacks#match</tt></pre></td> </tr> <tr class="inferred"> <td><pre><a name="line557">557</a> # and then it will advance both arrows.</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line558">558</a> #</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line559">559</a> # === Discards</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line560">560</a> # Otherwise, one of the arrows is pointing to an element of its sequence</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line561">561</a> # that is not part of the longest common subsequence.</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line562">562</a> # #traverse_sequences will advance that arrow and will call</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line563">563</a> # <tt>callbacks#discard_a</tt> or <tt>callbacks#discard_b</tt>,</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line564">564</a> # depending on which arrow it advanced.</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line565">565</a> #</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line566">566</a> # === Changes</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line567">567</a> # If both +a+ and +b+ point to elements that are not part of the longest</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line568">568</a> # common subsequence, then #traverse_sequences will try to call</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line569">569</a> # <tt>callbacks#change</tt> and advance both arrows. If</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line570">570</a> # <tt>callbacks#change</tt> is not implemented, then</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line571">571</a> # <tt>callbacks#discard_a</tt> and <tt>callbacks#discard_b</tt> will be</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line572">572</a> # called in turn.</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line573">573</a> #</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line574">574</a> # The methods for <tt>callbacks#match</tt>, <tt>callbacks#discard_a</tt>,</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line575">575</a> # <tt>callbacks#discard_b</tt>, and <tt>callbacks#change</tt> are</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line576">576</a> # invoked with an event comprising the action ("=", "+", "-", or "!",</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line577">577</a> # respectively), the indicies +ii+ and +jj+, and the elements</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line578">578</a> # <tt>A[ii]</tt> and <tt>B[jj]</tt>. Return values are discarded by</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line579">579</a> # #traverse_balanced.</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line580">580</a> #</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line581">581</a> # === Context</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line582">582</a> # Note that +ii+ and +jj+ may not be the same index position, even if</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line583">583</a> # +a+ and +b+ are considered to be pointing to matching or changed</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line584">584</a> # elements.</pre></td> </tr> <tr class="marked"> <td><pre><a name="line585">585</a> def traverse_balanced(seq1, seq2, callbacks = Diff::LCS::BalancedCallbacks)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line586">586</a> matches = Diff::LCS.__lcs(seq1, seq2)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line587">587</a> a_size = seq1.size</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line588">588</a> b_size = seq2.size</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line589">589</a> ai = bj = mb = 0</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line590">590</a> ma = -1</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line591">591</a> string = seq1.kind_of?(String)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line592">592</a> </pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line593">593</a> # Process all the lines in the match vector.</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line594">594</a> loop do</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line595">595</a> # Find next match indices +ma+ and +mb+</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line596">596</a> loop do</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line597">597</a> ma += 1</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line598">598</a> break unless ma < matches.size and matches[ma].nil?</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line599">599</a> end</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line600">600</a> </pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line601">601</a> break if ma >= matches.size # end of matches?</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line602">602</a> mb = matches[ma]</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line603">603</a> </pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line604">604</a> # Change(seq2)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line605">605</a> while (ai < ma) or (bj < mb)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line606">606</a> ax = string ? seq1[ai, 1] : seq1[ai]</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line607">607</a> bx = string ? seq2[bj, 1] : seq2[bj]</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line608">608</a> </pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line609">609</a> case [(ai < ma), (bj < mb)]</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line610">610</a> when [true, true]</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line611">611</a> if callbacks.respond_to?(:change)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line612">612</a> event = Diff::LCS::ContextChange.new('!', ai, ax, bj, bx)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line613">613</a> event = yield event if block_given?</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line614">614</a> callbacks.change(event)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line615">615</a> ai += 1</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line616">616</a> bj += 1</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line617">617</a> else</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line618">618</a> event = Diff::LCS::ContextChange.new('-', ai, ax, bj, bx)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line619">619</a> event = yield event if block_given?</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line620">620</a> callbacks.discard_a(event)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line621">621</a> ai += 1</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line622">622</a> ax = string ? seq1[ai, 1] : seq1[ai]</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line623">623</a> event = Diff::LCS::ContextChange.new('+', ai, ax, bj, bx)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line624">624</a> event = yield event if block_given?</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line625">625</a> callbacks.discard_b(event)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line626">626</a> bj += 1</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line627">627</a> end</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line628">628</a> when [true, false]</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line629">629</a> event = Diff::LCS::ContextChange.new('-', ai, ax, bj, bx)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line630">630</a> event = yield event if block_given?</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line631">631</a> callbacks.discard_a(event)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line632">632</a> ai += 1</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line633">633</a> when [false, true]</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line634">634</a> event = Diff::LCS::ContextChange.new('+', ai, ax, bj, bx)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line635">635</a> event = yield event if block_given?</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line636">636</a> callbacks.discard_b(event)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line637">637</a> bj += 1</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line638">638</a> end</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line639">639</a> end</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line640">640</a> </pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line641">641</a> # Match</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line642">642</a> ax = string ? seq1[ai, 1] : seq1[ai]</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line643">643</a> bx = string ? seq2[bj, 1] : seq2[bj]</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line644">644</a> event = Diff::LCS::ContextChange.new('=', ai, ax, bj, bx)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line645">645</a> event = yield event if block_given?</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line646">646</a> callbacks.match(event)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line647">647</a> ai += 1</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line648">648</a> bj += 1</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line649">649</a> end</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line650">650</a> </pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line651">651</a> while (ai < a_size) or (bj < b_size)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line652">652</a> ax = string ? seq1[ai, 1] : seq1[ai]</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line653">653</a> bx = string ? seq2[bj, 1] : seq2[bj]</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line654">654</a> </pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line655">655</a> case [(ai < a_size), (bj < b_size)]</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line656">656</a> when [true, true]</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line657">657</a> if callbacks.respond_to?(:change)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line658">658</a> event = Diff::LCS::ContextChange.new('!', ai, ax, bj, bx)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line659">659</a> event = yield event if block_given?</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line660">660</a> callbacks.change(event)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line661">661</a> ai += 1</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line662">662</a> bj += 1</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line663">663</a> else</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line664">664</a> event = Diff::LCS::ContextChange.new('-', ai, ax, bj, bx)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line665">665</a> event = yield event if block_given?</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line666">666</a> callbacks.discard_a(event)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line667">667</a> ai += 1</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line668">668</a> ax = string ? seq1[ai, 1] : seq1[ai]</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line669">669</a> event = Diff::LCS::ContextChange.new('+', ai, ax, bj, bx)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line670">670</a> event = yield event if block_given?</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line671">671</a> callbacks.discard_b(event)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line672">672</a> bj += 1</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line673">673</a> end</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line674">674</a> when [true, false]</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line675">675</a> event = Diff::LCS::ContextChange.new('-', ai, ax, bj, bx)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line676">676</a> event = yield event if block_given?</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line677">677</a> callbacks.discard_a(event)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line678">678</a> ai += 1</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line679">679</a> when [false, true]</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line680">680</a> event = Diff::LCS::ContextChange.new('+', ai, ax, bj, bx)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line681">681</a> event = yield event if block_given?</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line682">682</a> callbacks.discard_b(event)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line683">683</a> bj += 1</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line684">684</a> end</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line685">685</a> end</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line686">686</a> end</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line687">687</a> </pre></td> </tr> <tr class="marked"> <td><pre><a name="line688">688</a> PATCH_MAP = { #:nodoc:</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line689">689</a> :patch => { '+' => '+', '-' => '-', '!' => '!', '=' => '=' },</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line690">690</a> :unpatch => { '+' => '-', '-' => '+', '!' => '!', '=' => '=' }</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line691">691</a> }</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line692">692</a> </pre></td> </tr> <tr class="inferred"> <td><pre><a name="line693">693</a> # Given a patchset, convert the current version to the new</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line694">694</a> # version. If +direction+ is not specified (must be</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line695">695</a> # <tt>:patch</tt> or <tt>:unpatch</tt>), then discovery of the</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line696">696</a> # direction of the patch will be attempted.</pre></td> </tr> <tr class="marked"> <td><pre><a name="line697">697</a> def patch(src, patchset, direction = nil)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line698">698</a> string = src.kind_of?(String)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line699">699</a> # Start with a new empty type of the source's class</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line700">700</a> res = src.class.new</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line701">701</a> </pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line702">702</a> # Normalize the patchset.</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line703">703</a> patchset = __normalize_patchset(patchset)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line704">704</a> </pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line705">705</a> direction ||= Diff::LCS.__diff_direction(src, patchset)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line706">706</a> direction ||= :patch</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line707">707</a> </pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line708">708</a> ai = bj = 0</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line709">709</a> </pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line710">710</a> patchset.each do |change|</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line711">711</a> # Both Change and ContextChange support #action</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line712">712</a> action = PATCH_MAP[direction][change.action]</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line713">713</a> </pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line714">714</a> case change</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line715">715</a> when Diff::LCS::ContextChange</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line716">716</a> case direction</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line717">717</a> when :patch</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line718">718</a> el = change.new_element</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line719">719</a> op = change.old_position</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line720">720</a> np = change.new_position</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line721">721</a> when :unpatch</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line722">722</a> el = change.old_element</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line723">723</a> op = change.new_position</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line724">724</a> np = change.old_position</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line725">725</a> end</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line726">726</a> </pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line727">727</a> case action</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line728">728</a> when '-' # Remove details from the old string</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line729">729</a> while ai < op</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line730">730</a> res << (string ? src[ai, 1] : src[ai])</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line731">731</a> ai += 1</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line732">732</a> bj += 1</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line733">733</a> end</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line734">734</a> ai += 1</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line735">735</a> when '+'</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line736">736</a> while bj < np</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line737">737</a> res << (string ? src[ai, 1] : src[ai])</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line738">738</a> ai += 1</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line739">739</a> bj += 1</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line740">740</a> end</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line741">741</a> </pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line742">742</a> res << el</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line743">743</a> bj += 1</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line744">744</a> when '='</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line745">745</a> # This only appears in sdiff output with the SDiff callback.</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line746">746</a> # Therefore, we only need to worry about dealing with a single</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line747">747</a> # element.</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line748">748</a> res << el</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line749">749</a> </pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line750">750</a> ai += 1</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line751">751</a> bj += 1</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line752">752</a> when '!'</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line753">753</a> while ai < op</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line754">754</a> res << (string ? src[ai, 1] : src[ai])</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line755">755</a> ai += 1</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line756">756</a> bj += 1</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line757">757</a> end</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line758">758</a> </pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line759">759</a> bj += 1</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line760">760</a> ai += 1</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line761">761</a> </pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line762">762</a> res << el</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line763">763</a> end</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line764">764</a> when Diff::LCS::Change</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line765">765</a> case action</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line766">766</a> when '-'</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line767">767</a> while ai < change.position</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line768">768</a> res << (string ? src[ai, 1] : src[ai])</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line769">769</a> ai += 1</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line770">770</a> bj += 1</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line771">771</a> end</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line772">772</a> ai += 1</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line773">773</a> when '+'</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line774">774</a> while bj < change.position</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line775">775</a> res << (string ? src[ai, 1] : src[ai])</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line776">776</a> ai += 1</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line777">777</a> bj += 1</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line778">778</a> end</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line779">779</a> </pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line780">780</a> bj += 1</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line781">781</a> </pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line782">782</a> res << change.element</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line783">783</a> end</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line784">784</a> end</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line785">785</a> end</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line786">786</a> </pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line787">787</a> while ai < src.size</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line788">788</a> res << (string ? src[ai, 1] : src[ai])</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line789">789</a> ai += 1</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line790">790</a> bj += 1</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line791">791</a> end</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line792">792</a> </pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line793">793</a> res</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line794">794</a> end</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line795">795</a> </pre></td> </tr> <tr class="inferred"> <td><pre><a name="line796">796</a> # Given a set of patchset, convert the current version to the prior</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line797">797</a> # version. Does no auto-discovery.</pre></td> </tr> <tr class="marked"> <td><pre><a name="line798">798</a> def unpatch!(src, patchset)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line799">799</a> Diff::LCS.patch(src, patchset, :unpatch)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line800">800</a> end</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line801">801</a> </pre></td> </tr> <tr class="inferred"> <td><pre><a name="line802">802</a> # Given a set of patchset, convert the current version to the next</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line803">803</a> # version. Does no auto-discovery.</pre></td> </tr> <tr class="marked"> <td><pre><a name="line804">804</a> def patch!(src, patchset)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line805">805</a> Diff::LCS.patch(src, patchset, :patch)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line806">806</a> end</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line807">807</a> </pre></td> </tr> <tr class="inferred"> <td><pre><a name="line808">808</a> # private</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line809">809</a> # Compute the longest common subsequence between the sequenced Enumerables</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line810">810</a> # +a+ and +b+. The result is an array whose contents is such that</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line811">811</a> #</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line812">812</a> # result = Diff::LCS.__lcs(a, b)</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line813">813</a> # result.each_with_index do |e, ii|</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line814">814</a> # assert_equal(a[ii], b[e]) unless e.nil?</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line815">815</a> # end</pre></td> </tr> <tr class="marked"> <td><pre><a name="line816">816</a> def __lcs(a, b)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line817">817</a> a_start = b_start = 0</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line818">818</a> a_finish = a.size - 1</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line819">819</a> b_finish = b.size - 1</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line820">820</a> vector = []</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line821">821</a> </pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line822">822</a> # Prune off any common elements at the beginning...</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line823">823</a> while (a_start <= a_finish) and</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line824">824</a> (b_start <= b_finish) and</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line825">825</a> (a[a_start] == b[b_start])</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line826">826</a> vector[a_start] = b_start</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line827">827</a> a_start += 1</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line828">828</a> b_start += 1</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line829">829</a> end</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line830">830</a> </pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line831">831</a> # Now the end...</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line832">832</a> while (a_start <= a_finish) and</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line833">833</a> (b_start <= b_finish) and</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line834">834</a> (a[a_finish] == b[b_finish])</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line835">835</a> vector[a_finish] = b_finish</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line836">836</a> a_finish -= 1</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line837">837</a> b_finish -= 1</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line838">838</a> end</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line839">839</a> </pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line840">840</a> # Now, compute the equivalence classes of positions of elements.</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line841">841</a> b_matches = Diff::LCS.__position_hash(b, b_start .. b_finish)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line842">842</a> </pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line843">843</a> thresh = []</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line844">844</a> links = []</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line845">845</a> </pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line846">846</a> (a_start .. a_finish).each do |ii|</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line847">847</a> ai = a.kind_of?(String) ? a[ii, 1] : a[ii]</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line848">848</a> bm = b_matches[ai]</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line849">849</a> kk = nil</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line850">850</a> bm.reverse_each do |jj|</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line851">851</a> if kk and (thresh[kk] > jj) and (thresh[kk - 1] < jj)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line852">852</a> thresh[kk] = jj</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line853">853</a> else</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line854">854</a> kk = Diff::LCS.__replace_next_larger(thresh, jj, kk)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line855">855</a> end</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line856">856</a> links[kk] = [ (kk > 0) ? links[kk - 1] : nil, ii, jj ] unless kk.nil?</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line857">857</a> end</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line858">858</a> end</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line859">859</a> </pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line860">860</a> unless thresh.empty?</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line861">861</a> link = links[thresh.size - 1]</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line862">862</a> while not link.nil?</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line863">863</a> vector[link[1]] = link[2]</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line864">864</a> link = link[0]</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line865">865</a> end</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line866">866</a> end</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line867">867</a> </pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line868">868</a> vector</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line869">869</a> end</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line870">870</a> </pre></td> </tr> <tr class="inferred"> <td><pre><a name="line871">871</a> # Find the place at which +value+ would normally be inserted into the</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line872">872</a> # Enumerable. If that place is already occupied by +value+, do nothing</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line873">873</a> # and return +nil+. If the place does not exist (i.e., it is off the end</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line874">874</a> # of the Enumerable), add it to the end. Otherwise, replace the element</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line875">875</a> # at that point with +value+. It is assumed that the Enumerable's values</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line876">876</a> # are numeric.</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line877">877</a> #</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line878">878</a> # This operation preserves the sort order.</pre></td> </tr> <tr class="marked"> <td><pre><a name="line879">879</a> def __replace_next_larger(enum, value, last_index = nil)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line880">880</a> # Off the end?</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line881">881</a> if enum.empty? or (value > enum[-1])</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line882">882</a> enum << value</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line883">883</a> return enum.size - 1</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line884">884</a> end</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line885">885</a> </pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line886">886</a> # Binary search for the insertion point</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line887">887</a> last_index ||= enum.size</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line888">888</a> first_index = 0</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line889">889</a> while (first_index <= last_index)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line890">890</a> ii = (first_index + last_index) >> 1</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line891">891</a> </pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line892">892</a> found = enum[ii]</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line893">893</a> </pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line894">894</a> if value == found</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line895">895</a> return nil</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line896">896</a> elsif value > found</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line897">897</a> first_index = ii + 1</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line898">898</a> else</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line899">899</a> last_index = ii - 1</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line900">900</a> end</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line901">901</a> end</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line902">902</a> </pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line903">903</a> # The insertion point is in first_index; overwrite the next larger</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line904">904</a> # value.</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line905">905</a> enum[first_index] = value</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line906">906</a> return first_index</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line907">907</a> end</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line908">908</a> </pre></td> </tr> <tr class="inferred"> <td><pre><a name="line909">909</a> # If +vector+ maps the matching elements of another collection onto this</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line910">910</a> # Enumerable, compute the inverse +vector+ that maps this Enumerable</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line911">911</a> # onto the collection. (Currently unused.)</pre></td> </tr> <tr class="marked"> <td><pre><a name="line912">912</a> def __inverse_vector(a, vector)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line913">913</a> inverse = a.dup</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line914">914</a> (0 ... vector.size).each do |ii|</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line915">915</a> inverse[vector[ii]] = ii unless vector[ii].nil?</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line916">916</a> end</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line917">917</a> inverse</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line918">918</a> end</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line919">919</a> </pre></td> </tr> <tr class="inferred"> <td><pre><a name="line920">920</a> # Returns a hash mapping each element of an Enumerable to the set of</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line921">921</a> # positions it occupies in the Enumerable, optionally restricted to the</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line922">922</a> # elements specified in the range of indexes specified by +interval+.</pre></td> </tr> <tr class="marked"> <td><pre><a name="line923">923</a> def __position_hash(enum, interval = 0 .. -1)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line924">924</a> hash = Hash.new { |hh, kk| hh[kk] = [] }</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line925">925</a> interval.each do |ii|</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line926">926</a> kk = enum.kind_of?(String) ? enum[ii, 1] : enum[ii]</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line927">927</a> hash[kk] << ii</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line928">928</a> end</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line929">929</a> hash</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line930">930</a> end</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line931">931</a> </pre></td> </tr> <tr class="inferred"> <td><pre><a name="line932">932</a> # Examine the patchset and the source to see in which direction the</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line933">933</a> # patch should be applied.</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line934">934</a> #</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line935">935</a> # WARNING: By default, this examines the whole patch, so this could take</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line936">936</a> # some time. This also works better with Diff::LCS::ContextChange or</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line937">937</a> # Diff::LCS::Change as its source, as an array will cause the creation</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line938">938</a> # of one of the above.</pre></td> </tr> <tr class="marked"> <td><pre><a name="line939">939</a> def __diff_direction(src, patchset, limit = nil)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line940">940</a> count = left = left_miss = right = right_miss = 0</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line941">941</a> string = src.kind_of?(String)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line942">942</a> </pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line943">943</a> patchset.each do |change|</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line944">944</a> count += 1</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line945">945</a> </pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line946">946</a> case change</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line947">947</a> when Diff::LCS::Change</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line948">948</a> # With a simplistic change, we can't tell the difference between</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line949">949</a> # the left and right on '!' actions, so we ignore those. On '='</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line950">950</a> # actions, if there's a miss, we miss both left and right.</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line951">951</a> element = string ? src[change.position, 1] : src[change.position]</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line952">952</a> </pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line953">953</a> case change.action</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line954">954</a> when '-'</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line955">955</a> if element == change.element</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line956">956</a> left += 1</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line957">957</a> else</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line958">958</a> left_miss += 1</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line959">959</a> end</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line960">960</a> when '+'</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line961">961</a> if element == change.element</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line962">962</a> right += 1</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line963">963</a> else</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line964">964</a> right_miss += 1</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line965">965</a> end</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line966">966</a> when '='</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line967">967</a> if element != change.element</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line968">968</a> left_miss += 1</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line969">969</a> right_miss += 1</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line970">970</a> end</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line971">971</a> end</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line972">972</a> when Diff::LCS::ContextChange</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line973">973</a> case change.action</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line974">974</a> when '-' # Remove details from the old string</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line975">975</a> element = string ? src[change.old_position, 1] : src[change.old_position]</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line976">976</a> if element == change.old_element</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line977">977</a> left += 1</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line978">978</a> else</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line979">979</a> left_miss += 1</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line980">980</a> end</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line981">981</a> when '+'</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line982">982</a> element = string ? src[change.new_position, 1] : src[change.new_position]</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line983">983</a> if element == change.new_element</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line984">984</a> right += 1</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line985">985</a> else</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line986">986</a> right_miss += 1</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line987">987</a> end</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line988">988</a> when '='</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line989">989</a> le = string ? src[change.old_position, 1] : src[change.old_position]</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line990">990</a> re = string ? src[change.new_position, 1] : src[change.new_position]</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line991">991</a> </pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line992">992</a> left_miss += 1 if le != change.old_element</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line993">993</a> right_miss += 1 if re != change.new_element</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line994">994</a> when '!'</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line995">995</a> element = string ? src[change.old_position, 1] : src[change.old_position]</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line996">996</a> if element == change.old_element</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line997">997</a> left += 1</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line998">998</a> else</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line999">999</a> element = string ? src[change.new_position, 1] : src[change.new_position]</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line1000">1000</a> if element == change.new_element</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line1001">1001</a> right += 1</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line1002">1002</a> else</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line1003">1003</a> left_miss += 1</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line1004">1004</a> right_miss += 1</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line1005">1005</a> end</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line1006">1006</a> end</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line1007">1007</a> end</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line1008">1008</a> end</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line1009">1009</a> </pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line1010">1010</a> break if not limit.nil? and count > limit</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line1011">1011</a> end</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line1012">1012</a> </pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line1013">1013</a> no_left = (left == 0) and (left_miss >= 0)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line1014">1014</a> no_right = (right == 0) and (right_miss >= 0)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line1015">1015</a> </pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line1016">1016</a> case [no_left, no_right]</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line1017">1017</a> when [false, true]</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line1018">1018</a> return :patch</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line1019">1019</a> when [true, false]</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line1020">1020</a> return :unpatch</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line1021">1021</a> else</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line1022">1022</a> raise "The provided patchset does not appear to apply to the provided value as either source or destination value."</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line1023">1023</a> end</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line1024">1024</a> end</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line1025">1025</a> </pre></td> </tr> <tr class="inferred"> <td><pre><a name="line1026">1026</a> # Normalize the patchset. A patchset is always a sequence of changes, but</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line1027">1027</a> # how those changes are represented may vary, depending on how they were</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line1028">1028</a> # generated. In all cases we support, we also support the array</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line1029">1029</a> # representation of the changes. The formats are:</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line1030">1030</a> #</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line1031">1031</a> # [ # patchset <- Diff::LCS.diff(a, b)</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line1032">1032</a> # [ # one or more hunks</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line1033">1033</a> # Diff::LCS::Change # one or more changes</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line1034">1034</a> # ] ]</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line1035">1035</a> #</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line1036">1036</a> # [ # patchset, equivalent to the above</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line1037">1037</a> # [ # one or more hunks</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line1038">1038</a> # [ action, line, value ] # one or more changes</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line1039">1039</a> # ] ]</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line1040">1040</a> #</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line1041">1041</a> # [ # patchset <- Diff::LCS.diff(a, b, Diff::LCS::ContextDiffCallbacks)</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line1042">1042</a> # # OR <- Diff::LCS.sdiff(a, b, Diff::LCS::ContextDiffCallbacks)</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line1043">1043</a> # [ # one or more hunks</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line1044">1044</a> # Diff::LCS::ContextChange # one or more changes</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line1045">1045</a> # ] ]</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line1046">1046</a> #</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line1047">1047</a> # [ # patchset, equivalent to the above</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line1048">1048</a> # [ # one or more hunks</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line1049">1049</a> # [ action, [ old line, old value ], [ new line, new value ] ]</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line1050">1050</a> # # one or more changes</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line1051">1051</a> # ] ]</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line1052">1052</a> #</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line1053">1053</a> # [ # patchset <- Diff::LCS.sdiff(a, b)</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line1054">1054</a> # # OR <- Diff::LCS.diff(a, b, Diff::LCS::SDiffCallbacks)</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line1055">1055</a> # Diff::LCS::ContextChange # one or more changes</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line1056">1056</a> # ]</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line1057">1057</a> #</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line1058">1058</a> # [ # patchset, equivalent to the above</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line1059">1059</a> # [ action, [ old line, old value ], [ new line, new value ] ]</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line1060">1060</a> # # one or more changes</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line1061">1061</a> # ]</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line1062">1062</a> #</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line1063">1063</a> # The result of this will be either of the following.</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line1064">1064</a> #</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line1065">1065</a> # [ # patchset</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line1066">1066</a> # Diff::LCS::ContextChange # one or more changes</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line1067">1067</a> # ]</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line1068">1068</a> #</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line1069">1069</a> # [ # patchset</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line1070">1070</a> # Diff::LCS::Change # one or more changes</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line1071">1071</a> # ]</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line1072">1072</a> #</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line1073">1073</a> # If either of the above is provided, it will be returned as such.</pre></td> </tr> <tr class="inferred"> <td><pre><a name="line1074">1074</a> #</pre></td> </tr> <tr class="marked"> <td><pre><a name="line1075">1075</a> def __normalize_patchset(patchset)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line1076">1076</a> patchset.map do |hunk|</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line1077">1077</a> case hunk</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line1078">1078</a> when Diff::LCS::ContextChange, Diff::LCS::Change</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line1079">1079</a> hunk</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line1080">1080</a> when Array</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line1081">1081</a> if (not hunk[0].kind_of?(Array)) and hunk[1].kind_of?(Array) and hunk[2].kind_of?(Array)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line1082">1082</a> Diff::LCS::ContextChange.from_a(hunk)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line1083">1083</a> else</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line1084">1084</a> hunk.map do |change|</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line1085">1085</a> case change</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line1086">1086</a> when Diff::LCS::ContextChange, Diff::LCS::Change</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line1087">1087</a> change</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line1088">1088</a> when Array</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line1089">1089</a> # change[1] will ONLY be an array in a ContextChange#to_a call.</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line1090">1090</a> # In Change#to_a, it represents the line (singular).</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line1091">1091</a> if change[1].kind_of?(Array)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line1092">1092</a> Diff::LCS::ContextChange.from_a(change)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line1093">1093</a> else</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line1094">1094</a> Diff::LCS::Change.from_a(change)</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line1095">1095</a> end</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line1096">1096</a> end</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line1097">1097</a> end</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line1098">1098</a> end</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line1099">1099</a> else</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line1100">1100</a> raise ArgumentError, "Cannot normalise a hunk of class #{hunk.class}."</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line1101">1101</a> end</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line1102">1102</a> end.flatten</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line1103">1103</a> end</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line1104">1104</a> end</pre></td> </tr> <tr class="uncovered"> <td><pre><a name="line1105">1105</a> end</pre></td> </tr> </tbody> </table> <p>Generated on Fri Apr 22 17:22:41 -0700 2011 with <a href="http://github.com/relevance/rcov">rcov 0.9.8</a></p> </body>
</html>